Найти оптимальный план транспортной задачи

3.4. Найти оптимальный план транспортной задачи.

Решение

Запишем условие задачи в экономическом виде на основании таблицы, где заданы пункты отправления и назначения, запасы и потребности [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.

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

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;

a₃+b₂=3;

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.

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

a₁+b₃=7; 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+6=6 ≤ 9; a₁+b₂=0+7=7 ≤ 8;

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

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

a₄+b₁=–7+6=–1 ≤ 0; a₄+b₄=–7+4=–3 ≤ 0;

Условие оптимальности выполняется для всех клеток, следовательно последний план является оптимальным. Его стоимость составляет 1970 у.е. Следует заметить, что потребители не дополучат 230 ед. груза.

2) Метод минимальной стоимости

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

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

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

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

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

a₁+b₃=7; 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+6=6 ≤ 9; a₁+b₂=0+7=7 ≤ 8;

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

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

a₄+b₁=–7+6=–1 ≤ 0; a₄+b₄=–7+4=–3 ≤ 0;

Условие оптимальности выполняется для всех клеток, следовательно последний план является оптимальным. Его стоимость составляет 1970 у.е. Следует заметить, что потребители не дополучат 230 ед. груза.

Также отмечаем совпадение решений двумя методами.

Ответ: 1970.

Література

1. Акулич И. Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986. – 319 с.

2. Костевич Л. С. Математическое программирование. Мн.: Новое знание, 2003. – 424 с.