Решение задач р-методом

Решим задачу из примера 2.11.

Результаты решения приведены в симплекс-таблице. Таблица 2.4.

					-2	-4	0	0	0
S	I
	1	3	0	-3	-3	-1	1	0	0
0	2	4	0	-6	-4	-3	0	1	0
	3	5	0	3	1	2	0	0	1
	4			f = 0	2	4	0	0	0
	5				2/4	4/3	-	-	-
	1	3	0	3/2	0	5/4	1	3/4	0
1	2	1	-2	3/2	1	3/4	0	-1/4	0
	3	5	0	3/2	0	5/4	0	1/4	1
	4			f = -3	0	5/2	0	1/2	0
	5

Так как компоненты псевдоплана =( 3/2, 3/2, 3/2) являются неотрицательными, то является оптимальным опорным планом ЗЛП (2.78). Итак,

=( 3/2, 0, 3/2, 0, 3/2) и min =3.

Пример 2.12. Решим ЗЛП:

max = - x₁ + 2x₂

-2 x₁ + x₂ 2

x₁ + 2 x₂ 4 (2.82)

x₁ + 4 x₂ 4

x_1,2 0

Приведем рассматриваемую ЗЛП к каноническому виду

max = (- x₁ + 2 x₂ )

- 2 x₁ + x₂ - S₁ = 2

x₁ + 2x₂ + S₂ = 4

x₁ + 4x₂ - S₃ = 4

или

max = (- x₁ + 2 x₂ ) при ограничениях:

2 x₁ - x₂ + S₁ = - 2

x₁ + 2x₂ + S₂ = 4 (2.83)

- x₁ - 4x₂ + S₃ = - 4

Расширенная матрица

системы линейных уравнений (2.83) не являются Р-матрицей рассматриваемой ЗЛП, так как

=(0, 0, 0) + 1 = 1 > 0 , =(0, 0, 0) - 2 = -2 < 0.

Следовательно, к решению ЗЛП (2.82) не применим Р-метод.

Пример 2.13. Найти минимум функции

= ( 6 x₁ + 3x₂ )

при ограничениях : -3 x₁ + x₂ 1

2 x₁ - 3 x₂ 2 (2.84)

x_1,2 0 Приведем задачу к каноническому виду

= (- 6 ₁ - 3 ₂ ) max

3 x₁ - x₂ + S₁ = - 1

- 2 x₁ + 3x₂ + S₂ = - 2

Так как расширенная матрица

=

системы линейных уравнений рассматриваемой задачи является Р-матрицей ( = 6 >0; = 3 >0 ), то задачу можно решить Р-методом. Решение задачи ведем в симплексной таблице.

Таблица 2.5

					-6	-3	0	0
S	i
	1	3	0	-1	3	-1	1	0
	2	4	0	-2	-2	3	0	1
0	3		= 0		6	3	0	0
	4		-	-	3	-	-	-
	1	3	0	-4	0	7/2	1	3/2
	2	1	-6	1	1	-3/2	0	-1/2
1	3		= -6		0	12	0	3
	4		-		-	-	-	-

Так как = = -4 < 0, а все 0, то множество планов ЗЛП (2.84) является пустым множеством.