Метод минимальных тарифов
Метод минимальных тарифов[1] (правило минимальных затрат[2], правило «самая дешёвая продукция реализуется первой»[3]) — алгоритм получения допустимого начального решения транспортной задачи. В отличие от более простого метода северо-западного угла, в этом методе расчетчик записывает отгрузки, в первую очередь, в те ячейки, где тариф на перевозку груза минимален. Этот метод позволяет получить более приближенное к оптимальному решение, которое, однако, может потребовать дальнейшей оптимизации методом потенциалов.[1] Метод минимальных тарифов с его модификациями (минимальный тариф по строке или минимальный тариф по столбцу) был описан Данцигом в работе 1951 г.[4]
Числовой пример[править]
В этом примере стоимость доставки в рублях за кг записана в ячейках в квадратных скобках.
| Потребитель 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[править]
Находим ячейку с минимальной ценой. В нашем примере это ячейка X24 (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 руб./кг, выберем произвольную из них, скажем, X13 (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[править]
Находим в оставшихся незакрашенными серым (см. таблицу выше) ячейку с минимальной ценой. В нашем примере это ячейка X22 (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[править]
Осталась нераспределенной единственная ячейка X31 (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 руб./кг] |
Дальнейшая оптимизация решения[править]
Полученное методом минимальных тарифов решение транспортной задачи может оказаться не оптимальным, для его проверки на оптимальность и дальнейшей оптимизации используют метод потенциалов. Для получения начального решения можно использовать метод Фогеля, который с большей вероятностью выдает еще более оптимальное решение, чем метод минимальных тарифов, которое, однако, также подлежит дальнейшей оптимизации методом потенциалов. Если же нужно, наоборот, получить заведомо неоптимизированное решение (чтобы было, с чем сравнивать) используют метод северо-западного угла.
Программная реализация[править]
В коде для 1С:Предприятие 8.2 по ссылке метод представлен функцией РаспределениеМетодомМинимальныхТарифов.[5]
Источники[править]
- ↑ 1,0 1,1 Лунгу К. Н. Линейное программирование. Руководство к решению задач. — М.: Физматлит, 2005. — 128 с. — ISBN 5-9221-0631-7.(djvu)
- ↑ Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
- ↑ Б.Банди «Основы линейного программирования» М:Радио и связь, 1989 (djvu)
- ↑ Dantzig, G. В., Application of the Simplex Method to a Transportation Problem, chap. XXIII of // Koopmans T.C. (ed.), Activity Analysis of Production and Allocation, Cowles Commission Monograph 13, John Wiley & Sons, Inc., New York, 1951.
- ↑ http://www.kb.mista.ru/article.php?id=859
 ↑ [+] | |
|---|---|
| Транспортная задача |
Транспортная задача (классическая) • Решение симплекс-методом • Решение в Excel • Транспортная задача с промежуточными пунктами (и ограничением по транзиту, с запретами) • Трёхиндексная транспортная задача (алгоритм минимального элемента) |
| Начальное решение |
Метод северо-западного угла • Метод минимальных тарифов • Метод Фогеля |
| Вырожденные случаи | |