Компьютерное моделирование систем. Князев В.Н - 4 стр.

      N
      A(I,J)·X(J) + X(N+I) = B(I),   I=1,…,M ;
     J=1
                      N
     W(X) = - F(X) = - C(J)·X(J)  min ,
                      J=1           X


     X(J)0, J=1,...,N; X(N+I)0, I=1,...,M;
     X(N+I), I=1,... ,M - дополнительные переменные;
     X(J), J=1,...,N - свободные переменные;
     W(X) – вспомогательная целевая функция для канонической формы.

      Первоначально дополнительные переменные используются в качест-
ве базисных переменных.
      Базисным решением называется такое решение, в котором все сво-
бодные (небазисные) переменные равны нулю. Если при этом базисные
переменные оказываются неотрицательными, то это решение называется
опорным. Оптимальное решение является одним из опорных решений.
      Глобально симплекс-метод можно рассматривать состоящим из двух
этапов. На первом этапе определяют опорное решение. На втором этапе
это решение проверяют на оптимальность и, если оно не оптимально, пе-
реходят к соседнему опорному решению, имеющему меньшее значение
целевой функции, после чего второй этап повторяется.
      В процессе выполнения симплекс-метода либо через конечное число
шагов получается оптимальное решение, либо обнаруживается, что целе-
вая функция не ограничена на множестве допустимых решений.


     1.3 Этапы симплекс-метода

     Укрупненная схема программы симплекс-метода представлена на
рисунке 1.1.




                                      4