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

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

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

; ; , (20)

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

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

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

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

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

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

; ; , (21)

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

; . (22)

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

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

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

Совершенствование организации контейнерных перевозок морским транспортом в России на основании использования принципов логистики
История предприятия ОАО "Совтрансавто-Москва" ведется с марта 1945г. В начале 70-х предприятие стало базой для вновь созданного Главного управления международных автомобильных сообщений «Совтрансавто» Минавтотранса РСФСР с автопарком в 300 ед. подвижного состава. Открытое ак ...