Фирма «Три Толстяка» занимается доставкой мясных консервов с трех складов, расположенных в разных точках города в три магазина. Запасы консервов, имеющихся на складах, а также объемы заказов магазинов и тарифы на доставку (в условных денежных единицах) представлены в транспортной таблице.
Найти план перевозок, обеспечивающий наименьшие денежные затраты.
Склады Магазины Запасы
тыс.шт. ai
SKIPIF 1 < 0 SKIPIF 1 < 0 SKIPIF 1 < 0
Склад №1 A1 2 7 8 350
Склад №2 A2
4 2 6 250
Склад №3 A3
9 10 2 100
Заказы тыс. шт. bj 100 450 150
Ответ
Fопт=2700 у.е. Матрица перевозок:
100200500250000100
Решение
Пусть xij – количество мясных консервов (тыс. штук), доставляемых с i –го склада в j-ый магазин
Проверим, выполняется ли условие баланса для данной задачи:
i=13ai=350+250+100=700j=13bj=100+450+150=700⇒i=13aij=j=13bj,т.е. транспортная задача является закрытой. Целевая функция (совокупные транспортные затраты) имеет вид: F=2x11+7x12+8x13+4x21+2x22+6x23+9x31+10x32+2x33→min.
Ограничения:
Все консервы со всех складов нужно доставить в магазины, т.е.
x11+x12+x13=350x21+x22+x23=250x31+x32+x33=100.
Все потребности магазинов должны быть удовлетворены, т.е.
x11+x21+x31=100x12+x22+x32=450x13+x23+x33=150.
По экономическому смыслу переменные xij не должны быть отрицательными, т.е. xij≥0 i,j=1,2,3.
Таким образом, экономико-математическая модель транспортной задачи принимает вид:
F=2x11+7x12+8x13+4x21+2x22+6x23+9x31+10x32+2x33→min.
x11+x12+x13=350x21+x22+x23=250x31+x32+x33=100x11+x21+x31=100x12+x22+x32=450x13+x23+x33=150 xij≥0 i,j=1,2,3
2. Построим начальный опорный план транспортной задачи по правилу «северо-западного угла».
В этом методе в первую очередь заполняем клетку, стоящую в верхнем левом (северо-западном) углу таблицы поставок
. Затем заполнение клеток продолжаем вправо и вниз, заканчивая самой правой нижней клеткой (см. таблицу 1).
Число занятых клеток должно быть равно m+n-1=3+3-1=5. Таблица 1. Начальный план
b1=100
b2=450
b3=150
a1=350
2
100 7
250 8
a2=250
4
2
200 6
50
a3=100
9 10 2
100
3. Методом потенциалов проверим, является ли опорный план, полученный по правилу «северо-западного угла», оптимальным, и если это не так, то составим оптимальный план, обеспечивающий минимальную стоимость перегона.
Чтобы проверить оптимальность полученного плана перевозки мясных консервов, введём потенциалы складов ui (для каждой строки матрицы перевозок) и пунктов доставки - магазинов vj (для каждого столбца матрицы перевозок).
Потенциалы подбираются таким образом, чтобы для заполненной клетки i,j выполнялось равенство vj=uj+cij. Значение одного из потенциалов задаём произвольно: u1=0, тогда значения остальных потенциалов найдутся однозначно. Таблица 2. Нахождение потенциалов
2
100 7
250 8 u1=0
4
2
200 6
50 u2=5
9 10 2
100 u3=9
v1=2
v2=7
v3=11
Получим значение суммарных затрат, для данного начального решения:
Fнач=2∙100+7∙250+2∙200+6∙50+2∙100=2850 (у.е.).
Чтобы оценить оптимальность распределения, найдём для свободных клеток их оценки dij по формуле:
dij=ui+cij-vj.
Имеем: dij=000+8-115+4-2009+9-29+10-70=00-370016120.
Полученный начальный план перегона не является оптимальным, так как среди оценок dij есть одна отрицательная
Задать вопрос
на новый заказ в Автор24.
