Решить транспортную задачу методом потенциалов. Первоначальный опорный план составьте методом северо-западного угла.
Имеется три ткацких фабрики А1, А2 и А3 , которые поставляют ткань на три швейные фабрики в пределах России В1, В2 и В3. Известны запасы ткани на каждой ткацкой фабрике (в рулонах) и потребности в ней на каждой швейной фабрике. Известна также стоимость перевозки одного рулона ткани (у. е.) от каждого поставщика к каждому потребителю.
Найти такой план перевозок, при котором суммарные затраты оказались бы минимальными.
Условия (запасы, потребности и цена перевозки каждого рулона ткани) для каждого номера задачи приведены в таблицах.
4.05
запас B1 B2 B3
A1 15 6 7 5
A2 8 5 6 4
A3 20 9 10 6
потребность 16 20 35
Решение:
Прежде всего, проверим, является ли поставленная задача закрытой.
Запасы поставщиков: 15+8+20 = 43 единиц продукции.
Потребность потребителей: 16+20+35 = 71 единиц продукции.
Разница в 28 единиц продукции. Уравнение баланса не выполнено, следовательно, это транспортная задача открытого типа.
Такая задача сводится к закрытой введением фиктивного поставщика А4, с запасами 28 единиц продукции.
Стоимость доставки единицы продукции от поставщика А4 ко всем потребителям принимаются равными нулю
поставщики запас В1
В2
В3
А1
15 6 7 5
А2
8 5 6 4
А3 20 9 10 6
А4
28 0 0 0
Запросы потребителей
16 20 35
Теперь суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Решение будем строить непосредственно в транспортной таблице. Начальный план строим методом северо-западного угла.
Итерация №1 V1=6 V2=7 V3=3
поставщики запас В1
В2
В3
А1
15 6
15 7
5
U1=0
А2
8 5
1 6
7 4
U2=-1
А3 20 9 10
13 6
7 U3=3
А4
28 0 0 0
28 U4=-3
Запросы потребителей
16 20 35
Первой заполняем верхнюю левую клетку (северо-западный угол). У первого поставщика имеется 15 ед. груза, а потребности первого потребителя составляют 16 ед., поэтому 15 ед. мы забираем у первого поставщика. Первый потребитель обеспечен не полностью. Недостающие первому потребителю 1 ед. груза возьмем у 2-го поставщика. Оставшиеся у 2-го поставщика 7 ед. груза отправим 2-му потребителю. Недостающие 2-му потребителю 20-7=13 ед удовлетворяем из запасов 3-го поставщика. Оставшиеся запасы 3-го поставщика и 4-го поставщика отправляем 3-му потребителю. Весь груз распределен. Так как количество занятых клеток 6, а должно быть 4+3-1=6, то получено начальное решение задачи.
Стоимость доставки продукции для начального решения составит: Z0=615+51+67+1013+67+028=309 ден. ед.
Проверим оптимальность начального решения методом потенциалов.
Каждому поставщику Ai ставим в соответствие некоторое число Ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число Vj, называемое потенциалом потребителя. К табл. добавим сверху ещё одну строку и справа ещё один столбец.
В строке будем записывать потенциалы Vj, , а в столбце потенциалы Ui.
Для заполненных клеток, сумма потенциалов поставщика и потребителя равна тарифу задействованного маршрута, т.е. Ui+Vj=Cij, где Cij – тариф перевозки от поставщика Ai к потребителю Bj.
Значение одного потенциала необходимо задать. Пусть U1=0. Тогда для заполненных клеток:
(1;1): U1+V1=6 V1=6
(2;1): U2+V1=5 U2=-1
(2;2): U2+V2=6 V2=7
(3;2): U3+V2=10 U3=3
(3;3): U3+V3=6 V3=3
(4;3): U4+V3=0 U4=-3
Для каждой незанятой клетки сумма потенциалов должна не превышать стоимость перевозки, стоящей в этой клетке, т.е. Ui+VjCij. Если хотя бы одна клетка не удовлетворяет этому условию, то план является неоптимальным и его можно улучшить.
Найдем оценки пустых клеток по формуле ij=Ui+Vj-Cij.
12=0+7-7=0
13=0+3-5=-2
23=-1+3-4=-2
31=3+6-9=0
41=-3+6-0=3>0
42=-3+7-0=4>0
Три оценки оказались положительными, следовательно, найденный план перевозок неоптимален, его можно улучшить.
Для клетки (4,2) (у нее положительная оценка максимальна) строим цикл пересчета
Итерация №1 V1=6 V2=7 V3=3
поставщики запас В1
В2
В3
А1
15 6
15 7
5
U1=0
А2
8 5
1 6
7 4
U2=-1
А3 20 9 3689351054100010
-13 6
+7 U3=3
А4
28 0 0
+ 0
-28 U4=-3
Запросы потребителей
16 20 35
Клетка (4.2) – вершина цикла. Она находится в пустой клетке, остальные вершины – в заполненных клетках. Клетка (4.2) помечена знаком «+», далее последовательно расставлены знаки «- « и «+». Среди клеток, помеченных знаком «- « обычно определяют наименьшее значение перевозки и его перемещают по циклу. В нашем случае эта величина составила 13 единиц груза. Перемещаем грузы по циклу.
В клетки со знаком «+» добавляем 13 единиц груза, а со знаком минус уменьшаем на 13. Получаем новый план:
Итерация №2 V1=6 V2=7 V3=7
поставщики запас В1
В2
В3
А1
15 382270110490003822701104906
-15 7
643890120015005
+ U1=0
А2
8 5
382270-444500+1 6
568960-444500-7 4
U2=-1
А3 20 9 10
6
20 U3=-1
А4
28 0 530860187960000
+13 0
-15 U4=-7
Запросы потребителей
16 20 35
Стоимость доставки продукции для нового плана составит:
Z1=615+51+67+620+013+015=257 ден. ед.
Для оценки его оптимальности снова строим систему потенциалов, принимая U1=0.
Для заполненных клеток:
(1;1): U1+V1=6 V1=6
(2;1): U2+V1=5 U2=-1
(2;2): U2+V2=6 V2=7
(4;2): U4+V2=0 U4=-7
(4;3): U4+V3=0 V3=7
(3;3): U3+V3=6 U3=-1
Оценки пустых клеток:
12 =0+7-7=0
13=0+7-5=2>0
23=-1+7-4=2>0
31=-1+6-9=-4
32=-1+7-10=-4
41=-7+6-0=-1
Строим цикл для клетки (1,3), перемещая 7 ед груза:
Итерация №3 V1=6 V2=5 V3=5
поставщики запас В1
В2
В3
А1
15 248920186690006
-8 7
5
+7 U1=0
А2
8 5
8 6
4
U2=-1
А3 20 9 10
6
20 U3=1
А4
28 0
+ 0
20 0
-8 U4=-5
Запросы потребителей
16 20 35
Стоимость доставки продукции для нового плана составит:
Z3=68+58+57+620+020+08=243 ден. ед.
Для оценки его оптимальности снова строим систему потенциалов, принимая U1=0.
Оценки пустых клеток:
12 =0+5-7=-2
22=-1+5-6=-2
23=-1+5-4=0
31=1+6-9=-2
32=1+5-10=-4
41=-5+6-0=1>0
Строим цикл для клетки (4,1), перемещая 8 ед груза:
Итерация №4 V1=6 V2=6 V3=5
поставщики запас В1
В2
В3
А1
15 6
0 7
5
15 U1=0
А2
8 5
8 6
4
U2=-1
А3 20 9 10
6
20 U3=1
А4
28 0
8 0
20 0
U4=-6
Запросы потребителей
16 20 35
Z4=515+58+620+08+020+00=235 ден. ед.
Для оценки его оптимальности снова строим систему потенциалов, принимая U1=0.
Оценки пустых клеток:
12=0+6-7=-1
22=-1+6-6=-1
23=-1+5-4=0
31=1+6-9=-2
32=1+6-10=-3
43=-6+5-0=-1
Все оценки неположительные, следовательно, план оптимален.
Запишем ответ задачи: .
Поскольку последняя строка оптимального плана соответствует фиктивному потребителю из окончательного ответа она должна быть исключена. Отброшенные 28 ед. груза поставщика А4 останутся недоставленными. Окончательный ответ:
; ден. ед.
