Распределительный метод

Распределительный метод, как уже отмечалось, применяется для нахождения оптимального решения транспортной задачи, для которой ранее найдено первоначальное решение (опорный план перевозок с числом занятых клеток m + n – 1). Этот метод основан на последовательном рассмотрении пустых ячеек первоначального решения и возможном введении в них поставок.

Порядок действий опишем в виде алгоритма.

1 шаг. Выбирается любая пустая ячейка в опорном плане перевозок.

2 шаг. С помощью горизонтальных и вертикальных линий строится замкнутый контур, исходящий из выбранной ячейки, проходящий через ячейки-клетки, содержащие поставки, и завершающийся в выбранной ячейке. При этом любая из клеток контура имеет ровно одного соседа-клетку контура в своей строке и ровно одного соседа-клетку контура в своем столбце (в любой клетке контура сходятся горизонтальная и вертикальная линии). Такой замкнутый контур всегда можно построить (и притом только один!) с началом в любой выбранной пустой ячейке.

3 шаг. Обозначить угол полученной замкнутой ломаной линии (контура) в свободной клетке знаком (+), а последующие углы попеременно знаками (-) и (+).

4 шаг. Определить алгебраическую сумму стоимостей поставок для ячеек, через которые проведен контур, с учетом знаков, которыми они помечены.

5 шаг. Если полученная сумма положительна или равна нулю, то выбирают следующую ячейку и повторяют шаги 2–4.

6 шаг. Если полученная сумма меньше нуля, то в пустую ячейку вводят поставку, равную минимальному из значений поставок, находящихся в ячейках, обозначенных знаком (-).

7 шаг. В других углах построенного контура поставки пересчитываются следующим образом: для ячеек, обозначенных знаком (+), размер вводимой в пустую ячейку поставки прибавляется к имеющимся в них базовым поставкам; для ячеек, обозначенных знаком (-), вводимая поставка вычитается из соответствующих базовых поставок. В результате пересчета (перераспределения груза), по крайней мере, одна из клеток, помеченная знаком (-), получит нулевую перевозку (поставку). Эту клетку следует вывести из системы поставок (из плана перевозок). Если клеток, получивших в результате пересчета нулевую перевозку, несколько, из системы поставок выводят одну – ту, которой соответствует максимальное значение стоимости перевозки единицы груза.

8 шаг. В результате выполнения шагов 6 и 7 получена новая система поставок – новый опорный план перевозок, в котором число занятых клеток опять m + n – 1. Для этого плана определяются суммарные затраты на транспортировку груза.

9 шаг. Выбирается следующая пустая ячейка в первоначальном решении и повторяются шаги 2–8.

10 шаг. Процесс считается завершенным, когда полученные на шаге 4 суммы для всех свободных ячеек будут положительными.

Задача

Найти оптимальный план перевозок распределительным методом по данным задачи 1, используя в качестве начального решение, рассчитанное по методу наименьшей стоимости (табл. 3.1.18).

Таблица 3.1.18

Решение

Выберем ячейку (1,1) и построим замкнутый контур, проходящий через ячейки, содержащие поставки первоначального решения (табл. 3.1.19). Началом контура будет ячейка (1,1). При построении контура в него сначала пытаются включить ячейку, наиболее удаленную от выбранной. Если так контур построить не удается, то для включения в контур рассматривается занятая ячейка с меньшей «степенью дальности» от выбранной и т.д.

Выберем направление обхода против часовой стрелки, поэтому следующую ячейку будем искать в первом столбце. Наиболее удаленной занятой клеткой от ячейки (1,1) является клетка (2,1). Далее контур следует продолжить в горизонтальном направлении, то есть по строке 2. В этой строке найдем наиболее далекую ячейку, содержащую поставку. Это будет ячейка (2,4). Следующую ячейку находим снова по столбцу – (1,4). Из этой ячейки по горизонтали уже можно замкнуть контур, вернувшись в исходную ячейку (1,1). Обозначим угол прямоугольника в свободной клетке знаком (+), а последующие – попеременно знаками (-) и (+).

Таблица 3.1.19

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1	(+)			5 (-)
РЦ 2	15 (-)			5 (+)
РЦ 3
Спрос

Алгебраическая сумма стоимостей транспортировки груза с учетом знаков:

D_1,1 = 4 – 2 + 7 – 3 = 6 > 0

Алгебраическая сумма положительна, следовательно нельзя вводить условную поставку в ячейку (1,1), так как суммарные затраты на поставку груза возрастут.

Испытаем свободную клетку (1,2). Построим замкнутый контур (табл. 3.1.20) и определим алгебраическую сумму стоимостей.

Таблица 3.1.20

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1		5 (+)		5 (-)
РЦ 2
РЦ 3		10 (-)		20 (+)
Спрос

Алгебраическая сумма стоимостей транспортировки единицы груза с учетом знаков:

D_1,2 = 5 - 4 + 5 – 3 = 3 > 0

Рассмотрим ячейку (1,5). Построим замкнутый контур и определим алгебраическую сумму расстояний (табл. 3.1.21). В данном случае для примера выбрано другое направление построения контура.

Алгебраическая сумма стоимостей транспортировки единицы тонны груза с учетом знаков будет равна:

D_1,5 = 4 – 2 + 5 – 3 = 4 > 0

Таблица 3.1.21

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
(РЦ 1)				5 (-)	(+)
(РЦ 2)
(РЦ 3)				20 (+)	20 (-)
Спрос

Выберем ячейку (2,2) и построим замкнутый контур (табл. 3.1.22) и определим алгебраическую сумму стоимостей.

Таблица 3.1.22

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1
РЦ 2		6 (+)		5 (-)
РЦ 3		10 (-)		20 (+)
Спрос

Алгебраическая сумма стоимостей транспортировки единицы груза с учетом знаков:

D_2,2 = 6 - 4 + 5 – 7 = 0

Так как алгебраическая сумма равна нулю, то перераспределение поставок не изменит значение суммарных затрат на транспортировку 100 тонн груза от распределительных центров в магазины.

Введем условную поставку в ячейку (2,3). Построим замкнутый контур (табл. 3.1.23) и определим алгебраическую сумму стоимостей.

Таблица 3.1.23

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1			1 25 (-)	3 5 (+)
РЦ 2			4 (+)	5 (-)
РЦ 3
Спрос

Алгебраическая сумма стоимостей транспортировки единицы груза с учетом знаков:

D_2,3 = 4 – 7 + 3 – 1 = – 1 < 0

Полученный результат говорит о том, что на данном шаге имеющаяся структура поставок может быть улучшена.

Минимальная поставка в углах прямоугольника со знаком (-) равна 5. Введем в ячейку (2,3) поставку х_2,3 = 5 и произведем перерасчет объемов поставок (табл.3.1.24) в зависимости от знака. Получим новую матрицу поставок (табл. 3.1.25).

Таблица 3.1.24

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1			1 25 - 5	5 + 5
РЦ 2			+ 5	5 - 5
РЦ 3
Спрос

Таблица 3.1.25

Рассчитаем суммарные затраты на транспортировку 100 тонн груза:

Z = 20 * 1 + 10 * 3 + 15 * 2 + 5 * 4 + 10 * 4 + 20 * 5 + 20 * 2 = 280 у.е.

Испытаем свободную клетку (2,5). Построим замкнутый контур (табл. 3.1.26) и определим алгебраическую сумму стоимостей.

Таблица 3.1.26

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1			1 20 (+)	3 10 (-)
РЦ 2			4 5(-)		5 (+)
РЦ 3				5 20 (+)	20 (-)
Спрос

Алгебраическая сумма стоимостей транспортировки тонны груза с учетом знаков:

D_2,5 = 5 – 2 + 5 – 3 + 1 – 4 = 2 > 0

Выберем ячейку (3,1), построим замкнутый контур (табл. 3.1.27) и определим алгебраическую сумму стоимостей.

Таблица 3.1.27

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1			1 20 (-)	3 10 (+)
РЦ 2	2 15(-)		5(+)
РЦ 3	(+)			20 (-)
Спрос

Алгебраическая сумма стоимостей транспортировки тонны груза с учетом знаков:

D_3,1 = 3 - 5 + 3 - 1 + 4 – 2 = 2 > 0

Рассмотрим последнюю пустую ячейку (3,3). Построим замкнутый контур (табл. 3.1.28) и определим алгебраическую сумму стоимостей.

Таблица 3.1.28

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1			1 20 (-)	3 10 (+)
РЦ 2
РЦ 3			2 (+)	20 (-)
Спрос

Алгебраическая сумма стоимостей транспортировки тонны груза с учетом знаков будет равна:

D_3,3 = 2 – 5 + 3 – 1 = - 1 < 0

Минимальная поставка в углах прямоугольника с отрицательным знаком равна 20. Введем в ячейку (3,3) поставку, равную 20, и произведем перерасчет объемов поставок в зависимости от знака (табл.3.1.29). В итоге получим новую матрицу поставок (табл. 3.1.30).

