Конспект лекций по курсу «Математическое программирование»

 

Перейдем к новой симплекс-таблице (3.21)

 

 

 

 

Таблица 3.21

Б						Q
	1				0	1
	0	0	-2	-2	1	1
F	0	0	-2	-3	0	1

 

Получим оптимальный  план. Значение целевой функции при  оптимальном плане . Поэтому исходная ЗЛП неразрешима из-за пустоты ОДР.

Любопытно отметить, что система линейных уравнений исходной ЗЛП совместна и приводится к жордановой форме. Однако она не приводится к жордановой форме с неотрицательными правыми частями.

Сделаем еще  одно полезное замечание. В рассматриваемом  примере 2 можно было бы составить  более простую вспомогательную задачу:

Дело в том, что цель введения искусственных  переменных  - получение жордановой формы с неотрицательными правыми  частями для вспомогательной  задачи. Здесь эта цель достигается  с помощью одной искусственной переменной у . Допустимый базис состоит из переменных и у .

 

3.8. Вырожденность опорного  плана. Зацикливание.

 

Опорный план ЗЛП называется вырожденным, если некоторые из базисных переменных принимают значение 0. В этом случае при переходе от одного плана к другому может не произойти уменьшения целевой функции.       

                                                                                  

Пример. Пусть табличный вид ЗЛП таков:

Составим первую симплекс-таблицу (таблица 3.22).

Таблица 3.22

Б					Q
	1	0	1	-1	0
	0	1	2	3	10
f	0	0	2	1	4

Опорный план, соответствующий этой симплекс-таблице, является вырожденным, так как значение базисной переменной равно 0. Перейдем к новой симплекс-таблице (табл.3.23)

Таблица 3.23

Б					Q
	1	0	1	-1	0
	-2	1	0	5	10
f	-2	0	2	3	4

 

При новом опорном  плане значение целевой функции  осталось прежним: f=4.

При вырожденных  опорных планах возможна ситуация, когда, последовательно переходя от одного опорного плана к другому, через определенное количество шагов можно вернуться к прежнему опорному плану, так и не достигнув минимума функции. Это называется  зацикливанием.

На практике зацикливание встречается крайне редко. Существует такая модификация симплекс-алгоритма, при которой зацикливание исключается. Для практических целей достаточна и следующая  рекомендация: если произошло зацикливание, то при первой же возможности нужно иначе выбрать генеральный элемент, нежели это делалось в первый раз.

Справедлива теорема  о конечности симплекс-алгоритма: если ЗЛП разрешима, то оптимальное решение  всегда может быть найдено с помощью  симплекс-метода, причем начинать можно  с любого опорного плана.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

 

1. Экономическая интерпретация двойственных задач

Понятие двойственности в линейном программировании представляет большой теоретический и практический интерес. Двойственная задача - это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой задачи.

Рассмотрим  практическую ситуацию, которая приводит к необходимости рассмотрения двойственной задачи.

Предприятие выпускает  четыре вида продукции, для изготовления которой используется сырье трех видов. Запасы сырья, нормы расхода сырья на единицу продукции и прибыль от реализации единицы продукции приведены в следующей таблице:

Сырье	Виды продукции				Запасы  сырья
	П 1	П 2	П 3	П 4
	Нормы расхода  сырья
1	2	5	5	3	80
2	7	2	3	4	90
3	5	4	6	7	100
Прибыль	14	10	15	12

Требуется составить такой план производства продукции, при котором  суммарная прибыль была бы наибольшей.

Для записи математической модели задачи обозначим через x_j количество продукции П_j (j=1, 2, 3, 4). Математическая модель задачи:

