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

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

х1 ³ 0 , х2 ³ 0, -2у1 + у2 - у3 £ 5,

-2х1 - х2 ³ -5, - у1 - у2 -3у3 £ -8,

х1 - х2 ³ 1, у1 ³ 0, у2 ³ 0, у3 ³ 0.

- х1 - 3х2 ³ 10.

Задача 1 и задача 2 являются общими задачами. При помощи дополнительных неизвестных х3 ³ 0, х4 ³ 0, х5 ³ 0 в задаче 1 и у4 ³ 0, у5 ³ 0 в задаче 2 приведем каждую из задач к основной и запишем в виде (38).

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

Min ¦(Х) = 5х1 - 8х2 Max g (Y) = -5у1 + у2 -10у3

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

-2х1 - х2 + х3 = -5, -2у1 + у2 - у3 + y4 = 5, (38)

х1 - х2 - х4 = 1 - у1 - у2 -3у3 - y5 = -8,

- х1 - 3х2 + х5 =10.

xj ³ ( j = 1,2 ) yi ³ ( i = 1¸5 ).

Каждая из задач 1’ и 2’ не является канонической и требует введения одного искусственного неизвестного, так как в задаче 1’ нет базисного неизвестного во втором уравнении и в задаче 2’ нет базисного неизвестного также во втором уравнении. Выберем для решения задачу 2’, так как в ней па одно уравнение меньше, чем в задаче 1’. Составим для нее вспомогательную задачу, которую будем решать на первом этапе.

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

-2у1 + у2 - у3 + у4 = 5,

у1 + у2 + 3у3 - у5 + z1 = 8, (39)

yi ³ 0 ( i = 1 ¸ 5 ), z1 ³ 0, (40)

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

Решая вспомогательную задачу (39)—(41) симплекс-методом, получим для нее следующую последовательность симплексных таблиц.

		0	0	0	0	0	0	0	1
		Баз.	у0	у1	у2	у3	у4	у5	z1
	0	y4	5	-2	1	-1	1	0	0	Табл. 1
	1	z1	8	1	1	3	0	-1	1	q = 8/3
		j	8	1	1	3	0	-1	0
	0	y4	23/3	-5/3	4/3	0	1	-1/3	1/3	Табл.2
®	0	y3	8/3	1/3	1/3	1	0	-1/3	1/3
		j	0	0	0	0	0	0	-1

Из табл. 2 получим, что φ= 0, следовательно, существует каноническая задача, равносильная исходной, которую будем решать на втором этапе.

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

-5/3у1 + 4/3у2 + у4 - 1/3у5 = 23/3 ,

1/3у1 + 1/3у2 + у3 - у5 = 8/3 , (42)

yi ³ 0 (i = 1 ¸ 5), (43)

g(Y) = -5y1 + y2 - 10y3 ¾ max. (44)

Решение задачи (42)—(44) содержится в следующих таблицах.

			0	-5	1	-10	0	0
		Баз.	у0	у1	у2	у3	у4	у5
	0	у4	23/3	-5/3	4/3	0	1	-1/3	Табл.1
	-10	у3	8/3	1/3	1/3	1	0	-1/3	q=
		g	-80/3	5/3	-13/3	0	0	10/3
®	1	y2	23/4	-5/4	1	0	3/4	-1/4	Табл.2
	-10	y3	3/4	3/4	0	1	-1/4	-1/4
		g	-7/4	-15/4	0	0	13/4	9/4
	1	y2	7	0	1	5/3	1/3	-2/3	Табл.3
®	-5	y1	1	1	0	4/3	-1/3	-1/3
		g	2	0	0	5	2	1
			¦	x3	x4	x5	x1	x2

В индексной строке табл.3 нет отрицательных чисел, следовательно, из столбца свободных членов можно выписать оптимальный план и максимальное значение целевой функции g(U) основной задачи 2’: Y*= (1, 7, 0, 0, 0), g(Y*) = 2.