Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

2.8.7. Зациклення в задачах лінійного програмування

Як доведено вище, оптимальний план задачі лінійного програмування може знаходитись в одній з кутових точок багатогранника розв’язків, кількість яких є скінченною, тому, використовуючи для розв’язування задачі симплексний метод, за скінченну кількість кроків можна знайти оптимальний план або з’ясувати, що задача не має розв’язку. Однак строга монотонність симплексного алгоритму має місце лише у разі невиродженості всіх опорних планів, які отримані в ході ітераційної процедури алгоритму.

Якщо при дослідженні значень у симплексній таблиці існує кілька однакових значень з-поміж , то це означає, що можна вибрати для виключення з базису більш ніж один вектор. Наступна ітерація симплексного методу призведе до виродженого опорного плану, в якому хоча б одна з базисних змінних дорівнюватиме нулю.

Якщо деякий опорний план буде виродженим, тобто один або більше вільних членів основної системи обмежень дорівнюватимуть нулю, то при визначенні вектора, який необхідно на наступному кроці виводити з базису, найменше значення q буде дорівнювати нулю і відповідати тому рівнянню, вільний член якого нульовий. Отже, в наступній ітерації буде виведена з базису відповідна змінна, причому всі значення базисних змінних в наступному опорному плані залишаться без змін, тобто значення цільової функції після проведення ітерації не зміниться.

Це означає, що наступні ітерації можуть не привести до покращення значення цільової функції. В такому разі після певного числа ітерацій дістають план, який вже було отримано раніше в процесі розв’язування задачі. Подальші ітерації, проведені аналогічно, приведуть до повторного перебору тих самих опорних планів. Вироджений план є причиною того, що теоретично виникає можливість нескінченного числа повторень однакових послідовностей ітерацій, які не покращують розв’язку, тобто обчислювальна процедура не буде мати кінця. Таку ситуацію називають зацикленням. Циклу можна було б уникнути, запам’ятовуючи опорні плани, що утворили цикл, і не повертаючись до них. Проте, щоб забезпечити однозначність вибору вектора, який виводиться з базису, розроблено ряд спеціальних прийомів. Найцікавішим з них є так званий e-метод.

Виродженому плану відповідає вершина множини планів, що утворена більш ніж n гіперплощинами. Інакше кажучи, одна вершина відповідає кільком виродженим планам, що означає злиття кількох вершин багатогранника в одну. Ідея e-методу усунення зациклення полягає в роз’єднуванні злитих вершин. Для цього досить, очевидно, ввести замість нулів у відповідні рівняння якісь інші значення, однак зробити це так, щоб не було знову кількох мінімальних співвідношень у наступному кроці. У такий спосіб замість початкової матимемо змінену задачу. Проте можна легко довести, що, діставши оптимальний план зміненої задачі, й допустивши, що введені величини дорівнюють нулю, матимемо оптимальний розв’язок початкової задачі.

На практиці вводять величини, які є дуже малими – це поліноми довільно взятої малої (близької до нуля) додатної величини e. Коефіцієнтами поліномів беруть коефіцієнти при невідомих (базисних і небазисних) відповідного рівняння, а степенями e-номери цих невідомих, тобто для деякого i-го рівняння маємо поліном виду:

Цілком зрозуміло, що для будь-яких можна вибрати eнастільки малим, що завжди , бо доданки зі степенями e, вищими від і-го, будуть вищого порядку малості у порівнянні з першим . Внаслідок цього всі утворені поліноми різнитимуться за величиною. В оптимальному плані необхідно буде допустити, що .

Зауважимо, що в разі підозри на можливість зациклення (випадок, коли початковий опорний план вироджений) поліноми можна одразу додати до вільних членів системи обмежень, внаслідок чого матимемо: .