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

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

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

; ; , (20)

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

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

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

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

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

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

; ; , (21)

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

; . (22)

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

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

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

Организация технического обслуживания и ремонта подвижного состава
В рамках любой социально-экономической системы транспорт и связь играют важнейшую роль. Для независимого Казахстана с его огромной территорией (2725 тыс. км2), низкой плотностью населения (менее 6 чел/км2), рассредоточенностью сырьевых и производственных ресурсов транспортно-коммуникацион ...

Характеристика предприятия "Ялуторовское дорожное ремонтно-строительное управление ОАО "ТОДЭП"
История предприятия, его организационно-правовая форма, уставные виды деятельности, виды деятельности, осуществляемые фактически. Наличие лицензий и сертификатов. Территориальное расположение и генеральный план предприятия. Общая организационная структура предприятия. Наименование пре ...