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

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

a₂ +b₁ =4+9=13 > 5 [8]; a₂ +b₃ =4+4=8 ≤ 10; a₂ +b₄ =4+4=8 > 3 [5];

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

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

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

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

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

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

z₂ = 130 · 9+90 · 4+70 · 5+50 · 6+150 · 3+140 · 0+90 · 0 = 2630.

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

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

a₂ +b₁ =5; a₂ +b₂ =6;

a₃ +b₂ =3;

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

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

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

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

a₃ +b₁ =–7+9=2 ≤ 2; a₃ +b₃ =–7+4=–3 ≤ 5; a₃ +b₄ =–7+4=–3 ≤ 7;

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

Для клетки A₄ B₂ (из тех, что не выполняется условие оптимальности) разница потенциалов наибольшая, потому для нее делаем цикл пересчета на минимальную величину отрицательных вершин: min(50, 130, 90)=50.

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

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

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

z₃ = 80 · 9+140 · 4+120 · 5+150 · 3+50 · 0+140 · 0+40 · 0 = 2330.

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

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

a₂ +b₁ =5;