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

Запишем условие задачи в экономическом виде на основании таблицы, где заданы пункты отправления и назначения, запасы и потребности [1, c. 135].

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	9	8	7	4	220
A2	5	6	10	3	120
A3	2	3	5	7	150
Потребности	200	200	140	180	720\490

Поскольку запасы и потребности не совпадают, имеем задачу с неправильным балансом или открытую, следовательно введем фиктивный пункт отправления с количеством 230 единиц груза.

1) Диагональный метод

Найдем опорный план диагональным методом [1, c. 140].

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

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

z₀ = 200 · 9+20 · 8+120 · 6+60 · 3+90 · 5+50 · 0+180 · 0 = 3310.

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

a₁ +b₁ =9; a₁ +b₂ =8;

a₂ +b₂ =6;

a₃ +b₂ =3; a₃ +b₃ =5;

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

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

a₁ +b₃ =0+10=10 > 7 [3]; a₁ +b₄ =0+10=10 > 4 [6];

a₂ +b₁ =–2+9=7 > 5 [2]; a₂ +b₃ =–2+10=8 ≤ 10; a₂ +b₄ =–2+10=8 > 3 [5];

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

a₄ +b₁ =–10+9=–1 ≤ 0; a₄ +b₂ =–10+8=–2 ≤ 0;

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

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

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

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

z₁ = 200 · 9+20 · 4+120 · 6+80 · 3+70 · 5+70 · 0+160 · 0 = 3190.

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

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

a₂ +b₂ =6;

a₃ +b₂ =3; a₃ +b₃ =5;

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