Транспортные задачи

    Замечание 2. Можно показать, что если сумму  всех затрат по данному плану перевозок  выразить через свободные неизвестные [для этого надо исключить базисные неизвестные из выражения для S, см. формулу (2.4)], то коэффициент при каждом из таких неизвестных будет равен алгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок. Это еще раз подтверждает, что пересчет по циклам является специфической формой применения симплекс-метода к решению транспортной задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

    Задача, двойственная к транспортной.

    Построим  задачу, двойственную к транспортной. С этой целью вспомним, что каждому  пункту отправления Ai и назначения Bj отвечает определенное ограничение

                                               (6.1)

    В то же время каждому ограничению  из (6.1) сопоставляется определенная неизвестная  в двойственной задаче. Тем самым устанавливается соответствие между всеми пунктами Ai и Bj и всеми неизвестными двойственной задачи.

    Обозначим неизвестную в двойственной задаче, отвечающую пункту отправления Ai, через ui(i=1,..,n), а пункту назначения Bj – через vj(j,…m).

    Каждому неизвестному в транспортной задаче соответствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное xij входит ровно в два ограничения системы (6.1): одно из них отвечает пункту Ai, а другое – пункту Bj. В обоих этих уравнениях коэффициент при xij равен 1. Поэтому соответствующее xij ограничение в двойственной задаче имеет вид 

       .                               (6.2)

    Правая  часть неравенства (6.2) равна cij, потому что именно с этим коэффициентом неизвестная xij входит в минимизируемую формулу (2.4).

    Оптимизируемая  форма двойственной задачи имеет  вид

                                               (6.3)

    Таким образом, задача двойственная к транспортной формулируется следующим образом. При ограничениях (6.2) максимизировать формулу (6.3). Подчеркнем, что знак значений неизвестных ui(i=1,…,n) и vj(j,…,m) может быть произвольным.

    Предположим, что нам известно некоторое допустимое базисное решение транспортной задачи, в котором все базисные неизвестные строго положительны. Это решение оптимально лишь в том случае, когда соответствующая ей система оказывается совместной. Эта система возникает из системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным xij заменить точными равенствами.

    В итоге приходим к соотношению:

    ui + vj ≤ cij (для всех свободных неизвестных xij)                     (6.4)

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

 

5  Пример решения транспортной задачи

    В городе N имеется 4 склада Аi, на которых хранится ткань (в рулонах) и 5 магазинов Bj, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок. 

    В данном случае Σai=225 >Σbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу: 

    Математическая  модель: обозначим xij – количество товара, перевозимого из Аi в Bj. Тогда

      x11 x12 x13 x14 x15 x16

    x21 x22 x23 x24 x25 x26