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

Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причём оптимальные значения целевых функций этих задач равны:

.

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

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

Соотношения двойственности

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

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

Системы ограничений ПЗ и ОЗ примут вид:

, ;

, .

Первоначальным (свободным) переменным прямой задачи соответствуют допол­нительные (базисные) переменные обратной задачи, а дополнительным (базисным) пе­ременным ПЗ соответствуют первоначальные (свободные) переменные ОЗ.

Пример 2).

прямая задача			двойственная задача
ОЗЛП			ОЗЛП

Соответствие между переменными

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

Р е ш е н и е ПЗ.

1	Bi	x1	x2	x3	x6
z1	1	2	-1	-1	0
x4	24	-1	4	0	0
x5	3	1	-1	0	0
z2	5	1	1	0	-1
W	6M	3M-1	2
- искусственные переменные

2	Bi	z1	x2	x3	x6
x1					0
x4					0
x5					0
z2					-1
W

3	Bi	z1	z2	x3	x6
x1	2
x4	14
x5	5
x2	3
W	-4			1	1

4	Bi	z1	z2	x3	x4
x1	4
x6	6
x5	7
x2	7
W	-10

Ответ ПЗ: при , .

Ответ ОЗ: при , , .

Пример 3).

прямая задача			двойственная задача
ОЗЛП			ОЗЛП

Соответствие между переменными

основные (свободные)

дополнительные (базисные)

ПЗ

ОЗ

основные (свободные)

дополнительные (базисные)

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

Р е ш е н и е ОЗ.

1	Bi	y1	y2	y3		2	Bi	y1	y5	y3		3	Bi	y4	y5	y3
y4	2	3	4	-1		y4						y1				1
y5	1	1	3	-2		y2						y2				-1
	0	3	6	-3			-2	1	-2	1						0

Ответ ОЗ: при ; ; .

Ответ ПЗ: при ; .

Двойственный симплекс-метод (ПР № 8)

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

Этот метод обеспечивает выполнение условия оптимальности решения и система­тическое ‘приближение’ его к области допустимых решений. Когда получен­ное решение оказывается допустимым, процесс вычисления заканчивается, т.к. это ре­шение является и оптимальным.