Контрольная работа: Математическое программирование

a₄ +b₂ =0; a₄ +b₃ =0; a₄ +b₄ =0.

Поскольку количество переменных меньше, чем уравнений, то положим: a₁ =0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a₁ +b₂ =0+4=4 ≤ 8; a₁ +b₃ =0+4=4 ≤ 7;

a₂ +b₂ =–4+4=0 ≤ 6; a₂ +b₃ =–4+4=0 ≤ 10; a₂ +b₄ =–4+4=0 ≤ 3;

a₃ +b₁ =–1+9=8 > 2 [6]; a₃ +b₃ =–1+4=3 ≤ 5; a₃ +b₄ =–1+4=3 ≤ 7;

a₄ +b₁ =–4+9=5 > 0 [5];

Для клетки A₃ B₁ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(80, 40, 150)=40.

Переходим к следующей итерации.

B A		1		2		3		4		a
		200		200		140		180
1	220	9		8		7		4		0
		40	–	0	+	180
2	120	5		6		10		3		–4
		120
3	150	2		3		5		7		–7
		40	+	110	–
4	230	0		0		0		0		–10
		90	+	140	–
b		9		10		10		4

Стоимость 4 плана перевозки:

z₄ = 40 · 9+180 · 4+120 · 5+40 · 2+110 · 3+90 · 0+140 · 0 = 2090.

Для базисных клеток система потенциалов такая:

a₁ +b₁ =9; a₁ +b₄ =4;

a₂ +b₁ =5;

a₃ +b₁ =2; a₃ +b₂ =3;

a₄ +b₂ =0; a₄ +b₃ =0;

Поскольку количество переменных меньше, чем уравнений, то положим: a₁ =0. Проверяем условие оптимальности для свободных клеток: a + b ≤ c

a₁ +b₂ =0+10=10 > 8 [2]; a₁ +b₃ =0+10=10 > 7 [3];

a₂ +b₂ =–4+10=6 ≤ 6; a₂ +b₃ =–4+10=6 ≤ 10; a₂ +b₄ =–4+4=0 ≤ 3;

a₃ +b₃ =–7+10=3 ≤ 5; a₃ +b₄ =–7+4=–3 ≤ 7;

a₄ +b₁ =–10+9=–1 ≤ 0; a₄ +b₄ =–10+4=–6 ≤ 0;

Для клетки A₁ B₃ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(40, 110, 140)=40.

Переходим к следующей итерации.

B A		1		2		3		4		a
		200		200		140		180
1	220	9		8		7		4		0
		40	180
2	120	5		6		10		3		–1
		120
3	150	2		3		5		7		–4
		80	70
4	230	0		0		0		0		–7
		130	100
b		6		7		7		4

Стоимость 5 плана перевозки:

z₅ = 40 · 7+180 · 4+120 · 5+80 · 2+70 · 3+130 · 0+100 · 0 = 1970.

Для базисных клеток система потенциалов такая: