Транспортная Задача (Задача Монжа-Канторовича): Экономико-Математическое Моделирование и Метод Потенциалов

Введение: Актуальность задачи минимизации транспортных расходов

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

В эпоху глобализации, когда цепочки поставок охватывают континенты, оптимизация транспортных потоков становится не просто вопросом экономии, но и критическим фактором конкурентоспособности. Решение ТЗ позволяет устранить нерациональные, чрезмерно дальние, встречные или повторные перевозки, обеспечивая тем самым разработку наиболее рациональных логистических схем.

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

Теоретические и Исторические Основы Задачи Оптимального Транспорта

Понимание транспортной задачи невозможно без обращения к ее генезису. Это не просто абстрактная математическая модель, а результат эволюции представлений об оптимальном перемещении масс, начало которой было положено задолго до появления современных компьютеров, что подчеркивает ее фундаментальный, вневременной характер.

Истоки: Задача Монжа (1781 г.) о переносе масс

Концептуальная основа транспортной задачи была заложена французским математиком и инженером Гаспаром Монжем (Gaspard Monge) в его работе 1781 года, посвященной теории выемки и насыпи грунта.

Суть задачи Монжа заключалась в следующем: как перенести заданный объем земли (или грунта) с одной поверхности (зоны выемки) на другую (зону насыпи) таким образом, чтобы минимизировать суммарное произведение объема перемещенного груза на расстояние, на которое он был перемещен. Иными словами, Монж искал оптимальный план перемещения масс с минимальной стоимостью транспортировки.

Хотя Монж не сформулировал задачу в виде линейного программирования, поскольку этот аппарат еще не был разработан, его постановка является первой известной в истории математики, которая четко определяет принцип оптимального транспорта. Этот принцип лег в основу всей современной логистики.

Обобщение Канторовича и «Задача фанерного треста»

Фундаментальное обобщение и перевод задачи об оптимальном перемещении масс в русло линейного программирования принадлежит советскому математику и экономисту, лауреату Нобелевской премии Леониду Витальевичу Канторовичу. В своей работе «О перемещении масс» (1942 г.) Канторович не только обобщил классическую задачу Монжа, но и сформулировал ее как задачу линейного программирования — сегодня она известна как задача Монжа-Канторовича.

Канторович пришел к разработке этой модели, решая реальную технико-экономическую проблему в СССР в конце 1930-х годов, вошедшую в историю как «Задача фанерного треста».

Контекст «Задачи фанерного треста» (1938 г.)
Проблема заключалась в следующем: имелось пять лущильных станков, различающихся по своим техническим характеристикам и производительности, и восемь номенклатур сырья (шпона) с разными свойствами. Требовалось найти такой план оптимальной загрузки этих пяти станков восемью номенклатурами сырья, который бы обеспечил максимальный выпуск готовой фанерной продукции.

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

Каноническая Экономико-Математическая Модель Транспортной Задачи

Классическая постановка транспортной задачи предполагает, что имеется $m$ пунктов отправления (поставщиков) и $n$ пунктов назначения (потребителей).

Формальная Постановка и Условие Баланса

Канонической, или закрытой, транспортной задачей называется такая модель, в которой выполняется строгое условие баланса: суммарный объем запасов у всех поставщиков равен суммарному объему спроса у всех потребителей:

$$ \sum^{m}_{i=1} a_i = \sum^{n}_{j=1} b_j $$

Где:

• $a_i$ — запас продукции в $i$-м пункте отправления.
• $b_j$ — потребность в продукции в $j$-м пункте назначения.
• $x_{ij}$ — искомая переменная: количество продукции, перевозимой из пункта $i$ в пункт $j$.
• $c_{ij}$ — тариф (стоимость) перевозки единицы груза из пункта $i$ в пункт $j$.

1. Целевая Функция (Критерий Оптимальности)

Цель состоит в минимизации общих транспортных расходов ($Z$):

$$ Z = \sum^{m}_{i=1} \sum^{n}_{j=1} c_{ij} x_{ij} \to \min $$

2. Ограничения по Запасам (Поставщикам)

Объем продукции, отгруженной из каждого пункта отправления, должен быть равен имеющемуся запасу:

$$ \sum^{n}_{j=1} x_{ij} = a_i \quad \text{для } i = 1, 2, \dots, m $$

3. Ограничения по Потребностям (Потребителям)

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

$$ \sum^{m}_{i=1} x_{ij} = b_j \quad \text{для } j = 1, 2, \dots, n $$

4. Ограничения Неотрицательности

Объемы перевозок не могут быть отрицательными:

$$ x_{ij} \ge 0 $$

Свойства Системы Ограничений

Ключевое свойство закрытой транспортной задачи связано с ее системой ограничений. Общее количество ограничений в канонической постановке равно $m + n$. Однако, благодаря условию баланса, эта система содержит одно избыточное (линейно зависимое) уравнение.

Теорема о Ранге: Ранг матрицы системы ограничений закрытой транспортной задачи всегда равен:

$$ r = m + n — 1 $$

Это свойство имеет критическое значение, так как оно определяет количество базисных переменных, необходимых для формирования невырожденного опорного плана. Опорный план — это допустимое решение, удовлетворяющее всем ограничениям. Для того чтобы план был невырожденным, он должен содержать ровно $m+n-1$ занятых (базисных) клеток, то есть клеток с положительными объемами перевозок ($x_{ij} > 0$).

Методы Нахождения Начального Опорного Плана

Перед тем как приступить к оптимизации решения, необходимо найти любое допустимое базисное решение, то есть построить начальный опорный план.

Метод	Критерий выбора клетки	Экономичность начального плана	Сложность алгоритма
Северо-Западного Угла (МСЗУ)	Геометрический (верхний левый угол)	Низкая	Низкая (самый простой)
Минимального Элемента (ММЭ)	Минимальная стоимость $c_{ij}$	Средняя	Средняя
Аппроксимации Фогеля (МАФ)	Максимальный «штраф» (разность минимальных стоимостей)	Высокая	Высокая (самый сложный)

Метод Северо-Западного Угла и Метод Минимального Элемента

Метод Северо-Западного Угла (МСЗУ)
Это самый простой и механистический способ. Заполнение таблицы начинается с клетки $x_{11}$ (верхний левый угол), откуда и пошло название. На каждом шаге в текущую клетку записывается максимально возможный объем перевозки, ограниченный либо запасом $a_i$, либо потребностью $b_j$. После насыщения строки или столбца, они исключаются из рассмотрения, и процесс переходит к следующей незанятой клетке по горизонтали или вертикали. Главный недостаток МСЗУ — он полностью игнорирует транспортные тарифы $c_{ij}$, поэтому полученный начальный план часто оказывается далек от оптимального.

Метод Минимального Элемента (ММЭ)
Этот метод вносит экономическую логику в процесс построения начального плана. На каждом шаге выбирается клетка с наименьшим тарифом $c_{ij}$ среди всех доступных (незанятых) клеток. В эту клетку записывается максимально возможный объем перевозки. Такой подход гарантирует, что первые и, вероятно, самые большие перевозки будут осуществляться по самым дешевым маршрутам, что существенно улучшает качество начального решения по сравнению с МСЗУ. Разве не в этом суть рационального управления ресурсами?

Метод Аппроксимации Фогеля (МАФ)

Метод Фогеля является наиболее сложным, но одновременно и наиболее эффективным среди методов построения начального опорного плана.

Принцип работы: МАФ основан на концепции «штрафов» или «потерь». На каждом шаге рассчитываются разности (штрафы) между двумя наименьшими тарифами в каждой строке и каждом столбце. Эти разности показывают, насколько увеличатся расходы, если не использовать самый дешевый маршрут.

Алгоритм МАФ:

