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

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

¶История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

¶Применение

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

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

¶Пример

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

Поставщик \ Потребитель	П1	П2	П3
Поставщик 1	3	5	7
Поставщик 2	4	2	6

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

Поставщик 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) реализуют распределительный метод в составе более общих алгоритмов линейного программирования.

¶Источники

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

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →