Метод потенциалов
Для определения оптимальной структуры перевозок необходимо выполнить последовательно следующие шаги.
1 шаг. Каждой строке и каждому столбцу в первоначальном решении поставить в соответствие потенциалы Ui и Vj соответственно.
2 шаг. Определить значения потенциалов. Для этого для каждой (i, j), содержащей перевозку (занятой клетки), составить уравнение Ui + Vj = Ci,j. Общее число уравнений, таким образом, равно m + n – 1. Решить полученную систему уравнений, предварительно положив U1 = 0.
3 шаг. Для клеток (i, j), не содержащих перевозку, вычислить:
Si,j = Ui + Vj – Ci,j
4 шаг. Если Si,j 0 для всех клеток, то данная структура перевозок является оптимальной, а суммарные затраты на транспортировку груза от поставщиков к потребителям минимальны. Если для какой-либо клетки (i, j) выполняется Si,j > 0 (очевидно, такая клетка может быть только свободной, т. е. не содержать поставку), то план перевозок может быть улучшен.
5 шаг. Среди всех положительных значений Si,j выбрать максимальное. В соответствующую ячейку ввести условную поставку .
6 шаг. С помощью горизонтальных и вертикальных прямых линий построить замкнутый контур, который начинается и заканчивается в ячейке с условной поставкой и проходит через занятые клетки таблицы планирования. Клетки контура пометить (+) и (-) (аналогично тому, как это было сделано в распределительном методе).
7 шаг. Определить значение условной поставки , как минимальное из значений поставок, находящихся в клетках контура с пометкой «-».
8 шаг. Пересчитать значения поставок в углах замкнутого контура с учетом найденного значения , попеременно прибавляя его к существующим поставкам (в клетках «+») и вычитая из поставок (в клетках «-»).
9 шаг. Исключить из базисного решения ячейку, в которой после корректировки поставок значение объема равно нулю (если таких клеток несколько, исключается клетка с максимальной стоимостью перевозки единицы груза).
10 шаг. Для полученного плана перевозок определить потенциалы Ui и Vj и повторить шаги 3 – 10.
11 шаг. Процесс считается завершенным, если для всех клеток Si,j 0.
Задача
Найти оптимальный план перевозок методом потенциалов по данным задачи 1, используя в качестве начального решение, рассчитанное по методу наименьшей стоимости (табл. 3.1.31).
Решение
Введем потенциалы для строк Ui и для столбцов Vj.
Таблица 3.1.31
|
|
Магазин 1 V1 |
Магазин 2 V2 |
Магазин 3 V3 |
Магазин 4 V4 |
Магазин 5 V5 |
Предложение |
|
РЦ 1 U1 |
4
|
5 |
1 25 |
3 5 |
4 |
30 |
|
РЦ 2 U2 |
2 15 |
6 |
4 |
7 5 |
5 |
20 |
|
РЦ 3 U3 |
3 |
4 10 |
2 |
5 20 |
2 20 |
50 |
|
Спрос |
15 |
10 |
25 |
30 |
20 |
|
Для определения потенциалов по занятым клеткам составим уравнения Ui + Vj = Ci,j:
U1 + V3 = 1,
U1 + V4 = 3,
U2 + V1 = 2,
U2 + V4 = 7,
U3 + V2 = 4,
U3 + V4 = 5,
U3 + V5 = 2.
Положим U1 = 0, решим систему уравнений и определим значения потенциалов. Введем значения потенциалов в матрицу планирования (табл.3.1.32).
Таблица 3.1.32
|
|
Магазин 1 V1 = – 2 |
Магазин 2 V2 = 2 |
Магазин 3 V3 = 1 |
Магазин 4 V4 = 3 |
Магазин 5 V5 = 0 |
|
РЦ 1 U1 = 0 |
4
|
5
|
1 25 |
3 5 |
4 |
|
РЦ 2 U2 = 4 |
2 15 |
6 |
4
|
7 5 |
5 |
|
РЦ 3 U3 = 2 |
3
|
4 10 |
2 |
5 20 |
2 20 |
Используя вычисленные значения потенциалов, определим значения Si,j для свободных клеток. Результаты расчетов приведены в таблице 3.1.33.
Таблица 3.1.33
|
Свободная клетка |
Значение Si,j = Ui + Vj – Ci,j |
|
(1,1) |
S1,1 = U1 + V1 – C1,1 = 0 – 2 – 4 = – 6 |
|
(1,2) |
S1,2 = U1 + V2 – C1,2 = 0 + 2 – 5 = – 3 |
|
(1,5) |
S1,5 = U1 + V5 – C1,5 = 0 + 0 – 4 = – 4 |
|
(2,2) |
S2,2 = U2 + V2 – C2,2 = 4 + 2 – 6 = 0 |
|
(2,3) |
S2,3 = U2 + V3 – C2,3 = 4 + 1 – 4 = 1 |
|
(2,5) |
S2,5 = U2 + V5 – C2,5 = 4 + 0 – 5 = – 1 |
|
(3,1) |
S3,1 = U3 + V1 – C3,1 = 2 – 2 – 3 = – 3 |
|
(3,3) |
S3,3 = U3 + V3 – C3,3 = 2 + 1 – 2 = 1 |
Наибольшее значение Si,j, равное 1, соответствует ячейкам (2,3) и (3,3). Стоимости перевозки единицы груза в этих ячейках равны 4 и 2 соответственно. Введем условную поставку в ячейку (3,3). Такой выбор объясняется тем, что ячейке (3,3) соответствует меньшее, чем ячейке (2,3), стоимость перевозки единицы груза.
Построим замкнутый контур, проходящий через занятые клетки (табл. 3.1.34). Пометим клетки контура: клетке (3,3) дадим пометку (+), последующим клеткам, обходя контур против часовой стрелки, будем давать попеременно пометки (-) и (+). В клетки контура, помеченные знаком (+), добавим поставку , а из поставок в клетках, помеченных знаком (-), вычтем .
Таблица 3.1.34
|
|
Магазин1 |
Магазин 2 |
Магазин 3 |
Магазин 4 |
Магазин5 |
|
РЦ1 |
4
|
5
|
1 25 - (-) |
3 5 + (+) |
4 |
|
РЦ2 |
2 15 |
6 |
4
|
7 5 |
5 |
|
РЦ3 |
3
|
4 10 |
2 + (+) |
5 20 - (-) |
2 20 |
Вычислим значение условной поставки . Для этого выберем минимальное значение поставки среди ячеек, помеченных знаком (-):
= min(25, 20) = 20.
Откорректируем значения объемов перевозок в соответствии с вводимой в базисное решение поставкой (табл. 3.1.35). Ячейку (3,4) выведем из базисного решения, так как ее значение (поставка в ней) с учетом корректировки обращается в нуль.
Таблица 3.1.35
|
|
Магазин1 |
Магазин 2 |
Магазин 3 |
Магазин 4 |
Магазин5 |
|
РЦ1 |
4
|
5
|
1 5 |
3 25 |
4 |
|
РЦ2 |
2 15 |
6 |
4
|
7 5 |
5 |
|
РЦ3 |
3
|
4 10 |
2 20 |
5
|
2 20 |
Определим суммарные затраты на транспортировку 100 тонн груза от распределительных центров к потребителям.
Z = 5*1 + 25*3 + 15*2 + 5*7 + 10*4 + 20*2 + 20*2 = 265 у.е.
Полученный план перевозок позволяет на 20 у.е. (285 – 265) сократить затраты на транспортировку.
Проверку оптимальности полученного решения начнем с расчета потенциалы Ui и Vj по занятым клеткам, положив U1 = 0.
U1 + V3 = 1,
U1 + V4 = 3,
U2 + V1 = 2,
U2 + V4 = 7,
U3 + V2 = 4,
U3 + V3 = 2,
U3 + V5 = 2.
Решим систему уравнений и определим значения потенциалов. Введем значения потенциалов в матрицу планирования (табл.3.1.36).
Таблица 3.1.36
|
|
Магазин 1 V1 = – 2 |
Магазин 2 V2 = 3 |
Магазин 3 V3 = 1 |
Магазин 4 V4 = 3 |
Магазин 5 V5 = 1 |
|
РЦ 1 U1 = 0 |
4
|
5
|
1 5 |
3 25 |
4 |
|
РЦ 2 U2 = 4 |
2 15 |
6 |
4
|
7 5 |
5 |
|
РЦ 3 U3 = 1 |
3
|
4 10 |
2 20 |
5
|
2 20 |
Проверим оптимальность плана перевозок. Для этого определим значения Si,j для свободных клеток. Результаты расчетов приведены в табл. 3.1.37.
Таблица 3.1.37
|
Свободная клетка |
Значение Si,j = Ui + Vj – Ci,j |
|
(1,1) |
S1,1 = U1 + V1 – C1,1 = 0 – 2 – 4 = – 6 |
|
(1,2) |
S1,2 = U1 + V2 – C1,2 = 0 + 3 – 5 = – 2 |
|
(1,5) |
S1,5 = U1 + V5 – C1,5 = 0 + 1 – 4 = – 3 |
|
(2,2) |
S2,2 = U2 + V2 – C2,2 = 4 + 3 – 6 = 1 |
|
(2,3) |
S2,4 = U2 + V4 – C2,4 = 4 + 1 – 4 = 1 |
|
(2,5) |
S2,5 = U2 + V5 – C2,5 = 4 + 1 – 5 = 0 |
|
(3,1) |
S3,1 = U3 + V1 – C3,1 = 1 – 2 – 3 = – 4 |
|
(3,4) |
S3,3 = U3 + V4 – C3,4 = 1 + 3 – 5 = – 1 |
Наибольшее значение Si,j, равное 1, соответствует ячейкам (2,2) и (2,3). Стоимости перевозки единицы груза в этих ячейках равны 6 и 4 соответственно. Введем условную поставку в ячейку (2,3), так как ей соответствует меньшее, чем ячейке (2,2), стоимость перевозки единицы груза.
Построим замкнутый контур, проходящий через занятые клетки (табл. 3.1.38). Пометим клетки контура: клетке (2,3) дадим пометку (+), последующим клеткам, обходя контур против часовой стрелки, будем давать попеременно пометки (-) и (+). В клетки контура, помеченные знаком (+), добавим поставку , а из поставок в клетках, помеченных знаком (-), вычтем .
Таблица 3.1.38
|
|
Магазин1 |
Магазин 2 |
Магазин 3 |
Магазин 4 |
Магазин5 |
|
РЦ1 |
4
|
5
|
1 5 - (-) |
3 25 + (+) |
4 |
|
РЦ2 |
2 15 |
6 |
4 + (+) |
7 5 - (-) |
5 |
|
РЦ3 |
3
|
4 10 |
2 20 |
5
|
2 20 |
Вычислим значение условной поставки . Для этого выберем минимальное значение поставки среди ячеек, помеченных знаком (-):
= min(5, 5) = 5.
Откорректируем значения объемов перевозок в соответствии с вводимой в базисное решение поставкой (табл. 3.1.39). Две ячейки (1,3) и (2,4) получают нулевую перевозку.
Одна из клеток (1,3) или (2,4) должна быть удалена из плана перевозок. В качестве исключаемой можно выберем ячейку (2,4), так как ей соответствует большая стоимость перевозки единицы груза (7 против 1 для ячейки (1,3)).
Выберем в качестве исключаемой переменной (3,4).
Таблица 3.1.39
|
|
Магазин1 |
Магазин 2 |
Магазин 3 |
Магазин 4 |
Магазин5 |
|
РЦ1 |
4
|
5
|
1 0 |
3 30 |
4 |
|
РЦ2 |
2 15 |
6 |
4 5 |
7
|
5 |
|
РЦ3 |
3
|
4 10 |
2 20 |
5
|
2 20 |
Определим суммарные затраты на транспортировку ста тонн груза.
Z = 30*3 + 15*2 + 5*4 + 10*4 + 20*2 +20*2 = 260 у.е.
Суммарная стоимость при новом плане перевозок сокращается на 5 у.е. (265 – 260).
Определим, является ли полученный план оптимальным. Рассчитаем потенциалы из системы уравнений
U1 = 0.
U1 + V3 = 1,
U1 + V4 = 3,
U2 + V1 = 2,
U2 + V3 = 4,
U3 + V2 = 4,
U3 + V3 = 2,
U3 + V5 = 2.
Введем значения потенциалов в матрицу планирования (табл.3.1.40).
Таблица 3.1.36
|
|
Магазин 1 V1 = – 1 |
Магазин 2 V2 = 3 |
Магазин 3 V3 = 1 |
Магазин 4 V4 = 3 |
Магазин 5 V5 = 1 |
|
РЦ 1 U1 = 0 |
4
|
5
|
1 0 |
3 30 |
4 |
|
РЦ 2 U2 = 3 |
2 15 |
6 |
4 5 |
7
|
5 |
|
РЦ 3 U3 = 1 |
3
|
4 10 |
2 20 |
5
|
2 20 |
Проверим оптимальность плана перевозок. Для этого определим значения Si,j для свободных клеток. Результаты расчетов приведены в табл. 3.1.41.
Таблица 3.1.41
|
Свободная клетка |
Значение Si,j = Ui + Vj – Ci,j |
|
(1,1) |
S1,1 =U1 + V1 – C1,1 = 0 – 1 – 4 = – 5 |
|
(1,2) |
S1,2 =U1 + V2 – C1,2 = 0 + 3 – 5 = – 2 |
|
(1,5) |
S1,5 =U1 + V5 – C15 = 0 + 1 – 4 = – 3 |
|
(2,2) |
S2,2 =U2 + V2 – C2,2 = 3 + 3 – 6 = 0 |
|
(2,4) |
S2,4 =U2 + V4 – C2,4 = 3 + 3 – 7 = – 1 |
|
(2,5) |
S2,5 =U2 + V5 – C2,5 = 3 + 1 – 5 = –1 |
|
(3,1) |
S3,1 =U3 + V1 – C3,1 = 1 – 1 – 3 = – 3 |
|
(3,4) |
S3,4 =U3 + V4 – C3,4 = 1 + 3 – 5 = – 1 |
Так как Si,j 0 для всех свободных клеток, то построенный план перевозок (табл. 3.1.39) является оптимальным. Суммарные затраты на транспортировку 100 тонн груза от трех распределительных центров к пяти магазинам при таком плане перевозок минимальны и равны 260 у.е.
Таким образом, полученные разными способами решения приводят к одинаковому результату – минимальные затраты на перевозку 100 т. груза от трех распределительных центров к пяти магазинам равны 260 у.е