Метод наименьшей стоимости
Алгоритм получения начального базисного решения
1 шаг. В матрице выбирается ячейка с наименьшей стоимостью поставки единицы груза. В случае если несколько ячеек имеют минимальное значение, то выбирается любая.
2 шаг. В выбранную ячейку вводится максимально возможная условная поставка (поставка, полностью реализующая предложение или спрос).
3 шаг. Вычеркивается соответствующая строка или столбец с реализованным спросом или предложением в соответствии заданными ограничениями. Если в выбранной ячейке (i,j) спрос равен предложению, то вычеркивается на выбор строка или столбец.
4 шаг. В оставшейся матрице выбирают ячейку с наименьшей стоимостью поставки единицы груза и повторяют шаги 2-4.
5 шаг. В случае полной реализации спроса и предложения процесс останавливают.
В качестве примера рассмотрим решение приведенной выше задачи №1 методом наименьшей стоимости. В матрице выберем ячейку (1,3) с наименьшей стоимостью поставки единицы (тонны) груза и введем условную поставку 25 т, удовлетворив тем самым спрос Магазина 3 (табл. 3.1.6). Третий столбец из дальнейшего рассмотрения вычеркиваем.
Таблица 3.1.6
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 |  25 | 30 (25) | ||||
| РЦ 2 | ||||||
| РЦ 3 | ||||||
| Спрос | 25 (25) |
В оставшейся матрице ячейки (2,1), (3,5) имеют минимальную стоимость поставки единицы (тонны) груза. Выберем ячейку (3,5) и введем условную поставку, равную 20 т (табл. 3.1.7) и полностью удовлетворяющую спрос пятого магазина. Пятый столбец из дальнейшего рассмотрения вычеркиваем.
Таблица 3.1.7
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 |  1 |  4 | 30 (25) | |||
| РЦ 2 | ||||||
| РЦ 3 | 50 (20) | |||||
| Спрос | 25 (25) | 20 (20) |
Введем в ячейку (2,1), условную поставку 15 т (табл. 3.1.8), полностью реализовав спрос первого магазина. Первый столбец из дальнейшего рассмотрения вычеркиваем.
Таблица 3.1.8
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 |  |  25 | 4 | 30 (25) | ||
| РЦ 2 | 20 (15) | |||||
| РЦ 3 | 50 (20) | |||||
| Спрос | 15 (15) | 25 (25) | 20 (20) |
Введем в ячейку (1,4) условную поставку 5 т (табл. 3.1.9), полностью реализующую предложение первого распределительного центра. Первую строку из дальнего рассмотрения вычеркиваем.
Таблица 3.1.9
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 |  4  | 25 |  4 | 30 (30) | ||
| РЦ 2 | 20 (15) | |||||
| РЦ 3 | 50 (20) | |||||
| Спрос | 15 (15) | 25 (25) | 30 (5) | 20 (20) |
В ячейку (3,2) с наименьшей стоимостью поставки единицы (тонны) груза введем условную поставку 10 т (табл. 3.1.10), полностью удовлетворяющую потребность второго магазина в товаре. Второй столбец из дальнейшего рассмотрения вычеркиваем.
Таблица 3.1.10
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 |  4 | 5 | 25 | 4 | 30 (30) | |
| РЦ 2 | 20 (15) | |||||
| РЦ 3 | 50 (30) | |||||
| Спрос | 15 (15) | 10 (10) | 25 (25) | 30 (5) | 20 (20) |
В оставшиеся ячейки четвертого столбца (табл. 3.1.11) введем соответствующие поставки, удовлетворяющие спрос и реализующие предложения.
Таблица 3.1.11
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 | 30 (30) | |||||
| РЦ 2 | 20 (20) | |||||
| РЦ 3 | 50 (50) | |||||
| Спрос | 15 (15) | 10 (10) | 25 (25) | 30 (30) | 20 (20) |
Количество поставок в базисном решении равно 7, что соответствует числу независимых ограничений (m + n – 1).
Суммарные затраты на транспортировку 100 т. товаров от трех распределительных центров в пять сетевых магазинов для определения первоначального решения по методу наименьшей стоимости:
Z = 25*1 + 5*3 + 15*2 + 5*7 + 10*4 + 20*5 + 20*2 = 285 у.е.
Метод Фогеля
Рассмотрим шаги получения начального решения задачи методом Фогеля.
1 шаг. Рассчитать для каждой строки и каждого столбца штрафы (разность между двумя наименьшими значениями стоимости транспортировки единицы груза).
2 шаг. Выбрать строку или столбец с наибольшим штрафом. В случае если таких столбцов или строк несколько, то выбирается любая строка или столбец. В случае если максимальный штраф имеется и в столбце и в строке, то суммируются штрафы по строкам и столбцам. Выбирается максимальное число из суммы штрафов по строкам и столбцам. В соответствующих строках или столбцах выбирается максимальное число.
3 шаг. В соответствующей строке или столбце выбрать ячейку с наименьшей стоимостью перевозки единицы груза.
4 шаг. В выбранную ячейку вводится максимальная условная поставка, удовлетворяющая ограничению по спросу и предложению.
5 шаг. Соответствующая строка или столбец вычеркивается. Если значение спроса для ячейки (i.j) равно предложению, то вычеркивается строка или столбец на выбор.
6 шаг. В оставшейся матрице для каждой строки и столбца повторяются шаги 1–5.
7 шаг. Процесс считается завершенным, когда реализовано всё предложение и полностью удовлетворён спрос.
В качестве примера рассмотрим задачу №1. В матрице рассчитаем штрафы как разницу между двумя минимальными стоимостями поставки единицы груза для соответствующей строки или столбца (табл. 3.1.12).
Таблица 3.1.12
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Штраф | Предложение | |
| РЦ 1 | 3 – 1 = 2 | ||||||
| РЦ 2 | 4 – 2 = 2 | ||||||
| РЦ 3 | 2 – 2 = 0 | ||||||
| Штраф | 3 – 2 = 1 | 5 – 4 = 1 | 2 – 1 = 1 | 5 – 3 = 2 | 4 – 2 = 2 | ||
| Спрос |
Максимальный штраф равен двум и соответствует как строкам, так и столбцам. Рассчитаем сумму штрафов по строкам и столбцам.
Сумма штрафов по строкам: 2 + 2 + 0 = 4
Сумма штрафов по столбцам: 1 + 1 + 1 + 2 + 2 = 7
Максимальная сумма штрафов – по столбцам. Следовательно, из четвертого и пятого столбцов выбираем ячейку с наименьшей стоимостью транспортировки единицы груза – ячейку (3,5).
Таблица 3.1.13
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Штраф | Штраф | Предложение | |
| РЦ 1 |  4 | 3 – 1 = 2 | 3 – 1 = 2 | |||||
| РЦ 2 | 4 – 2 = 2 | 4 – 2 = 2 | ||||||
| РЦ 3 | 2 – 2 = 0 | 3 – 2 = 1 | 50 (20) | |||||
| Штраф | 3 – 2 = 1 | 5 – 4 = 1 | 2 – 1 = 1 | 5 – 3 = 2 | 4 – 2 = 2 | |||
| Спрос | 20 (20) |
В данную ячейку введем поставку, полностью удовлетворяющую спрос и пересчитаем штрафы для строк. Пятый столбец из дальнейшего рассмотрения вычеркнем (табл. 3.1.13).
Максимальный штраф также находится и в строках, и в столбце.
Сумма штрафов по строкам: 2 + 2 + 1 = 5
Сумма штрафов по столбцам: 1 + 1 + 1 + 2 = 5
Так как сумма штрафов по строкам и столбцам одинакова, то найдем на пересечении строк и столбцов с максимальным штрафом ячейку с минимальной стоимостью транспортировки единицы тонн груза. В данную ячейку введем поставку, удовлетворяющую спрос и предложение (табл. 3.1.14). Вычеркнем из дальнейшего рассмотрения первую строку и произведем расчет штрафов для полученной матрицы.
Таблица 3.1.14
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Штраф | Штраф | Предложение | |
| РЦ 1 |  4 |  4 | 3 – 1 = 2 | 3 – 1 = 2 | 30 (30) | |||
| РЦ 2 | 4 – 2 = 2 | 4 – 2 = 2 | ||||||
| РЦ 3 | 2 – 2 = 0 | 3 – 2 = 1 | 50 (20) | |||||
| Штраф | 3 – 2 = 1 | 5 – 4 = 1 | 2 – 1 = 1 | 5 – 3 = 2 | 4 – 2 = 2 | |||
| Штраф | 3 – 2 = 1 | 6 – 4 = 2 | 4 – 2 = 2 | 7 – 5 = 2 | ||||
| Спрос | 30 (30) | 20 (20) |
Сумма штрафов по строкам: 2 + 1 = 3
Сумма штрафов по столбцам: 1 + 2 + 2 + 2 = 7
Таблица 3.1.15
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Штраф | Штраф | Штраф | Предложение | |
| РЦ 1 |  4 |  1 | 4 | 3 – 1 = 2 | 3 – 1 = 2 | 30 (30) | |||
| РЦ 2 | 4 – 2 = 2 | 4 – 2 = 2 | 6 – 2 = 4 | ||||||
| РЦ 3 | 2 – 2 = 0 | 3 – 2 = 1 | 4 – 3 = 1 | 50 (45) | |||||
| Штраф | 3 – 2 = 1 | 5 – 4 = 1 | 2 – 1 = 1 | 5 – 3 = 2 | 4 – 2 = 2 | ||||
| Штраф | 3 – 2 = 1 | 6 – 4 = 2 | 4 – 2 = 2 | 7 – 5 = 2 | |||||
| Штраф | 3 – 2 = 1 | 6 – 4 = 2 | |||||||
| Спрос | 25 (25) | 30 (30) | 20 (20) |
Максимальная сумма штрафов – по столбцам, следовательно, выберем в столбцах два и три ячейку с наименьшей стоимостью транспортировки единицы груза.
В данную ячейку введем поставку, полностью удовлетворяющую спрос (табл. 3.1.15), и пересчитаем штрафы для строк. Третий столбец из дальнейшего рассмотрения вычеркнем.
Максимальный штраф находится во второй строке. В ячейку (2,1) с минимальной стоимостью транспортировки единицы груза введем поставку, полностью удовлетворяющую спрос первого магазина в товаре (табл. 3.1.16).
Таблица 3.1.16
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Штраф | Штраф | Штраф | Предложение | |
| РЦ 1 |  4  |  |  4 | 3 – 1 = 2 | 3 – 1 = 2 | 30 (30) | |||
| РЦ 2 | 4 – 2 = 2 | 4 – 2 = 2 | 6 – 2 = 4 | 20 (15) | |||||
| РЦ 3 | 2 – 2 = 0 | 3 – 2 = 1 | 4 – 3 = 1 | 50 (45) | |||||
| Штраф | 3 – 2 = 1 | 5 – 4 = 1 | 2 – 1 = 1 | 5 – 3 = 2 | 4 – 2 = 2 | ||||
| Штраф | 3 – 2 = 1 | 6 – 4 = 2 | 4 – 2 = 2 | 7 – 5 = 2 | |||||
| Штраф | 3 – 2 = 1 | 6 – 4 = 2 | |||||||
| Спрос | 15 (15) | 25 (25) | 30 (30) | 20 (20) |
Для оставшейся матрицы введем поставки, удовлетворяющие спрос магазинов в товарах и реализующие предложение распределительных центов.
Таблица 3.1.17
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Штраф | Штраф | Штраф | Предложение | |
| РЦ 1 | 3 – 1 = 2 | 3 – 1 = 2 | 30 (30) | ||||||
| РЦ 2 | 4 – 2 = 2 | 4 – 2 = 2 | 6 – 2 = 4 | 20 (20) | |||||
| РЦ 3 | 2 – 2 = 0 | 3 – 2 = 1 | 4 – 3 = 1 | 50 (50) | |||||
| Штраф | 3 – 2 = 1 | 5 – 4 = 1 | 2 – 1 = 1 | 5 – 3 = 2 | 4 – 2 = 2 | ||||
| Штраф | 3 – 2 = 1 | 6 – 4 = 2 | 4 – 2 = 2 | 7 – 5 = 2 | |||||
| Штраф | 3 – 2 = 1 | 6 – 4 = 2 | |||||||
| Спрос | 15 (15) | 10 (10) | 25 (25) | 30 (30) | 20 (20) |
Поставки будем вводить, начиная с ячейки с наименьшей стоимостью транспортировки единицы (тонны) груза (табл. 3.1.17).
Суммарные затраты на транспортировку 100 тонн груза от распределительных центров к магазинам:
Z = 30*3 + 15*2 + 5*6 + 5*4 + 25*2 + 20*2 = 260 у.е.
Первоначальное решение задачи методами северо-западного угла, наименьшей стоимости и Фогеля показало, что наиболее близкое к оптимальному решение дает метод Фогеля.
Для нахождения оптимального плана перевозок товаров применяют распределительный метод, метод потенциалов.
Методы построения оптимального плана
Распределительный метод
Распределительный метод, как уже отмечалось, применяется для нахождения оптимального решения транспортной задачи, для которой ранее найдено первоначальное решение (опорный план перевозок с числом занятых клеток 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 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 | ||||||
| РЦ 2 | ||||||
| РЦ 3 | ||||||
| Спрос |
Решение
Выберем ячейку (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 | ||||||
| Спрос |
Алгебраическая сумма стоимостей транспортировки груза с учетом знаков:
D1,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 (+) | ||||
| Спрос |
Алгебраическая сумма стоимостей транспортировки единицы груза с учетом знаков:
D1,2 = 5 - 4 + 5 – 3 = 3 > 0
Рассмотрим ячейку (1,5). Построим замкнутый контур и определим алгебраическую сумму расстояний (табл. 3.1.21). В данном случае для примера выбрано другое направление построения контура.
Алгебраическая сумма стоимостей транспортировки единицы тонны груза с учетом знаков будет равна:
D1,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 (+) | ||||
| Спрос |
Алгебраическая сумма стоимостей транспортировки единицы груза с учетом знаков:
D2,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 | ||||||
| Спрос |
Алгебраическая сумма стоимостей транспортировки единицы груза с учетом знаков:
D2,3 = 4 – 7 + 3 – 1 = – 1 < 0
Полученный результат говорит о том, что на данном шаге имеющаяся структура поставок может быть улучшена.
Минимальная поставка в углах прямоугольника со знаком (-) равна 5. Введем в ячейку (2,3) поставку х2,3 = 5 и произведем перерасчет объемов поставок (табл.3.1.24) в зависимости от знака.
Таблица 3.1.24
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 |  1 25 - 5 | 5 + 5 | ||||
| РЦ 2 | + 5 | 5 - 5 | ||||
| РЦ 3 | ||||||
| Спрос |
Получим новую матрицу поставок (табл. 3.1.25).
Таблица 3.1.25
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 | ||||||
| РЦ 2 | ||||||
| РЦ 3 | ||||||
| Спрос |
Рассчитаем суммарные затраты на транспортировку 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 (-) | ||||
| Спрос |
Алгебраическая сумма стоимостей транспортировки тонны груза с учетом знаков:
D2,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 (-) | ||||
| Спрос |
Алгебраическая сумма стоимостей транспортировки тонны груза с учетом знаков:
D3,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 (-) | ||||
| Спрос |
Алгебраическая сумма стоимостей транспортировки тонны груза с учетом знаков будет равна:
D3,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
| Магазин 1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин 5 | Предложение | |
| РЦ 1 | ||||||
| РЦ 2 | ||||||
| РЦ 3 | ||||||
| Спрос |
Суммарные затраты на транспортировку 100 тонн груза будут равны 260 у.е.:
Z = 30*3 + 15*2 + 5*4 + 10*4 + 20*2 + 20*2 = 260 у.е.
Структура перевозок, определяемая табл. 3.1.30, является оптимальной, так как алгебраическая сумма стоимостей транспортировки единицы груза для всех свободных ячеек положительна. Минимальные суммарные затраты на транспортировку 100 тонн груза от распределительных центров в магазины равны 260 у.е.
Метод потенциалов
Для определения оптимальной структуры перевозок необходимо выполнить последовательно следующие шаги.
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 выбрать максимальное. В соответствующую ячейку ввести условную поставку q.
6 шаг. С помощью горизонтальных и вертикальных прямых линий построить замкнутый контур, который начинается и заканчивается в ячейке с условной поставкой и проходит через занятые клетки таблицы планирования. Клетки контура пометить (+) и (-) (аналогично тому, как это было сделано в распределительном методе).
7 шаг. Определить значение условной поставки q, как минимальное из значений поставок, находящихся в клетках контура с пометкой «-».
8 шаг. Пересчитать значения поставок в углах замкнутого контура с учетом найденного значения q, попеременно прибавляя его к существующим поставкам (в клетках «+») и вычитая из поставок (в клетках «-»).
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 | ||||||
| РЦ 2 U2 | ||||||
| РЦ 3 U3 | ||||||
| Спрос |
Для определения потенциалов по занятым клеткам составим уравнения 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 | |||||
| РЦ 2 U2 = 4 | |||||
| РЦ 3 U3 = 2 |
Используя вычисленные значения потенциалов, определим значения 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 соответственно. Введем условную поставку 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
| Магазин1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин5 | |
| РЦ1 | |||||
| РЦ2 | |||||
| РЦ3 |
Определим суммарные затраты на транспортировку 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 | |||||
| РЦ 2 U2 = 4 | |||||
| РЦ 3 U3 = 1 |
Проверим оптимальность плана перевозок. Для этого определим значения 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,3 = U2 + V3 – C2,3 = 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,4 = U3 + V4 – C3,4 = 1 + 3 – 5 = – 1 |
Наибольшее значение Si,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
| Магазин1 | Магазин 2 | Магазин 3 | Магазин 4 | Магазин5 | |
| РЦ1 | |||||
| РЦ2 | |||||
| РЦ3 |
Определим суммарные затраты на транспортировку ста тонн груза.
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 | |||||
| РЦ 2 U2 = 3 | |||||
| РЦ 3 U3 = 1 |
Проверим оптимальность плана перевозок. Для этого определим значения 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 у.е.
3.1.3. Определение плана перевозок
для доставки мелких партий груза
Отличие построения данного плана перевозок от общего случая транспортной задачи состоит в том, что поставка товаров осуществляется с одного склада в несколько пунктов назначения, что часто можно встретить в сетевой рознице. Целью данного класса задач является определение количества маршрутов и очередность поставки товаров в магазины для каждого маршрута с наименьшими транспортными затратами.
Решение данной задачи раскладывается на два этапа:
1. Определение количества маршрутов и входящих в каждый маршрут пунктов назначения.
2. Определение последовательности доставки товаров в пункты назначения внутри каждого маршрута.
Алгоритм решения.
1 шаг. Определить количество маршрутов путем деления общего объема спроса на грузоподъемность транспортного средства.
2 шаг. Методом минимального остовного дерева связать все пункты назначения в единую сеть минимального длины.
3 шаг. По каждой полученной ветви, начиная с наиболее удаленного пункта назначения, группируют пункты в маршруты с учетом объема спроса и грузоподъемностью транспортного средства.
4 шаг. С использованием метода ветвей и границ или суммирования по столбцам определяют последовательность поставки товаров в магазины внутри маршрута.
Задача 1
Определить оптимальный план перевозок товаров со склада S в магазины. Товар в магазины поставляется со склада с использованием Газели грузоподъемностью 1,5 тонны. Транспортная сеть представлена на рис. 3.1.1, а потребности магазинов в товаре отображены в таблице 3.1.42.
 |
Рис. 3.1.1. Транспортная сеть.
Таблица 3.1.42
Потребность магазинов в товаре
| Магазины | ||||||||
| Спрос, т. | 0,33 | 0,25 | 0,35 | 0,45 | 0,25 | 0,5 | 0,47 | 0,31 |
Решение
Определим количество маршрутов:
где
– суммарный спрос товаров в магазинах, т.;
Q – грузоподъемность транспортного средства, т.
марш.