Задачи линейного программирования транспортного типа. Горячев Л.В. - 9 стр.

                                                                                                      9

оставляет их без изменений (вырожденный случай). Опишем отдельную итерацию метода, ограни-
чившись вначале невырожденным случаем.
    Допустим, что мы находимся на k – ой итерации метода и имеем опорный план X k = xkij mn .
Рассмотрим очередную k + 1 итерацию.
    Этап 1. Составляем систему уравнений для определения потенциалов строк и столбцов: vj −
ui = cij для (i, j) – базисных. Число уравнений, ввиду опорности плана, равно m + n − 1, а число
переменных — m + n. Значение одной из переменных, например u1 , зададим сами u1 = 0. Тогда
система довольно просто решается, и находятся неизвестные ui , vj , i = 1, 2, . . . , m. Если полученные
величины удовлетворяют неравенствам vj −ui ≤ cij для любой пары (i, j), то опорный план является
оптимальным планом двойственной задачи. Если же хотя бы для одной пары индексов (i, j) vj −
ui > cij , то план X k не оптимален и может быть улучшен.
    Этап 2. Вычисляем уклонения для всех внебазисных клеток ij = cij − (vj − ui ). По условию,
среди чисел ij есть отрицательные. Определим пару (i0 , j0 ) из условия i0 j0 = min ij . Вообще
говоря, в качестве (i0 , j0 ) можно принять любую пару (i, j) с отрицательным уклонением, но такой
выбор ускоряет сходимость. Из выбранной и базисной клеток строим цикл. Это можно сделать,
так как система векторов будет линейно-зависима. В новом опорном плане будет присутствовать
клеточка (i0 , j0 ), поэтому надо найти базисную клеточку цикла, которая должна быть исключена.
Таким образом, общее число базисных компонент останется равным m + n − 1. В узлах цикла,
начиная с клеточки (i0 , j0 ), расставляем поочередно знаки  + и  − . Рассмотрим клеточки цикла
со знаком  − . Минимальную перевозку в таких клетках обозначим через Θ0 , то есть

                                         Θ0 = min xij = xik jl                                     (12)
                                               (i,j)


От перевозок, стоявших в клеточках с  − , отнимаем величину Θ0 , а в клеточках с  + добавим
к перевозкам величину Θ0 . В результате клеточка (ik , jl ) выйдет из числа базисных, а оставшиеся
в плане клеточки будут образовывать новый опорный план. Возможно, что в некоторых клеточках
нового опорного плана будут нулевые перевозки: этот случай возникнет, если минимум в (12) будет
достигаться на двух или более парах (i, j). Значение линейной формы Т.З. на новом опорном плане
уменьшиться на величину Θ0 i0 j0 . (Доказать!).
   Если улучшаемым является вырожденный опорный план, тогда среди базисных компонент име-
ются нулевые перевозки. В этом случае при переходе по методу потенциалов к следующему опорно-
му плану величина Θ0 окажется равной нулю и, следовательно, суммарные транспортные издержки
не уменьшаться. При этом монотонность убывания нарушается и конечность алгоритма, вообще го-
воря, не очевидна.

                              Построение начальных опорных планов.

    1. Метод северо-западного угла. Алгоритм построения плана состоит из нескольких шагов, на
каждом из которых заполняется либо строка (случай 1), либо столбец (случай 2) матрицы плана
X = xij m·n . Процесс начинается с заполнения клеточки (1, 1): x11 = min(a1 , b1 ). Если a1 < b1 ,
тогда x11 := a1 , остальные клеточки строки остаются незаполненными, и первую строку исключаем
из дальнейшего рассмотрения, b1 := b1 − a1 .
    Если a1 ≥ b1 , тогда x11 = b1 , исключаем из рассмотрения первый столбец, а ai = a1 − b1 . На
этом первый шаг заканчивается. Допустим, что уже проделано t шагов, опишем t + 1 шаг.
    Снова найдем левый верхний элемент матрицы плана X из числа еще не определенных.    µ−1 Пусть
этим элементом будет xλµ , (λ + µ = t + 2). Полагаем, xλµ = min(aλ , bµ ), aλ := aλ − j=1 xλj , где
          λ−1
bµ := bµ − i=1 xiµ . Если aλ < bµ , то xλµ := aλ , bµ := bµ −aλ и строку λ исключаем из рассмотрения.
    Если aλ ≥ bµ , то заполняем нулями µ – ый столбец, начиная с (λ + 1) – й строки. При этом
aλ := aλ − bµ .
    Алгоритм продолжает работать до полного распределения произведенного продукта по пунк-
там потребления. План, полученный методом северо-западного угла, всегда является опорным. Это
следует из того, что на каждом шаге мы вычеркиваем либо строку, либо столбец, что означает, что
ни одна из заполняемых клеток не войдет в цикл. На последнем шаге заполняются две или более
клеточки.