Распределительный метод

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

История

Истоки распределительного метода восходят к работам советского математика Леонида Витальевича Канторовича, который в 1939 году опубликовал работу «Математические методы организации и планирования производства». В ней он впервые сформулировал задачу оптимального распределения ресурсов (например, станков, сырья, рабочей силы) и предложил метод разрешающих множителей — прообраз будущего симплекс-метода. За эти исследования Канторович в 1975 году был удостоен Нобелевской премии по экономике.

В 1940–1950-х годах американский математик Джордж Данциг разработал симплекс-метод — универсальный алгоритм решения задач линейного программирования, который лёг в основу многих вычислительных процедур, включая распределительный метод. В СССР в 1950–1960-х годах метод активно развивался в трудах В.С. Немчинова, А.Л. Лурье и других учёных для решения задач планирования народного хозяйства, транспорта и снабжения.

Классификация распределительных методов

В зависимости от решаемой задачи и алгоритма выделяют несколько основных типов:

По типу задачи

• Транспортная задача — поиск оптимального плана перевозок от поставщиков к потребителям с минимальной стоимостью.
• Задача о назначениях — распределение работников (или машин) по работам для минимизации времени или затрат.
• Задача оптимального раскроя — минимизация отходов при раскрое материалов.
• Задача управления запасами — распределение складских ресурсов между точками потребления.

По алгоритму решения

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

Устройство и алгоритм (на примере транспортной задачи)

Распределительный метод решения транспортной задачи включает несколько этапов:

1. Построение математической модели. Определяются поставщики (m), потребители (n), объёмы запасов (a_i), потребности (b_j) и матрица тарифов (c_ij — стоимость перевозки единицы груза от i-го поставщика к j-му потребителю). Условие баланса: сумма запасов равна сумме потребностей (закрытая задача). Если баланс не выполняется, вводится фиктивный поставщик или потребитель.

1. Построение начального опорного плана. Используется один из методов (северо-западного угла, минимальной стоимости, Фогеля). План представляется в виде таблицы, где заполненные клетки соответствуют ненулевым перевозкам. Количество заполненных клеток должно быть равно m + n – 1 (невырожденный план).

1. Проверка плана на оптимальность. Для каждой строки и столбца вычисляются потенциалы (u_i, v_j) из условия u_i + v_j = c_ij для заполненных клеток. Затем для каждой свободной клетки рассчитывается оценка Δ_ij = c_ij – (u_i + v_j). Если все Δ_ij ≥ 0, план оптимален. Если есть отрицательные оценки, план можно улучшить.

1. Улучшение плана (перераспределение). Строится цикл пересчёта — замкнутая ломаная линия, проходящая через свободную клетку с отрицательной оценкой и заполненные клетки. В углах цикла поочерёдно прибавляется и вычитается некоторое значение θ (максимально возможное, чтобы не нарушить баланс). После пересчёта получается новый план с меньшей суммарной стоимостью.

1. Итерация. Шаги 3–4 повторяются до получения оптимального плана.

Применение

Распределительный метод широко используется в различных отраслях экономики и управления:

• Логистика и транспорт. Оптимизация маршрутов доставки грузов, распределение автомобилей по рейсам, планирование железнодорожных и авиаперевозок.
• Промышленность. Распределение сырья между цехами, загрузка оборудования, планирование производства.
• Сельское хозяйство. Распределение удобрений, кормов, техники по полям и фермам.
• Торговля и снабжение. Оптимизация поставок товаров со складов в магазины.
• Военное дело. Планирование снабжения войск, распределение боеприпасов и топлива.
• Энергетика. Распределение нагрузки между электростанциями для минимизации затрат на топливо.

Пример

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

Начальный план по методу северо-западного угла:

• Поставщик 1 → Потребитель 1: 80 ед. (остаток 20)
• Поставщик 1 → Потребитель 2: 20 ед. (запас исчерпан)
• Поставщик 2 → Потребитель 2: 100 ед. (остаток 100)
• Поставщик 2 → Потребитель 3: 100 ед.

Стоимость: 80×3 + 20×5 + 100×2 + 100×6 = 240 + 100 + 200 + 600 = 1140.

После применения метода потенциалов (расчёт опущен) оптимальный план может дать стоимость, например, 1080, что достигается перераспределением части поставок.

Критика и ограничения

• Линейность. Распределительный метод предполагает линейную зависимость затрат от объёма перевозок, что не всегда соответствует реальности (скидки за объём, штрафы за недопоставку).
• Статичность. Метод не учитывает динамику спроса, сезонность, изменения тарифов во времени.
• Размерность. При большом количестве поставщиков и потребителей (сотни и тысячи) ручной расчёт становится трудоёмким, требуется использование ЭВМ.
• Необходимость баланса. Для применения классического метода требуется сбалансированность запасов и потребностей, что не всегда выполняется на практике (требуется введение фиктивных элементов).
• Сложность с нелинейными ограничениями. Метод плохо применим к задачам с нелинейными целевыми функциями или дополнительными ограничениями (например, пропускная способность дорог).

Интересные факты

• Распределительный метод стал одним из первых практических применений линейного программирования в СССР — он использовался для планирования перевозок лесоматериалов и металла.
• Метод потенциалов, лежащий в основе оптимизации транспортного плана, по сути является частным случаем симплекс-метода, адаптированным под структуру транспортной задачи.
• В 1960-х годах в СССР были созданы первые автоматизированные системы планирования перевозок (АСУ «Транспорт»), использующие распределительный метод.
• Современные программные комплексы (например, IBM ILOG CPLEX, Gurobi, LPSolve) реализуют распределительный метод в составе более общих алгоритмов линейного программирования.

Источники

1. Канторович Л.В. «Математические методы организации и планирования производства». — Л.: Изд-во ЛГУ, 1939.
2. Данциг Дж. «Линейное программирование, его обобщения и применения». — М.: Прогресс, 1966.
3. Немчинов В.С. «Экономико-математические методы и модели». — М.: Мысль, 1965.
4. Лурье А.Л. «Экономико-математические модели в планировании и управлении». — М.: Наука, 1973.
5. Таха Х. «Введение в исследование операций». — М.: Вильямс, 2005.
6. Акулич И.Л. «Математическое программирование в примерах и задачах». — М.: Высшая школа, 1986.