Основы исследования операций (стр. 6 )

(4.15)

(4.16)

1.  Подставляем в ограничения задачи, убеждаемся, что удовлетворяет ограничениям (4.15) и (4.16), следовательно – допустимое решение.

2.  Строим двойственную задачу

(4.17)

(4.18)

(4.19)

1.  По этим двум задачам составим систему уравнений вида (4.13). Так как на решении компонентыx1 и x3положительные, то первое и третье ограничение из (4.18) выполняются как строгие равенства.

(4.20)

На решении третье ограничение в (4.15) выполняется как строгое неравенство (7<9), поэтому соответствующая переменная двойственной задачи должна быть равна нулю:

y3 = 0 (4.21)

2.  Решая систему уравнений (4.20), (4.21) получим .

3.  Проверяем, удовлетворяет ли это решение ограничениям двойственной задачи (4.18), (4.19). Первое и третье ограничение из (4.18) выполняются по условию построения системы (4.20). Подставляя в остальные ограничения (4.18), убеждаемся, что они выполняются. Поскольку оказался допустимым решением двойственной задачи, то по двойственному признаку оптимальности является оптимальным решением исходной задачи.

5. РЕШЕНИЕ ЗАДАЧ ДВОЙСТВЕННОЙ ПАРЫ СИМПЛЕКС-МЕТОДОМ

Симплексный метод, (или М-метод) примененный к одной из задач двойственной пары, автоматически приводит к решению другой задачи. Это означает, что оптимальное решение двойственной задачи может быть получено непосредственно из симплекс-таблицы для оптимального решения прямой задачи.

Для получения оптимального решения необходимо воспользоваться следующим утверждением:

Утверждение 1.

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

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

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

(5.1)

(5.2)

(5.3)

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

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

(5.4)

(5.5)

yi не ограничены в знаке (5.6)

(5.7)

В этом случае начальные базисные переменные xn+i () ассоциируются с ограничениями двойственной задачи .

(5.8)

Тогда в соответствии с утверждением 1

(5.9)

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

(5.10)

Это соотношение сохраняет силу и в том случае, когда исходная задача решается М-методом.

Если имеется симметричная двойственная пара, то начальными базисными переменными являются балансовые переменные, не входящие в целевую функцию, т. е. . Поэтому формула (5.10) преобразуется в следующую:

(5.11)

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

Для иллюстрации сформулированного выше утверждения 1 рассмотрим следующую задачу линейного программирования:

(5.12)

(5.13)

(5.14)

Приведем задачу (5.12)–(5.14) к каноническому виду

(5.15)

(5.16)

(5.17)

Исходное опорное решение рассматриваемой задачи неизвестно, поэтому ее следует решать по М-методу.

Сформулируем М-задачу

(5.18)

(5.19)

(5.20)

Тогда – исходное опорное решение М-задачи, а x3, x4, x7 – начальные базисные переменные.

Построим задачу, двойственную к (5.18)–(5.20)

(5.21)

yi не ограничены в знаке, (5.22)

(5.23)

Тогда переменной x3 соответствует ограничение, переменной , а переменной x7- ограничение .

Решим М-задачу по симплексному методу (таблица 2). В этом случае соотношения (5.10) запишутся следующим образом:

(5.24)

,

где D4, D3D7, оценки переменных x4, x3, x7 соответственно в оптимальной симплексной таблице.

Таблица 2

С	1	2	1	-3	0	0	-М
СВ	Базис	x1	x2	x3	x4	x5	x6	x7	ВО
-3	x4	-1	2	0	1	1	0	0	8
1	x3	2	0	1	0	0	0	0	11
-М	x7	4	1	0	0	0	-1	1	10
	Dj	4-4M	-8-M	0	0	-3	M	0	-10M -13
-3	x4	0	9/4	0	1	1	-1/4	1/4	21/2
1	x3	0	-1/2	1	0	0	1/2	-1/2	6
1	x1	1	1/4	0	0	0	-1/4	1/4	5/2
	Dj	0	-9	0	0	-3	1	-1+M	-23
2	x2	0	1	0	4/9	4/9	-1/9	1/9	14/3
1	x3	0	0	1	2/9	2/9	4/9	-4/9	25/3
1	x1	1	0	0	-1/9	-1/9	-2/9	2/9	4/3
	Dj	0	0	0	4	1	0	M	19

Оптимальное решение исходной задачи