Моделирование транспортной задачи в линейном программировании: полный гайд для академической работы

По данным опроса 180 специалистов в области транспортной логистики, проведенного ресурсом loglink.ru, комплексная автоматизация транспортной логистики в России способна сократить средний пробег единицы транспорта на 10-30% и снизить стоимость доставки одной тонны груза до европейского уровня, которая в среднем на 30% выше в России. Эти цифры убедительно демонстрируют потенциал оптимизации, скрытый в логистических процессах, и подчеркивают критическую роль математических методов в достижении этой экономии. В этом контексте транспортная задача, будучи одной из фундаментальных моделей линейного программирования, становится не просто академическим упражнением, но и мощным инструментом для повышения эффективности бизнеса.

Введение: Транспортная задача в мире оптимизации

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

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

В рамках данной академической работы мы предпримем всестороннее исследование транспортной задачи. Мы начнем с ее теоретических основ, углубляясь в определение, экономическую сущность и исторический контекст. Затем перейдем к строгому математическому описанию, представив целевую функцию и систему ограничений. Особое внимание будет уделено классическим методам решения – от построения начального опорного плана до методов оптимизации, таких как метод потенциалов, с подробными пошаговыми примерами. Мы также рассмотрим роль универсального симплекс-метода и объясним, почему специализированные алгоритмы часто оказываются более предпочтительными. Не останутся без внимания и вызовы реального мира: ограничения пропускной способности, динамические условия и сложности многопродуктовых задач. В завершение мы обсудим практические применения ТЗ, методы экономической интерпретации результатов и обзор современных программных средств, используемых для ее решения. Наша цель — представить полный гайд, который не только даст исчерпывающие знания по теме, но и послужит надежной основой для дальнейших исследований и практического применения.

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

Определение и экономическая сущность транспортной задачи

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

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

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

Исторический контекст: от Монжа до Данцига и Канторовича

История транспортной задачи — это увлекательная повесть о развитии математических методов и их приложении к реальным экономическим проблемам. Ее корни уходят в конец XVIII века, когда французский математик Гаспар Монж в 1781 году сформулировал задачу о «переносе масс» (или «задачу Монжа»), которая считается одной из первых постановок транспортной задачи. Монж искал способ перемещения сыпучего груза из одной области в другую с минимальными затратами, что по сути является геометрической интерпретацией современной ТЗ.

Однако до систематического изучения и решения транспортной задачи как таковой прошло еще почти полтора столетия. Значительный прорыв произошел в середине XX века. В Советском Союзе Леонид Канторович, будущий лауреат Нобелевской премии по экономике, в 1939 году в своей работе «Математические методы организации и планирования производства» предложил методы для оптимизации распределения сырья и оборудования, что фактически стало одним из первых подходов к решению задач линейного программирования, включая прототипы транспортной задачи. Независимо от него, примерно в то же время, советский математик Михаил Гавурин в 1941 году сформулировал и исследовал транспортную задачу в ее классическом виде, предложив алгоритмы ее решения.

На Западе параллельные исследования велись Джорджем Данцигом, который в 1947 году разработал симплекс-метод — универсальный алгоритм для решения задач линейного программирования. Именно Данциг впоследствии, в 1951 году, предложил метод северо-западного угла для нахождения начального опорного плана транспортной задачи, который был назван Чарнесом и Купером «правилом северо-западного угла».

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

Классификация транспортных задач: открытая и закрытая модели

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

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

Σmi=1 ai = Σnj=1 bj

где a_i — объем груза у i-го поставщика, b_j — потребность j-го потребителя. Это равенство является не просто условием, а необходимым и достаточным условием совместимости и разрешимости транспортной задачи. Если это условие выполняется, то существует хотя бы один план перевозок, при котором все грузы будут вывезены, а все потребности удовлетворены.

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

Σmi=1 ai ≠ Σnj=1 bj

В этом случае возможны два сценария:

1. Избыток предложения: Σmi=1 ai > Σnj=1 bj. Суммарный объем запасов превышает суммарный спрос. Это означает, что часть груза останется невывезенной.
2. Дефицит предложения: Σmi=1 ai < Σnj=1 bj. Суммарный спрос превышает суммарный объем запасов. В этом случае часть потребностей останется неудовлетворенной.

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

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

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

Математическая постановка транспортной задачи

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

Экономико-математическая модель: переменные, целевая функция и ограничения

Предположим, что у нас есть m пунктов отправления (поставщиков) и n пунктов назначения (потребителей). Для формализации задачи введем следующие обозначения:

• m — число пунктов отправления (поставщиков), индексируемых i от 1 до m.
• n — число пунктов назначения (потребителей), индексируемых j от 1 до n.
• a_i — объем груза, имеющегося у i-го поставщика (запас).
• b_j — потребность j-го потребителя в грузе (спрос).
• c_ij — стоимость перевозки единицы груза из i-го пункта отправления в j-й пункт назначения (тариф).
• x_ij — количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Это наши искомые переменные, которые формируют оптимальный план перевозок.

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

Z = Σmi=1 Σnj=1 cij xij → min

Эта функция суммирует произведения стоимости перевозки единицы груза на объем перевезенного груза для каждого возможного маршрута (i, j), стремясь к минимизации общей суммы.

Задача должна быть решена при соблюдении следующих систем ограничений:

1. По запасам поставщиков: Каждый поставщик должен отправить весь имеющийся у него груз (или его часть, если задача открытая и есть избыток, который будет отправлен фиктивному потребителю).

Σnj=1 xij = ai для i = 1, ..., m

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

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

Σmi=1 xij = bj для j = 1, ..., n

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

3. Условие неотрицательности: Количество перевозимого груза не может быть отрицательным.

xij ≥ 0 для всех i, j

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

Особенности структуры матрицы ограничений

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

Рассмотрим эти особенности:

1. Неотрицательность коэффициентов целевой функции: Все стоимости перевозок (c_ij) априори неотрицательны (c_ij ≥ 0). В реальной жизни не существует «отрицательных» затрат на перевозку, хотя в некоторых теоретических моделях могут использоваться штрафы или премии, которые формально могут быть отрицательными, но для классической ТЗ это нехарактерно.
2. Неотрицательность правых частей ограничений: Объемы запасов (a_i) и потребностей (b_j) всегда неотрицательны (a_i ≥ 0, b_j ≥ 0), так как они представляют собой физические объемы груза.
3. Коэффициенты при переменных в ограничениях принимают только два значения: нули и единицы. В уравнениях ограничений (Σnj=1 xij = ai и Σmi=1 xij = bj) каждая переменная x_ij либо присутствует с коэффициентом 1, либо отсутствует (что эквивалентно коэффициенту 0). Это формирует особую, «блочную» структуру матрицы ограничений.
4. Каждая переменная входит в систему ограничений ровно два раза: Один раз — в систему ограничений по запасам (в уравнение, соответствующее i-му поставщику: Σnj=1 xij = ai) и один раз — в систему ограничений по потребностям (в уравнение, соответствующее j-му потребителю: Σmi=1 xij = bj). Это свойство также существенно упрощает матрицу ограничений.
5. Ранг матрицы системы ограничительных уравнений транспортной задачи на единицу меньше числа уравнений: Если у нас m уравнений по поставщикам и n уравнений по потребителям, то общее число уравнений равно m + n. Однако, благодаря линейной зависимости этих уравнений (например, сумма всех уравнений по поставщикам равна сумме всех уравнений по потребителям, если задача сбалансирована), одно из уравнений является избыточным. Поэтому ранг матрицы равен r = m + n - 1. Это означает, что для нахождения базисного решения нам потребуется m + n - 1 базисных переменных (ненулевых перевозок).
6. Опорный план задачи имеет m + n — 1 базисных переменных и mn — (m + n — 1) свободных переменных, равных нулю. Количество занятых клеток (перевозок) в любом базисном решении (опорном плане) всегда будет равно m + n - 1. Остальные mn - (m + n - 1) переменных будут свободными, то есть их значения будут равны нулю, что означает отсутствие перевозок по соответствующим маршрутам.

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

Классические методы решения транспортной задачи: от опорного плана к оптимальному

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

Важным требованием к опорному плану является его ацикличность. Это означает, что в распределении перевозок в транспортной таблице из занятых (ненулевых) клеток нельзя образовать ни одного цикла. Цикл — это замкнутая ломаная линия, состоящая из отрезков, параллельных сторонам таблицы, и соединяющая только занятые клетки. Наличие цикла означало бы линейную зависимость векторов условий, соответствующих базисным переменным, что противоречит определению базиса. Ацикличность гарантирует линейную н��зависимость базисных переменных.

Построение начального опорного плана: методы и их эффективность

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

Метод северо-западного угла (МСЗУ)

Метод северо-западного угла (МСЗУ) — это один из самых простых и интуитивно понятных способов получения допустимого начального решения транспортной задачи. Он был предложен Данцигом в 1951 году и позднее назван Чарнесом и Купером «правилом северо-западного угла» из-за своего алгоритма.

Алгоритм МСЗУ:

1. Начало: Начинаем заполнение клеток таблицы с самой левой верхней клетки, то есть с клетки (1,1), которая находится в «северо-западном углу» таблицы.
2. Заполнение клетки: Сравниваем объем груза у текущего поставщика (a_i) и потребность текущего потребителя (b_j). В клетку (i,j) записываем меньшее из этих двух значений: x_ij = min(a_i, b_j).
3. Корректировка запасов/потребностей:
   • Если a_i < b_j, это означает, что i-й поставщик полностью исчерпал свой запас. Строка i «закрывается» (исключается из дальнейшего рассмотрения), а потребность j-го потребителя уменьшается на x_ij (b_j = b_j — x_ij). Переходим к следующей строке (i+1, j).
   • Если a_i > b_j, это означает, что j-й потребитель полностью удовлетворил свою потребность. Столбец j «закрывается», а запас i-го поставщика уменьшается на x_ij (a_i = a_i — x_ij). Переходим к следующему столбцу (i, j+1).
   • Если a_i = b_j, то «закрываются» и строка i, и столбец j. В этом случае, чтобы обеспечить m + n - 1 базисных переменных и избежать циклов, необходимо одну из оставшихся клеток в соседней строке или столбце сделать базисной, присвоив ей нулевую перевозку. Это называется вырожденным опорным планом. Переходим к следующей строке (i+1, j) или столбцу (i, j+1) по выбору.
4. Продолжение: Повторяем шаги 2 и 3 до тех пор, пока все запасы поставщиков не будут распределены, а все потребности потребителей не будут удовлетворены. Заполнение продолжается вниз и вправо, заканчивая последней клеткой для перевозки.

Преимущества: Простота и понятность алгоритма. Не требует сравнения стоимостей, что ускоряет процесс ручного расчета.

Недостатки: Низкая эффективность. Сформированный план в большинстве случаев далек от оптимального, так как метод полностью игнорирует стоимости перевозок (c_ij). Это означает, что для достижения оптимального решения потребуется значительное число итераций на следующем этапе оптимизации. Метод северо-западного угла является наименее эффективным для получения оптимального решения.

Пример с иллюстрацией:

Рассмотрим следующую транспортную задачу:

Поставщик/Потребитель	П1 (b1=70)	П2 (b2=30)	П3 (b3=50)	Запас (ai)
С1 (a1=50)	c11=5	c12=3	c13=8	50
С2 (a2=60)	c21=6	c22=7	c23=4	60
С3 (a3=40)	c31=3	c32=5	c33=9	40
Потребность (bj)	70	30	50	Σa=150, Σb=150

Задача сбалансирована: 50 + 60 + 40 = 150, и 70 + 30 + 50 = 150.

Шаг 1: Клетка (1,1)
a₁ = 50, b₁ = 70.
x₁₁ = min(50, 70) = 50.
Запас С1 исчерпан (a₁ = 0). Потребность П1 уменьшается (b₁ = 70 — 50 = 20).
Таблица:

Поставщик/Потребитель	П1 (b1=20)	П2 (b2=30)	П3 (b3=50)	Запас (ai)
С1 (a1=0)	50			0
С2 (a2=60)	c21=6	c22=7	c23=4	60
С3 (a3=40)	c31=3	c32=5	c33=9	40
Потребность (bj)	20	30	50

Шаг 2: Клетка (2,1) (С1 закрыт, переходим к С2)
a₂ = 60, b₁ = 20.
x₂₁ = min(60, 20) = 20.
Потребность П1 исчерпана (b₁ = 0). Запас С2 уменьшается (a₂ = 60 — 20 = 40).
Таблица:

Поставщик/Потребитель	П1 (b1=0)	П2 (b2=30)	П3 (b3=50)	Запас (ai)
С1 (a1=0)	50			0
С2 (a2=40)	20	c22=7	c23=4	40
С3 (a3=40)		c32=5	c33=9	40
Потребность (bj)	0	30	50

Шаг 3: Клетка (2,2) (П1 закрыт, переходим к П2)
a₂ = 40, b₂ = 30.
x₂₂ = min(40, 30) = 30.
Потребность П2 исчерпана (b₂ = 0). Запас С2 уменьшается (a₂ = 40 — 30 = 10).
Таблица:

Поставщик/Потребитель	П1 (b1=0)	П2 (b2=0)	П3 (b3=50)	Запас (ai)
С1 (a1=0)	50			0
С2 (a2=10)	20	30	c23=4	10
С3 (a3=40)			c33=9	40
Потребность (bj)	0	0	50

Шаг 4: Клетка (2,3) (П2 закрыт, переходим к П3)
a₂ = 10, b₃ = 50.
x₂₃ = min(10, 50) = 10.
Запас С2 исчерпан (a₂ = 0). Потребность П3 уменьшается (b₃ = 50 — 10 = 40).
Таблица:

Поставщик/Потребитель	П1 (b1=0)	П2 (b2=0)	П3 (b3=40)	Запас (ai)
С1 (a1=0)	50			0
С2 (a2=0)	20	30	10	0
С3 (a3=40)			c33=9	40
Потребность (bj)	0	0	40

Шаг 5: Клетка (3,3) (С2 закрыт, переходим к С3)
a₃ = 40, b₃ = 40.
x₃₃ = min(40, 40) = 40.
Запас С3 исчерпан (a₃ = 0). Потребность П3 исчерпана (b₃ = 0).

Итоговый опорный план (МСЗУ):

Поставщик/Потребитель	П1	П2	П3	Запас
С1	50	0	0	50
С2	20	30	10	60
С3	0	0	40	40
Потребность	70	30	50

Количество занятых клеток = 5. m+n-1 = 3+3-1 = 5. План невырожденный.
Общие затраты = 50·5 + 20·6 + 30·7 + 10·4 + 40·9 = 250 + 120 + 210 + 40 + 360 = 980.

