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

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

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

; ; , (20)

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

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

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

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

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

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

; ; , (21)

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

; . (22)

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

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

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

Организация работы контейнерного пункта
Контейнерно-транспотная система (КТС) РФ – организационно технический комплекс, действующий на основе единых правовых норм, системы планирования и унифицированных технологических процессов перевозок. КТС охватывает планирование и организацию перевозок грузов на всех видах транспорта. В ...