Транспортная задача

Задание

По\Пн	=20	=25	=15	=10
=40	3	1	2	4
=20	2	3	1	6
=10	1	1	2	5

Решение:

 

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

 

	1	2	3	4	Запасы
1	3	1	2	4	40
2	2	3	1	6	20
3	1	1	2	5	10
Потребности	20	25	15	10

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 40 + 20 + 10 = 70

∑b = 20 + 25 + 15 + 10 = 70

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

	1	2	3	4	Запасы
1	3	1	2	4	40
2	2	3	1	6	20
3	1	1	2	5	10
Потребности	20	25	15	10

 

Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

 

	1	2	3	4	Запасы
1	3[5]	1[25]	2	4[10]	40
2	2[5]	3	1[15]	6	20
3	1[10]	1	2	5	10
Потребности	20	25	15	10

 

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

Опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*5 + 1*25 + 4*10 + 2*5 + 1*15 + 1*10  = 115

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

 

	v1=3	v2=1	v3=2	v4=4
u1=0	3[5]	1[25]	2	4[10]
u2=-1	2[5]	3	1[15]	6
u3=-2	1[10]	1	2	5

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

 

Минимальные затраты составят: F(x) = 3*5 + 1*25 + 4*10 + 2*5 + 1*15 + 1*10  = 115

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (5), в 2-й магазин (25), в 4-й магазин (10)

Из 2-го склада необходимо груз направить в 1-й магазин (5), в 3-й магазин (15)

Из 3-го склада необходимо весь груз направить в 1-й магазин