- •Тема 1. Математическая модель задачи линейного программирования (злп)
- •1. Предмет математического программирования
- •2. Математическая модель мп
- •3. Основные типы задач мп:
- •4. Многокритериальная оптимизация
- •5. Основные понятия теории оптимизации
- •6. Постановка злп. Различные формы записи ее математической модели
- •Тема 2. Графический метод решения злп. Закономерности и общие свойства решения злп
- •1. Геометрическая интерпретация решения злп
- •2. Алгоритм решения злп графическим методом
- •3. Возможные случаи области допустимых решений при решении злп графическим методом:
- •4. Основные свойства решений злп:
- •5. Классификация решений злп
- •6. Решение злп с точки зрения линейной алгебры
- •Тема 3. Симплексный метод решения задач линейного программирования
- •1. Суть симплексного метода
- •2. Критерий оптимальности решения злп
- •3. Алгоритм основного симплекс-метода:
- •4. Алгоритм двойственного симплекс-метода:
- •5. Алгоритм смешанного симплекс-метода:
- •6. Особые случаи симплекс-метода:
- •Тема 4. Модифицированный симплекс-метод решения злп. Устойчивость оптимального решения злп
- •1. Обращенный базис и симплекс-множители
- •2. Модифицированный симплекс-метод
- •3. Устойчивость оптимального решения злп:
- •Тема 5. Двойственность в линейном программировании
- •1. Понятие двойственности и теневой цены
- •2. Правила построения двойственной злп
- •3. Основные теоремы двойственности и их экономическое содержание
- •Тема 6. Элементы теории матричных игр
- •1. Основные понятия
- •2. Теоремы теории игр для парных матричных игр с нулевой суммой
- •3. Способы решения задач ти:
- •Тема 7. Матричные статистические игры
- •1. Понятие статистической игры
- •2. Критерии выбора оптимальной стратегии при решении статистической игры
- •3. Кооперативные игры
- •Тема 8. Транспортная задача (тз)
- •1. Постановка тз
- •2. Математическая модель тз
- •3. Решение тз методом потенциалов
- •4. Проверка плана на оптимальность
- •5. Цикл пересчета
- •6. Метод дифференциальных рент
- •7. Дополнительные ограничения тз
- •Тема 9. Дискретное программирование
- •1. Задача целочисленного линейного программирования
- •2. Метод Гомори
- •3. Метод ветвей и границ
- •Тема 10. Элементы нелинейного программирования
- •1. Постановка задачи нелинейного программирования
- •2. Метод множителей Лагранжа
- •3. Задача выпуклого программирования
- •4. Задача квадратического программирования
- •Тема 11. Метод динамического программирования
- •1. Общая постановка задачи динамического программирования
- •2. Принцип оптимальности. Функциональные уравнения Беллмана
- •3. Задача оптимального распределения инвестиций
- •4. Задача о замене оборудования
- •Тема 12. Программирование на сетях
- •1. Основные понятия теории графов
- •2. Экстремальное дерево графа
- •3. Матричные способы задания графов. Упорядочение элементов орграфа
- •4. Потоки на сетях. Постановка задачи о максимальном потоке
- •5. Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
- •Тема 13. Планирование на сетях
- •1. Понятие сетевого графика
- •2. Основные параметры сг
- •3. Связь временных параметров сг
- •4. Алгоритм расчета параметров сг:
Тема 4. Модифицированный симплекс-метод решения злп. Устойчивость оптимального решения злп
План лекции:
1. Обращенный базис и симплекс-множители
2. Алгоритм модифицированного симплекс-метода
3. Устойчивость оптимального решения ЗЛП
1. Обращенный базис и симплекс-множители
Рассмотрим решение ЗЛП с точки зрения линейной алгебры. В матричном виде каноническая форма ЗЛП имеет вид:
, где ,
.
Представим матрицу A в виде «склеенных» двух матриц . Здесь матрица – матрица, состоящая из столбцов матрицы A, соответствующих переменным, которые в оптимальной таблице являются базисными. Матрица состоит из всех оставшихся столбцов. Предположим, известна матрица B–1. Умножим слева ограничения ЗЛП на матрицу B–1:
, здесь , следовательно,
, следовательно, , .
В невырожденном допустимом базисном решении (НДБР) базисным переменным соответствует единичная матрица, то есть . Так как A умножается на B–1, то , что соответствует матрице коэффициентов оптимальной таблицы. Следовательно, в оптимальной таблице в столбцах тех переменных, которые были базисными в НДБР находится матрица B–1.
Определение 4.1. Матрица, находящаяся в оптимальной таблице среди коэффициентов ограничений, стоящих в столбцах тех переменных, которые были базисными в исходной таблице, называется обращенным базисом и обозначается B–1.
Запишем ЗЛП в канонической форме с предпочтительными переменными:
.
Умножим каждое ограничение на некоторое число соответственно и сложим с выражением целевой функции, тогда получим:
. (4.1)
Значения можно подобрать таким образом, чтобы коэффициенты перед базисными переменными равнялись нулю. Без ограничения общности, например, первые m переменных являются базисными, тогда можно определить из системы:
.
Если предположить, что подобрали таким образом, что перед базисными переменными коэффициенты равны 0, а перед свободными – неотрицательны, то вид (4.1) будет соответствовать оптимальному виду таблицы. Следовательно, в оптимальной таблице коэффициенты в выражении целевой функции перед переменными, которые были базисными в исходной таблице, есть , при этом .
Определение 4.2. Симплекс-множители – это такие числа , при умножении на которые каждого ограничения соответственно и сложении с выражением целевой функции будет получен такой вид целевой функции, что перед базисными переменными коэффициенты равны нулю, а перед свободными – неотрицательны.
Замечание 4.1. Если не все коэффициенты свободных переменных в выражении целевой функции неотрицательны, то это симплекс-множители промежуточного решения.
2. Модифицированный симплекс-метод
Модифицированный симплекс-метод предусматривает выполнение точно таких же этапов, как и обычный симплекс-метод. Главное отличие между ними заключается в том, что в модифицированном симплекс-методе основные действия связаны с использованием обращенного базиса и симплекс-множителей, позволяющих использовать найденное решение ЗЛП, если происходят изменения условий задачи, при этом применяются следующие формулы:
Элементы симплекс-таблицы |
Формулы |
Столбцы симплекс-таблицы вне обращенного базиса |
(4.2) (4.3) |
Коэффициенты при свободных переменных целевой функции |
(4.4) (4.5) |
Значение целевой функции |
(4.6) (4.7) |
Элементы без знака « » – это элементы начальной итерации, а элементы со знаком « » – это элементы текущей итерации.
Задача. Кондитерская фабрика для производства трех видов карамели использует три вида сырья: сахар, патоку, фруктовое пюре согласно технологической таблице:
Вид сырья |
Нормы расхода сырья на производство карамели |
Общее количество сырья |
||
A |
B |
С |
||
Сахар |
0,4 |
0,5 |
0,6 |
8 |
Патока |
0,6 |
0,4 |
0,3 |
6 |
Фруктовое пюре |
0 |
0,1 |
0,1 |
1,2 |
Прибыль от реализации единицы продукции, ден.ед. |
8 |
12 |
17 |
|
Найти план производства, обеспечивающий максимальную прибыль.
Решение задачи:
Введем обозначения: х1 – количество карамели первого вида, х2 – количество карамели второго вида, х3 – количество карамели третьего вида. Тогда математическая модель задачи имеет вид:
.
Преобразуем математическую модель ЗЛП к допустимому предпочтительному виду канонической формы:
.
По алгоритму основного симплекс-метода заполним симплексную таблицу задачи:
N |
б.п. |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
b |
0 |
x4 |
4 |
5 |
6 |
1 |
0 |
0 |
80 |
x5 |
6 |
4 |
3 |
0 |
1 |
0 |
60 |
|
x6* |
0 |
1 |
1 |
0 |
0 |
1 |
12 |
|
F |
-8 |
-12 |
-17* |
0 |
0 |
0 |
0 |
|
1 |
x4* |
4 |
-1 |
0 |
1 |
0 |
-6 |
8 |
x5 |
6 |
1 |
0 |
0 |
1 |
-3 |
24 |
|
x3 |
0 |
1 |
1 |
0 |
0 |
1 |
12 |
|
F |
-8* |
5 |
0 |
0 |
0 |
17 |
-204 |
|
2 |
x1 |
1 |
-1/4 |
0 |
1/4 |
0 |
-3/2 |
2 |
x5 |
0 |
5/2 |
0 |
-3/2 |
1 |
6 |
12 |
|
x3 |
0 |
1 |
1 |
0 |
0 |
1 |
12 |
|
F |
0 |
3 |
0 |
2 |
0 |
5 |
-220 |
Ответ: x* = (2; 0; 12), = 220.
Таким образом, для получения кондитерской фабрикой максимальной прибыли в размере 220 ден. ед. надо производить 2 усл. ед. карамели первого вида и 12 усл. ед. третьего вида, производить карамель второго вида не стоит.