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

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

x2 - 5/4x3 = 5,

x1 -7/4 x3 = 4, (16)

xj ³ 0 (j = 1, 2, 3), (17)

¦(X) = 2x1 -3x2 + 4x3 ¾ max (18)

Решим симплекс-методом задачу (

		0	2	-3	4
	Баз.	x0	x1	x2	x3
-3	x2	5	0	1	-5/4	Табл. 1
2	x1	4	1	0	-7/4
	¦	-7	0	0	-15/4

В индексной строке табл. 1 есть отрицательный элемент -15/4 а над ним в таблице нет ни одного положительного. Следовательно, в задаче (целевая функция не ограничена сверху на множестве планов задачи и оптимального плана не существует. Значит, не существует оптимального плана и в исходной задаче (

Пример 3. Решить симплекс-методом следующую задачу ЛП:

x1 + 4x2 + 3x3 - x4 = 8,

2x2 + x3 - 5x4 = 12, (19)

xj ³ 0 (j = 1¸4), (20)

¦(X) = 5x + 4x + 2x - 5x ¾ min. (21)

Основная задача (19)—(21) не является канонической, так как во втором уравнении системы (19) нет базисного неизвестного и, значит, система (19) не является канонической. Составим вспомогательную задачу, введя искусственное базисное неизвестное, только во второе уравнение системы (19), так как в первом уравнении уже есть базисное неизвестно

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

x1 + 4x2 + 3x3 - x4 = 8,

2x2 + x3 -5x4 + z1= 12, (22)

xj ³ 0 (j = 1¸4), z1 ³ 0, (23)

j(X) = z1 + z2 ¾ min. (24)

Применив к задаче (22)—(24) алгоритм симплекс-метода, получим последовательность симплексных таблиц вида:

			0	0	0	0	0	1
		Баз.	x0	x1	x2	x3	x4	z1
	0	x1	8	1	4	3	-1	0	Табл.1 q=min (8/4,12/2)= 8/4
	1	z1	12	0	2	1	-5	1
		j	12	0	2	1	-5	0
®	0	x2	2	1/4	1	3/4	-1/4	0	Табл. 2
	1	z1	8	-1/2	0	-1/2	-9/2	1
		j	8	-1/2	0	-1/2	-9/2	0

Из индексной строки табл.2 видим, что вспомогательная задача (решена, причём минимальное значение вспомогательной функции (24) ,jmin = 8> 0. Так как jmin > 0, то можно сделать вывод, что исходная основная задача (вообще не имеет ни одного плана, и для неё не существует равносильной канонической задачи. В таком случае задача (не имеет оптимального плана.