Метод минимальной стоимости (наименьших стоимостей/элемента)

Метод минимальной стоимости, также известный как метод наименьших стоимостей или метода минимального элемента, представляет собой более «умный» подход к построению начального опорного плана по сравнению с МСЗУ. Его основное преимущество в том, что он учитывает тарифы на перевозку с самого начала, что, как правило, позволяет получить более экономичный первоначальный план, приближенный к оптимальному.

Алгоритм метода минимальной стоимости:

1. Выбор клетки: Из всех доступных (незакрытых) клеток таблицы выбирается та, которая имеет минимальную стоимость перевозки (c_ij). Если таких клеток несколько, выбор может быть произвольным (например, первая по порядку строки, затем столбца).
2. Заполнение клетки: В выбранную клетку (i,j) записывается максимально возможное количество груза, то есть xij = min(ai, bj).
3. Корректировка запасов/потребностей:
   • Если a_i < b_j, строка i «закрывается» (ее запас исчерпан), и потребность j-го потребителя уменьшается на x_ij (b_j = b_j — x_ij).
   • Если a_i > b_j, столбец j «закрывается» (его потребность удовлетворена), и запас i-го поставщика уменьшается на x_ij (a_i = a_i — x_ij).
   • Если a_i = b_j, то «закрываются» и строка i, и столбец j. Как и в МСЗУ, для невырожденности опорного плана, одна из оставшихся клеток в соседней строке или столбце должна быть сделана базисной с нулевой перевозкой.
4. Продолжение: Исключенные строки и/или столбцы больше не участвуют в поиске минимальной стоимости. Процесс повторяется для оставшейся части таблицы до тех пор, пока все запасы не будут распределены, а все потребности не будут удовлетворены.

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

Недостатки: Может быть чуть сложнее в ручном расчете, так как требует постоянного поиска минимального элемента среди оставшихся клеток.

Пример с иллюстрацией (используем ту же задачу):

Поставщик/Потребитель	П1 (b1=70)	П2 (b2=30)	П3 (b3=50)	Запас (ai)
С1 (a1=50)	c11=5	c12=3	c13=8	50
С2 (a2=60)	c21=6	c22=7	c23=4	60
С3 (a3=40)	c31=3	c32=5	c33=9	40
Потребность (bj)	70	30	50	Σa=150, Σb=150

Шаг 1: Поиск минимальной стоимости.
Минимальная стоимость c₁₂ = 3 (также есть c₃₁ = 3). Выберем c₁₂.
a₁ = 50, b₂ = 30.
x₁₂ = min(50, 30) = 30.
Потребность П2 исчерпана (b₂ = 0). Запас С1 уменьшается (a₁ = 50 — 30 = 20).
Таблица:

Поставщик/Потребитель	П1 (b1=70)	П2 (b2=0)	П3 (b3=50)	Запас (ai)
С1 (a1=20)	c11=5	30	c13=8	20
С2 (a2=60)	c21=6		c23=4	60
С3 (a3=40)	c31=3		c33=9	40
Потребность (bj)	70	0	50

Шаг 2: Поиск минимальной стоимости среди оставшихся.
Минимальная стоимость c₃₁ = 3 (П2 исключен).
a₃ = 40, b₁ = 70.
x₃₁ = min(40, 70) = 40.
Запас С3 исчерпан (a₃ = 0). Потребность П1 уменьшается (b₁ = 70 — 40 = 30).
Таблица:

Поставщик/Потребитель	П1 (b1=30)	П2 (b2=0)	П3 (b3=50)	Запас (ai)
С1 (a1=20)	c11=5	30	c13=8	20
С2 (a2=60)	c21=6		c23=4	60
С3 (a3=0)	40			0
Потребность (bj)	30	0	50

Шаг 3: Поиск минимальной стоимости среди оставшихся.
Минимальная стоимость c₂₃ = 4.
a₂ = 60, b₃ = 50.
x₂₃ = min(60, 50) = 50.
Потребность П3 исчерпана (b₃ = 0). Запас С2 уменьшается (a₂ = 60 — 50 = 10).
Таблица:

Поставщик/Потребитель	П1 (b1=30)	П2 (b2=0)	П3 (b3=0)	Запас (ai)
С1 (a1=20)	c11=5	30	c13=8	20
С2 (a2=10)	c21=6		50	10
С3 (a3=0)	40			0
Потребность (bj)	30	0	0

Шаг 4: Поиск минимальной стоимости среди оставшихся.
Минимальная стоимость c₁₁ = 5 (c₂₁ = 6).
a₁ = 20, b₁ = 30.
x₁₁ = min(20, 30) = 20.
Запас С1 исчерпан (a₁ = 0). Потребность П1 уменьшается (b₁ = 30 — 20 = 10).
Таблица:

Поставщик/Потребитель	П1 (b1=10)	П2 (b2=0)	П3 (b3=0)	Запас (ai)
С1 (a1=0)	20	30		0
С2 (a2=10)	c21=6		50	10
С3 (a3=0)	40			0
Потребность (bj)	10	0	0

Шаг 5: Последняя клетка (2,1).
a₂ = 10, b₁ = 10.
x₂₁ = min(10, 10) = 10.
Запас С2 исчерпан (a₂ = 0). Потребность П1 исчерпана (b₁ = 0).

Итоговый опорный план (Метод минимальной стоимости):

Поставщик/Потребитель	П1	П2	П3	Запас
С1	20	30	0	50
С2	10	0	50	60
С3	40	0	0	40
Потребность	70	30	50

Количество занятых клеток = 5. m+n-1 = 3+3-1 = 5. План невырожденный.
Общие затраты = 20·5 + 30·3 + 10·6 + 50·4 + 40·3 = 100 + 90 + 60 + 200 + 120 = 570.

Как видим, метод минимальной стоимости дал значительно меньшие затраты (570) по сравнению с методом северо-западного угла (980) уже на этапе построения начального опорного плана. Это подчеркивает важность учета стоимостей на ранних этапах оптимизации.

Метод аппроксимации Фогеля и метод двойного предпочтения

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

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

Алгоритм метода Фогеля:

1. Вычисление «штрафов»: Для каждой строки (поставщика) и каждого столбца (потребителя) вычисляется «штраф» (разность или «пенальти»). Штраф для строки/столбца равен разнице между наименьшей и следующей за ней по величине стоимостью перевозки в этой строке/столбце.
2. Выбор строки/столбца: Выбирается строка или столбец с наибольшим штрафом. Это означает, что неиспользование наименьшей стоимости в этом ряду приведет к наибольшим дополнительным затратам.
3. Заполнение клетки: В выбранной строке или столбце находится клетка с наименьшей стоимостью. В эту клетку записывается максимально возможное количество груза (min(ai, bj)).
4. Корректировка и исключение: Обновляются запасы и потребности. Строка или столбец, запас/потребность которого исчерпаны, исключаются из дальнейшего рассмотрения. Если одновременно исчерпаны и запас, и потребность, исключается только один из них (произвольно), а для поддержания невырожденности в оставшийся ряд (который не был исключен) добавляется фиктивная нулевая перевозка в любую свободную клетку.
5. Повторение: Шаги 1-4 повторяются до тех пор, пока все запасы не будут распределены, а все потребности не будут удовлетворены.

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

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