1. Для каждой строки и столбца найти разность между наименьшим и следующим по величине тарифами.
2. Выбрать строку или столбец с максимальным штрафом.
3. В выбранной строке (или столбце) заполнить клетку с минимальным тарифом.
4. Исключить насыщенную строку или столбец и повторить процесс.

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

Алгоритм Оптимизации: Метод Потенциалов (Метод Распределения)

Метод потенциалов — это итерационный алгоритм, основанный на идеях двойственности линейного программирования, предназначенный для проверки опорного плана на оптимальность и его последовательного улучшения. Этот метод является ключевым для достижения истинной эффективности, поскольку именно он переводит «допустимый» план в «оптимальный».

Расчет Потенциалов и Критерий Оптимальности

Основная идея метода заключается в том, что для оптимального плана должны выполняться условия двойственной оптимальности.

Шаг 1. Расчет потенциалов
Необходимо найти две совокупности чисел — потенциалы поставщиков ($u_i$) и потенциалы потребителей ($v_j$) — которые должны удовлетворять следующим условиям для всех занятых (базисных) клеток ($x_{ij} > 0$):

$$ u_i + v_j = c_{ij} $$

У нас имеется $m+n-1$ линейно независимых уравнений (по числу базисных клеток) и $m+n$ неизвестных потенциалов ($u_1, \dots, u_m$ и $v_1, \dots, v_n$). Поскольку число переменных превышает число уравнений, система является неопределенной. Для получения единственного решения необходимо и достаточно **одному из потенциалов произвольно присвоить нулевое значение** (например, $u_1 = 0$).

Шаг 2. Оценка свободных клеток
После определения всех потенциалов, для каждой свободной (небазисной, $x_{ij} = 0$) клетки вычисляется ее оценка (или невязка) $\Delta_{ij}$:

$$ \Delta_{ij} = c_{ij} — (u_i + v_j) $$

Шаг 3. Проверка оптимальности
План считается оптимальным (для задачи минимизации), если выполняются условия двойственной оптимальности:

$$ \Delta_{ij} \ge 0 \quad \text{для всех свободных клеток} $$

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

Экономическая Интерпретация Потенциалов

Экономический смысл потенциалов $u_i$ и $v_j$ выходит за рамки просто математических коэффициентов. В терминах двойственной задачи линейного программирования, потенциалы представляют собой объективно значимые цены (ОЗЦ) или теневые цены.

• Потенциал поставщика ($u_i$): Может быть интерпретирован как «стоимость» или «ценность» единицы продукции, отгружаемой из $i$-го пункта.
• Потенциал потребителя ($v_j$): Может быть интерпретирован как «ценность» или «полезность» единицы продукции, получаемой в $j$-м пункте, с учетом транспортных расходов.

Уравнение $u_i + v_j = c_{ij}$ для базисного маршрута означает, что для маршрута, который фактически используется в оптимальном плане, транспортные расходы ($c_{ij}$) точно уравновешиваются разницей в ОЗЦ между пунктами.

Оценка $\Delta_{ij} = c_{ij} — (u_i + v_j) > 0$ для свободного маршрута означает, что стоимость перевозки $c_{ij}$ по этому маршруту выше, чем совокупная ценность (ОЗЦ) этой перевозки. Следовательно, вводить этот маршрут невыгодно.

Построение Замкнутого Цикла и Пересчет Плана

Если в Шаге 3 обнаруживается отрицательная оценка ($\Delta_{kl} < 0$), это означает, что маршрут $(k, l)$ выгоден, и его введение позволит уменьшить общую стоимость перевозок.

Шаг 4. Выбор вводимой переменной
Выбирается клетка $(k, l)$ с наибольшей отрицательной оценкой $\min(\Delta_{ij} < 0)$. В эту клетку необходимо ввести перевозку.

Шаг 5. Построение Замкнутого Цикла
Чтобы сохранить условия баланса при введении новой перевозки $x_{kl}$, необходимо перераспределить объемы в других занятых клетках. Строится замкнутый цикл пересчета — ломаная линия, которая начинается и заканчивается в клетке $(k, l)$ и проходит только через занятые клетки (углы цикла).

