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

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

Транспортная задача относится к задачам математического программирования и чаще всего решается симплекс-методом, который разработан американским математиком Д.Данцигом в 1949г. для задач в канонической форме записи:

; ; , (20)

где А – матрица условий задачи размеров , ранг которой будем всегда считать равным m;

– вектор-строка коэффициентов целевой функции;

– вектор-столбец коэффициентов ограничений.

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

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

Если рассматривать задачу

; ; , (21)

как прямую, то в соответствии с теорией двойственности ей можно сопоставить следующую двойственную задачу:

; . (22)

Другое по теме:

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

Модернизация энергетической установки танкера проекта 621 с целью повышения скорости его движения на 3%
Речной транспорт – неотъемлемая составная часть транспортной системы России и его развитию присущи те же тенденции, что и развитию транспортной системы в целом. Такими тенденциями являются: ресурсосбережение; повышение надежности, безопасности и экологической чистоты; повышение произво ...

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