Задача линейного программирования. Проверка оптимальности текущего плана, страница 3

№	Б	Сб	В	c1=1	c2=1	c3=1	c4=0	c5=0
				A1	A2	A3	A4	A5
1	A1	с1= 1	b1=1	1	0	0	-1	-1
2	A2	с2= 1	b2=1	0	1	0	-2	-2
3	A3	с3= 1	b3=2	0	0	1	-3	-3
4			Z=4	0	0	0	-6	-6

2) Находим базисные столбцы матрицы системы ограничений      А₁ = ,  А₂ = ,   А₃ =  .

3) В столбце Б симплексной таблицы запишем базисные столбцы А₁, А₂ и А₃ так, что в столбце А_i единица стоит на i-ом месте.

4) В столбце С_б симплексной таблицы запишем коэффициенты целевой функции Z(X), номера которых совпадают с номерами базисных столбцов этой строки.

5) В столбце В запишем свободные члены b₁ = 1, b₂ = 1, b₃ = 2.

6) Сверху над столбцами А₁, А₂, А₃, А₄ и А₅ запишем коэффициенты целевой функции с₁ = 1, с₂ = 1, с₃ = 1, с₄ = 0 и с₅ = 0.

7) В столбцах А₁, А₂, А₃, А₄ и А₅ запишем столбцы матрицы А.

8) В строке 4 запишем текущие значения Z целевой функции, а также оценки ∆₁, ∆₂, ∆₃, ∆₄ и ∆₅ столбцов А₁, А₂, А₃, А₄ и А₅.

9) Находим Z по формуле:

Z =С_бВ =(с₁=1, с₂=1, с₃=1)∙(b₁=1, b₂=1, b₃=2)= (1)∙(1)+(1)∙(1)+(1)∙(2) = 4.

10) Находим оценки небазисных столбцов ∆₄ и ∆₅ по формуле: ∆_i= C_бА_i– c_i ,

∆₄ = C_бА₄ – c₄ = (с₁=1, с₂=1, с₃=1)∙(а₁₄=-1, а₂₄=-2, а₃₄=-3) – 0 = (+1)∙(-1)+(1)∙(-2)+(1)∙(-3) = –1 –2 –3 = –6 < 0 .

∆₅ = C_бА₅ – c₅ = (с₁=1, с₂=1, с₃=1)∙( а₁₅=-1, а₂₅=-2, а₃₅=-3) – 0 = (1)∙(-1)+(1)∙(-2)+(1)∙(-3) = –1 –2 –3 = –6 < 0 .

Для базисных столбцов А₁, А₂, А₃ оценки равны ∆_j = 0; j=1, 2, 3.

11) Значения базисных переменных в таблице равны  x₁= b₁=1, x₂= b₂=1, x₃= b₃= 2.

12) Значения небазисных переменных берутся равными нулю, т. е. х₄= 0, х₅= 0.

13) Текущий план по таблице Х₀ = (х₁ = 1, х₂ = 1, х₃ = 2, х₄ = 0, х₅ = 0).

14)Так как ∆_i ≤0 при j = 1,2,3,4,5 ,значит текущий план оптимален: Х^*=Х₀=(х₁=1,х₂=1,х₃=2,х₄=0,х₅=0),а минимальное значение функции Z(X) равно min Z(X) = 4.

15) Проверка: 1 + 0 + 0 – 0 – 0 = 1 ,0 + 1 + 0 – 0 – 0 = 1 ,0 + 0 + 2 – 0 – 0 = 2 ,

x₁ = 1 > 0 ,   x₂ = 1 > 0 ,   x₃ = 2 > 0 ,   х₄ = 0 ,   х₅ = 0 ,Z(X₀) = Z (1, 1, 2, 0, 0) = 1 + 1 + 2 = 4.

°2) В задаче на максимум, если  ∆ _j  ³ 0 при всех  j = m+1, m+2, …, n , то текущий план Х₀ оптимален: Х₀ = Х^*, и тогда max Z(X) = Z. Если же хотя бы одна оценка ∆ _j < 0 , то текущий план Х₀ не оптимален. Его можно улучшить, то есть перейти к другому текущему плану Х₁ , для которого значение Z(X) окажется большим.

Пример 3. Z(X) = 0x₁ + 1x₂ + 1x₃ – 2x₄ → max,

x₁ + 0x₂ + 0x₃ + 3x₄ = 4,

0x₁ + 0x₂ + x₃ + 4x₄ = 13 ,

0x₁ + x₂ + 0x₃ - 2x₄ = 2 ,

x_i ≥ 0, i = 1, 2, 3, 4.

Решение. 1) Составим симплексную таблицу.

№	Б	Сб	В	c1=0	c2=1	c3=1	c4=-2
				A1	A2	A3	A4
1	A1	с1= 0	b1=4	1	0	0	3
2	A3	с3= 1	b2=13	0	0	1	4
3	A2	с2= 1	b 3=2	0	1	0	-2
4			Z=15	∆1=0	∆2=0	∆3=0	∆4=4

2) Находим базисные столбцы матрицы ограничений.А₁ = ,  А₃ = ,   А₃ =  .

3) В столбце Б симплексной таблицы запишем базисные столбцы А₁, А₂ и А₃ так, что в столбце А_i единица стоит на i-ом месте.