Таблица 3.1.29

	Магазин 1	Магазин 2	Магазин 3	Магазин 4	Магазин 5	Предложение
РЦ 1			1 20 - 20	3 10 + 20
РЦ 2
РЦ 3			2 + 20	20 - 20
Спрос

Так как количество поставок в базисном решении должно быть равно 7 (количество строк плюс количество столбцов минус один), то уберем одну любую ячейку с нулевой перевозкой.

Таблица 3.1.30

Суммарные затраты на транспортировку 100 тонн груза будут равны 260 у.е.:

Z = 30*3 + 15*2 + 5*4 + 10*4 + 20*2 + 20*2 = 260 у.е.

Структура перевозок, определяемая табл. 3.1.30, является оптимальной, так как алгебраическая сумма стоимостей транспортировки единицы груза для всех свободных ячеек положительна. Минимальные суммарные затраты на транспортировку 100 тонн груза от распределительных центров в магазины равны 260 у.е.

Метод потенциалов

Для определения оптимальной структуры перевозок необходимо выполнить последовательно следующие шаги.

1 шаг. Каждой строке и каждому столбцу в первоначальном решении поставить в соответствие потенциалы U_i и V_j соответственно.

2 шаг. Определить значения потенциалов. Для этого для каждой (i, j), содержащей перевозку (занятой клетки), составить уравнение U_i + V_j = C_i,j. Общее число уравнений, таким образом, равно m + n – 1. Решить полученную систему уравнений, предварительно положив U₁ = 0.

3 шаг. Для клеток (i, j), не содержащих перевозку, вычислить:

S_i,j = U_i + V_j – C_i,j

4 шаг. Если S_i,j£ 0 для всех клеток, то данная структура перевозок является оптимальной, а суммарные затраты на транспортировку груза от поставщиков к потребителям минимальны. Если для какой-либо клетки (i, j) выполняется S_i,j > 0 (очевидно, такая клетка может быть только свободной, т. е. не содержать поставку), то план перевозок может быть улучшен.

5 шаг. Среди всех положительных значений S_i,j выбрать максимальное. В соответствующую ячейку ввести условную поставку q.

6 шаг. С помощью горизонтальных и вертикальных прямых линий построить замкнутый контур, который начинается и заканчивается в ячейке с условной поставкой и проходит через занятые клетки таблицы планирования. Клетки контура пометить (+) и (-) (аналогично тому, как это было сделано в распределительном методе).

7 шаг. Определить значение условной поставки q, как минимальное из значений поставок, находящихся в клетках контура с пометкой «-».

8 шаг. Пересчитать значения поставок в углах замкнутого контура с учетом найденного значения q, попеременно прибавляя его к существующим поставкам (в клетках «+») и вычитая из поставок (в клетках «-»).

9 шаг. Исключить из базисного решения ячейку, в которой после корректировки поставок значение объема равно нулю (если таких клеток несколько, исключается клетка с максимальной стоимостью перевозки единицы груза).

10 шаг. Для полученного плана перевозок определить потенциалы U_i и V_j и повторить шаги 3 – 10.

11 шаг. Процесс считается завершенным, если для всех клеток S_i,j£ 0.

Задача

Найти оптимальный план перевозок методом потенциалов по данным задачи 1, используя в качестве начального решение, рассчитанное по методу наименьшей стоимости (табл. 3.1.31).

Решение

Введем потенциалы для строк U_i и для столбцов V_j.

Таблица 3.1.31

Для определения потенциалов по занятым клеткам составим уравнения U_i + V_j = C_i,j:

U₁ + V₃ = 1,

U₁ + V₄ = 3,

U₂ + V₁ = 2,

U₂ + V₄ = 7,

U₃ + V₂ = 4,

U₃ + V₄ = 5,

U₃ + V₅ = 2.

Положим U₁ = 0, решим систему уравнений и определим значения потенциалов. Введем значения потенциалов в матрицу планирования (табл.3.1.32).

Таблица 3.1.32

Используя вычисленные значения потенциалов, определим значения S_i,j для свободных клеток. Результаты расчетов приведены в таблице 3.1.33.

Таблица 3.1.33

Наибольшее значение S_i,j, равное 1, соответствует ячейкам (2,3) и (3,3). Стоимости перевозки единицы груза в этих ячейках равны 4 и 2 соответственно. Введем условную поставку q в ячейку (3,3). Такой выбор объясняется тем, что ячейке (3,3) соответствует меньшее, чем ячейке (2,3), стоимость перевозки единицы груза.

