Оптимизация в логистике. Транспортная задача

3.6. Метод минимальных тарифов

 

Метод минимальных  тарифов (правило минимальных затрат, правило «самая дешёвая продукция реализуется первой») — алгоритм получения допустимого начального решения транспортной задачи. В отличие от более простого метода северо-западного угла, в этом методе расчетчик записывает отгрузки, в первую очередь, в те ячейки, где тариф на перевозку груза минимален. Этот метод позволяет получить более приближенное к оптимальному решение, которое, однако, может потребовать дальнейшей оптимизации методом потенциалов. Метод минимальных тарифов с его модификациями (минимальный тариф по строке или минимальный тариф по столбцу) был описан Данцигом в работе 1951 г.

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

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30 кг	Потребитель B3,  потребность 30 кг	Потребитель B4,  потребность 10 кг
Поставщик A1,  запас 30 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг]	[4 руб./кг]
Поставщик A2,  запас 40 кг	[3 руб./кг]	[2 руб./кг]	[5 руб./кг]	[1 руб./кг]
Поставщик A3,  запас 20 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

В эти же ячейки транспортной таблицы  следует вписать объемы перевозки, чтобы распределить запасы поставщиков по потребителям.

Шаг 1

Находим ячейку с минимальной ценой. В нашем примере это ячейка X₂₄ (2-й поставщик, 4-й потребитель), где цена доставки = 1 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя (берем минимум между 40 и 10 кг, то есть 10 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет.

 

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30 кг	Потребитель B3,  потребность 30 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг]	[4 руб./кг]
Поставщик A2,  запас 40-10=30 кг	[3 руб./кг]	[2 руб./кг]	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

 

Шаг 2

Находим в оставшихся незакрашенными серым ячейку с минимальной ценой (см. таблицу выше). В нашем примере  есть несколько ячеек, где цена доставки = 2 руб./кг, выберем произвольную из них, скажем, X₁₃ (1-й поставщик, 3-й потребитель). Вписываем в эту ячейку максимальный объем, который позволяет (см. таблицу выше) запас поставщика и спрос потребителя (30 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет. Поскольку возможности поставщика также были исчерпаны, закрашиваем в серый цвет и соответствующую строку.

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30 кг	Потребитель B3,  потребность 30-30=0 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30-30=0 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг] 30 кг	[4 руб./кг]
Поставщик A2,  запас 40-10=30 кг	[3 руб./кг]	[2 руб./кг]	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

 

Шаг 3

Находим в оставшихся незакрашенными серым (см. таблицу выше) ячейку с  минимальной ценой. В нашем примере  это ячейка X₂₂ (2-й поставщик, 2-й потребитель) с ценой доставки 2 руб./кг. Вписываем в эту ячейку максимальный объем, который позволяет (см. таблицу выше) запас поставщика и спрос потребителя (30 кг). Поскольку спрос потребителя полностью удовлетворен, закрашиваем соответствующий столбец в серый цвет. Поскольку возможности поставщика также были исчерпаны, закрашиваем в серый цвет и соответствующую строку.

	Потребитель B1,  потребность 20 кг	Потребитель B2,  потребность 30-30=0 кг	Потребитель B3,  потребность 30-30=0 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30-30=0 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг] 30 кг	[4 руб./кг]
Поставщик A2,  запас 40-10-30=0 кг	[3 руб./кг]	[2 руб./кг] 30 кг	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20 кг	[4 руб./кг]	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

 

Шаг 4

Осталась нераспределенной единственная ячейка X₃₁ (3-й поставщик, 1-й потребитель) с ценой доставки 4 руб./кг. Вписываем в эту ячейку оставшийся объем (20 кг), который должен полностью завершить распределение и закрыть объемы. Если на этом шаге окажется, что объемы поставщика и потребителя не равны друг другу, то это значит, что транспортная задача открытая и ее нужно сбалансировать.

	Потребитель B1,  потребность 20-20=0 кг	Потребитель B2,  потребность 30-30=0 кг	Потребитель B3,  потребность 30-30=0 кг	Потребитель B4,  потребность 10-10=0 кг
Поставщик A1,  запас 30-30=0 кг	[2 руб./кг]	[3 руб./кг]	[2 руб./кг] 30 кг	[4 руб./кг]
Поставщик A2,  запас 40-10-30=0 кг	[3 руб./кг]	[2 руб./кг] 30 кг	[5 руб./кг]	[1 руб./кг] 10 кг
Поставщик A3,  запас 20-20=0 кг	[4 руб./кг] 20 кг	[3 руб./кг]	[2 руб./кг]	[6 руб./кг]

 

Результат = 4*20 + 2*30 + 2*30 + 1*10 = 210 р.

3.7. Метод Фогеля

 

Данный метод генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов.

Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы (в примерах ниже они закрашиваются серым цветом), и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых («серых») ячеек.

 

 

 

3.8. Метод Потенциалов

 

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

3.8.1. Проверка правильности распределения объемов

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

В показанном выше примере,

• Для 1-й строки: 30 кг = 20 + 10 кг
• Для 2-й строки: 40 кг = 20 + 20 кг
• Для 3-й строки: 20 кг = 10 + 10 кг
• Для 1-го столбца: 20 кг = 20 кг
• Для 2-го столбца: 30 кг = 10 + 20 кг
• Для 3-го столбца: 30 кг = 20 + 10 кг
• Для 4-го столбца: 10 кг = 10 кг

3.8.2. Вычисление общей стоимости транспортировки

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

 

	B1, 20 кг	B2, 30 кг	B3, 30 кг	B4, 10 кг
A1, 30 кг	С11=2 руб./кг,  X11=20 кг	С12=3 руб./кг,  Х12=10 кг	С13=2 руб./кг	С14=4 руб./кг
A2, 40 кг	С21=3 руб./кг	С22=2 руб./кг,  Х22=20 кг	С23=5 руб./кг,  Х23=20 кг	С24=1 руб./кг
A3, 20 кг	С31=4 руб./кг	С32=3 руб./кг	С33=2 руб./кг,  Х33=10 кг	С34=6 руб./кг,  Х34=10 кг

 

В данном примере, сумма затрат на перевозку груза составляет

2×20 + 3×10 + 2×20 + 5×20 + 2×10 + 6×10 = 290 руб.

3.8.3. Разделение ячеек на базисные и свободные

Ячейки (клетки) транспортной таблицы  с ненулевыми перевозками называются базисными, а клетки с нулевыми объемами перевозки — свободными.

3.8.4. Проверка плана на вырожденность

Базисных ячеек таблицы должно быть не менее m+n−1, где m и n — соответственно, число поставщиков и потребителей, иначе решение считается вырожденным и требует введения в базис одной из ячеек с нулевой перевозкой (чтобы алгоритм не впал в бесконечный цикл, эта ячейка должна быть случайной). Для исключения ситуаций с вырожденностью к объемам потребления добавляют небольшие возмущения — числа, заведомо ничтожные при перевозках (такие как 0.00001), при этом к объему поставки одного из поставщиков добавляют их сумму (или наоборот).

3.8.5. Вычисление потенциалов

Каждому поставщику A_i соответствует потенциал U_i, а каждому потребителю B_j соответствует потенциал V_j. Данциг называет потенциалы U_i и V_j симплекс-множителями или неявными ценами. Чтобы определить эти потенциалы, полагают, что U₁=0, а остальные потенциалы вычисляют из соотношения

U_i + V_j = C_ij

для всех занятых (базисных) ячеек таблицы (отмечены зеленым).

	V1	V2	V3	V4
U1=0	С11=2 руб./кг	С12=3 руб./кг
U2		С22=2 руб./кг	С23=5 руб./кг
U3			С33=2 руб./кг	С34=6 руб./кг

U₁+V₁=2. Поскольку U₁=0, 0+V₁=2, следовательно, V₁=2 руб./кг

U₁+V₂=3. Поскольку U₁=0, 0+V₂=3, следовательно, V₂=3 руб./кг

U₂+V₂=2. Поскольку V₂=3, U₂+3=2, следовательно, U₂=–1 руб./кг

U₂+V₃=5. Поскольку U₂=–1, –1+V₃=5, следовательно, V₃=6 руб./кг

U₃+V₃=2. Поскольку V₃=6, U₃+6=2, следовательно, U₃=–4 руб./кг