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

Материал из Циклопедии
Перейти к: навигация, поиск

Метод минимальных тарифов[1]:87 (правило минимальных затрат[2]:304, правило «самая дешёвая продукция реализуется первой»[3]:85) — алгоритм получения допустимого начального решения транспортной задачи. В отличие от более простого метода северо-западного угла, в этом методе расчетчик записывает отгрузки, в первую очередь, в те ячейки, где тариф на перевозку груза минимален. Этот метод позволяет получить более приближенное к оптимальному решение, которое, однако, может потребовать дальнейшей оптимизации методом потенциалов.[1]:87 Метод минимальных тарифов с его модификациями (минимальный тариф по строке или минимальный тариф по столбцу) был описан Данцигом в работе 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. 1,0 1,1 Лунгу К. Н. Линейное программирование. Руководство к решению задач. — М.: Физматлит, 2005. — 128 с. — ISBN 5-9221-0631-7.(djvu)
  2. Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 (djvu)
  3. Б.Банди «Основы линейного программирования» М:Радио и связь, 1989 (djvu)
  4. 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.
  5. http://www.kb.mista.ru/article.php?id=859


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты