Несимметричные двойственные задачи

 

Пуст ЗЛП задана в каноническом виде:

при

(),

().

Переведем данную задачу в симметричную форму:

Прямая задача на максимум, значит неравенства должны быть ≤. Умножим второе неравенство на (-1). Получим:

Составим двойственную задачу для полученной симметричной. Для этого введем двойственные переменные и . Получим:

при ограничениях:

Преобразуем систему ограничений следующим образом:

Обозначим y разность . и положительны, но их разность может быть как положительна, так и отрицательна.

В результате получим двойственную задачу вида:

при

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

при (), (), (), – любого знака ().

при (), (), (), – любого знака ().

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

1. Если на переменную прямой задачи наложено условие неотрицательности, то j-тое условие системы ограничений двойственной задачи в виде неравенств и наоборот.

2. Если на переменную прямой задачи не наложено условие неотрицательности, то j-тое ограничение двойственной задачи записывается в виде строго равенства.

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

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

Рассмотри пару двойственных задач.

Теорема 1: (об основном неравенстве двойственности) Для любых допустимых планов X= и Y= прямой и двойственной задачи линейного программирования справедливо неравенство:

.

Экономическое содержание основного неравенства двойственности состоит в том, что для любого допустимого плана производства Х и любого вектора оценок ресурсов Y общая созданная стоимость не превосходит суммарной оценки ресурсов.

Теорема 2: (критерий оптимальности Канторовича) Если для некоторых допустимых планов и пары двойственных задач выполняется равенство z()=f(), то и являются оптимальными планами соответствующих задач.

Экономическое содержание теоремы состоит в том, что план производства Х и вектор оценок ресурсов Y является оптимальным, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.

Теорема 3: (малая теорема двойственности) Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.

Теорема 4: Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны: z()=f(). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых планов, то система ограничений другой – противоречива.

Между переменными двойственных задач можно установить соответствие, сопоставляя свободным переменным одной задачи базисные переменные другой. Опорному оптимальному плану исходной задачи соответствует опорный оптимальный план двойственной, который оказывается записанным с противоположными знаками в индексной строке последней симплексной таблицы.

Пример 1: Решить исходную задачу линейного программирования, исходя из решения двойственной:

при

Решение.

Преобразуем систему ограничений следующим образом:

Составим двойственную задачу для данной:

при

Решим полученную задачу симплексным методом. Преобразуем систему ограничений следующим образом:

Для полученной М-задачи составим симплексную таблицу.

БП	СБ	А
	-4	-6				M	M	M
	M			-1	-1	-1
	M				-1		-1
	M							-1
M					-1	-1	-1
св. член		-8
				-1	-1	-1
	M						-1
	M							-1
M						-1	-1
св. член			-4	-2	-8
					-1	-1/2	-1/2
	-4					1/2	-1/2
	M					1/2	1/2	-1
M					1/2	1/2	-1
св. член				-2	-6
								-1
	-4					1/2	-1/2
	-6					1/2	1/2	-1
					-5	-1	-2

Полученный план оптимальный.

f=10 в (2, 0, 1, 0, 0, 0, 0)

Найдем решение прямой задачи.

Z=10 в (5, 1, 2)