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

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

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

; ; , (20)

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

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

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

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

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

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

; ; , (21)

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

; . (22)

Страницы: 1 2 3 4 5

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

Экономические показатели работы автотранспортного предприятия
Для автомобилей-такси дневная выработка определяется в платных километрах пробега и рублях выручки (1.1) где Lпл. -платный пробег автомобиля-такси за сутки, км; Для грузовых автомобилей, работающих из почасового расчета, автобусов маршрутных и работаю по заказам и ...

Компрессор двухконтурного турбореактивного двигателя
В качестве прототипа двигателя принят ТРДД Д–18Т – трёхвальный турбореактивный двухконтурный двигатель. Особенность трёхвальной схемы–разделение ротора компрессора на три самостоятельных ротора, каждый из которых приводится во вращение своей турбиной. Конструкция двигателя выполнена ...

Предложение по внедрению контейнерной технологии международных перевозок легковых автомобилей
Анализ состояния и перспектив развития рынка грузоперевозок в Северо-Западном регионе РФ целесообразно проводить с учетом влияния последствий мирового финансового кризиса 2008 – 2009 гг., вызвавшим резкие изменения мирового спроса и предложения. В России транспортные компании ощутили ...