Задание 8.3

Задание

По\Пн	=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.

	v₁=3	v₂=1	v₃=2	v₄=4
u₁=0	3[5]	1[25]	2	4[10]
u₂=-1	2[5]	3	1[15]	6
u₃=-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

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

Поделиться этим