Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 74 стр.

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                           u1 = w1 - gˆ1r +1u r +1 - L - gˆ1i · u i - L - gˆ1nu n ,
                                                                    *




                       …………………………………………..

                           u k = wk - g kr +1u r +1 - L - gˆki * u i - L - gˆknu n ,
                                                                    *




                       …………………………………………..

                        u r = wr - gˆrr +1u r +1 - L - gˆri * u i - L - gˆrnu n .
                                                                *
                                                                                                                   (2)

     8. Перейти к пункту 2 алгоритма, где вместо формул (3.4) использовать
формулы (2).

     Через конечное число итераций либо будет получено решение задачи
линейного   программирования,                    либо       будет          установлено,               что      решение
неограниченно. Заметим, что алгоритм симплекс-метода находит решение
обязательно как угловую точку допустимого множества, даже если это решение
не является единственным.

    Пример 5. Решить задачу линейного программирования из примера 2.

     1. Столбцы с номерами 2,3,5 образуют базис, поскольку

                                              1 2 3
                                             16 2 5 = 30 ¹ 0 .
                                             26 4 8

    Уравнения (1.1) разрешаем относительно переменных x 2 , x 3 , x 5 . Имеем

               x 2 = 5 - 5 x1 + x 4 ,       x 3 = 16 - 13x1 + 2 x 4 ,      x 5 = 6 + 9 x1 - 2 x 4 .

     2. Целевая функция, выраженная через внебазисные переменные угловой
                                                                        точки v , имеет вид
     Таблица 2                                                                      I ( x) = 5 - 9 x1 + x4 .

                      x1                x4          С.ч.                     3. Получено симплекс
       x2             5*                -1             5                разложение для угловой точки
       x3             13                -2             16
       x5             -9                2              6

                                                       74