Детализация пошагового примера для метода Фогеля может быть довольно объемн��й из-за итеративного вычисления штрафов. Однако, его основная идея заключается в том, чтобы сосредоточиться на тех строках или столбцах, где разница между самым дешевым и вторым по дешевизне маршрутом наибольшая, тем самым «наказывая» за выбор более дорогого маршрута. Это позволяет избежать изначально невыгодных решений.

Пример с иллюстрацией для метода Фогеля (используем ту же задачу):

Поставщик/Потребитель	П1 (70)	П2 (30)	П3 (50)	Запас (ai)	Штраф (строки)
С1 (50)	c11=5	c12=3	c13=8	50	2 (5-3)
С2 (60)	c21=6	c22=7	c23=4	60	2 (6-4)
С3 (40)	c31=3	c32=5	c33=9	40	2 (5-3)
Потребность (bj)	70	30	50
Штраф (столбцы)	2 (5-3)	2 (5-3)	4 (8-4)

• Шаг 1: Вычисляем штрафы.
  • С1: min(3,5,8) = 3, next_min = 5. Штраф = 5-3 = 2.
  • С2: min(4,6,7) = 4, next_min = 6. Штраф = 6-4 = 2.
  • С3: min(3,5,9) = 3, next_min = 5. Штраф = 5-3 = 2.
  • П1: min(3,5,6) = 3, next_min = 5. Штраф = 5-3 = 2.
  • П2: min(3,5,7) = 3, next_min = 5. Штраф = 5-3 = 2.
  • П3: min(4,8,9) = 4, next_min = 8. Штраф = 8-4 = 4.

Наибольший штраф равен 4 для столбца П3. В П3 выбираем клетку с минимальной стоимостью: c₂₃ = 4.
x23 = min(a2=60, b3=50) = 50.
Обновляем: a2 = 60-50 = 10, b3 = 0. Столбец П3 закрыт.

• Шаг 2: Пересчитываем штрафы для оставшейся таблицы.

Поставщик/Потребитель	П1 (70)	П2 (30)	П3 (0)	Запас (ai)	Штраф (строки)
С1 (50)	c11=5	c12=3		50	2 (5-3)
С2 (10)	c21=6	c22=7	50	10	1 (7-6)
С3 (40)	c31=3	c32=5		40	2 (5-3)
Потребность (bj)	70	30	0
Штраф (столбцы)	2 (5-3)	2 (5-3)

Наибольший штраф равен 2 (их много, выберем, например, строку С1). В С1 выбираем клетку с минимальной стоимостью: c₁₂ = 3.
x12 = min(a1=50, b2=30) = 30.
Обновляем: a1 = 50-30 = 20, b2 = 0. Столбец П2 закрыт.

• Шаг 3: Пересчитываем штрафы.

Поставщик/Потребитель	П1 (70)	П2 (0)	П3 (0)	Запас (ai)	Штраф (строки)
С1 (20)	c11=5	30		20	—
С2 (10)	c21=6		50	10	—
С3 (40)	c31=3			40	—
Потребность (bj)	70	0	0
Штраф (столбцы)	2 (5-3)

Наибольший штраф 2 для столбца П1. В П1 выбираем клетку с минимальной стоимостью: c₃₁ = 3.
x31 = min(a3=40, b1=70) = 40.
Обновляем: a3 = 0, b1 = 70-40 = 30. Строка С3 закрыта.

• Шаг 4: Остались две клетки, П1 с потребностью 30, С1 с запасом 20 и С2 с запасом 10.
  x11 = min(a1=20, b1=30) = 20.
  Обновляем: a1 = 0, b1 = 30-20 = 10. Строка С1 закрыта.
• Шаг 5: Осталась одна клетка (2,1).
  x21 = min(a2=10, b1=10) = 10.
  Обновляем: a2 = 0, b1 = 0.

Итоговый опорный план (Метод Фогеля):

Поставщик/Потребитель	П1	П2	П3	Запас
С1	20	30	0	50
С2	10	0	50	60
С3	40	0	0	40
Потребность	70	30	50

Общие затраты = 20·5 + 30·3 + 10·6 + 50·4 + 40·3 = 100 + 90 + 60 + 200 + 120 = 570.
В данном примере, метод Фогеля дал такой же результат, как и метод минимальной стоимости. Часто метод Фогеля дает либо оптимальный план, либо очень близкий к нему, что делает его крайне ценным для сокращения последующих итераций.

Сравнительный анализ методов построения опорного плана

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

Критерий	Метод северо-западного угла (МСЗУ)	Метод минимальной стоимости	Метод аппроксимации Фогеля
Сложность реализации	Очень низкая. Заполнение начинается с фиксированной точки (верхний левый угол) и не требует сравнения стоимостей.	Средняя. Требует поиска минимальной стоимости на каждом шаге среди оставшихся доступных клеток.	Высокая. Требует вычисления «штрафов» (разностей двух наименьших стоимостей) для каждой строки/столбца на каждом шаге.
Качество начального решения (близость к оптимуму)	Низкое. Часто дает очень неоптимальный начальный план, так как полностью игнорирует стоимости перевозок.	Среднее. Учитывает стоимости, что позволяет получить более экономичный начальный план.	Высокое. Как правило, дает план, наиболее близкий к оптимальному, а иногда и оптимальный. Это связано с учетом «штрафов» за неиспользование выгодных маршрутов.
Число итераций для оптимизации	Высокое. Из-за неоптимальности начального плана потребуется много итераций для достижения оптимального решения.	Среднее. Меньше, чем у МСЗУ, но, возможно, больше, чем у Фогеля.	Низкое. Поскольку начальный план близок к оптимуму, требуется меньше итераций для его доведения до оптимального.
Применимость	Подходит для быстрого получения любого допустимого решения, когда скорости расчета не критичны или нужна только проверка разрешимости.	Хороший баланс между простотой и качеством, часто используется на практике.	Рекомендуется для получения наилучшего начального решения, особенно для больших задач, где сокращение итераций критично.

Таким образом, если цель — максимальная простота и скорость получения любого допустимого плана, МСЗУ — подходящий выбор. Однако для более эффективного решения, особенно в автоматизированных системах или при ручном расчете, где каждая итерация дорога, предпочтительнее методы минимальной стоимости или, что еще лучше, метод аппроксимации Фогеля.

Метод потенциалов: алгоритм оптимизации

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

Алгоритм метода потенциалов:

1. Построение опорного плана. Как уже было сказано, это первый шаг. Опорный план может быть построен любым из методов: северо-западного угла, минимальной стоимости или аппроксимации Фогеля. Важно, чтобы этот план был ациклическим и невырожденным (или вырожденным, но с добавлением нулевых перевозок для соблюдения условия m+n-1 базисных переменных).
2. Вычисление потенциалов поставщиков (u_i) и потребителей (v_j). Для каждой занятой (базисной) клетки (i,j) в транспортной таблице должно выполняться равенство:
   ui + vj = cij
   Эта система из m + n - 1 уравнений с m + n неизвестными (потенциалами) является линейно зависимой. Для ее решения один из потенциалов (например, u₁) принимается равным нулю. После этого остальные потенциалы могут быть последовательно вычислены.
3. Вычисление оценок (Δ_ij) для всех свободных (небазисных) клеток. Для каждой свободной клетки (i,j) вычисляется ее оценка по формуле:
   Δij = cij − (ui + vj)
   Экономический смысл оценки Δ_ij заключается в том, что она показывает изменение общей стоимости перевозок, если начать перевозку единицы груза по данному маршруту (i,j).
