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

Пример 7.7. Найти оптимальное распределение поставок задачи из примера 7.1.

Решение. Начнем с базисного распределения поставок, полученного в примере 7.3 для этой задачи. Как было установлено (см. пример 7.5), данное распределение не оптимально. Оценка свободной клетки – это коэффициент при соответствующей свободной переменной в выражении линейной функции. Учитывая результат примера 7.6, имеем . Значение F ₀ = 810 для данного распределения поставок найдено в примере 7.3. Далее поступаем так, как поступили бы, решая задачу симплексным методом: переменную x ₁₃, коэффициент при которой отрицателен, будем переводить в основные (базисные) переменные. Переменная х ₁₃начинает возрастать от нуля. Как было показано в § 7.3, перевод поставки в свободную клетку вызывает перераспределение поставок (передвижение поставки по циклу). Означенный цикл пересчета для клетки (1,3) показан на рис. 7.3.

Подобно тому, как это было в симплексном методе, увеличиваем поставку х ₁₃ в клетке (1,3) до тех пор, пока поставка в одной из заполненных клеток не станет равной нулю (дальнейшее увеличение х ₁₃уводит в область недопустимых решений). Эта клетка принадлежит, конечно, циклу, построенному на рис. 7.3 для клетки (1,3). Найдем ее. Если в клетку (1,3) передать поставку, равную z, то поставка в клетках цикла со знаком "+" увеличится на z, а в клетках со знаком "-" -уменьшится на z. Поэтому искомая клетка находится среди клеток цикла, имеющих знак "-". Более того, она имеет минимальную поставку среди таких клеток. Так как (рис. 7.3) min{60,40} = 40, то в нашем случае - это клетка (3,3), и для обнуления поставки в этой клетке по циклу следует передать 40 единиц груза (т.е. поставка, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со знаком "-"). После этого клетка (1,3) считается заполненной, а клетка (3,3) - свободной.

2 -

5 +

(1,2) (1,3)

	(3,3)

7 -

3 +

(3,2) ()())

Рис.7.3

В клетках со знаком "+" цикла поставка увеличивается на передаваемую поставку: поставка клетки (3,2) станет равной 90 единицам, поставка клетки (1,3) — 40 единицам. Аналогично в клетках со знаком "-" поставка уменьшится на передаваемую поставку, например поставка клетки (1,2) станет равной 20 единицам, что видно из табл. 7.12. Нетрудно доказать, что вновь полученное распределение поставок — базисное.

Таблица 7.12

0 0 -3 -1

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

(7.14)

