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

Второй этап. Задача, равносильная основной

9/4х1 + х3 = 18,

1/4 х1 + х2 = 7,

xj ³ 0 ( j = 1 ¸ 3 ),

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

		0	2	-3	0
Баз.	х0	х1	х2	х3
	0	х3	18	2	-1	1	Табл.1 q = min(18: 9/4, 7:1/4) = 18 : 9/4
	-3	x2	7	1	4	0
	j	-21	-11/4	0	0
®	2	Х1	8	1	0	4/9	Табл.2
	-3	х2	5	0	0	-1/9
		j	1	0	0	11/9

В индексной строке табл. 2 нет отрицательных чисел и, значит, Х* = (8, 5, 0) — оптимальный план основной задачи (и ¦(Х*) = 1 — ¦max, а тогда Х*= (8, 5) - оптимальный план общей задачи (и ‚(Х*) = 1 ¾ ¦max.

Проверим с помощью второго критерия оптимальности планов двойственных задач, правильно ли найден оптимальный план задачи (С этой целью для данной

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

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

Min ¦(Х) = 2х1 - 3х2 Max g (Y) = 11у1 + 28у2

при условиях: при условия х:

х1 ³ 0 , х2 ³ 0, 2у1 + у2 ³ 2 , (59)

2х1 - х2 £ 11, - у1 + 4у2 ³ -3 ,

х1 + 4х2 = 28, у1 ³ 0, у2 ³ люб. зн..

Для того, чтобы Х* = (8, 5) был оптимальны планом задачи 1, необходимо и достаточно, чтобы существовал план Y*= (у*1, y*2) двойственной ей задачи 2, такой что в каждой паре сопряженных неравенств задач (59) строгому неравенству соответствовало бы равенство. Подставив компоненты плана Х* (8, 5) в ограничения за дачи 1 и использовано правило соответствия строгому неравенству равенства, получим следующие условия.

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

¦(Х*) = 2 ´ 8 - 3 ´ 5 = 1 g (Y*) = 11у*1 + 28у*2

при условиях: при условия х:

х*1 = 8 > 0 , х*2 = 5 > 0, 2у*1 + у*2 ³ 2 , (60)

2 ´ 8 - 5 = 11, - у*1 + 4у*2 ³ -3 ,

8 + 4 ´ 5 = 28, у*1 ³ 0, у*2 ³ люб. зн..

Решив систему уравнений задачи 2

2у1 + у2 = 2,

-у1 + 4у2 = -3,

получим у*1 = 11/9 > 0, у*2 = -4/9 < 0, что удовлетворяет остальным двум условиям задачи 2, причем g(Y*) = 11 ´ 11/9 + 28 ´ (-4/9) = 1. Значит, Х*=(8, 5) действительно является оптимальным планом задачи 1. Попутно мы нашли и оптимальный план Y*= ( 11/9, -4/9) задачи 2, причем ¦(Х*) = g(Y*) = 1

5. Транспортная задача.

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

Постановка задачи

Пусть имеется m поставщиков и n потребителей некоторой однородной продукции. Известны мощности поставщиков - числа ai > 0 (i = 1, 2, ..., m), емкости потребителей - числа bj > 0 (j = 1, 2, . ., n) и числа сij > 0 (i = 1, 2, ..., m; j = 1, 2, ..., n) - стоимости перевозки единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, то есть указать, сколько единиц продукции каждый поставщик должен доставить каждому потребителю, чтобы суммарная стоимость перевозок была наименьшей. Если суммарная мощность поставщиков равна суммарной емкости потребителей, то есть Sai = Sbj ,

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

Условия транспортной задачи можно представить в виде следующей таблицы.

bj ai	b1	b2	¼	bn
a1	c11	c12	¼	c1n
a2	c21	c22	¼	c2n
¼	¼	¼	¼	¼
am	cm1	cm2	¼	cmn

(61)