Линейное программирование. Азарнова Т.В - 43 стр.

                                                                Линейное программирование


                  *       *                              *
                          *                        *
                  *                      *
                                         *         *

        Цикл, который используется в алгоритме решения транспортной зада-
чи, строится следующим образом. Ставятся (*) в клетках из множества Ω B
и в клетке (i 0 , j 0 ) , которая будет вводиться в базис. Просматриваются все
строки таблицы и вычеркиваются те строки, в которых имеется не более од-
ной (*). Затем вычеркиваем те столбцы, в которых содержится не более одно-
го элемента. Затем снова просматриваются строки и т.д. Оставшиеся элемен-
ты образуют цикл.
        Когда цикл построен, можно следующим образом найти коэффициенты
вводимого вектора: перенумеровать все элементы цикла, присвоив вводимо-
му элементу 0, следующему - 1 и т.д.; коэффициенты разложения вектора
 Ai0 j0 равны +1 по векторам из цикла с нечетными номерами, -1 - по элемен-
там цикла с четными номерами и 0 по векторам, не входящим в цикл. Обо-
значим через Ω + множество индексов (i, j ) с четными номерами, через Ω −
- множество индексов (i, j ) с нечетными номерами .
        Зная координаты вектора Ai0 j0 , его можно ввести в базис по правилам
симплексного метода. Поскольку координаты вводимого вектора равны +1
                                                                (     )
или -1, то значение θ = min x ij0 =xi0* j* . Вектор с i * , j * ∈Ω B , на котором
                                    −
                           ( i , j )∈Ω
достигается этот минимум, считается в дальнейшем небазисным. Остальные
базисные координаты новой базисной точки пересчитываются по формуле:
                        x ijH =x ij0 +θ , (i , j ) ∈Ω +;
                              x ijH =x ij0 −θ , (i, j ) ∈Ω −;
xijH =xij по элементам, не входящим в цикл.
Вычисление нового значения функции цели может быть произведено по
формуле                        LH =L −θ∆i0 j0 .
Может оказаться, что     θ = min − xij0            достигается в нескольких нечетных
                                ( i , j )∈Ω
элементах цикла. Тогда небазисным для новой базисной точки считается
только один из них, например тот, которому соответствует наибольшее зна-
чение функции цели. Остальные элементы считаются базисными со значени-
ем в новой базисной точке равными нулю. В этом случае мы имеем вырож-
денную базисную точку.




                                              45