На оптовых складах А1, А2, А3, А4 имеются запасы некоторого продукта в известных количествах, который необходимо доставить в магазины В1, В2, В3, В4, В5. Известны также тарифы на перевозку единицы продукта из каждого склада в каждый магазин.
Найти такой вариант прикрепления магазинов к складам, при котором сумма затрат на перевозку была бы минимальной.
Оптовые склады Магазины Запасы
В1
В2
В3 В4
В5
А1
5 4 10 7 8 350
А2
7 6 7 10 6 650
А3 2 9 5 3 4 950
А4
6 11 4 12 5 700
Потребности 660 470 250 980 640
Решение
Проверим условие разрешимости задачи.
A=i=1mai=350+650+950+700=2650; B=j=1nbj=660+470+250+980+640=3000.
Как видно, суммарная потребность груза в пунктах назначения не равна суммарному запасу груза. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем фиктивный склад, с запасом равным 350. Тарифы перевозки единицы груза из склада во все магазины полагаем равными нулю.
Занесем исходные данные в распределительную таблицу и составим первый план транспортной задачи методом наименьшей стоимости. Заполнение клеток таблицы начнем с левой верхней клетки.
Оптовые склады Магазины Запасы
В1
В2
В3 В4
В5
А1
5 4
350 10 7 8 350
А2
7 6
120 7 10
340 6
190 650
А3 2
660 9 5 3
290 4 950
А4
6 11 4
250 12 5
450 700
А5 0 0 0 0
350 0 350
Потребности 660 470 250 980 640
Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 =9. Следовательно, опорный план является невырожденным.
Запишем исходное опорное решение в виде матрицы перевозок
X0=0066000 350120000 0002500 03402900350 019004500
Значение целевой функции для этого опорного плана равно:
FX0=4∙350+6∙120+10∙340+6∙190+2∙660+
+3∙290+4∙250+5∙450+0∙350=12100
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β2=4α2+β2=6α2+β4=10α2+β5=6α3+β1=2α3+β4=3α4+β3=4α4+β5=5α5+β4=0
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=2; α3=-5; α4=1; α5=-8
β1=7; β2=4; β3=3; β4=8; β5=4
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=5-0-7=-2
∆13=10-0-3=7
∆14=7-0-8=-1
∆15=8-0-4=4
∆21=7-2-7=-2
∆23=7-2-3=2
∆32=9+5-4=10
∆33=5+5-3=7
∆35=4+5-4=5
∆41=6-1-7=-2
∆42=11-1-4=6
∆43=12-1-8=3
∆51=0+8-7=1
∆52=0+8-4=4
∆53=0+8-3=5
∆55=0+8-4=4
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную по модулю отрицательную оценку свободной клетки.
Для этого в перспективную клетку 1;1 поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Оптовые склады Магазины Запасы
В1
В2
В3 В4
В5
А1
293333153446029333315329600[+] 5 [-]392393153446 4
350 10 7 8 350
А2
7 3925421611410[+] 6
120 7 [-]3493991610660 10
340 6
190 650
А3 [-]293333126776 2
660 9 5 [+] 3
290 4 950
А4
6 11 4
250 12 5
450 700
А5 0 0 0 0
350 0 350
Потребности 660 470 250 980 640
Цикл приведен в таблице 1,1 → 1,2 → 2,2 → 2,4 → 3,4 → 3,1.
Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е
. y=min2, 4=340.
Прибавляем 340 к объемам грузов, стоящих в плюсовых клетках и вычитаем 340, стоящих в минусовых клетках. В результате получим новый опорный план.
Оптовые склады Магазины Запасы
В1
В2
В3 В4
В5
А1
5
340 4
10 10 7 8 350
А2
7 6
460 7 10 6
190 650
А3 2
320 9 5 3
630 4 950
А4
6 11 4
250 12 5
450 700
А5 0 0 0 0
350 0 350
Потребности 660 470 250 980 640
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=2; α3=-3; α4=1; α5=-6
β1=5; β2=4; β3=3; β4=6; β5=4
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆13=10-0-3=7
∆14=7-0-6=1
∆15=8-0-4=4
∆21=7-2-5=0
∆23=7-2-3=2
∆24=10-2-6=2
∆32=9+3-4=8
∆33=5+3-3=5
∆35=4+3-4=3
∆41=6-1-5=0
∆42=11-1-4=6
∆44=12-1-6=5
∆51=0+6-5=1
∆52=0+6-4=2
∆53=0+6-3=3
∆55=0+6-4=2
Опорный план является оптимальным, так как все оценки свободных клеток положительны.
X2=340032000 10460000 0002500 006300350 019004500
Минимальные затраты составят FX2=11420.
Анализ оптимального плана.
Из 1-го склада необходимо направить в 3-й магазин груз в количестве 340 единиц, во 2-й магазин 10 единиц.
Из 2-го склада необходимо груз направить во 2-й магазин в количестве 460 единиц, в 5-й магазин 190 единиц.
Из 3-го склада необходимо груз направить в 1-й магазин в количестве 320 единиц, а в 4-й магазин в количестве 630 единиц.
Из 4-го склада необходимо груз направить в 3-й магазин в количестве 250 единиц, а в 5-й магазин в количестве 450 единиц.
Контрольные вопросы к зачёту по теме
«Решение открытой транспортной задачи методом потенциалов»
В чём состоят отличия закрытой и открытой моделей транспортной задачи?
Существует две разновидности транспортной задачи – открытая и закрытая
Задать вопрос
на новый заказ в Автор24.
