Теория принятия оптимальных решений

18. Закрытая транспортная задача по критерию стоимости. Постановка задачи, подходы к их решению

19. Закрытая транспортная задача по критерию стоимости. Нахождение первоначального базисного распределения

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

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

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

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

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

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

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

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

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

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

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

Выше рассматривалась закрытая модель транспортной задачи, с правильным балансом, когда выполняется условие (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 с его заявкой b n+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

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

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

Распределительный метод решения закрытой транспортной задачи по критерию стоимости. Метод потенциалов.

Распределительный метод

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

Пусть для транспортной задачи найдено начальное опорное решение Х1 и вычислено значение целевой функции на этом решении F(Х1). По доказанной выше теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину

можно получить новое опорное решение Х2.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l,m), приращение целевой функции Дlm равно разности двух сумм:

где - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+” ; - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”.

В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки ( l, m ) меньше нуля, т.е. Д lm< 0, то перераспределение величины и по соответствующему циклу приведет к уменьшению значения F(X) на величину и*Дlm, т.е. опорное решение можно улучшить. Если же величины Дlm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

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

.

В результате получится новое опорное решение.

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

Метод потенциалов

Метод потенциалов используется для решения транспортной задачи. Основой вычислительного процесса при улучшении опорного плана является определение критерия оптимальности dij:

dij = сij* - сij,

где сij - затраты (истинные тарифы), связанные с доставкой одной единицы груза из i-того пункта отправления в j-ый пункт назначения; сij* - расчётные затраты (косвенные тарифы), связанные с доставкой одной единицы груза из i-того пункта отправления в j-ый пункт назначения, определяемые для тех клеток опорного плана, ресурсы в которые не распределены (для незаполненных клеток).

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

23. Транспортная задача по критерию времени: постановка задачи и подходы к решению

Размещено на Allbest.ru