Page 15 - 4719
P. 15

5. Всі елементи ведучої стрічки (крім a ij) множать на λ і
           результат записують у нижню частину кліток.
                6. Всі елементи ведучого стовпчика (крім a ij) множать на
           ”– λ” і результат записується у нижню частину кліток.
                7. У ведучій стрічці обводять всі верхні елементи, крім
           a ij, а у ведучому стовпчику всі нижні.
                8.  Для  всіх  інших  елементів  таблиці  внизу  клітинок
           записують  добуток  обведених  елементів  у  відповідних
           ведучих стрічках і стовпчиках.
                9.  Переписують  таблицю,  замінивши  базову  і  вільну
           змінні  місцями;  елементи  ведучих  стрічок  і  стовпчиків  –
           числами,  які  стояли  внизу  клітинок;  для  інших  клітинок  –
           сумою верхніх і нижніх елементів.
                10.  Якщо  у  стрічці  z  немає  додатних  елементів,  то
           отримано оптимальний розв’язок, інакше переходять до кроку
           2.
                         Штучний початковий розв’язок
                У  симплексному  методі  для  отримання  початкового
           базового  розв’язання  використовувалось  залишкові  змінні.
           Однак, коли вихідне обмеження записане як рівність, або має
           знак  ≥,  не  можна  відразу  отримати  допустимий  початковий
           базовий  розв’язок.  Для  розв’язання    задачі  в  цьому  випадку
           застосовують  штучні  змінні.  Ідея  застосування  штучних
           змінних досить проста. Вона припускає включення додатних
           змінних  у  ліву  частину  кожного  із  рівнянь,  які  не  містять
           „очевидних”  початкових  базових  змінних.  Однак,  введення
           штучних  змінних  допустиме  тільки  в  тому  випадку,  коли
           алгоритм  отримання  оптимального  розв’язку  забезпечує
           рівність нулю штучних змінних в оптимальному розв’язку.
                Розроблено  два  методи  отримання  стартової  точки  за
           допомогою штучних змінних.

                Задача  3.1  Аналітично  за  допомогою  симплекс  методу
           розв’язати задачу лінійного програмування. Знайти максимум
           цільової функції:
                                     Z = 3X + 5X
                                           1
                                                2
           при обмеженнях:


                                          14
   10   11   12   13   14   15   16   17   18   19   20