ТРАНСПОРТНАЯ ЗАДАЧА

— задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления. Пусть имеется пунктов производства некоего однородного продукта и пунктов его потребления пункте производится единиц, а в пункте потребляется b единиц продукта. Предполагают, что

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

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

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

Для устранения вырожденности, Т. з. незначительно изменяется, в результате получается новая невырожденная Т. з. В новой Т. з. объемы производств в от, равны е, а объемы потребления пунктов , равны

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

Т. з. решают спец. методами программирования линейного. Наиболее известны из них — метод потенциалов и т. н. венгерский метод.

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

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

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

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

Лит.: Триус Е. Б. Задачи математического программирования транспортного типа. М., 1967 [библиогр. с. 202—204]; Гольштейн Е. Г., Юдин Д. Б. Задачи линейного программирования транспортного типа. М., 1969 [библиогр. с. 375—378].

И. М. Мельник.