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

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

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

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

• — замкнутости;
• — в каждой вершине должно встречаться два звена.

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

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

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

Рис. 2.

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

• — коэффициент равен 0, если соответствующая базисная клетка не является вершиной цикла пересчета данной свободной клетки;
• — коэффициент равен 1, если базисная клетка является положительной вершиной цикла пересчета данной свободной клетки;
• — коэффициент равен -1, если базисная клетка является отрицательной вершиной пересчета данной свободной клетки.

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

Рис. 3.

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

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

.

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

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

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

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

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

=220 + 310 + 220 + 520 + 210 + 610 = 290.

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

Рис. 4.

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

х_{13 13} = с₁₃ — с₂₃ + с₂₂ — с₁₂ = 2 — 5 + 2 — 3 = -4 ,.

х_{14 14} = с₁₄ — с₂₄ +с₃₃ — с₂₃ + с₂₂ — с₁₂ = 4 — 6 + 2 — 5 + 2 — 3 = -6 ,.

х_{21 21} = с₂₁ — с₁₁ + с₁₂ — с₂₂ = 3 — 2+ 3 — 2 = 2 ,.

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

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

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

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

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

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

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

Таблица 7.

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

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

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

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

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

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

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

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