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

UptoLike

6
Таблица 1.1
J 1 … N N+1
Х(Р(I))
X(Q(J))
B(I)
X(I)
...
X(N)
X(N+1)
...
A(1,N)
B(1)
...
...
...
...
X(N+M)
...
A(M,N)
B(M)
Z(J)
...
C(N)
W(X)
В таблице приняты следующие обозначения:
Р(I) , I=1....,М - номера базисных переменных;
Q(J) , J=l,...,N - номера свободных переменных (небазисных).
Для исходной симплексной таблицы имеем
P(1)=N+1,..., P(M)=N+M;
Q(1)=1,..., Q(N)=N.
В симплексной таблице свободные (небазисные) переменные равны
нулю, а базисные - соответствующим свободным членам В(I).
Z(J) ,J=l, ... ,N+l - индексная строка симплексной таблицы.
B(I) ,I=l, ... ,M+l - столбец свободных членов симплексной таблицы.
Если элементы индексной строки неположительны (J= l.....N), то ре-
шение является оптимальным..
2 Пример
Исходная задача линейного программирования:
2X(1) + X(2) 4;
F(X) = 4X(1) + 3X(2) max;
X(1) + 2X(2) 5; X
Каноническая форма задачи линейного программирования:
2X(1) + X(2) + X3) = 4;
W(X) = - 4X(1) - 3X(2) min;
X(1) + 2X(2) + X(4) = 5; X
I
1
M
M+1
          Таблица 1.1
               J                 1     …           N    N+1
                                      X(Q(J))
      I     Х(Р(I))                                      B(I)
                         X(I)          ...      X(N)

            X(N+1)       A(l,l)         ...     A(1,N)   B(1)
      1
     …         ...         ...          ...       ...     ...

      M     X(N+M)      A(M,1)          ...     A(M,N)   B(M)

    M+1       Z(J)        C(1)          ...      C(N)    W(X)


     В таблице приняты следующие обозначения:
     Р(I) , I=1....,М - номера базисных переменных;
     Q(J) , J=l,...,N - номера свободных переменных (небазисных).
     Для исходной симплексной таблицы имеем
     P(1)=N+1,..., P(M)=N+M;
     Q(1)=1,..., Q(N)=N.
     В симплексной таблице свободные (небазисные) переменные равны
нулю, а базисные - соответствующим свободным членам В(I).
     Z(J) ,J=l, ... ,N+l - индексная строка симплексной таблицы.
     B(I) ,I=l, ... ,M+l - столбец свободных членов симплексной таблицы.
     Если элементы индексной строки неположительны (J= l.....N), то ре-
шение является оптимальным..

     2 Пример

     Исходная задача линейного программирования:
      2X(1) + X(2)  4;
                                       F(X) = 4X(1) + 3X(2)  max;
       X(1) + 2X(2)  5;                                       X

 Каноническая форма задачи линейного программирования:
      2X(1) + X(2) + X3) = 4;
                                       W(X) = - 4X(1) - 3X(2)  min;
       X(1) + 2X(2) + X(4) = 5;                                  X




                                        6