Материал: Роль транспортной задачи в экономике

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

Алгоритм решения задачи методом потенциалов:

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

) Строят начальное опорное решение (методом наименьших стоимостей). Количество занятых клеток должно равняться m+n-1. Если количество клеток не совпадает с числом N, то задача называется вырожденной. Чтобы избавиться от вырожденности, необходимо заполнить клетки до совпадения с числом N нулями так, чтобы они не образовывали цикл с уже имеющимися заполненными клетками. В противном случае задача называется невырожденной и можно переходить к следующему этапу алгоритма.

) Строят систему потенциалов. Для этого решают систему уравнений.

) Проверяют, выполняются ли условия оптимальности для свободных клеток таблицы.

Δij=

Δij≥0

Если Δij≤0, то решение не оптимальна. Таким образом, его нужно улучшить.

) Переходят к новому опорному решению. Для этого находят клетку таблицы задачи, которой соответствует наименьшая отрицательная оценка min. Затем строят цикл, включающий в свой состав данную клетку и часть клеток занятых опорным решением. Осуществляется сдвиг и возвращаемся обратно к пункту 3 алгоритма решения.

) Решим конкретный пример с помощью методом потенциалов транспортную задачу:

значит, задача с правильным балансом.

) Находим опорное решение методом наименьшей стоимости:

= m+n-1=3+4-1=6 (невырожденная).

) F(

)

Для заполнения клеток вычислим значения потенциалов:

(1; 1)

(1; 2)

(2; 1)

(3; 2)

(3; 3)

(3; 4)

Вычислим оценки для пустых клеток:

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

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

Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак “+”, т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.

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

min= min

) F= (

Для заполненных клеток вычислим значения потенциалов:

(1; 1)

(1; 2)

(1; 3)

(2; 1)

(3; 2)

(3; 4)

Оценки

3) F= (

(1; 2)

(1; 3)

(2; 1)

(3; 1)

(3; 2)

(3; 4)

F (

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример. Решить распределительным методом транспортную задачу, исходные данные которой приведены в таблице: b1 b2 b3