4. Проверка опорного плана на оптимальность.
   • Если все оценки Δij ≥ 0, то текущий опорный план является оптимальным. Дополнительные перевозки по свободным маршрутам не приведут к уменьшению общих затрат.
   • Если среди оценок есть хотя бы одно отрицательное число (Δij < 0), то текущий план не оптимален, и его следует улучшить.
5. Выбор входящей переменной и построение цикла пересчета.
   • Если план не оптимален, выбирается свободная клетка с наибольшим отрицательным значением Δ_ij. Переменная x_ij, соответствующая этой клетке, становится входящей базисной переменной.
   • Для этой входящей клетки строится цикл пересчета (замкнутая ломаная линия). Цикл начинается и заканчивается во входящей свободной клетке. Все остальные вершины цикла должны быть в занятых (базисных) клетках. Стороны цикла должны быть параллельны сторонам таблицы. Количество звеньев в цикле всегда четное.
   • Вершинам цикла поочередно присваиваются знаки + и −, начиная со знака + для входящей свободной клетки. Знаки должны чередоваться при переходе от одной занятой клетки к другой.
6. Нахождение минимальной перевозки и перераспределение груза по циклу.
   • Среди всех занятых клеток цикла со знаком минус (−) выбирается клетка с минимальным объемом перевозки. Пусть это значение будет θ. Это значение θ определяет, сколько груза может быть перераспределено.
   • Выполняется перераспределение груза:
     • К объему перевозок в клетках со знаком + прибавляется θ.
     • Из объема перевозок в клетках со знаком − вычитается θ.
   • Одна из клеток со знаком −, которая имела минимальную перевозку θ, обнуляется и становится свободной (выходит из базиса). Входящая переменная, получившая значение θ, становится базисной.
7. Повторение. Процесс возвращается к шагу 2 (вычисление потенциалов) и повторяется до тех пор, пока все оценки свободных клеток не станут неотрицательными.

Пример с иллюстрацией (продолжим с опорного плана, полученного методом минимальной стоимости):

Опорный план:

Поставщик/Потребитель	П1 (70)	П2 (30)	П3 (50)	Запас (ai)	ui
С1 (50)	x11=20 (c=5)	x12=30 (c=3)	x13	50	u1
С2 (60)	x21=10 (c=6)	x22	x23=50 (c=4)	60	u2
С3 (40)	x31=40 (c=3)	x32	x33	40	u3
Потребность (bj)	70	30	50
vj	v1	v2	v3

Шаг 2: Вычисление потенциалов.
Примем u1 = 0.
Используем ui + vj = cij для занятых клеток:

1. Клетка (1,1): x₁₁=20, c₁₁=5. u1 + v1 = 5 → 0 + v1 = 5 → v1 = 5.
2. Клетка (1,2): x₁₂=30, c₁₂=3. u1 + v2 = 3 → 0 + v2 = 3 → v2 = 3.
3. Клетка (2,1): x₂₁=10, c₂₁=6. u2 + v1 = 6 → u2 + 5 = 6 → u2 = 1.
4. Клетка (2,3): x₂₃=50, c₂₃=4. u2 + v3 = 4 → 1 + v3 = 4 → v3 = 3.
5. Клетка (3,1): x₃₁=40, c₃₁=3. u3 + v1 = 3 → u3 + 5 = 3 → u3 = -2.

Потенциалы: u = [0, 1, -2], v = [5, 3, 3].

Шаг 3: Вычисление оценок Δ_ij для свободных клеток.
Формула: Δij = cij − (ui + vj)

1. Клетка (1,3): c₁₃=8. Δ13 = 8 − (u1 + v3) = 8 − (0 + 3) = 8 − 3 = 5.
2. Клетка (2,2): c₂₂=7. Δ22 = 7 − (u2 + v2) = 7 − (1 + 3) = 7 − 4 = 3.
3. Клетка (3,2): c₃₂=5. Δ32 = 5 − (u3 + v2) = 5 − (-2 + 3) = 5 − 1 = 4.
4. Клетка (3,3): c₃₃=9. Δ33 = 9 − (u3 + v3) = 9 − (-2 + 3) = 9 − 1 = 8.

Шаг 4: Проверка оптимальности.
Все Δij ≥ 0. Следовательно, текущий план является оптимальным. Общие затраты Z = 570.
В данном случае опорный план, полученный методом минимальной стоимости, оказался сразу оптимальным. Если бы были отрицательные оценки, мы бы перешли к шагам 5-7.

Пример Шага 5-7 (гипотетический, если бы Δ22 = -2, при c22=7, u2=1, v2=3):
Предположим, Δ22 было бы -2 (хотя в нашем примере оно 3). Выбираем клетку (2,2) как входящую.
Построим цикл: (2,2) → (1,2) → (1,1) → (2,1) → (2,2)
Клетки цикла и их знаки:
(2,2) — (+)
(1,2) — (−) x12=30
(1,1) — (+) x11=20
(2,1) — (−) x21=10

Минимальная перевозка в клетках со знаком минус: min(x12=30, x21=10) = 10. Пусть θ = 10.
Перераспределение:
x22 = 0 + 10 = 10
x12 = 30 - 10 = 20
x11 = 20 + 10 = 30
x21 = 10 - 10 = 0

Новый опорный план:

Поставщик/Потребитель	П1 (70)	П2 (30)	П3 (50)	Запас (ai)
С1 (50)	x11=30 (c=5)	x12=20 (c=3)	x13	50
С2 (60)	x21=0 (c=6)	x22=10 (c=7)	x23=50 (c=4)	60
С3 (40)	x31=40 (c=3)	x32	x33	40
Потребность (bj)	70	30	50

Переменная x₂₁ вышла из базиса (стала 0), x₂₂ вошла в базис (стала 10). Далее процесс повторяется с шага 2 для нового опорного плана.

Распределительный метод и его связь с методом потенциалов

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

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

Алгоритм распределительного метода включает следующие общие этапы:

1. Нахождение первоначального ациклического плана. Этот этап совпадает с первым шагом метода потенциалов. Используются методы построения начального опорного плана (северо-западного угла, минимальной стоимости, Фогеля). Важно убедиться, что план ацикличен, то есть из занятых клеток нельзя образовать ни одного цикла, что гарантирует линейную независимость базисных переменных.
2. Проверка опорного плана на оптимальность. На этом этапе выявляется, есть ли возможность улучшить текущий план, то есть уменьшить общие транспортные расходы. В контексте метода потенциалов это делается путем вычисления оценок Δ_ij для свободных клеток. Если все оценки неотрицательны, план оптимален.
3. Переход к новому опорному плану, если предыдущий не оптимален. Если найдены отрицательные оценки, это указывает на то, что план можно улучшить. Происходит однократное замещение одной базисной переменной (которая выходит из базиса и становится свободной, равной нулю) на свободную переменную (которая входит в базис и становится ненулевой). Это замещение осуществляется путем построения цикла пересчета, как это описано в методе потенциалов. В результате этого перераспределения грузов по циклу общие затраты уменьшаются.
4. Повторение. Шаги 2 и 3 повторяются до тех пор, пока не будет достигнут оптимальный план, то есть пока все оценки свободных клеток не станут неотрицательными.

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

• Определения, является ли план оптимальным (через потенциалы и оценки).
• Выбора, какой маршрут ввести в базис (наибольшее отрицательное Δ_ij).
• Формирования нового опорного п��ана (через цикл пересчета).

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

