Методы оптимальных решений (стр. 9 )

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

x1 Û y4, x2 Û y5, x3 Û y1, x4 Û y2, x5 Û y3,

то есть будут соответствующими основные неизвестные одной из двойственных задач и дополнительные неизвестные другой задачи (неизвестные задачи 1’ подписаны под соответствующими неизвестными задачи 2’ в нижней части табл. 3).

Из индексной строки табл. 3 выпишем оптимальный план и минимальное значение целевой функции f(Х) основной задачи 1’: X* = (2, 1, 0, 0, 5), ¦(Х*) = 2.

Отбросив значения дополнительных неизвестных, получим оптимальные планы общих задач (37): Х*= (2, 1) — оптимальный план задачи 1, ¦(Х*) = 2 — ¦min;

Y*= (1, 7, 0) — оптимальный план задачи 2, ¦(Y*) = 2 — gmax. Заметим, что если получен симплекс-методом оптимальный план задачи минимизации, то оптимальный план двойственной ей задачи максимизации выписывается из индексной строки последней симплексной таблицы решенной задачи аналогично предыдущему, только компоненты оптимального плана берутся с противоположными знаками или по абсолютной величине.

Правильность найденных выше оптимальных планов Х* и U* задач (37) можно проверить с помощью критериев оптимальности планов двойственных задач.

Первый критерий. Для того, чтобы план Х* одной из двойственных задач был оптимальным, необходимо и достаточно, чтобы существовал план Y* другой задачи, таr что значения целевых функций для этих планов равны, то есть ¦(Х*) = g(U*).

Назовем парой сопряженных неравенств любые два неравенства, оказавшиеся в одной строке, при условии, что двойственные задачи записаны по схеме (33), например,

х1³0 и а11у1 + а21у2³ с1 или а11х1 + а12х2 + а13х3 £ b1 и у1 ³ 0.

Второй критерий. Для того, чтобы план C* одной из двойственных задач был оптимальным, необходимо и достаточно, чтобы существовал план U* другой задачи, такой что в каждой паре сопряженных неравенств строгому неравенству соответствовало бы равенство, то есть хотя бы одно из пары сопряженных неравенств должно выполняться как равенство.

Для проверки подставим компоненты оптимальных планов Х*= (2, 1) и *U= (1, 7,0)

во все неравенства и в целевые функции задачи 1’ и задачи 2’, записанных в схеме (37). В результате получим соотношения (45).

Задача 1 Задача 2

х*1= 2 > 0, х*2= 1 > 0, -2 ´ 1 + 7 - 0 = 5,

-2 ´ 2 - 1 = -5,´ 0 = -8, (45)

2 - 1 = 1, y*1= 1 > 0, y*2= 7 > 0,

´ 1 = -5 > -10, y*3= 0 = 0,

¦(C*) = 5 ´ 2 - 8 ´ 1 = 2. g(Y*) = -5 ´ 1 + ´ 0 = 2.

Из соотношений (45) следует, что выполняются оба критерия оптимальности планов двойственных задач. действительно, оба вектора C* и U* удовлетворяют всем неравенствам пары двойственных задач (37) и ¦(Х*) = g(U*) следовательно, выполняется первый критерий. Кроме того, в каждой паре сопряженных неравенств этих задач, вычисленных для планов Х* и U* строгому не равенству соответствует равенство, например, 2> 0 и -2 + 7 = 5 или= -5 > -10 и 0 = 0 и т. п,, то есть выполняется второй критерий.

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

Для задачи линейного программирования, среди ограничений которой имеются не только неравенства, но и уравнения, также можно составить двойственную. В результате получится пара так называемых несимметричных двойственных задач. По определению, это задачи, которые можно записать в виде (46).

Задача 1 Задача 2

Max ¦(X) = c1x1 + c2x2 + c3x3 Min g(Y) = b1y1 + b2y2 + b3y3

при условиях: х1 ³ 0, х2 ³ 0, х3 ³ 0 при условиях:

а11х1 + а12х2 + а13х3 = b1, a11y1 + a12y2 + a13y3 ³ c1, (46)

a21x1 + a22x2 + a23x3 = b2, a21y1 + a22y2 + a23y3 ³ c2,

a31x1 + a32x2 + a33x3 £ b3. a31y1 + a32y2 + a33y3 ³ c3,

y1 - люб. зн,. y2 - люб. зн., y3 ³ 0

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

Пример 6. Дана следующая задача ЛП:

2х1 - х2 £ 11,

х1 + 4х2 =28, (47)

xi ³ 0 ( i = 1,2 ), (48)

¦(X) = 2x1 - 3x2 ¾ max. (49)

Решить задачу (симплекс-методом. Далее составить для нее двойственную задачу и проверить Оптимальность плана исход ной задачи с помощью критериев оптимальности планов двойственных задач.

Приведем Общую задачу (к основной, введя в первое не равенство добавочное неизвестное х3 ³ 0 .

2x1 - x2 + x3 = 11, (50)

x1 + 4x2 = 28,

xi ³ 0 (i = 1 ¸ 3), (51)

¦(X) = 2x1 - 3x2 ¾ max. (52)

Основная задача (не является канонической, так как во втором уравнении нет базисного неизвестного. Применим метод искусственного базиса.

Первый этап. Вспомогательная задача.

-2х1 - х2 + х3 = 11,

х1 + 4х2 + + z1 = 28, (53)

хj ³ 0 ( j = 1 ¸ 3 ), z1 ³ 0, (54)

j (Y) = z1 ¾ min. (55)

			0	0	0	0	1
		Баз.	х0	х1	х2	х3	z1
	0	х3	11	2	-1	1	0	Табл.1
	1	z1	28	1	4	0	1	q = 28/4
		j	28	1	4	0	0
	0	х3	18	9/4	0	1	1/4	Табл.2
®	0	х2	7	1/4	1	0	1/4
		j	0	0	0	0	-1