Так как среди свободных клеток есть клетка (1,1) с отрицательной оценкой, то найденное распределение не оптимально и передача поставки в клетку (1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл пересчета для клетки (1,1) приведен на рис. 7.4. По правилу, сформулированному выше, поставка, передаваемая по циклу х ₁₁= {20,20,10} = 10. Передвигая эту поставку по циклу (рис. 7.4), приходим к новому распределению поставок (табл. 7.13).

-

+

(1,1) (1,2)

-

+

(2,1) (2,4)

	(3,4)

-

+

(3,2)

Рис. 7.4

Таблица 7.13

(7.15)

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

Суммарные затраты на перевозку для этого распределения поставок в денежных единицах:

.

Экономия F, достигнутая в результате применения метода перераспределения поставок, составляет в денежных единицах . Знак "минус" в данном случае показывает, что при переходе к оптимальному распределению суммарные затраты на перевозку уменьшились.

Замечание 1. Поставка, передаваемая по циклу, не может быть ни меньше, ни больше минимума поставок клеток цикла со знаком "-". Действительно, в первом случае ни одна из клеток цикла не будет иметь нулевой поставки, а потому общее число заполненных клеток таблицы будет равно m + и, и, следовательно, распределение не будет базисным. Во втором случае уходим в область недопустимых решений.

Замечание 2. Оптимальное распределение поставок, найденное в примере 7.7 (табл. 7.13), не единственное, так как среди оценок свободных клеток есть нулевые, например, клетка (2,3) в матрице (7.15). Аналогично в симплексном методе решение не единственное, если в выражении линейной функции оптимального решения через неосновные (свободные) переменные коэффициенты при некоторых свободных переменных равны нулю. В связи с данным замечанием можно предложить читателю следующее упражнение: проверить, что перераспределение поставки в свободную клетку с нулевой оценкой не изменит оптимального значения затрат F _min.

Замечание 3. В некоторых случаях требуется определить изменение затрат на перевозку (экономию затрат) для некоторого i -го шага решения (или для каждого из шагов) транспортной задачи. Из экономического смысла оценки свободной клетки следует, что экономия затрат , достигнутая на некотором i -м шаге, равна произведению оценки клетки, в которую передается поставка, на передаваемую поставку. Например, при переходе от исходного распределения поставок (см. табл. 7.11) к распределению поставок по табл. 7.12 поставка 40 единиц передается в клетку, оценка которой равна -1. Тогда экономия затрат на первом шаге примера 7.7 составит = (-1)40 = -40.

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

1. Для данного базисного распределения поставок подбираем потенциалы строк и столбцов таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю. Составляем матрицу оценок.

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

3. Для избранной свободной клетки строится означенный цикл пересчета. Поставка z, передаваемая по циклу, определяется как минимум среди поставок в клетках со знаком "-". Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком "+" увеличивается на z, а в клетках со знаком "-" - уменьшается на z- Клетка, поставка в которой при этом станет равной нулю, будет считаться свободной (далее рассмотрен случай, когда таких клеток несколько), остальные клетки цикла - заполненными. Таким образом, получено новое базисное распределение поставок.

4. Переходим к пункту 1 алгоритма.

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

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

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

Пример 7.8. Завершить решение транспортной задачи из примера 7.4.

Решение. Установим сначала оптимально ли распределение, полученное в указанном примере методом "северо-западного" угла (см. табл. 7.8). Подберем потенциалы строк и столбцов этой таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю (табл. 7.14).

Таблица 7.14

-1 -3 -2

Это приводит к матрице оценок 7.16. Так как среди свободных клеток таблицы есть клетка (3,2) с отрицательной оценкой, то данное базисное распределение поставок не оптимально. Переведем поставку в клетку (3,2) с отрицательной оценкой. Строя для клетки (3,2) означенный цикл пересчета (рис. 7.5), находим, что объем передаваемой поставки в данном случае равен x ₃₂ = min{0,10} = 0. Передавая по построенному циклу нулевую поставку, приходим к новому базисному распределению (табл. 7.15).

	-		+

(2,2) (2,3)

	(3,3)

-

+

(3,2) ()())

Рис.7.5

Таблица 7.15

1 -1 -2

(7.17)

3 +

3 -

Подбирая потенциалы к строкам и столбцам таблицы 7,15, находим матрицу (7.17) оценок данного распределения. Так как среди свободных клеток таблицы есть клетка (1,3) с отрицательной оценкой, то данное базисное распределение не оптимально. Найдем новое базисное распределение, передавая поставку в клетку (1,3) с отрицательной оценкой. Построим цикл для клетки (1,3), показанный на рис. 7.6. Поставка, передаваемая в клетку (1,3): х ₁₃ = min{10,10} - 10. При передаче по циклу (рис. 7.6) 10 единиц груза станут равными нулю поставки в клетках (1,2) и (3,3). Полагаем, что только одна из них стала свободной, например, клетка (3,3), клетка (1,2) заполнена нулевой поставкой. Таким образом, получено следующее базисное распределение поставок (табл. 7.16).

(1,2) (1,3)

	(3,3)

()())

1 +

2 -

(3,2)

Рис.7.6

Таблица 7.16

0 -2 -2

(7.18)

Находя матрицу оценок (7.18), видим, что среди оценок свободных клеток найденного распределения нет отрицательных, т.е. найденное распределение (табл. 7.16) оптимально.