Симплекс-метод в контексте транспортной задачи

Общая применимость симплекс-метода

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

Для того чтобы решить транспортную задачу симплекс-методом, необходимо выполнить следующие шаги:

1. Формулировка задачи: Сначала транспортная задача должна быть четко сформулирована как задача линейного программирования со всеми переменными (x_ij), целевой функцией (Σcijxij → min) и системой ограничений (по поставщикам и потребителям).
2. Приведение к стандартной форме: Если ограничения представлены в виде равенств (как в классической ТЗ), они уже в значительной степени соответствуют стандартной форме. Условия неотрицательности переменных также присутствуют.
3. Инициализация симплекс-таблицы: Далее формируется начальная симплекс-таблица, которая включает коэффициенты целевой функции, коэффициенты при переменных в ограничениях и правые части ограничений. Для определения начального базисного решения может потребоваться введение искусственных переменных, если в матрице ограничений нет единичного базиса.
4. Применение симплекс-алгоритма: Затем последовательно применяются итерации симплекс-метода:
   • Определение входящей базисной переменной (по критерию оптимальности, например, наименьший отрицательный коэффициент в строке целевой функции для задачи минимизации).
   • Определение выходящей базисной переменной (по минимальному отношению правых частей ограничений к положительным коэффициентам входящей переменной).
   • Пересчет симплекс-таблицы путем элементарных преобразований.
   • Повторение до достижения оптимального решения (когда все коэффициенты в строке целевой функции соответствуют критерию оптимальности).

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

Особенности адаптации и вычислительная эффективность

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

Основные изменения для адаптации симплекс-метода к ТЗ:

• Размерность задачи: Классическая транспортная задача с m поставщиками и n потребителями имеет mn переменных и m + n ограничений. Для задачи с m + n - 1 независимыми ограничениями, симплекс-таблица может стать очень громоздкой. Например, для задачи 10 поставщиков и 10 потребителей потребуется 100 переменных и 20 ограничений.
• Разреженность матрицы ограничений: Матрица ограничений транспортной задачи является очень разреженной, то есть большинство ее элементов равны нулю, а ненулевые коэффициенты — это только единицы. Общий симплекс-метод не использует это структурное преимущество. Он обрабатывает все коэффициенты одинаково, что приводит к избыточным вычислениям.
• Добавление дополнительных переменных: Для формирования исходной системы линейных уравнений симплекс-метода, особенно при наличии неравенств или для создания начального базиса, могут потребоваться дополнительные переменные (базисные, искусственные).

Почему специализированные методы вычислительно более эффективны?

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

1. Сокращение числа арифметических операций: Метод потенциалов оперирует непосредственно с транспортной таблицей, а не с большой симплекс-таблицей. Вычисление потенциалов и оценок, а также построение циклов пересчета значительно проще и быстрее, чем полные итерации симплекс-метода с матричными преобразованиями.
2. Экономия памяти: Не требуется хранить всю громоздкую симплекс-таблицу. Достаточно хранить только транспортную таблицу с объемами перевозок и стоимостями.
3. Быстрое достижение оптимума: Начальные опорные планы, полученные методами вроде Фогеля, уже достаточно близки к оптимальному, что сокращает число итераций.
4. Интуитивность: Алгоритмы, такие как метод потенциалов, более наглядны и интуитивно понятны для специалистов по логистике, работающих непосредственно с планами перевозок.

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

Вызовы и ограничения транспортной задачи в реальных условиях

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

Ограничения на пропускную способность маршрутов и запрет перевозок

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

Математическая модель такой задачи включает дополнительное ограничение для каждой такой «проблемной» дуги (маршрута):

xij ≤ dij

где d_ij — максимальная пропускная способность коммуникации между i-м поставщиком и j-м потребителем.

Эти ограничения вносят существенные коррективы в свойства задачи:

• Влияние на разрешимость: Условие сбалансированности (Σai = Σbj) перестает быть достаточным для разрешимости задачи. Даже если общий запас равен общему спросу, из-за ограничений пропускной способности может оказаться невозможным перевезти весь груз.
• Усложнение решения: Для учета ограничений на пропускную способность могут быть приспособлены обычные вычислительные алгоритмы ТЗ, например, метод потенциалов, но с модификациями. При вычислении оценок свободных клеток необходимо учитывать, что некоторые маршруты могут быть «насыщены» (перевозка по ним достигла d_ij), и в этом случае их оценка может измениться или они могут быть исключены из рассмотрения для увеличения потока. Для строгих ограничений, когда xlm > a (перевозка не менее a) или xlm < b (перевозка не более b), применяются специальные подходы, включающие корректировку запасов/потребностей или введение фиктивных потребителей с большими тарифами (M >> 1).

Запрет перевозок по определенным маршрутам является частным случаем ограничения на пропускную способность, где dij = 0. Моделируется он крайне просто: назначением сколь угодно большой (штрафной) стоимости перевозки (M) для такого маршрута. Таким образом, в целевой функции этот маршрут становится настолько невыгодным, что система оптимизации никогда не выберет его, если есть хоть какая-то альтернатива.

Динамические условия и нечеткие данные: выход за рамки статической модели

Классическая транспортная задача относится к задачам со статичными данными. Это означает, что все параметры задачи — объемы запасов (a_i), потребности (b_j) и тарифы (c_ij) — предполагаются известными, фиксированными и неизменными на протяжении всего периода планирования. Такое упрощение, хотя и позволяет эффективно решить задачу, далеко не всегда соответствует реальным экономическим системам, где данные могут быть динамичными и нечеткими.

• Динамические условия: В логистике запасы и потребности могут меняться в течение времени (сезонные колебания, внезапные заказы, сбои поставок). Тарифы на перевозки могут зависеть от времени суток, погодных условий, цен на топливо. В таких случаях статическая модель становится неточной. Для учета динамики применяются следующие подходы:
  • Многопериодные модели: Разработка транспортных задач для нескольких последовательных периодов, где решение каждого периода влияет на начальные условия следующего.
  • Модели с изменяющимися параметрами: Использование методов параметрического программирования, где решение ищется для диапазона возможных значений параметров.
  • Эвристические подходы и симуляция: В сильно динамичных средах могут применяться эвристические алгоритмы и методы симуляции для получения «достаточно хороших» решений в реальном времени.
• Нечеткие данные: В реальности параметры a_i, b_j, c_ij могут быть неточными, приближенными или даже неопределенными. Например, «примерная потребность» или «ориентировочная стоимость». Классическая ТЗ не справляется с такой неопределенностью. Для этого используются:
  • Стохастическое программирование: Когда параметры являются случайными величинами с известным распределением вероятностей.
  • Нечеткое линейное программирование: Когда параметры описываются нечеткими числами или интервалами, и цель — найти «наиболее приемлемое» решение в условиях нечеткости.
  • Анализ чувствительности: Позволяет оценить, как изменение исходных данных повлияет на оптимальное решение, давая представление о «надежности» плана.

Применение ТЗ в сложных экономических задачах часто ограничено именно этим упрощенным описанием производственных возможностей и динамики рынка. Как же обеспечить адекватность модели в условиях постоянно меняющихся внешних факторов?

Многоиндексные (многопродуктовые) транспортные задачи

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

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

• x_ijk: количество груза k-го типа, перевозимого из i-го пункта отправления в j-й пункт назначения.
• c_ijk: стоимость перевозки единицы груза k-го типа из i-го пункта отправления в j-й пункт назначения.

Целевая функция становится:

Z = Σmi=1 Σnj=1 Σpk=1 cijk xijk → min

где p — число видов продукта.

Система ограничений также усложняется:

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

Методы решения многоиндексных задач:
Вычислительная сложность решения быстро возрастает с увеличением размерности (количества индексов и их значений). Для решения таких задач применяются:

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

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

Практические применения и экономическая интерпретация результатов

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

Типичные сценарии применения в логистике, производстве и экономике

1. Оптимизация поставок сырья и материалов на производственные предприятия: Предприятия могут иметь несколько поставщиков сырья, расположенных в разных точках, и несколько производственных площадок. ТЗ позволяет определить, от какого поставщика и сколько сырья следует доставлять на каждую производственную площадку, чтобы минимизировать общие логистические затраты.
2. Оптимизация доставок товаров со складов в розничные магазины: Крупные розничные сети имеют распределительные центры (склады) и множество магазинов. ТЗ помогает спланировать, с какого склада и сколько продукции следует отправить в каждый магазин, чтобы удовлетворить спрос с минимальными транспортными расходами.
3. Оптимизация пассажирских перевозок: Хотя ТЗ чаще ассоциируется с грузами, ее принципы применимы и к пассажирским перевозкам. Например, можно оптимизировать распределение автобусов или поездов по маршрутам для удовлетворения спроса при минимальных операционных расходах.
4. Разработка рационального плана транспортных перевозок: Общая задача формирования оптимальных маршрутов и объемов перевозок для национальных или региональных транспортных систем.
5. Оптимизация размеров и размещения производств: В стратегическом планировании ТЗ может использоваться для определения оптимального размещения новых заводов или складов относительно источников сырья и рынков сбыта, чтобы минимизировать будущие логистические издержки.
6. Прикрепление потребителей ресурса к производителям (задача оптимизации прикрепления): Классическая задача, когда необходимо определить, какой производитель будет снабжать какого потребителя, чтобы минимизировать затраты.
7. Взаимная привязка грузопотоков прямого и обратного направлений: В некоторых случаях возможно комбинировать прямые и обратные грузопотоки для повышения эффективности использования транспорта.
8. Отдельные задачи оптимальной загрузки промышленного оборудования: Например, распределение заказов между различными станками с учетом их производительности и стоимости обработки.
9. Оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями: Если у компании несколько заводов, производящих один и тот же продукт, ТЗ поможет решить, сколько произвести на каждом заводе для удовлетворения общего спроса с минимальными затратами (включая производство �� доставку).
10. Управление запасами и планирование производства: ТЗ может быть интегрирована в более сложные модели управления запасами и планирования производства, где оптимальные объемы перевозок влияют на объемы производства и уровень запасов на различных стадиях.
11. Оптимизация мультимодальных транспортных перевозок: Как было упомянуто, многоиндексные ТЗ позволяют оптимизировать перемещение грузов с использованием нескольких видов транспорта (автомобильный, железнодорожный, морской, воздушный).
12. Задача оптимального распределения оборудования или работ: Например, прикрепление строительной техники к объектам или бригад к заданиям.

Экономическое обоснование и интерпретация оптимального плана

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

Как интерпретировать полученные значения x_ij и Z:

• x_ij > 0: Эти значения указывают на активные, используемые маршруты. Каждый x_ij говорит о конкретном объеме груза, который должен быть отправлен от поставщика i к потребителю j. Логист может использовать эту информацию для составления маршрутных листов и графиков поставок.
• x_ij = 0: Эти маршруты не используются в оптимальном плане, поскольку они являются либо слишком дорогими, либо неэффективными с точки зрения общей оптимизации. Эта информация также важна: она позволяет исключить невыгодные направления.
• Z_min: Это ключевой показатель. Он представляет собой минимально возможную общую стоимость всех перевозок при заданных условиях. Сравнение этого значения с текущими или историческими затратами позволяет количественно оценить эффект от оптимизации.

Экономическое обоснование:

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

1. Сокращение затрат на транспортировку: Прямой результат оптимизации. Предприятия могут существенно снизить свои логистические расходы, что напрямую влияет на конечную стоимость продукции и увеличивает прибыль.
2. Улучшение эффективности логистических процессов: Оптимальный план минимизирует порожние пробеги, сокращает время в пути, оптимизирует загрузку транспортных средств, тем самым повышая общую производительность логистической системы.
3. Повышение конкурентоспособности предприятий: Снижение логистических издержек позволяет компании предложить более конкурентоспособные цены на свою продукцию или инвестировать сэкономленные средства в развитие.
4. Обоснование управленческих решений: Оптимальный план служит четким руководством для логистов и менеджеров по цепочкам поставок, предоставляя им данные для принятия решений о распределении ресурсов, выборе маршрутов и планировании операций.

Реальная экономия и эффективность:
Данные показывают, что решения, полученные с помощью транспортной задачи, практически точно отражают реальную картину перевозок и часто совпадают с выбором опытных специалистов отдела логистики. Более того, эти решения позволяют не только сократить затраты, но и значительно оптимизировать работу логиста, сокращая время, необходимое на планирование маршрутов, с нескольких часов до нескольких минут с помощью программных средств. Согласно исследованиям, автоматизация транспортной логистики может сократить средний пробег транспорта на 10-30% и существенно снизить стоимость доставки грузов. Например, в России это позволяет приблизить стоимость доставки одной тонны груза к европейскому уровню, что в среднем на 30% выше в РФ. Это подтверждает, что математическое моделирование, в частности транспортная задача, является незаменимым инструментом в арсенале современного бизнеса.

Программные средства для моделирования и решения транспортных задач

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

Решение ТЗ в MS Excel Solver: пошаговое руководство

Одним из наиболее доступных и широко используемых инструментов для решения задач линейного программирования, включая транспортную задачу, является надстройка «Поиск решения» (Solver) в MS Excel. Это удобное средство для студентов и специалистов, позволяющее быстро освоить принципы моделирования без необходимости изучения специализированных языков программирования.

Пошаговое руководство по использованию «Поиска решения» в Excel:

1. Подготовка таблицы данных:
   • Создайте матрицу для переменных x_ij (количество перевозимого груза). Это будут изменяемые ячейки.
   • Рядом создайте матрицу для стоимостей перевозок c_ij (тарифы).
   • Создайте столбцы/строки для запасов поставщиков (a_i) и потребностей потребителей (b_j).
2. Формулирование целевой функции:
   • В отдельной ячейке (например, C15) создайте формулу для расчета общей стоимости перевозок. Это будет сумма произведений x_ij на c_ij. Удобно использовать функцию СУММПРОИЗВ(): =СУММПРОИЗВ(диапазон_x; диапазон_c). Эта ячейка будет целевой ячейкой.
3. Формулирование ограничений:
   • Ограничения по запасам: Для каждого поставщика (строки) создайте ячейку, которая суммирует все отправления от этого поставщика (СУММ(строка_x)). Эти суммы должны быть равны соответствующим запасам a_i.
   • Ограничения по потребностям: Для каждого потребителя (столбца) создайте ячейку, которая суммирует все прибытия к этому потребителю (СУММ(столбец_x)). Эти суммы должны быть равны соответствующим потребностям b_j.
   • Неотрицательность переменных: Все ячейки с x_ij должны быть ≥ 0.