Шаг 6. Пересчет плана

• Клетке $(k, l)$ присваивается знак «+».
• Остальным углам цикла поочередно присваиваются знаки «–», «+», «–» и т.д.
• Выбирается минимальный объем перевозки среди клеток со знаком «–» (обозначим его $\theta$). Это критическое значение $\theta$ определяет, какой максимальный объем можно перенести по циклу.
• Новые объемы перевозок рассчитываются:
  • Клетки «+» получают: $x’_{ij} = x_{ij} + \theta$
  • Клетки «–» получают: $x’_{ij} = x_{ij} — \theta$
• Клетка, в которой объем стал нулевым, становится свободной (выводится из базиса), а клетка $(k, l)$ становится занятой (вводится в базис).

Полученный новый опорный план имеет меньшую суммарную стоимость итеративно повторяет процесс с Шага 1 до достижения критерия оптимальности.

Особенности Постановки и Сведение Задач

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

Сведение Открытой Транспортной Задачи к Закрытой

Открытая (несбалансированная) транспортная задача — это модель, в которой суммарный запас не равен суммарной потребности ($\Sigma a_i \neq \Sigma b_j$). Метод потенциалов и стандартные алгоритмы применимы только к сбалансированной (закрытой) модели, поэтому несбалансированную задачу необходимо искусственно привести к канонической форме путем введения фиктивного пункта.

Случай 1: Избыток Запасов ($\Sigma a_i > \Sigma b_j$)

Если суммарное предложение превышает суммарный спрос, необходимо ввести фиктивного потребителя (пункт назначения $n+1$) с потребностью, равной небалансу: $b_{n+1} = \Sigma a_i — \Sigma b_j$. Тарифы на перевозку в этот фиктивный пункт принимаются равными нулю ($c_{i, n+1} = 0$), поскольку это не реальная перевозка, а лишь учет неиспользованного запаса.

Экономический смысл фиктивного потребителя: Переменная $x_{i, n+1}$, полученная в результате решения, представляет собой неиспользованные запасы (излишки), которые остаются у $i$-го поставщика.

Случай 2: Дефицит Запасов ($\Sigma a_i < \Sigma b_j$)

Если суммарный спрос превышает суммарное предложение, необходимо ввести фиктивного поставщика (пункт отправления $m+1$) с запасом, равным небалансу: $a_{m+1} = \Sigma b_j — \Sigma a_i$. Тарифы на перевозку из фиктивного пункта также равны нулю ($c_{m+1, j} = 0$).

Экономический смысл фиктивного поставщика: Переменная $x_{m+1, j}$, полученная в результате решения, представляет собой неудовлетворенный спрос (дефицит) у $j$-го потребителя.

Введение фиктивного пункта позволяет удовлетворить условие баланса, не меняя при этом реальную целевую функцию, поскольку все фиктивные перевозки имеют нулевую стоимость.

Задача о Назначениях как Частный Случай

Транспортная задача является базовой моделью, к которой могут быть сведены многие другие распределительные задачи линейного программирования. Наиболее ярким примером является задача о назначениях.

Задача о назначениях ставит целью распределить $m$ исполнителей на $n$ работ (при условии $m=n$) таким образом, чтобы общая стоимость или время выполнения работ было минимальным, причем каждый исполнитель выполняет ровно одну работу, и каждая работа выполняется ровно одним исполнителем.

В контексте ТЗ, задача о назначениях — это специфический случай, где:

• Запас каждого поставщика равен единице: $a_i = 1$.
• Потребность каждого потребителя равна единице: $b_j = 1$.

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

Заключение

Транспортная задача, уходящая корнями в классическую задачу Монжа об оптимальном переносе масс и получившая свое строгое математическое оформление благодаря работам Л. В. Канторовича, остается одним из наиболее важных и практичных инструментов в исследовании операций.

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

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

Список использованной литературы

