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

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


                                        u i +v j =c ij , (i, j ) ∈Ω B ,    (5)
где Ω B - множество базисных пар индексов. Заметим, что система (5) име-
ет n +m переменных и m +n −1 уравнение. Ранг системы равен m +n −1 .
Отсюда следует, что одну из переменных можно выбрать произвольно, на-
пример, u1 =0 , а все остальные переменные найти по цепочке.
Сформулируем теперь критерий оптимальности для транспортной задачи.
Пусть X =( xij0 ), i =1, m, j =1, n - некоторое базисное решение транспортной
задачи, Ω B - множество базисных пар индексов данного базисного решения,
u i0 , i =1, m и v 0j , j =1, n - произвольное решение системы
                        u i +v j =c ij , (i, j ) ∈Ω B .
Если существует пара индексов (i, j )∉Ω B , для которой
                              u i0 +v 0j >cij ,
то существует базисное решение X =(xij ), для которого
                                   m                m
                                   ∑ ∑ cij xij ≤∑ ∑ c ij xij0 ,                                 (6)
                                   i =1 j =1       i =1 j =1

если для всех пар индексов                     (i, j )∉Ω B     выполнено          u i0 +v 0j ≤cij , то
 X =( x ij0 ), i =1, m, j =1, n - решение задачи. Заметим, что для транспортной за-
дачи гарантируется построение новой базисной точки, так как эта задача при
соблюдении баланса всегда разрешима. Отметим также, что неравенство (6)
является нестрогим в связи с возможностью вырожденности базисных точек.
Как следует из алгоритма симплексного метода, если существует вектор
 Ai0 j0 с положительной оценкой, то вектор Ai0 j0 должен быть введен в базис.
Для введения вектора в базис нужно знать его текущие координаты. Заметим,
что эти координаты являются коэффициентами разложения вектора Ai0 j0 по
текущему базису. В транспортной задачи для определения координат исполь-
зуется понятие цикла.

      Определение. Говорят, что множество пар индексов (i, j ) образует
цикл, если их можно расположить, например, в следующей последователь-
ности: (i 0 , j 0 ) → (i 0 , j1 ) → (i1 , j1 ) → ... → (i k , j k ) → (i k , j 0 ) → (i 0 , j 0 ) . От-
метим, что каждые две рядом стоящие пары индексов должны иметь оди-
наковые номера строк или одинаковые номера столбцов. Сами пары, входя-
щие в цикл, называются элементами цикла..

         Рассмотрим пример цикла.




                                                 45