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

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

Пример 2.4. Установить, является ли оптимальным базисное распределение поставок, найденное в задаче 2.3 (таблица 2.3).

Решение. Найдем оценку свободной клетки, например, клетки (1,3). Для этого дадим в клетку (1,3) единичную поставку. При этом потребуется изменить поставки в заполненных клетках так, чтобы сохранился баланс по строкам и столбцам. (Будем полагать, что во всех свободных клетках, отличных от клетки (1,3), поставка останется нулевой). Так, чтобы 3-й потребитель получил по-прежнему 40 единиц груза, поставку в клетке (3,3) следует уменьшить на 1. Для того, чтобы 3-й поставщик по-прежнему отправил 100 единиц груза, поставку в клетке (3,2) увеличиваем на 1. Но 2-му потребителю нужно только 110 единиц груза, поэтому поставку в клетке (1,2) придется уменьшить на 1.

Таблица 2.4

Поставщики	Поставщикки	В1	В2	В3	В4	аi
А1		60-1	+1
А2	20			100
А3		50+1	40-1	10
bj

 

Существенно, что найденный вариант перераспределения поставок, затрагивающий заполненные клетки и увеличивающий на 1 единицу поставку клетки (1,3), единственный. Полученное распределение поставок представлено в табл. 2.5.

Найдем изменение ΔF суммарных затрат при указанном перераспределении поставок.

Первоначально затраты на перевозку (таблица 2.3) составили

Fн = 2∙60 + 5∙0 + 1∙20 + 2∙100 + 3∙50 + 7∙40 + 4∙10 = 810 ед.,

После перераспределения (таблица 2.5) затраты составляют:

Fп = 2∙59 + 5∙1 + 1∙20 + 2∙100 + 3∙51 + 7∙39 + 4∙10 = 809 ед.

Таблица 2.5.

Поставщики	Поставщикки	В1	В2	В3	В4	аi
А1		59	1
А2	20			100
А3		5 1	39	10
bj

 

Учитывая экономический смысл оценки свободной клетки, можем записать

β₁₃ = ΔF = Fп – Fн = 2∙ (-1) + 5∙1 + 3∙1 + 7∙ (-1) = -1.

То есть, среди клеток табл. 2.5 есть клетка с отрицательной оценкой, следовательно, данное распределение поставок (табл. 2.3) не оптимально.

* * * * * * * * * * * * * *

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

Проанализируем решение задачи 2.4 для упрощения вычислений.

При вычислении ΔF многие слагаемые в выражениях Fн и Fп взаимно уничтожаются, не влияя на значение ΔF: существенны лишь коэффициенты затрат тех клеток, в которых поставка при рассматриваемом перераспределении изменится. При этом в выражение для ΔF некоторые из них входят со знаком «+», а некоторые – со знаком «-». Для нахождения «правила знаков» удобна схема, называемая означенным циклом пересчета, представленная на рис. 2.1. На схеме изображены только те клетки, в которых будут изменены поставки (слева от каждой клетки написан в скобках ее номер; клетки, соответствующие базисным переменным, изображены двойными линиями).

При этом знаком «+» помечены те клетки, поставки в которых увеличатся. Видно, что именно их коэффициенты затрат войдут в выражение для ΔF со знаком «+». В остальных клетках рис. 2.1 поставки уменьшатся (в них вписан знак «-»), их коэффициенты затрат войдут в выражение для ΔF со знаком «-». Ломаную, соединяющую клетки с изменяемой поставкой, называют означенным циклом пересчета.

 

 

Рис. 2.1.

Таким образом, можно сформулировать правило 1 нахождения оценки свободной клетки: для свободной клетки следует построить цикл пересчета, в вершинах этого цикла расставить последовательно чередующие знаки, начиная со знака «+» в свободной клетке. Тогда значение оценки свободной клетки равно алгебраической сумме коэффициентов затрат клеток цикла, взятых с соответствующими знаками. Так, β₁₃ = 5 – 7 + 3 - 2 = -1.

Аналогично, составляя означенный цикл пересчета для каждой свободной клетки, можно найти ее оценку. При этом, конечно, цикл не всегда будет получаться таким простым, как в разобранном примере для клетки (1,3).

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

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

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

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

С этого используется следующая теорема.

Теорема 2.3. (о потенциалах). Оценка свободной клетки не изменится, если к коэффициентам затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Это число называется потенциалом данной строки (столбца).

Рассмотрение воображаемой ситуации и теорема 2.3 приводит к правилу 2 нахождения оценок свободных клеток: к коэффициентам затрат таблицы поставок в каждой строке и столбце надо прибавить такие числа (потенциалы), чтобы коэффициенты затрат в заполненных клетках стали равными нулю. Полученные при этом коэффициенты затрат свободных клеток равны оценкам этих клеток.

Пример 2.5. Найти оценки свободных клеток базисного распределения поставок, найденного в задаче 2.3 (табл. 2.3).

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

Таблица 2.6.

			-1 0 -1 0 0 5 0 0 (6.9) 3 0 0 0

-1(2)

-4(4)

0(7)

0(6)

В правом крае каждой клетки таблицы приведены:

