Методом минимального элемента
Построение первоначального плана перевозок
Методом «северо-западного угла»
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом верхнем углу ячейки.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 | 2 | 35 |
А3 | 1 | 4 | 3 | 7 | 3 | 45 |
Потребность | 20 | 26 | 16 | 38 | 20 |
Замечание. В дальнейшем все действия должны проводится в этой таблице, хотя для удобства изложения на каждом шаге заполнения таблица будет представлена заново.
Для решения задачи необходимо выполнение следующего условия:
Cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей.
Проверим.
Запасы поставщиков: 40 + 35 + 45 = 120 единиц продукции.
Потребность потребителей: 20 + 26 + 16 + 38 + 20 = 120 единиц продукции.
Таким образом, суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.
Для решения задачи необходимо выполнение следующего условия:
количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.
В нашем случае проверка правильности вычисления первоначального плана состоит в следующем:
|
|
m- количество строк (3)
n- количество столбцов (5)
m+n-1=5+3-1=7 (= количеству заполненных клеток)
Поэтому если возникнет ситуация, в которой будет необходимо исключить столбец и строку одновременно, мы исключим что-то одно.
Начинаем заполнять таблицу от левого верхнего угла (клетка A1,B1) и постепенно "двигаемся" к правому нижнему (от северо-запада к юго-востоку).
Клетка A1,B1 соответствует пункту поставщика A1 и пункту потребителя B1. Запас груза в пункте A1 равен 40, а потребность в грузе в пункте B1 – 20 единицам.
Удовлетворим потребность пункта B1 за счет поставщика A1 и впишем 20 в клетку A1,B1.
Тем самым, потребность для потребителя B1 полностью удовлетворена (пишем 0 в нижней строчке столбца B1) поставщиком А1.
Столбец В1 из дальнейшего рассмотрения удаляем.
Запас в A1 стал равным 40-20=20 (табл. 1)
Другими словами, в клетку A1,B1 мы записываем , т.е. либо потребность потребителя удовлетворяется полностью, либо на величину имеющегося запаса продукции.
Таблица 1.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 | 6 | 8 | 7 | |
А2 | 5 | 9 | 5 | 7 | 2 | 35 |
А3 | 1 | 4 | 3 | 7 | 3 | 45 |
Потребность | | 26 | 16 | 38 | 20 |
|
|
Переходим к следующей незаполненной северо-западной клетке. Это А1, В2 (стоимость равна 3).
В нее записываем . Остаток запаса в А1 стал равен 20-20=0. Запас полностью исчерпан. Потребность потребителя В2 стала равной 26-20=0 (табл. 2).
Строку А1 из дальнейшего рассмотрения удаляем.
Таблица 2.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | |
А2 | 5 | 9 | 5 | 7 | 2 | 35 |
А3 | 1 | 4 | 3 | 7 | 3 | 45 |
Потребность | | | 16 | 38 | 20 |
Переходим к следующей незаполненной северо-западной клетке. Это А1, В2 (стоимость равна 3).
В нее записываем . Остаток запаса в А2 стал равен 35-6=29. Потребность потребителя В2 стала равной 6-6=0 полностью удовлетворена (табл. 3).
|
|
Столбец В2 из дальнейшего рассмотрения удаляем.
Таблица 3.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | |
А2 | 5 | 9 6 | 5 | 7 | 2 | |
А3 | 1 | 4 | 3 | 7 | 3 | 45 |
Потребность | | | 16 | 38 | 20 |
Переходим к следующей незаполненной северо-западной клетке. Это А2,В3 (стоимость равна 9).
В нее записываем . Остаток запаса в А2 стал равен 29-16=13. Потребность потребителя В3 стала равной 16-16=0, т.е. полностью удовлетворена (табл. 4).
Столбец В3 из дальнейшего рассмотрения удаляем.
Таблица 4.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | |
А2 | 5 | 9 6 | 5 16 | 7 | 2 | |
А3 | 1 | 4 | 3 | 7 | 3 | 45 |
Потребность | | | | 38 | 20 |
|
|
Следующая северо-западная клетка А2,В4 (стоимость равна 7). В нее записываем . Остаток запаса в А2 стал равен 13-13=0. Потребность потребителя В4 стала равной 38-13=25. Строку A2 из дальнейшего рассмотрения удаляем. (табл. 5).
Таблица 5.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | |
А2 | 5 | 9 6 | 5 16 | 7 13 | 2 | |
А3 | 1 | 4 | 3 | 7 | 3 | 45 |
Потребность | | | | | 20 |
Следующая северо-западная клетка А3,В4 (стоимость равна 7). В нее записываем . Остаток запаса в А3 стал равен 45-25=20. Потребность в В4 равна 25-25=0 т.е. полностью удовлетворена (табл. 6).
Столбец В4 из дальнейшего рассмотрения удаляем.
Таблица 6.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | |
А2 | 5 | 9 6 | 5 16 | 7 13 | 2 | |
А3 | 1 | 4 | 3 | 7 25 | 3 | |
Потребность | | | | | 20 |
Последняя клетка А3,В5 (стоимость равна 3). В нее записываем . Остаток запаса в А3 равен 20-20=0, потребность в В5 равна 20-20=0 (табл. 7). Итак, все распределено.
Таблица 7.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | |
А2 | 5 | 9 6 | 5 16 | 7 13 | 2 | |
А3 | 1 | 4 | 3 | 7 25 | 3 20 | |
Потребность | | | | | |
Проверка правильности вычисления первоначального плана:
m- количество строк (3)
n- количество столбцов (5)
m + n -1=5+3-1=7 (= количеству заполненных клеток)
Построение первоначального плана методом «северо-западного угла» закончено.
Стоимость перевозки по этому плану:
z=20*2 + 20*3 + 6*9 + 16*5 + 13*7 + 25*7 + 20*3 = 560
Замечание: в отчете должна быть окончательная таблица №7 и расчет стоимости перевозки
Построение первоначального плана перевозок
методом минимального элемента
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, как и в предыдущем методе, помещают меньшее из чисел Аi или Вj. Затем, также как и в методе северо-западного угла, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Исходная таблица:
Таблица 8.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 | 2 | 35 |
А3 | 1 | 4 | 3 | 7 | 3 | 45 |
Потребность | 20 | 26 | 16 | 38 | 20 |
Находим клетку с наименьшей стоимостью доставки – это А3, В1 (стоимость равна 1).
В нее записываем . Остаток запаса в А3 стал равен 45-20=25. Потребность потребителя В1 стала равной 20-20=0 (полностью удовлетворена). Столбец В1 из дальнейшего рассмотрения удаляем (табл. 9)
Таблица 9.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 | 2 | 35 |
А3 | 1 20 | 4 | 3 | 7 | 3 | |
Потребность | | 26 | 16 | 38 | 20 |
Следующая клетка с наименьшей стоимостью доставки – это А2, В5 (стоимость равна 2).
В нее записываем . Остаток запаса в А2 стал равен 35-20=15. Потребность потребителя В1 стала равной 20-20=0 (полностью удовлетворена) (табл.10).
Столбец В5 из дальнейшего рассмотрения удаляем.
Таблица 10.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 | 2 20 | |
А3 | 1 20 | 4 | 3 | 7 | 3 | |
Потребность | | 26 | 16 | 38 | |
Следующая клетка с наименьшей стоимостью доставки – это А1, В2 (стоимость равна 3).
В нее записываем . Остаток запаса в А1 стал равен 40-26=14. Потребность потребителя В2 стала равной 26-26=0 (полностью удовлетворена) (табл.11).
Столбец В2 из дальнейшего рассмотрения удаляем.
Таблица 11.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 26 | 6 | 8 | 7 | |
А2 | 5 | 9 | 5 | 7 | 2 20 | |
А3 | 1 20 | 4 | 3 | 7 | 3 | |
Потребность | | | 16 | 38 | |
Следующая клетка с наименьшей стоимостью доставки – это А3, В3 (стоимость равна 3).
В нее записываем . Остаток запаса в А3 стал равен 25-16=9. Потребность потребителя В3 стала равной 16-16=0 (полностью удовлетворена) (табл.12).
Столбец В3 из дальнейшего рассмотрения удаляем.
Таблица 12.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 26 | 6 | 8 | 7 | |
А2 | 5 | 9 | 5 | 7 | 2 20 | |
А3 | 1 20 | 4 | 3 16 | 7 | 3 | |
Потребность | | | | 38 | |
Следующая клетка с наименьшей стоимостью доставки – это А2, В4 (стоимость равна 7).
В нее записываем . Остаток запаса в А2 стал равен 15-15=0. Потребность потребителя В4 стала равной 38-15=23 (табл.12).
Таблица 12.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 26 | 6 | 8 | 7 | |
А2 | 5 | 9 | 5 | 7 15 | 2 20 | |
А3 | 1 20 | 4 | 3 16 | 7 | 3 | |
Потребность | | | | | |
Следующая клетка с наименьшей стоимостью доставки – это А3, В4 (стоимость равна 7).
В нее записываем . Остаток запаса в А3 стал равен 9-9=0. Потребность потребителя В4 стала равной 23-9=14
Таблица 13.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 26 | 6 | 8 | 7 | |
А2 | 5 | 9 | 5 | 7 15 | 2 20 | |
А3 | 1 20 | 4 | 3 16 | 7 9 | 3 | |
Потребность | | | | | |
Следующая клетка с наименьшей стоимостью доставки – это А1, В4 (стоимость равна 8).
В нее записываем . Остаток запаса в А1 стал равен 14-14=0. Потребность потребителя В4 стала равной 14-14=0 (полностью удовлетворена) (табл. 14).
Таблица 14.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 | 3 26 | 6 | 8 14 | 7 | |
А2 | 5 | 9 | 5 | 7 15 | 2 20 | |
А3 | 1 20 | 4 | 3 16 | 7 9 | 3 | |
Потребность | | | | | |
Проверка правильности вычисления первоначального плана:
m- количество строк (3)
n- количество столбцов (5)
m + n -1=5+3-1=7 (= количеству заполненных клеток)
Стоимость перевозки по этому плану:
z = 26*3 + 14*8 + 15*7 + 20*2 + 20*1 + 16*3 + 9*7 = 466
Замечание. Стоимость перевозки, рассчитанная по методу наименьшей стоимости меньше, чем по методу северо-западного угла (как правило). В данном случае эта стоимость является оптимальной (совпадает со значением полученным в Excel). Однако, матрицы перевозок отличаются, т.е. решение, обеспечивающее минимум стоимости перевозок в данном случае неединственное.
Метод потенциалов
(начальное распределение рассчитано по методу «северо-западного угла»)
Каждому поставщику ставим в соответствие некоторое число , называемое потенциалом поставщика.
Каждому потребителю ставим в соответствие некоторое число , называемое потенциалом потребителя.
Возьмем первоначальный план (табл. 7), полученный по методу «северо-западного угла».
Таблица 15.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | u1= |
А2 | 5 | 9 6 | 5 16 | 7 13 | 2 | u2= |
А3 | 1 | 4 | 3 | 7 25 | 3 20 | u3= |
V | v1= | v2= | v3= | v4= | v5= |
Для каждой заполненной клетки, т. е. для каждой базисной переменной, строится соотношение:
Получаем систему с числом уравнений, равным количеству базисных переменных. Из этой системы определяем неизвестные потенциалы и , полагая одно из .
В нашем случае система уравнений и ее решение при взятом значении выглядит так:
|
Записав эти значения в таблицу, получим:
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 | 3 20 | 6 | 8 | 7 | u1=-6 |
А2 | 5 | 9 6 | 5 16 | 7 13 | 2 | u2=0 |
А3 | 1 | 4 | 3 | 7 25 | 3 20 | u3=0 |
V | v1=8 | v2=9 | v3=5 | v4=7 | v5=3 |
Вычислим разности для свободных клеток.
План перевозок будет являться оптимальным, если все являются неотрицательными.
A1B3 : | Δ13 = c13 - ( u1 + v3 ) = 6 - ( -6 + 5 ) = 7 |
A1B4 : | Δ14 = c14 - ( u1 + v4 ) = 8 - ( -6 + 7 ) = 7 |
A1B5 : | Δ15 = c15 - ( u1 + v5 ) = 7 - ( -6 + 3 ) = 10 |
A2B1 : | Δ21 = c21 - ( u2 + v1 ) = 5 - ( 0 + 8 ) = -3 |
A2B5 : | Δ25 = c25 - ( u2 + v5 ) = 2 - ( 0 + 3 ) = -1 |
A3B1 : | Δ31 = c31 - ( u3 + v1 ) = 1 - ( 0 + 8 ) = -7 |
A3B2 : | Δ32 = c32 - ( u3 + v2 ) = 4 - ( 0 + 9 ) = -5 |
A3B3 : | Δ33 = c33 - ( u3 + v3 ) = 3 - ( 0 + 5 ) = -2 |
Есть отрицательные значения. Значит план не является оптимальным.
ШАГ 1.
Выбираем клетку с максимальным отрицательным значением. Это клетка A3B1.
Строим цикл, т. е. замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки.
Ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной клетки. Он единственный. Направление обхода не имеет значения.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20 ⊖ | 3 20 ⊕ | 6 | 8 | 7 | u1=-6 |
А2 | 5 | 9 6 ⊖ | 5 16 | 7 13 ⊕ | 2 | u2=0 |
А3 | 1 ⊕ | 4 | 3 | 7 25 ⊖ | 3 20 | u3=0 |
V | v1=8 | v2=9 | v3=5 | v4=7 | v5=3 |
В каждую клетку цикла поочередно вписывают знаки “+” и “–“. Из всех клеток с отрицательными знаками (в данном случае из А3,В4; А2,В2; А1,В1) выбирается минимальная величина поставки, обозначаемая как D.
В те вершины, которые имеют знак “+” прибавляется поставка D, а в вершинах со знаком “–“ поставки уменьшаются на величину D.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 20-6 ⊖ | 3 20+6 ⊕ | 6 | 8 | 7 | u1=-6 |
А2 | 5 | 9 6-6 ⊖ | 5 16 | 7 13+6 ⊕ | 2 | u2=0 |
А3 | 1 +6 ⊕ | 4 | 3 | 7 25-6 ⊖ | 3 20 | u3=0 |
V | v1=8 | v2=9 | v3=5 | v4=7 | v5=3 |
При этом суммы поставок по строкам и столбцам не изменяются. В результате клетка, для которой строился цикл, станет занятой, а в одной из бывших занятых клеток окажется нулевая поставка и её надо объявить свободной. Общее количество заполненных клеток не изменится, следовательно, новый план перевозок является невырожденным.
Получили новое решение
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 16 | 7 19 | 2 | 35 |
А3 | 1 6 | 4 | 3 | 7 19 | 3 20 | 45 |
Потребность | 20 | 26 | 16 | 38 | 20 |
Стоимость перевозки по этому плану:
z=14*2 + 26*3 + 16*5 + 19*7 +6*1+ 19*7 + 20*3 = 518 (т.е. меньше, чем было 560)
(или z= 560 + Δ31 * 6 = 560 -7 * 6 = 518)
Проверим, является ли полученное решение оптимальным.
Последовательно найдем значения потенциалов.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | u1= |
А2 | 5 | 9 | 5 16 | 7 19 | 2 | u2= |
А3 | 1 6 | 4 | 3 | 7 19 | 3 20 | u3= |
V | v1= | v2= | v3= | v4= | v5= |
Значение одного потенциала необходимо задать. Пусть u3 = 0.
A3B1 : | v1 + u3 = 1 | v1 = 1 - 0 = 1 |
A3B4 : | v4 + u3 = 7 | v4 = 7 - 0 = 7 |
A3B5 : | v5 + u3 = 3 | v5 = 3 - 0 = 3 |
A1B1 : | v1 + u1 = 2 | u1 = 2 - 1 = 1 |
A1B2 : | v2 + u1 = 3 | v2 = 3 - 1 = 2 |
A2B4 : | v4 + u2 = 7 | u2 = 7 - 7 = 0 |
A2B3 : | v3 + u2 = 5 | v3 = 5 - 0 = 5 |
Записав эти значения в таблицу, получим:
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | u1=1 |
А2 | 5 | 9 | 5 16 | 7 19 | 2 | u2=0 |
А3 | 1 6 | 4 | 3 | 7 19 | 3 20 | u3=0 |
V | v1=1 | v2=2 | v3=5 | v4=7 | v5=3 |
Вычислим разности для свободных клеток.
A1B3 : | Δ13 = c13 - ( u1 + v3 ) = 6 - ( 1 + 5 ) = 0 |
A1B4 : | Δ14 = c14 - ( u1 + v4 ) = 8 - ( 1 + 7 ) = 0 |
A1B5 : | Δ15 = c15 - ( u1 + v5 ) = 7 - ( 1 + 3 ) = 3 |
A2B1 : | Δ21 = c21 - ( u2 + v1 ) = 5 - ( 0 + 1 ) = 4 |
A2B2 : | Δ22 = c22 - ( u2 + v2 ) = 9 - ( 0 + 2 ) = 7 |
A2B5 : | Δ25 = c25 - ( u2 + v5 ) = 2 - ( 0 + 3 ) = -1 |
A3B2 : | Δ32 = c32 - ( u3 + v2 ) = 4 - ( 0 + 2 ) = 2 |
A3B3 : | Δ33 = c33 - ( u3 + v3 ) = 3 - ( 0 + 5 ) = -2 |
Есть отрицательные оценки. Значит план не является оптимальным.
ШАГ 2.
Выбираем клетку с максимальным отрицательным значением. Это клетка A3B3.
Строим цикл, т. е. замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | u1= |
А2 | 5 | 9 | 5 16 -16⊖ | 7 19+16⊕ | 2 | u2= |
А3 | 1 6 | 4 | 3 +16 ⊕ | 7 19-16 ⊖ | 3 20 | u3= |
V | v1= | v2= | v3= | v4= | v5= |
Из всех клеток с отрицательными знаками (в данном случае из А2,В3; А3,В4) выбирается минимальная величина поставки, обозначаемая как D.
В те вершины, которые имеют знак “+” прибавляется поставка D, а в вершинах со знаком “–“ поставки уменьшаются на величину D.
Получили новое решение.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 35 | 2 | 35 |
А3 | 1 6 | 4 | 3 16 | 7 3 | 3 20 | 45 |
Потребность | 20 | 26 | 16 | 38 | 20 |
Стоимость перевозки по этому плану:
z=14*2 + 26*3 + 35*7 +6*1+16*3 + 3*7 + 20*3 = 486
(или z= 518 + Δ33 * 16 = 518 -2 * 16 = 486)
Проверим, является ли полученное решение оптимальным.
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u3 = 0
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | u1= |
А2 | 5 | 9 | 5 | 7 35 | 2 | u2= |
А3 | 1 6 | 4 | 3 16 | 7 3 | 3 20 | u3= |
V | v1= | v2= | v3= | v4= | v5= |
A3B1 : | v1 + u3 = 1 | v1 = 1 - 0 = 1 |
A3B3 : | v3 + u3 = 3 | v3 = 3 - 0 = 3 |
A3B4 : | v4 + u3 = 7 | v4 = 7 - 0 = 7 |
A3B5 : | v5 + u3 = 3 | v5 = 3 - 0 = 3 |
A1B1 : | v1 + u1 = 2 | u1 = 2 - 1 = 1 |
A1B2 : | v2 + u1 = 3 | v2 = 3 - 1 = 2 |
A2B4 : | v4 + u2 = 7 | u2 = 7 - 7 = 0 |
Записав эти значения в таблицу, получим:
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | u1=1 |
А2 | 5 | 9 | 5 | 7 35 | 2 | u2=0 |
А3 | 1 6 | 4 | 3 16 | 7 3 | 3 20 | u3=0 |
V | v1=1 | v2=2 | v3=3 | v4=7 | v5=3 |
Вычислим разности для свободных клеток.
A1B3 : | Δ13 = c13 - ( u1 + v3 ) = 6 - ( 1 + 3 ) = 2 |
A1B4 : | Δ14 = c14 - ( u1 + v4 ) = 8 - ( 1 + 7 ) = 0 |
A1B5 : | Δ15 = c15 - ( u1 + v5 ) = 7 - ( 1 + 3 ) = 3 |
A2B1 : | Δ21 = c21 - ( u2 + v1 ) = 5 - ( 0 + 1 ) = 4 |
A2B2 : | Δ22 = c22 - ( u2 + v2 ) = 9 - ( 0 + 2 ) = 7 |
A2B3 : | Δ23 = c23 - ( u2 + v3 ) = 5 - ( 0 + 3 ) = 2 |
A2B5 : | Δ25 = c25 - ( u2 + v5 ) = 2 - ( 0 + 3 ) = -1 |
A3B2 : | Δ32 = c32 - ( u3 + v2 ) = 4 - ( 0 + 2 ) = 2 |
Есть отрицательные оценки. Значит план не является оптимальным.
ШАГ 3.
Выбираем клетку с максимальным отрицательным значением. Это клетка A2B5.
Строим цикл, т. е. замкнутый многоугольник, соединяющий выбранную клетку с ней же самой и проходящий через заполненные клетки.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 35-20⊖ | 2 +20 ⊕ | 35 |
А3 | 1 6 | 4 | 3 16 | 7 3+20 ⊕ | 3 20-20 ⊖ | 45 |
Потребность | 20 | 26 | 16 | 38 | 20 |
Из всех клеток с отрицательными знаками (в данном случае из А2,В4; А3,В5) выбирается минимальная величина поставки, обозначаемая как D.
В те вершины, которые имеют знак “+” прибавляется поставка D, а в вершинах со знаком “–“ поставки уменьшаются на величину D.
Получили новое решение.
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 15 | 2 20 | 35 |
А3 | 1 6 | 4 | 3 16 | 7 23 | 3 | 45 |
Потребность | 20 | 26 | 16 | 38 | 20 |
Стоимость перевозки по этому плану:
z=14*2 + 26*3 + 15*7 +20*2+6*1+16*3 + 23*7 = 466
(или z= 486 + Δ25 * 20 = 486 -1 * 20 = 466)
Проверим, является ли полученное решение оптимальным.
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u3 = 0
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | u1= |
А2 | 5 | 9 | 5 | 7 15 | 2 20 | u2= |
А3 | 1 6 | 4 | 3 16 | 7 23 | 3 | u3= |
V | v1= | v2= | v3= | v4= | v5= |
A3B1 : | v1 + u3 = 1 | v1 = 1 - 0 = 1 |
A3B3 : | v3 + u3 = 3 | v3 = 3 - 0 = 3 |
A3B4 : | v4 + u3 = 7 | v4 = 7 - 0 = 7 |
A1B1 : | v1 + u1 = 2 | u1 = 2 - 1 = 1 |
A1B2 : | v2 + u1 = 3 | v2 = 3 - 1 = 2 |
A2B4 : | v4 + u2 = 7 | u2 = 7 - 7 = 0 |
A2B5 : | v5 + u2 = 2 | v5 = 2 - 0 = 2 |
Записав эти значения в таблицу, получим:
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | u1=1 |
А2 | 5 | 9 | 5 | 7 15 | 2 20 | u2=0 |
А3 | 1 6 | 4 | 3 16 | 7 23 | 3 | u3=0 |
V | v1=1 | v2=2 | v3=3 | v4=7 | v5=2 |
Вычислим разности для свободных клеток.
A1B3 : | Δ13 = c13 - ( u1 + v3 ) = 6 - ( 1 + 3 ) = 2 |
A1B4 : | Δ14 = c14 - ( u1 + v4 ) = 8 - ( 1 + 7 ) = 0 |
A1B5 : | Δ15 = c15 - ( u1 + v5 ) = 7 - ( 1 + 2 ) = 4 |
A2B1 : | Δ21 = c21 - ( u2 + v1 ) = 5 - ( 0 + 1 ) = 4 |
A2B2 : | Δ22 = c22 - ( u2 + v2 ) = 9 - ( 0 + 2 ) = 7 |
A2B3 : | Δ23 = c23 - ( u2 + v3 ) = 5 - ( 0 + 3 ) = 2 |
A3B2 : | Δ32 = c32 - ( u3 + v2 ) = 4 - ( 0 + 2 ) = 2 |
A3B5 : | Δ35 = c35 - ( u3 + v5 ) = 3 - ( 0 + 2 ) = 1 |
Нет отрицательных оценок. Следовательно, уменьшить общую стоимость доставки продукции невозможно и этот план является оптимальным.
Ответ:
Поставщик | Потребитель | Запас | ||||
B1 | B2 | B3 | B4 | B5 | ||
А1 | 2 14 | 3 26 | 6 | 8 | 7 | 40 |
А2 | 5 | 9 | 5 | 7 15 | 2 20 | 35 |
А3 | 1 6 | 4 | 3 16 | 7 23 | 3 | 45 |
Потребность | 20 | 26 | 16 | 38 | 20 |
Стоимость перевозки по этому плану:
z=14*2 + 26*3 + 15*7 +20*2+6*1+16*3 + 23*7 = 466
Дата добавления: 2020-12-22; просмотров: 69; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!