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

UptoLike

5
Рис. 1.1 – Укрупненная схема программы симплекс-метода
Первоначально составляется исходная симплексная таблица S
(табл.1.1) с опорным решением S=S(I,J), I=1,...,M+1, J=1,...,N+1.
Начало
Ввод M, N ;
P(I),I=1,…,M;
Q(J),J=1,…,N
S(I,J),I=1,…,
M+1; J=1,…,
N+1
Определение
S(I,N+1)
min ———-
I=1,…,M S(I,K)
S(I,K)>0
и ключевой строки R
S(M+1,J)0
J=1,…,N
Обмен X(P(R))
и X(Q(K))
Пересчѐт
симплексной таблицы
S(I,J) , I=1,…,M+1,
J=1,…,N+1
Определение
max S(M+1,J) ,
J=1,…,N
и
ключевого столбца K
S(I,K)0
I=1,…,M
Вывод
X(P(I))=B(I),
I=1,…,M ;
X(Q(J))=0;
J=1,…,N;
F(X)=S(M+1,
N+1)
Вывод
"Функция не
ограничена"
Конец
Да
Нет
Нет
           Начало
                                                        Определение
                                                              S(I,N+1)
                                                        min    ———-
                                                    I=1,…,M     S(I,K)
                                                    S(I,K)>0
       Ввод M, N ;
       P(I),I=1,…,M;                                и ключевой строки R
       Q(J),J=1,…,N
       S(I,J),I=1,…,
       M+1; J=1,…,                                   Обмен X(P(R))
       N+1                                              и X(Q(K))



                                                           Пересчѐт
                                                    симплексной таблицы
                                                     S(I,J) , I=1,…,M+1,
                                                              J=1,…,N+1




                       Нет     Определение                                 Нет
      S(M+1,J)0               max S(M+1,J) ,             S(I,K)0
        J=1,…,N                   J=1,…,N                 I=1,…,M
                                      и
                             ключевого столбца K


                Да                                                   Да
    Вывод
    X(P(I))=B(I),                                         Вывод
    I=1,…,M ;                                         "Функция не
    X(Q(J))=0;                       Конец            ограничена"
    J=1,…,N;
    F(X)=S(M+1,
    N+1)




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




      Первоначально составляется исходная симплексная таблица S
(табл.1.1) с опорным решением S=S(I,J), I=1,...,M+1, J=1,...,N+1.




                                         5