а) в первой строке – исходное значение коэффициента затрат;

б) во второй и третьей строках - значения коэффициента затрат после изменения потенциалов строки и столбца данной клетки.

Начнем со второй строки таблицы. Пусть потенциал этой строки равен -1 (табл. 2.6). Рядом с потенциалом в скобках записываем номер шага (поставки опускаем, в таблице их сохраняем только для выделения базисных клеток).

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

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

В полученной матрице (2.9) две отрицательные оценки. Следовательно, рассматриваемое базисное распределение не оптимально. Продолжим решение этой задачи.

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

Решение. Как было установлено в задаче 2.5, базисное распределение поставок, полученное в задаче 2.3 (методом наименьших затрат) не оптимально. Оценка свободной клетки – это коэффициент при соответствующей свободной переменной в выражении целевой функции. Учитывая результат задачи 2.5 (табл. 2.6), можем записать

F = 810 – х₁₁ – х₁₃ + 5 х₂₂ + 3 х₃₁. (*)

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

Подобно тому, как это было в симплексном методе, увеличиваем поставку в клетку (1, 3) до тех пор, пока поставка в одной из заполненных клеток не станет равной нулю (дальнейшее увеличение х₁₃ уводит в область недопустимых решений). Если в клетку (1, 3) передаем поставку z, то поставки в клетках цикла со знаком «+» увеличатся на z, в клетках со знаком «-.» - уменьшатся на z. следовательно эта обнуляемая клетка находится среди клеток цикла, имеющих знак «-». Кроме того, эта клетка имеет минимальную поставку среди таких клеток. Так как z = min (60; 40) = 40, то в данном случае обнуляемая клетка (3,3) и по циклу пердается поставка 40 единиц груза.

То есть, поставка z, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со знаком «-».

В данной задаче z = min (60; 40) = 40. Эта поставка передается в клетку (1,3), то есть, х₁₃ = z = 40, а поставка клетки (3,3) обнуляется, то есть, х₃₃=40-z = 0. После этого клетка (1,3) считается заполненной (базисной), а клетка (3, 3) – свободной.

	(1,2)
	(3,2)

 

 

Рис. 2.2.

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

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

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

Так как среди свободных клеток есть клетка (1,1) с отрицательной оценкой, то найденное распределение не оптимально и передача поставки в клетку (1,1) приведет к уменьшению суммарных затрат на перевозку.

 

Таблица 2.7.

-1	20	40	-2(5) -1 0 0 0 0 5 1 0 (6.10) 3 0 1 0
20			-1(1) 100
	90		-3(3) 10

-1(2)

-3(4)

0(7)

0(6)

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

 

Рис. 2.3. Означенный цикл пересчета клетки (1,1)

По правилу, сформулированному выше, поставка, передаваемая по циклу, равна z=min{20, 20, 10}=10. Передвигая эту поставку по циклу (рис. 2.3), приходим к новому распределению поставок (таблица 2.9). Для полученного базисного распределения поставок найдем матрицу оценок свободных клеток (матрица 2.11)

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

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

Fmin = 1∙10 + 2∙10 + 5∙40 + 1∙10 + 2∙110 + 3∙100 = 760 ед.

Таблица 2.8.

			0 0 0 1 0 4 0 0 (6.11) 4 0 1 1

 

Экономия ΔF, достигнутая в результате применения метода перераспределения поставок, в денежных единицах составляет:

ΔF = Fmin – Fo = 760-810 = -50. Знак «-» в данном случае показывает, что при переходе к оптимальному распределению суммарные затраты на перевозку уменьшились.

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

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

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

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

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

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

Примечание 2. Оптимальное распределение поставок, найденное в задаче 2.6 (см. табл. 2.7), не единственное, так как среди оценок свободных клеток есть нулевые, например, клетка (2,3) в матрице (2.11). Аналогично, при симплексном методе решение не единственное, если в выражении целевой функции оптимального решения через свободные переменные коэффициенты при некоторых свободных переменных равны нулю.

Примечание 3. В некоторых случаях требуется определить изменение затрат ΔF_i на перевозку (экономия затрат) для некоторого i-го шага решения (или для каждого из шагов) транспортной задачи. Из экономического смысла оценки свободной клетки следует, что экономия затрат ΔF_i, достигнутая на некотором i-го шаге, равна произведению оценки клетки, в которую передается поставка, на величину передаваемой поставки. Например, при переходе из исходного распределения поставок (см. табл. 2.5) к распределению поставок по табл. 2.6 поставка 40 единиц передается в клетку, оценка которой равна -1. Тогда экономия затрат ΔF_iна первом шаге задачи 2.5 составит ΔF = (-1)∙40 = -40 ед.

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

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

а) суммарные запасы превышают суммарные потребности a_i > b_j;

б) суммарные потребности превышают суммарные запасы a_i < b_j;

Линейная функция одинакова в обоих случаях, изменяется только система ограничений.

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

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный (n+1)-ый потребитель, потребности которого равны

b_n+1 = a_i - b_j. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный (m+1)-ый поставщик, запасы которого a_m+1 = b_j - a_i.

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