Построим замкнутый контур, проходящий через занятые клетки (табл. 3.1.34). Пометим клетки контура: клетке (3,3) дадим пометку (+), последующим клеткам, обходя контур против часовой стрелки, будем давать попеременно пометки (-) и (+). В клетки контура, помеченные знаком (+), добавим поставку q, а из поставок в клетках, помеченных знаком (-), вычтем q.

Таблица 3.1.34

	Магазин1	Магазин 2	Магазин 3	Магазин 4	Магазин5
РЦ1			1 25 - q(-)	5 + q(+)
РЦ2
РЦ3			+ q(+)	20 - q(-)

Вычислим значение условной поставки q. Для этого выберем минимальное значение поставки среди ячеек, помеченных знаком (-):

q = min(25, 20) = 20.

Откорректируем значения объемов перевозок в соответствии с вводимой в базисное решение поставкой (табл. 3.1.35). Ячейку (3,4) выведем из базисного решения, так как ее значение (поставка в ней) с учетом корректировки обращается в нуль.

Таблица 3.1.35

Определим суммарные затраты на транспортировку 100 тонн груза от распределительных центров к потребителям.

Z = 5*1 + 25*3 + 15*2 + 5*7 + 10*4 + 20*2 + 20*2 = 265 у.е.

Полученный план перевозок позволяет на 20 у.е. (285 – 265) сократить затраты на транспортировку.

Проверку оптимальности полученного решения начнем с расчета потенциалы U_i и V_j по занятым клеткам, положив U₁ = 0.

U₁ + V₃ = 1,

U₁ + V₄ = 3,

U₂ + V₁ = 2,

U₂ + V₄ = 7,

U₃ + V₂ = 4,

U₃ + V₃ = 2,

U₃ + V₅ = 2.

Решим систему уравнений и определим значения потенциалов. Введем значения потенциалов в матрицу планирования (табл.3.1.36).

Таблица 3.1.36

Проверим оптимальность плана перевозок. Для этого определим значения S_i,j для свободных клеток. Результаты расчетов приведены в табл. 3.1.37.

Таблица 3.1.37

Наибольшее значение S_i,j, равное 1, соответствует ячейкам (2,2) и (2,3). Стоимости перевозки единицы груза в этих ячейках равны 6 и 4 соответственно. Введем условную поставку q в ячейку (2,3), так как ей соответствует меньшее, чем ячейке (2,2), стоимость перевозки единицы груза.

Построим замкнутый контур, проходящий через занятые клетки (табл. 3.1.38). Пометим клетки контура: клетке (2,3) дадим пометку (+), последующим клеткам, обходя контур против часовой стрелки, будем давать попеременно пометки (-) и (+). В клетки контура, помеченные знаком (+), добавим поставку q, а из поставок в клетках, помеченных знаком (-), вычтем q.

Таблица 3.1.38

	Магазин1	Магазин 2	Магазин 3	Магазин 4	Магазин5
РЦ1			1 5 - q(-)	25 + q(+)
РЦ2			+ q(+)	5 - q(-)
РЦ3

Вычислим значение условной поставки q. Для этого выберем минимальное значение поставки среди ячеек, помеченных знаком (-):

q = 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

Определим суммарные затраты на транспортировку ста тонн груза.

Z = 30*3 + 15*2 + 5*4 + 10*4 + 20*2 +20*2 = 260 у.е.

Суммарная стоимость при новом плане перевозок сокращается на 5 у.е. (265 – 260).

Определим, является ли полученный план оптимальным. Рассчитаем потенциалы из системы уравнений

U₁ = 0.

U₁ + V₃ = 1,

U₁ + V₄ = 3,

U₂ + V₁ = 2,

U₂ + V₃ = 4,

U₃ + V₂ = 4,

U₃ + V₃ = 2,

U₃ + V₅ = 2.

Введем значения потенциалов в матрицу планирования (табл.3.1.40).

Таблица 3.1.36

Проверим оптимальность плана перевозок. Для этого определим значения S_i,j для свободных клеток. Результаты расчетов приведены в табл. 3.1.41.

Таблица 3.1.41

Так как S_i,j £ 0 для всех свободных клеток, то построенный план перевозок (табл. 3.1.39) является оптимальным. Суммарные затраты на транспортировку 100 тонн груза от трех распределительных центров к пяти магазинам при таком плане перевозок минимальны и равны 260 у.е.

Таким образом, полученные разными способами решения приводят к одинаковому результату – минимальные затраты на перевозку 100 т. груза от трех распределительных центров к пяти магазинам равны 260 у.е

Не нашли, что искали? Воспользуйтесь поиском: