|
|
Скiнченнiсть симплекс-методу
ЗЛП будемо називати невиродженою, якщо невиродженими є всі її базисні розв'язки. Розглянемо спочатку невироджену ЗЛП. Якщо вона записана у канонічній формі то це означає, що величини
Оскiльки значення цільової функції у двох послідовних iтерацiйних точках
причому У випадку виродженої ЗЛП одна або декілька базисних змінних базисного розв'язку можуть бути рівними нулю. При цьому Це може привести до того, що на протязі ряду iтерацiй симплекс-методу буде розглядатися одна i та ж вершина, а змінюватимуться лише базисні вектори, що відповідають нульовим базисним змінним i можливе повернення до початкового базису, що відповідає цій вершині. Таке явище називається за циклюванням симплексного методу. Можливiсть зациклювання є реальною лише тоді, коли для розглядуваного базисного розв'язку принаймні дві базисні змінні дорівнюють нулю. У цьому випадку існує неоднозначність при виборі вектора, що підлягає виведенню з базисних при Незважаючи на те, що при розв'язуванні практичних задач зациклювання симплекс-методу не зустрічалося i що побудовано лише декілька штучних прикладів, де це явище має місце, розроблені різні методи його попередження (виходу з циклу). Зроблені вище зауваження свідчать про те, що будь-який з цих методів має гарантувати однозначність вибору вектора, що підлягає виведенню з базисних.
Симплекс-таблицi Спочатку розглянемо допоміжне твердження, що дозволяє стандартним чином (за допомогою симплекс-перетворення) обчислювати симплекс-рiзницi для змінних у КЗЛП. Нехай на s-у кроцi симплекс-методу є КЗЛП
Лема 1.5. Якщо з цільової функції L(x) КЗЛП виключити базисні змінні, то коефіцієнтами при небазисних змінних будуть відповідні їм симплекс-рiзницi i з'являється вільний член, що дорівнює значенню цільової функції в базисній точці, що розглядається. Тепер симплекс-рiзницi змінних у КЗЛП легко одержати, якщо на початковій iтерацiї додати до вихідних непрямих обмежень ЗЛП рівняння L(x) = 0, з якого виключені базисні змінні. На наступних iтерацiях симплексне перетворення застосовується також i до цього нового рівняння. При проведенні ручних розрахунків, пов'язаних з розв'язуванням ЗЛП симплексним методом, зручно всі обчислення на кожній iтерацiї заносити до симплекс-таблицi, що має такий вигляд:
6. 7. Метод штучного базису : застосовується в тих випадках, коли для канонічної форми задачі ЛП не означений початковий опорний план. Тоді симплекс-методом розв’язується перетворена задача зі штучним базисом. Вона утворюється з початкової задачі додаванням до лівої частини векторного рівняння-обмеження стількох штучних одиничних векторів з відповідними невід’ємними штучними змінними, щоб створена матриця містила систему т одиничних, лінійно-незалежних векторів. В цільову функцію початкової задачі додається складова, яка дорівнює добутку суми штучних змінних на число (- М), в разі максимізації Z, або + М, в разі мінімізації Z, де М - досить велике число. Якщо в оптимальному плані задачі зі штучним базисом усі штучні змінні дорівнюють нулю, то відповідний опорний план є оптимальним планом початкової задачі. Якщо оптимальний план задачі зі штучним базисом містить хоч одну штучну змінну або задача нерозв’язна, то початкова задача також не має розв'язків. У попередніх параграфах розглядався випадок, коли система обмежень задачі лінійного програмування містила одиничну матрицю порядку m. Проте більшість задач не можна звести до потрібного вигляду. В такому разі застосовується метод штучного базису. Розглянемо задачу лінійного програмування:
Задача подана в канонічному вигляді і система обмежень (2.61) не містить одиничної матриці. Отримати одиничну матрицю можна, якщо до кожного рівняння в системі обмежень задачі додати одну змінну
У результаті додавання змінних у рівняння системи (2.61) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (2.63) називають розширеною, або М-задачею 8. 9. 10.11.   ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
строго додатні. При цьому додатною є також величина
та 
пов'язані співвідношенням
Звiдси, приймаючи до уваги, що число вершин допустимої множини скiнченне, приходимо до висновку про скінченність симплексного методу.
i, отже, 
Така ж неоднозначність може мати місце i для невиродженого базисного розв'язку. Однак у цьому випадку 
i новий базисний розв'язок приводить до зменшення значення цільової функції. При цьому, внаслідок згаданої неоднозначності, новий базисний розв'язок буде виродженим.
(2.60)
(2.61)
(2.62)
. Такі змінні називають штучними. (Не обов’язково кількість введених штучних змінних має дорівнювати m. Їх необхідно вводити лише в ті рівняння системи обмежень, які не розв’язані відносно базисних змінних.) Допустимо, що система рівнянь (2.61) не містить жодного одиничного вектора, тоді штучну змінну вводять у кожне рівняння:
(2.63)