15. Решение задач

Вернемся к решению задачи из примера в начале темы. Для задачи (3.51)–(3.53) запишем ВЗ:

-(U1+U2+U3) Max (3.84)

2X1 + 2X3 + 4X4 + X5 + U1 = 150

X1 + X2 + 2X5 + U2 = 200 (3.85)

X1 + X3 + 2X6 + U3 = 300

Xj ≥ 0; Ui ≥ 0; j = ; I = . (3.86)

Результаты первого этапа представлены в табл. 3.5.

Таблица 3.5

					0	0	0	0	0	0	-1	-1	-1
S	I
	1	7	-1	150	0	2	2	4	1	0	1	0	0		37,5
0	2	8	-1	200	1	1	0	0	2	0	0	1	0		-
	3	9	-1	300	1	0	1	0	0	2	0	0	1		-
	4			-650	-2	-3	-3	-4	-3	-2	0	0	0
	1	4	0	37,5	0	0,5	0,5	1	0,25	0	0,25	0	0	-	150	-
1	2	8	-1	200	1	1	0	0	2	0	0	1	0	200	100	-
	3	9	-1	300	1	0	1	0	0	2	0	0	1	300	-	150
	4			-500	-2	-1	-1	0	-2	-2	1	0	0
	1	4	0	37,5	0	0,5	0,5	1	0,25	0	0,25	0	0		-
2	2	1	0	200	1	1	0	0	2	0	0	1	0		-
	3	9	-1	100	0	-1	1	0	-2	2	0	-1	1		50
	4			-100	0	1	-1	0	2	-2	1	2	0
	1	4	0	37,5	0	0,5	0,5	1	0,25	0	0,25	0	0
3	2	1	0	200	1	1	0	0	2	0	0	1	0
	3	6	0	50	0	-0,5	0,5	0	-1	1	0	-0,5	0,5
	4			0	0	0	0	0	0	0	1	1	1

На третьей итерации симплексного метода получен оптимальный план вспомогательной задачи: = (200; 0; 0; 37.5; 0; 50; 0; 0; 0), в котором ни одна из искусственных переменных не является базисной, следовательно, вектор = (200; 0; 0; 37.5; 0; 50) является невырожденным опорным планом исходной задачи, определяемым К-матрицей.

На втором этапе решаем задачу

max (–0,4X1–0,3X2–0,1X3–0,1X5–0,2X6)

.

Решение приведено в табл. 3.6.

Таблица 3.6

					-0.4	-0.3	-0.1	0	-0.1	-0.2
S	I
	1	4	0	37,5	0	0,5	0,5	1	0,25	0	150
0	2	1	-0,4	200	1	1	0	0	2	0	100
	3	6	-0,2	50	0	-0,5	0,5	0	-1	1	-
	4			-90	0	0	0	0	-0,5	0
	1	4	0	12,5	-0,125	0,375	0,5	1	0	0	25
1	2	5	-0,1	100	0,5	0,5	0	0	1	0	-
	3	6	-0,2	150	1	0	1	0	0	1	300
	4			-40	0,25	0,25	0	0	0	0
	1	3	-0,1	25	-0,25	0,75	1	2	0	0
2	2	5	-0,1	100	0,5	1	0	0	1	0
	3	6	-0,2	137,5	0,625	-0,375	0	-1	0	1
	4			-100	0,25	0,25	0	0	0	0

На первой итерации (табл. 3.6) второго этапа получен оптимальный план исходной задачи 1 = (0; 0; 12.5; 100; 150) и = 40.

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

2 = (0; 0,25; 0; 100; 137,5) и = 40.

Исходная задача имеет бесчисленное множество решений, задаваемое формулой

(3.87)

Пример 3.15. Решить ЗЛП:

max (2X1 – X2 – X4)

X1 – 2X2 + X3 = 10

–2X1 – X2 – 2X4 18 (3.88)

3X1 + 2X2 + X4 36

Приведем ЗЛП (3.88) к каноническому виду

max (2X1 – X2 – X4)

X1 – 2X2 + X3 = 10

-2X1 – X2 – 2X4 – S1 =18 (3.89)

3X1 + 2X2 + X4-S2 = 36

Расширенная матрица системы линейных уравнений (3.89)

Не является К-матрицей ЗЛП (3.89) , т. к. не содержит единичной подматрицы.

Запишем вспомогательную задачу для ЗЛП (3.89). Т. к. матрица Содержит один единичный вектор = (1; 0; 0), то при формулировке ВЗ достаточно ввести лишь две искусственные переменные U1; U2 во второе и третье уравнения системы (3.89).

Итак, ВЗ имеет вид

-(U1+U2) Max

X1 – 2X2 + X3 = 10

-2X1 – X2 – 2X4 – X5 + U1 = 18 (3.90)

3X1 + 2X2 + X4 – X6 + U2 = 36

; U1 ,U2 0

Решение ВЗ приведено в табл. 3.7.

Таблица 3.7

					0	0	0	0	0	0	-1	-1
S	I
	1	3	0	10	-1	-2	1	0	0	0	0	0	-
0	2	7	-1	18	-2	-1	0	-2	-1	0	1	0	-
	3	8	-1	36	3	2	0	1	0	-1	0	1	18
	4			-54	-1	-1	0	1	1	1	0	0
	1	3	0	46	2	0	1	1	0	-1	0	1
1	2	7	-1	36	-0,5	0	0	-1,5	-1	-0,5	1	0,5
	3	2	0	18	1,5	1	0	0,5	0	-0,5	0	0,5
	4			-36	0,5	0	0	1,5	1	0,5	0	0,5

На первой итерации получен оптимальный план.

= (0; 18; 46; 0; 0; 36; 0).

Т. к. вектор имеет отличную от нуля искусственную переменную U1 = 36, то множество планов ЗЛП (3.88) пусто в силу несовместности системы уравнений (3.89).

< Предыдущая		Следующая >