4. Активация «Поиска решения»:
   • Если надстройка не активирована, перейдите в «Файл» → «Параметры» → «Надстройки» → «Надстройки Excel» → «Перейти…», затем установите флажок напротив «Поиск решения» и нажмите «ОК».
   • Вкладка «Данные» → «Анализ» → «Поиск решения».
5. Настройка «Поиска решения»:
   • Установить целевую ячейку: Укажите ячейку с целевой функцией (например, C15).
   • Равной: Выберите «минимальному значению».
   • Изменяя ячейки переменных: Укажите диапазон ячеек, где находятся ваши переменные x_ij.
   • Ограничения: Нажмите «Добавить» и введите все ограничения:
     • Суммы по строкам = запасы a_i.
     • Суммы по столбцам = потребности b_j.
     • Диапазон xij >= 0 (можно поставить флажок «Сделать переменные без ограничений неотрицательными»).
   • Выбрать метод решения: Для транспортной задачи, которая является задачей линейного программирования, выберите «Симплекс-метод LP».
6. Запуск и анализ: Нажмите «Найти решение». Excel вычислит оптимальный план и отобразит его в вашей таблице. Вы сможете увидеть значения x_ij и минимальные общие затраты Z.

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

Обзор специализированных математических пакетов и логистических платформ

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

Специализированные математические пакеты:
Эти пакеты предоставляют мощные алгоритмы для линейного программирования, включая различные модификации симплекс-метода и специализированные решатели для транспортных задач. Примеры включают:

• CPLEX, Gurobi, Xpress: Это коммерческие решатели высокого уровня, используемые в академических исследованиях и промышленности для решения задач оптимизации любой сложности. Они обладают огромной скоростью и способны обрабатывать задачи с миллионами переменных и ограничений.
• MATLAB, Octave, SciPy (Python): Эти платформы предоставляют библиотеки и функции для реализации алгоритмов линейного программирования и оптимизации. Они популярны среди исследователей и разработчиков, позволяя создавать собственные модели и алгоритмы.
• R: Статистическая среда R также имеет пакеты для линейного программирования, такие как lpSolve.
• TORA (Х. Таха): Этот пакет, разработанный Хамди А. Таха, широко используется в учебных целях. Интересно, что TORA часто использует формат транспортной задачи только для экранного представления данных, выполняя вычисления обычным симплекс-методом «под капотом», что подчеркивает взаимосвязь этих подходов.

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

• «ШЕДЕКС»: Комплексная система для управления транспортом и логистикой, включающая функционал по оптимизации маршрутов.
• «Маппа»: Геоинформационная система с модулями для транспортной логистики и планирования перевозок.
• «Логист Уно»: Программный комплекс для управления логистикой, часто используемый для планирования и контроля перевозок.
• «Roolz»: Облачная система для автоматизации логистики, маршрутизации и мониторинга.
• «КосКомТранс»: Разработка, ориентированная на автоматизацию грузоперевозок.
• «1С: TMS Логистик»: Решение на базе платформы «1С:Предприятие», предназначенное для управления транспортной логистикой, включая планирование, контроль и учет перевозок. Это один из наиболее распространенных продуктов в РФ благодаря широкому распространению 1С.
• «Мегалогист TMS»: Еще одно решение для управления транспортной логистикой, предлагающее функции маршрутизации и оптимизации.
• «AXELOT SCAP»: Платформа для управления цепочками поставок, включающая мощные средства оптимизации.
• «Умная Логистика Карго» и «TransTrade»: Программы для транспортных компаний, обеспечивающие автоматизацию процессов, от приема заявок до построения оптимальных маршрутов.

Особенности использования и интеграции:
Многие из этих современных российских логистических платформ имеют готовую интеграцию с «1С:Предприятие». Это критически важно для российских компаний, поскольку 1С является стандартом де-факто для бухгалтерского и управленческого учета. Такая интеграция позволяет автоматизировать процессы управления транспортной логистикой, оперативно планировать доставку товаров, обмениваться данными с бухгалтерией и складскими системами, что значительно повышает общую эффективность бизнеса.

Важно отметить, что даже программная реализация сетевого алгоритма решения транспортной задачи, такого как метод потенциалов, вполне доступна студентам, обладающим элементарными навыками программирования (например, на Python, C++ или Java). Это позволяет не только использовать готовые решения, но и глубже понять внутренние механизмы работы алгоритмов.

Заключение

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

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

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

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

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

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

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

1. Мирошник, И.В. Теория автоматического управления. Линейные системы: Учебное пособие для вузов. Санкт-Петербург: Питер, 2005. 336 с.
2. Туманов, М.П. Теория управления. Теория линейных систем автоматического управления: Учебное пособие. Москва: МГИЭМ, 2005. 82 с. URL: http://window.edu.ru/window_catalog/files/r24738/5.pdf.
3. Бесекерский, В.А., Попов, Е.П. Теория систем автоматического регулирования. Москва: Наука, 1975.
4. Желтиков, О.М. Основы теории управления. Конспект лекций. Самара: СГТУ, 2008. URL: http://www.jelomak.ru/pager.htm.
5. Транспортная задача: задания для самостоятельного решения. URL: https://galyautdinov.ru/post/transportnaya-zadacha-zadaniya-dlya-samostoyatelnogo-resheniya.
6. Транспортная задача линейного программирования. Хабр. URL: https://habr.com/ru/articles/574244/.
7. Транспортная задача (учебное пособие для студентов). URL: http://resolventa.ru/spr/lp/tz.htm.
8. Транспортная задача онлайн. Шаг за шагом — Решение задач по линейному программированию. URL: https://www.matburo.ru/sub_subject.php?p=lin_opt_transp_solver.
9. Транспортная задача — Экономико-математические методы и модели. Studref.com. URL: https://studref.com/346892/ekonomika/transportnaya_zadacha.
10. Решение транспортной задачи линейного программирования: постановка, определение типа, решение. МатБюро. URL: https://www.matburo.ru/tv_sub.php?p=lp_transport.
11. Использование транспортной задачи для определения оптимального плана грузоперевозок. Cyberleninka.ru. URL: https://cyberleninka.ru/article/n/ispolzovanie-transportnoy-zadachi-dlya-opredeleniya-optimalnogo-plana-gruzoperevozok.
12. Исследование операций. Хабр. URL: https://habr.com/ru/articles/563812/.
13. Транспортная задача — решение методом потенциалов. Галяутдинов — сайт преподавателя экономики. URL: https://galyautdinov.ru/post/transportnaya-zadacha-metod-potencialov.
14. Транспортная задача. Метод северо-западного угла — Решение задач по линейному программированию. URL: https://www.matburo.ru/tv_sub.php?p=lin_opt_transp_northwest.
15. Решение транспортную задачу распределительным методом — Онлайн-калькулятор. URL: https://www.matburo.ru/tv_sub.php?p=lin_opt_transp_distr.
16. Практическое применение транспортной задачи в сетевой форме. Elibrary. URL: https://www.elibrary.ru/item.asp?id=49779148.
17. Использование транспортной задачи для определения оптимального плана грузоперевозок. Журнал Human Progress. URL: https://humanprogress.ru/article/242130.
18. Экономические задачи, сводящиеся к транспортной модели — Онлайн-калькулятор. URL: https://www.matburo.ru/tv_sub.php?p=lin_opt_transp_problems.
19. Применение задач оптимизации в управлении инвестиционно-строительными проектами. Молодой ученый. URL: https://moluch.ru/archive/129/35760/.