Методы принятия управленческих решений (стр. 3 )

В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи):

Исходная задача	Двойственная задача
Симметричные пары
1.	1.
2.	2.
Несимметричные пары
3.	3.
4.	4.

Первая теорема двойственности.

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

Если же целевая функция одной из пары двойственных задач не ограничена (для исходной – сверху, для двойственной – снизу), то другая задача вообще не имеет планов.

Вторая теорема двойственности.

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

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

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

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

Решение

а) Число переменных в двойственной задаче равно числу уравнений в системе, т. е. 3. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений, т. е. 6, 24, 30. Коэффициенты целевой функции исходной задачи являются свободными членами двойственной.

Целевая функция исходной задачи исследуется на максимум, а система условий содержит одно неравенство и два уравнения. Поэтому в двойственной задаче целевая функция исследуется на минимум, а переменные, которым соответствуют равенства, могут принимать любые значения. Так как все три переменные исходной задачи принимают только неотрицательные значения, то в системе условий двойственной задачи должны быть неравенства вида "≥". Следовательно, двойственная задача такова:

б) Приведем задачу к каноническому виду. Для этого в левую часть первого неравенства вводим дополнительную переменную с коэффициентом +1. В целевую функцию переменная входит с коэффициентом 0 (т. е. не входит). Получаем

Преобразованную систему уравнений запишем в векторной форме:

,

где ; ; ; ; ; ; .

Поскольку среди векторов P1, P2, P3, P4, P5, P6 имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является с единичным базисом .

Составим симплексную таблицу для I итерации:

Б			9	5	4	3	2	0
	0	6	1	-2	2	0	0	1	6	3
	3	24	1	2	1	1	0	0	24	24
	2	30	2	1	-4	0	1	0	15	-
	F0=132	-2	3	-9	0	0	0

Вычислим оценки разложений векторов по базису опорного решения по формуле , где zj находится как скалярное произведение вектора Pj (j=1,m) на вектор Сб=(с1, с2, ...,сm):

Оценки векторов, входящих в базис, всегда равны нулю.

Значение F0 равно скалярному произведению вектора P0 на вектор Сб : F0=6*0+24*3+30*2=132.

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

Чтобы перейти к новому опорному решению, в базис можно ввести любой из векторов P1 и P3. Для определения вектора, подлежащего выводу из базиса, находят для всех aij>0.

Для вектора P1 получим , для вектора P3 получим (в таблице записаны в двух последних столбцах).

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

Далее выполним преобразование Жордана с элементом =2: 1) разделим всю 1-ю строку на 2 (на месте элемента получим 1) и запишем её в новую симплексную таблицу; 2) остальные элементы столбца нужно «занулить», для этого полученную 1-ю строку сначала умножим на -1 и сложим со второй, результат запишем во вторую строку новой симплексной таблицы, а затем умножим на 4 и сложим с третьей строкой, результат запишем в третью строку новой симплексной таблицы.