Сформулируем теперь двойственную задачу. Предположим теперь, что  некоторая организация решила купить у предприятия все сырье. Покупатель стремится установить цены у_i на единицу сырья i-ro вида (i = 1, 2, 3, 4) так, чтобы минимизировать суммарную стоимость сырья, которая выражается величиной φ=80у₁+90у₂+100у₃. При ценах, предложенных покупателем, предприятие получит за сырье, потраченное на изготовление продукции П₁, выручку 2y₁+7у₂+5у₃. Предприятие согласится на сделку с покупателем, если эта выручка будет не меньше прибыли предприятия от изготовления единицы продукции П₁, т.е. если будет выполняться условие 2y₁+7у₂+5у₃≥14. Такие же ограничения покупатель вынужден учитывать и для всех остальных видов продукции. Таким образом, математическая модель задачи, решаемой покупателем, имеет вид:

Получившаяся задача является двойственной для исходной.

С экономической  точки зрения ясно, что f_max=φ_min. Действительно, в случае f_max>φ_min предприятие не будет продавать сырье, так как при производстве оно бы получило бóльшую прибыль. В случае же f_max<φ_min покупатель откажется от покупки сырья, так как его плата за сырье больше прибыли от производства.

Результаты  решения двойственной задачи выявляют наиболее дефицитные виды сырья (наиболее дефицитным видом является то сырье, которое в оптимальном решении двойственной задачи имеет наибольшую цену у_i). Анализ решения позволяет определить влияние увеличения запасов дефицитного сырья на прибыль производства. Он может также подсказать направление изменения технологии производства, при котором дефицитное сырье используется в меньших количествах.

 

2. Понятие двойственной задачи

Пусть имеется  следующая задача линейного программирования, которую будем называть прямой:

Задача 1.

 

Легко видеть, что  к такому виду можно привести любую  ЗЛП. Двойственная задача для задачи 1 записывается так:

Задача 2.

Можно показать, что имеет место принцип взаимной двойственности: двойственной к задаче 2 является задача 1. Таким образом, несущественно, какую из задач 1 или 2 называть прямой, а какую двойственной.

 

 

 

Пример 1. Дана ЗЛП

 

Построить двойственную задачу.

Задачу нужно  привести к виду, в котором записана задача 1. Все ограничения, кроме требований неотрицательности переменных, должны быть неравенствами вида ≤. Первое неравенство умножим на (-1). Затем заменим равенство – x₁+x₂=2 двумя неравенствами –x₁+x₂≤2 и –x₁+x₂≥2; второе из этих неравенств умножим на (-1). В результате ЗЛП примет вид:

Теперь запишем  двойственную задачу. Каждому линейному  ограничению (кроме требований неотрицательности  переменных) сопоставим  переменную двойственной задачи. Затем, двигаясь вдоль столбцов, запишем целевую функцию и ограничения двойственной задачи. Получим:

 

3. Теоремы двойственности

Приведем без доказательства следующие  две теоремы.

Первая теорема двойственности. Прямая задача разрешима тогда и только тогда, когда разрешима двойственная. При этом f_max=φ_min.

Вторая теорема двойственности. Для того чтобы два допустимых решения x₁', x₂',...,x_n' и у₁', у₂',…,y_m' пары двойственных задач были оптимальными, необходимо и достаточно, чтобы эти решения удовлетворяли условиям

Вторая теорема двойственности дает возможность находить оптимальное  решение одной из пары двойственных задач, имея оптимальное решение  другой задачи.

 

Пример 2. Дана задача

Построить двойственную задачу, решить ее геометрически, а затем с помощью второй теоремы двойственности найти оптимальное решение прямой задачи.

Обратим внимание, что, данная задача записана в форме (4.4) - (4.6). Так как имеет место  принцип взаимной двойственности, то будем записывать двойственную задачу в форме (4.1) - (4.3). Получим:

Решим геометрически  двойственную задачу. Построим на координатной плоскости граничные прямые (1) 8у₁–5у₂=11; (2) –у₁+3у₂=1; (3) –2у₁–7у₂=–7; находим полуплоскости, определяем ОДР, а затем находим на ОДР оптимальную точку А (см. рисунок). Для отыскания координат точки А решаем систему уравнений

 Получаем у₁=2, у₂=1. Подставив эти значения переменных в целевую функцию, получим φ_max=7.