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

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

Для преобразования таблицы используется понятие цикла.

Циклом в матрице называется ломаная с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющая требованиям:

– замкнутости;

– в каждой вершине должно встречаться два звена.

Если в любом цикле вершинам приписать при обходе в одном направлении поочередно знаки «+» и «–», то в каждой строке (столбце) число положительных вершин будет равно числу отрицательных.

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

Например, для свободной клетки с координатами (3,3) левой матрицы строится цикл, приведенный на рисунке, и осуществляется сдвиг по циклу на величину 8. В результате получаются новые значения перевозок, приведенные на правой матрице. Клетки, не являющиеся вершинами цикла, при этом остаются без изменений.

+		—
			Сдвиг по циклу на 8
—		· +

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

– коэффициент равен 0, если соответствующая базисная клетка не является вершиной цикла пересчета данной свободной клетки;

– коэффициент равен 1, если базисная клетка является положительной вершиной цикла пересчета данной свободной клетки;

– коэффициент равен –1, если базисная клетка является отрицательной вершиной пересчета данной свободной клетки.

Например, матрица перевозок имеет 4 пункта отправления и 4 пункта назначения. В ней записано некоторое базисное решение в заштрихованных клетках x₁₁ , x₁₂ , x₂₃ , x₂₄ , x₃₂ , x₄₁ и x₄₃ , число которых должно быть r=m+n-1=7. При этом в каждой строке и каждом столбце таблицы должна быть как минимум одна базисная клетка.

	В1	В2	В3	В4
А1	–			· +
А2			+	–
А3
А4	+		–

Построим цикл пересчета для свободной клетки x₁₄ так, чтобы все остальные вершины лежали в базисных клетках. Такой цикл существует только один и приведен в таблице, при этом свободной клетке x₁₄ присваивается знак «+», а знаки всех последующих вершин чередуются при их обходе по циклу в одном направлении.

Таким образом, можно по теореме утверждать, что клетка x₁₄ входит в выражение для неизвестных базисных со знаками:

.

Аналогично можно найти коэффициенты для других свободных неизвестных.

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

Найденное любым методом допустимое базисное решение вносится в матрицу перевозок и занимает r=m+n-1 клеток. Вносятся и нулевые базисные решения. Далее меняются местами базисные и свободные переменные для приближения к оптимальному решению.

Во-первых, определяется свободная неизвестная, переводимая в число базисных.

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

=2×20 + 3×10 + 2×20 + 5×20 + 2×10 + 6×10 = 290.

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

 

 

	В1	В2	В3	В4	ai
A1	2	3 –	2 +	4
A2	3	2 +	5 –	1
A3	4	3	2	6
bj

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

х₁₃ ® g₁₃ = с₁₃ - с₂₃ + с₂₂ - с₁₂ = 2 - 5 + 2 - 3 = -4 ,

х₁₄ ® g₁₄ = с₁₄ - с₂₄ +с₃₃ – с₂₃ + с₂₂ - с₁₂ = 4 – 6 + 2 - 5 + 2 - 3 = -6 ,

х₂₁ ® g₂₁ = с₂₁ - с₁₁ + с₁₂ - с₂₂ = 3 - 2+ 3 - 2 = 2 ,

аналогично g₂₄ = - 8, g₃₁ = 6, g₃₂ = 4.

Выбираем те из свободных переменных, которые имеют отрицательное значение суммы стоимости по циклу пересчета. В рассматриваемом примере это х₁₃, х₁₄, х₂₄.

Во-вторых, определяется базисная переменная, переводимая в число свободных.

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

Производя преобразования по циклу, мы должны получить нуль в одной из базисных переменных. Кроме того, необходимо учитывать, что переменные не могут принимать отрицательных значений. Поэтому выбирается та базисная переменная, которая имеет наименьшее значение из всех базисных переменных, расположенных в отрицательных вершинах цикла пересчета. В нашем примере это будет х₁₂=10.

Для получения нового допустимого базисного решения осуществляем сдвиг по циклу пересчета выбранной свободной переменной х₁₃ на величину значений выбранной базисной переменной х₁₂=10, которая после сдвига переводится в свободные.

При этом получим новую таблицу матрицы перевозок.

	В1	В2	В3	В4	ai
A1	2	3	2	4
A2	3	2	5	1
A3	4	3	2	6
bj

Сдвиг по циклу привел к новому допустимому базисному решению:

х₁₁=20, х₁₃=10, х₂₂=30, х₂₃=10, х₃₃=10, х₃₄=10, остальные x_ij=0.

Новое решение дает значение целевой функции F=250, меньшее предыдущего, т. е. ближе к оптимальному значению.

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

Для нового базисного решения также подсчитываются суммы стоимостей по циклам пересчета для каждой свободной неизвестной: g₁₂=4, g₁₄=2, g₁₂=4, g₂₁= - 2,g₂₄= - 8, g₃₁= 2, g₂₃= 4.

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

Для рассматриваемого примера оптимальным решением является следующее:

х₁₁=20, х₁₃=10, х₂₂=30, х₂₄=10, х₃₃=10, х₁₂=0, остальные x_ij=0. Стоимость оптимальной перевозки F=170, и уменьшить ее дальше невозможно.