В качестве критерия оптимальности транспортных перевозок. Критерии оптимальности

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления в п пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i -го пункта отправления в j -й пункт назначения, через – запасы груза в i -м пункте отправления, через – потребности в грузе в j – м пункте назначения, а через – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

(64)

(65)

(66)

Поскольку переменные удовлетворяют системам уравнений (64) и (65) и условию неотрицательности (66), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Определение 15.

Всякое неотрицательное решение систем линейных уравнений (64) и (65), определяемое матрицей , называется планом транспортной задачи.

Определение 16.

План , при котором функция (63) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы 21.

Таблица 21

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

Теорема 13.

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство (67).

В случае превышения запаса над потребностью, т. е. вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (67).

Аналогично, при вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (67).

Число переменных в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт , а число уравнений в системах (64) и (65) равно п+т . Так как мы предполагаем, что выполняется условие (67), то число линейно независимых уравнений равно п+т – 1. Следовательно, опорный план транспортной задачи может иметь не более п + т – 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п +т – 1, то план является невырожденным, а если меньше – то вырожденным.

Как и для всякой , оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы.

Пример 19.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i –го пункта его получения на j –е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(68)

При данном плане перевозок общая стоимость перевозок составит

Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (68), при котором целевая функция (69) принимает минимальное значение.

Программа для решения транспортной задачи методом потенциалов

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

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

Через конечное число шагов приходят к искомому оптимальному базисному решению.

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

В зависимости от методов подсчета алгебраических сумм тари­фов для свободных клеток различают два метода отыскания опти­мальногорешения транспортной задачи:

Распределительный метод. При этомметоде для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.

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

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

Применяя метод потенциалов, можно говорить не о знаке алгебраических сумм тарифов, а о сравнении косвенных тарифов с истинными. Требование неотрицательности алгебраических сумм тарифов заменяется условием, что косвенные тарифы не превосхо­дят истинных.

Следует иметь в виду, что потенциалы (так же как и циклы) для каждого нового базисного плана определяются заново.

Выше рассматривалась закрытая модель транспортной задачи, с правильным балансом, когда выполняется условие (1.3). В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (транспортная задача с избытком запасов):

а i > b j (где i=1,...,m ; j=1,...,n);

2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

а i < b j (где i=1,...,m ; j=1,...,n);

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

Сведем её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В 1 , B 2 , ... , B n , введём ещё один, фиктивный, пункт назначения B n +1 , которому припишем фиктивную заявку, равную избытку запасов над заявками

b n+1 = а i - b j (где i=1,...,m ; j=1,...,n) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b n +1 будем считать равной нулю. Введением фиктивного пункта назначения B n +1 с его заявкой b n +1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления A m +1 с запасом a m +1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.

План перевозок

является оптимальным планом тогда и только тогда, когда найдется система платежей

для которой выполняются условия:

Доказательство. Сформулируем вторую теорему двойственности в терминах переменных транспортной задачи.

удовлетворяют ограничениям прямой задачи, а

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

необходимо и достаточно выполнение условий

Условие а) выполняется для любых допустимых решений прямой задачи, так как

Условие b) можно расписать как следствие о дополняющей нежесткости, а именно

Итак, для базисных переменных

имеем равенство

а для небазисных переменных

достаточно выполнения допустимости двойственных переменных

Таким образом имеем условия 1) и 2) критерия.

Критерий доказан.

9.5 Построение опорного плана транспортной задачи

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:

Базисными клетками транспортной таблицы являются клетки с от-

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

1) сумма перевозок в каждой строке равна запасу в данной

2) сумма перевозок в каждом столбце равна соответствующему

столбцу спросу

Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок

Опорный план называется вырожденным , если число ненулевых перевозок

меньше и n+m-1, опорный план - невырожден , если число

ненулевых перевозок равно n+m-1.

Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях.

Метод севево-западного угла

Рассмотрим "северо-западный угол" незаполненной таблицы, то

есть клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая.

Это означает, что первый поставщик отгрузил весь произведенный продукт первому потребителю и его

