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

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

Решение. Начнем с базисного распределения поставок, полученного в задаче 7.3. Как было установлено ранее (см. задачу 7.5), данное распределение не оптимально. Оценка свободной клетки — это коэффициент при соответствующей свободной переменной в выражении линейной функции. Учитывая результат задачи 7.6, имеем:

Значение F() = 810 для данного распределения поставок найдено в задаче 7.3. Далее поступаем так, как поступили бы, решая задачу симплексным методом: переменную х, 3, коэффициент при которой отрицателен, будем переводить в основные (базисные) переменные. Переменная х}3 начинает возрастать от нуля. Как было показано в параграфе 7.3, перевод поставки в свободную клетку вызывает перераспределение поставок (передвижение поставки по циклу). Означенный цикл пересчета для клетки (1, 3) показан на рис. 7.3.

Подобно тому, как это было в симплексном методе, увеличиваем поставку х|3 в клетке (1, 3), до тех пор пока поставка в одной из заполненных клеток нс станет равной нулю (дальнейшее увеличение х13 уводит в область недопустимых решений). Эта клетка принадлежит, конечно, циклу, построенному на рис. 7.3 для клетки (1,3). Найдем ее. Если в клетку (1, 3) передать поставку, равную г, то поставка в клетках цикла со знаком «+» увеличится на 2, а в клетках со знаком «-» — уменьшится на z. Поэтому искомая клетка.

Рис. 7.3.

находится среди клеток цикла, имеющих знак «-». Более того, она имеет минимальную поставку среди таких клеток. Так как (см. рис. 7.3) min{60,40} = 40, то в нашем случае это клетка (3, 3), и для «обнуления» поставки в этой клетке по циклу следует передать 40 единиц груза, т.е. поставка, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со знаком «-» . После этого клетка (1,3) считается заполненной, а клетка (3, 3) — свободной.

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

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

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

Таблица 7.12

				— 2.
				— 1.
				— 3.
		— 5.	— 1.

(7.14).

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

Рис. 7.4.

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

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

Таблица 7.13.

(7.15).

Экономия ?F, достигнутая в результате применения метода перераспределения поставок, составляет в денежных единицах ?Т = Fmin -F0 =760−810 = -50. Знак «-» в данном случае показывает, что при переходе к оптимальному распределению суммарные затраты на перевозку уменьшились. >

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

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

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

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

• 1. Для данного базисного распределения поставок подбираем потенциалы строк и столбцов таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю. Составляем матрицу оценок.
• 2. Если оценки всех свободных клеток неотрицательны, то найденное распределение оптимально — решение закончено. Если среди оценок свободных клеток есть отрицательные, то выбираем одну из них для передачи в нее поставки (для определенности можно брать, например, одну из клеток с наименьшей оценкой).
• 3. Для избранной свободной клетки строится означенный цикл пересчета. Поставка z, передаваемая по циклу, определяется как минимум среди поставок в четных клетках со знаком «-». Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком «+» увеличивается на z, а в клетках со знаком «-» уменьшается на г. Клетка, поставка в которой при этом станет равной нулю, будет считаться свободной (далее рассмотрен случай, когда таких клеток несколько), остальные клетки цикла — заполненными. Таким образом, получено новое базисное распределение поставок.
• 4. Переходим к ?. 1 алгоритма.

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

• 1. В некоторых случаях поставка, переводимая по циклу, может оказаться равной нулю. Эго возможно тогда, когда четная клетка цикла со знаком «-» содержала нулевую поставку. В этом случае по циклу передается нулевая поставка. В результате та свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой — свободной.
• 2. Если при переводе поставки по циклу поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной из них следует считать только одну (любую), остальные клетки, поставка в которых стала равной нулю, следует считать заполненными нулевой поставкой. Разберем перечисленные особые случаи на примере.
• 7.8. Завершить решение транспортной задачи 7.4.

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

Таблица 7.14

— 1.

(7.16).

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

Рис. 7.5.

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

			— 2.

(7.17).

Подбирая потенциалы к строкам и столбцам табл. 7.15, находим матрицу (7.17) оценок данного распределения. Так как среди свободных клеток таблицы есть клетка (1,3) с отрицательной оценкой, то данное базисное распределение нс оптимально. Найдем новое базисное распределение, передавая поставку в клетку (1, 3) с отрицательной оценкой. Построим цикл для клетки (1, 3), показанный на рис. 7.6. Поставка, передаваемая в клетку (1,3): х13 = minjlO, 10} = 10. При передаче по циклу (см. рис. 7.6) 10 единиц груза поставки в клетках (1, 2) и (3, 3) станут равными нулю. Полагаем, что только одна из них стала свободной, например клетка (3, 3), а клетка (1,2) заполнена нулевой поставкой.

Рис. 7.6.

Таким образом будет получено базисное распределение поставок, представленное в табл. 7.16.

Таблииа 7.16

			— 1.

(7.18).

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