1. Акулич И. Л. Математическое программирование в примерах и задачах. М.: Высш. шк., 1996. 319 с.
2. Балашевич В. А. Основы математического программирования. Минск: Вышэйш. шк., 1976. 173 с.
3. Вентцель Е. С. Исследование операций: задачи, принципы, методология. М.: Наука, 1988. 206 с.
4. Использование электронных таблиц Excel в инженерных расчетах: Учеб. пособие / В. Я. Гуськов, Р. Л. Кочубиевская, Г. А. Руев, Н. Н. Федорова. Новосибирск: НГАСУ, 1999. 80 с.
5. Деордица Ю. С., Нефедов Ю. М. Исследование операций в планировании и управлении. Киев: Вища шк., 1991. 270 с.
6. Зайченко Ю. П. Исследование операций. Киев: Вища шк., 1998. 320 с.
7. Зуховицкий С. М., Авдеева Л. И. Линейное и выпуклое программирование. М.: Наука, 1967. 460 с.
8. Калихман И. Л. Линейная алгебра и программирование. М.: Высш. шк., 1967. 428 с.
9. Калихман И. Л. Сборник задач по математическому программированию. М.: Высш. шк., 1975. 270 с.
10. Карманов В. Г. Математическое программирование. М.: Наука, 1986. 286 с.
11. Киселева Э. В., Соловьева С. И. Линейное и нелинейное программирование: Метод. указания. Новосибирск: НИСИ, 1987. 32 с.
12. Киселева Э. В., Соловьева С. И. Математическое программирование: Учеб. задания. Новосибирск: НГАС, 1996. 32 с.
13. Задачи транспортного типа: Метод. указания / Э. В. Киселева, С. И. Соловьева, М. С. Соппа, И. Н. Мухина. Новосибирск: НГАС, 1994. 32 с.
14. Конюховский П. В. Математические методы исследования операций в экономике. СПб., 2000. 208 с.
15. Кузнецов А. В., Сакович В. А., Холод Н. М. Высшая математика. Математическое программирование. Минск: Вища шк., 1994. 286 с.
16. Кузнецов Ю. Н., Кузубов В. И., Волощенко А. Б. Математическое программирование. М.: Высш. шк., 1980. 300 с.
17. Сакович В. А. Исследование операций. Минск: Вышэйш. шк., 1985. 256 с.
18. Таха Х. Введение в исследование операций: В 2 кн. М.: Мир, 1985. Кн. 1. 479 с.; Кн. 2. 496 с.
19. Методы построения начального опорного решения [Электронный ресурс]. URL: https://semestr.ru/art/tz-nachalnyy-plan.php (дата обращения: 28.10.2025).
20. Сравнение результатов применения методов решения транспортной задачи линейного программирования [Электронный ресурс]. URL: https://cyberleninka.ru/article/n/sravnenie-rezultatov-primeneniya-metodov-resheniya-transportnoy-zadachi-lineynogo-programmirovaniya (дата обращения: 28.10.2025).
21. Методы нахождения опорных планов [Электронный ресурс]. URL: https://allmath.ru/oper/oporniy_plan.php (дата обращения: 28.10.2025).
22. Транспортная задача [Электронный ресурс]. URL: https://sseu.ru/files/metodichki/ekonom-mat_metody/transportnaya-zadacha.pdf (дата обращения: 28.10.2025).
23. Транспортная задача и концентрация [Электронный ресурс]. URL: https://www.mccme.ru/circles/oim/kantorovich.pdf (дата обращения: 28.10.2025).
24. Л. В. Канторович и экономико-математическое моделирование: синтез реальности, математики и экономики [Электронный ресурс]. URL: https://cyberleninka.ru/article/n/l-v-kantorovich-i-ekonomiko-matematicheskoe-modelirovanie-sintez-realnosti-matematiki-i-ekonomiki (дата обращения: 28.10.2025).
25. Транспортная задача [Электронный ресурс]. URL: http://grigorevasv.ru/wp-content/uploads/2016/11/Транспортная-задача-ЛП.pdf (дата обращения: 28.10.2025).