запас равен нулю, поэтому

При этом неудовлетворенный спрос в первом пункте потребления равен

то есть спрос первого потребителя полностью удовлетворен и поэтому

а остаток продукта в первом пункте производства равен

из рассмотрения можно исключить и поставщика, и потребителя. Однако при атом план получается вырожденным,

поэтому условно считается, что выбывает только поставщик,

а спрос потребителя остается неудовлетворенным и равным нулю.

После этого рассматриваем северо-западный угол оставшейся не-

заполненной части таблицы и повторяем те же действия. В результате

через n+m-1 шагов получим опорный план.

10. Математическая модель транспортной задачи. Открытые и закрытые задачи. Допустимый, опорный и оптимальный планы перевозок.

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:

Следнет обратить внимание на то, что математическая модель задает закрытую транспортную задачу.

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3.3)

при этом полагают .

Второй случай. Суммарный объем производства больше суммарного объема потребления:

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (3.5)

при этом полагают .

Методы решения.

· Как задача линейного программирования ТЗ может быть решена симплекс методом .

· Также разработаны специальные (более эффективные) методы решения транспортной задачи: обобщенный венгерский метод ; метод северо-западного угла, метод минимального элемента для нахождения опорного плана; метод потенциалов для нахождения оптимального плана .

11. Построение начального (опорного) плана перевозок по методу северо–западного угла и по методу наименьшей стоимости.

1.Метод северо-западного угла. При нахождении опорного плана на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного («северо-западный угол») и заканчивается клеткой для неизвестного, т.е. как бы по диагонали таблицы.

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

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

1) Объем работы транспорта (критерий - расстояние в т/км). Минимум пробега удобен для оценки планов перевозок, поскольку расстояние перевозки определяется легко и точно для любого направления. Поэтому критерию нельзя решать транспортные задачи с участием многих видов транспорта. С успехом применяется при решении транспортных задач для автомобильного транспорта. При разработке оптимальных схем перевозки однородных грузов автомобилями.

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

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

4) Сроки доставки грузов (критерий - затраты времени).

5) Приведенные затраты (с учетом эксплуатационных расходов, зависящих от размеров движения и капиталовложения в подвижной состав).

6) Приведенные затраты (с учетом полных эксплуатационных расходов капиталовложений на строительство объектов в подвижной состав).

где - эксплутационные издержки,

Расчетный коэффициент эффективности капиталовложения,

Капитальные вложения, приходящие на 1 т груза на протяжении участка,

Т - время следования,

Ц - цена одной тоны груза.

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

Поскольку переменные удовлетворяют системам линейных уравнений (2) и (3) и условию неотрицательности (4), то обеспечиваются вывоз имеющегося груза из всех пунктов отправления, доставка необходимого количества груза в каждый из пунктов назначения, а также исключаются обратные перевозки.

Таким образом, Т-задача представляет собой задачу ЛП с m*n числом переменных, и m + n числом ограничений - равенств.

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.

то модель такой транспортной задачи называется закрытой или сбалансированной .

Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми . Возможные два случая:

В первом случае полное удовлетворение спроса невозможно .

Такую задачу можно привести к обычной транспортной задаче следующим образом. В случае превышения потребности над запасом, т. е. вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю:

Тогда требуется минимизировать

при условиях

Рассмотрим теперь второй случай .

Аналогично, при вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю:

Тогда соответствующая Т-задача запишется так:

Минимизировать

при условиях:

Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (5).

В некоторых случаях нужно задать, что по каким-либо маршрутам нельзя перевозить продукцию. Тогда стоимости перевозок по этим маршрутам задаются так, чтобы они превышали самые высокие стоимости возможных перевозок (для того, чтобы было невыгодно везти по недоступным маршрутам) – при решении задачи на минимум. На максимум – наоборот.

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

· из запаса соответствующего пункта отправки;

· из потребности соответствующего пункта назначения.

Конец работы -

Эта тема принадлежит разделу:

Транспортная задача

Пример.. четыре предприятия данного экономического района для производства продукции..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях: