Метод наименьшей цены

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

Описание алгоритма

Метод наименьшей цены применяется для построения начального плана транспортной задачи, которая формулируется следующим образом: имеется \( m \) поставщиков с запасами \( a_i \) и \( n \) потребителей с потребностями \( b_j \). Известна матрица стоимостей перевозки \( c_{ij} \) единицы груза от \( i \)-го поставщика к \( j \)-му потребителю. Необходимо найти план перевозок \( x_{ij} \) (количество груза, перевозимого от \( i \)-го поставщика к \( j \)-му потребителю), минимизирующий суммарные транспортные расходы.

Алгоритм метода наименьшей цены включает следующие шаги:

1. Построение матрицы стоимостей. Создаётся таблица, в строках которой указаны поставщики, в столбцах — потребители, а в ячейках — стоимости перевозки \( c_{ij} \). В отдельные столбцы и строки выносятся остатки запасов поставщиков и неудовлетворённые потребности потребителей.

1. Выбор ячейки с минимальной стоимостью. На каждом шаге среди всех ячеек таблицы, для которых ещё не назначены перевозки и которые не вычеркнуты, выбирается ячейка с наименьшим значением \( c_{ij} \). Если таких ячеек несколько, выбирается любая из них (обычно первая слева или сверху).

1. Назначение максимально возможной перевозки. В выбранную ячейку записывается максимально возможная величина перевозки \( x_{ij} \), которая определяется как минимум из остатка запаса \( i \)-го поставщика и остатка потребности \( j \)-го потребителя: \( x_{ij} = \min(a_i, b_j) \).

1. Корректировка остатков. После назначения перевозки остатки запасов и потребностей уменьшаются на величину \( x_{ij} \):

• Если \( a_i \) становится равным 0, то строка \( i \) вычёркивается из дальнейшего рассмотрения (все неиспользованные ячейки этой строки считаются пустыми).
• Если \( b_j \) становится равным 0, то столбец \( j \) вычёркивается.
• Если одновременно обнуляются и запас, и потребность, вычёркивается либо строка, либо столбец (по соглашению, чтобы избежать вырожденности плана).

1. Повторение шагов 2–4 до тех пор, пока все запасы не будут распределены, а все потребности — удовлетворены. Количество заполненных ячеек (базисных переменных) в итоговом плане должно быть равно \( m + n - 1 \) (условие невырожденности).

Пример применения

Рассмотрим транспортную задачу с тремя поставщиками (запасы: 100, 150, 200 ед.) и четырьмя потребителями (потребности: 80, 120, 100, 150 ед.). Матрица стоимостей (условные единицы):

Шаг 1. Минимальная стоимость в таблице — 1 (ячейка A2B2). Назначаем перевозку: \( x_{22} = \min(150, 120) = 120 \). Остаток запаса A2: 30, потребность B2: 0. Столбец B2 вычёркивается.

Шаг 2. Среди оставшихся ячеек минимальная стоимость — 2 (ячейки A1B1 и A3B3). Выбираем A1B1: \( x_{11} = \min(100, 80) = 80 \). Остаток A1: 20, B1: 0. Столбец B1 вычёркивается.

Шаг 3. Минимальная стоимость — 2 (ячейка A3B3). \( x_{33} = \min(200, 100) = 100 \). Остаток A3: 100, B3: 0. Столбец B3 вычёркивается.

Шаг 4. Остались только ячейки столбца B4. Минимальная стоимость — 4 (A1B4), 5 (A3B4), 8 (A2B4). Выбираем A1B4: \( x_{14} = \min(20, 150) = 20 \). Остаток A1: 0, B4: 130. Строка A1 вычёркивается.

Шаг 5. Остались A2 (остаток 30) и A3 (остаток 100) для B4 (остаток 130). Минимальная стоимость — 5 (A3B4). \( x_{34} = \min(100, 130) = 100 \). Остаток A3: 0, B4: 30. Строка A3 вычёркивается.

Шаг 6. Последняя ячейка A2B4: \( x_{24} = \min(30, 30) = 30 \). Все запасы распределены, потребности удовлетворены.

Итоговый план перевозок: \( x_{11}=80, x_{22}=120, x_{33}=100, x_{14}=20, x_{34}=100, x_{24}=30 \). Суммарная стоимость: \( 80\cdot2 + 120\cdot1 + 100\cdot2 + 20\cdot4 + 100\cdot5 + 30\cdot8 = 160 + 120 + 200 + 80 + 500 + 240 = 1300 \) условных единиц.

Сравнение с другими методами

Метод наименьшей цены является одним из трёх основных способов построения начального опорного плана в транспортной задаче, наряду с методом северо-западного угла и методом Фогеля (методом аппроксимации Фогеля).

• Метод северо-западного угла — самый простой и быстрый, но даёт план, как правило, далёкий от оптимального, так как не учитывает стоимости перевозок.
• Метод наименьшей цены — учитывает стоимости, что позволяет получить план, более близкий к оптимальному, чем метод северо-западного угла. Однако он не гарантирует оптимальности и может приводить к локально невыгодным решениям на поздних шагах.
• Метод Фогеля — более сложный, но даёт наилучшее начальное приближение среди эвристических методов, часто близкое к оптимальному решению.

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

Применение

Метод наименьшей цены применяется в задачах логистики, планирования перевозок, распределения ресурсов, управления цепочками поставок. Он позволяет быстро получить допустимый план, который затем может быть улучшен с помощью точных методов (например, метода потенциалов или симплекс-метода). В коммерческих программных продуктах для решения транспортных задач (например, в модулях SAP, Oracle, 1С) метод наименьшей цены может использоваться как один из алгоритмов для начальной инициализации.

Критика

Основной недостаток метода наименьшей цены — его локальность. На каждом шаге выбирается минимальная стоимость среди оставшихся ячеек, но это не гарантирует глобальной оптимальности итогового плана. В некоторых случаях метод может привести к плану, который значительно хуже оптимального, особенно если в задаче присутствуют большие различия в стоимостях. Кроме того, метод не учитывает возможность «перекоса» — когда на ранних шагах исчерпываются ресурсы поставщика с дешёвыми перевозками, а оставшиеся дорогие перевозки становятся неизбежными.

Источники

1. Кремер Н. Ш. Исследование операций в экономике. — М.: Юрайт, 2018.
2. Таха Х. А. Введение в исследование операций. — М.: Вильямс, 2016.
3. Зайцев М. Г., Варфоломеев В. И. Методы оптимизации управления и принятия решений. — М.: Дело, 2010.
4. Лотов А. В. Введение в экономико-математическое моделирование. — М.: Наука, 1984.