Элементы теории двойственности. Чернышова Г.Д - 19 стр.

     Пусть есть ситуация, в которой
                                     � j � C BT B �1 A j � c j � 0

и при этом существует, по крайней мере, одна координата ( B �1b) l � 0 . То-
гда ради сохранения вышеприведенного условия предлагается выводить из
базиса вектор Al . Пусть на некоторой итерации происходит замена вектора
Al на Ak , то есть направляющим элементом является alk . Формулы пере-
счета при этом имеют вид:
                                                     alj
                                     aijн � aij �          aik
                                                     alk
                                               alj
                                     a kjн �
                                               alk
                                               bl
                                     bkн �         , в данном случае alk <0.
                                               alk
     Таким образом, вектор Ak стал на место Al . Пусть множество базис-
ных индексов I � �1,..., m�. Рассмотрим, как связаны новые оценки с преды-
дущими.
                                                             �               �
                                        alj          alj     �               � a              alj
                                                             �               �
� j � �ci aij � ck akj � c j � �ci (aij � ) � ck     � c j � � �ci aij � c j � � �ci aik � ck
                                                                                 lj
  н          н         н
                                                                                                  �
        i�I                    i�I       alk     alk         � i�I           � alk i� l       a
        i� l                   i� l                          � i� l          �                 lk
                                                             �               �
   �                � alj
� �� �ci aij � c j �� � (�ci aik � ck ).
  �� i�I           �� alk i�I
     Таким образом получаем
                                                           alj
                                         �нj � � j �             �k � 0 .
                                                           alk
     Отсюда следует правило для нахождения alk :
                                           �k           �j
                                               � min        .
                                           alk   j:a �0
                                                      ljalj
     Если для некоторого l такого, что bl � 0 , а все alj � 0 , то задача не раз-
решима и на этом процесс вычислений заканчивается.
   Если для каждого l такого, что bl � 0 , по крайней мере одна из компо-
нент alj � 0 , то переходим к следующему этапу алгоритма.
     Вычислительная схема алгоритма двойственного симплекс-метода похожа
на вычислительную схему симплекс-метода. Аналогичны и формы таблицы.
                                   19