Правила вибору який дозволить елемента при пошуку опорного плану

За умови відсутності "0-рядків" (обмежень-рівностей) і "сво-Бодня" змінних (тобто змінних, на які не накладено вимога неотрі-цатель-ності).

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

Є негативні елементи в стовпці вільних членів, наприклад

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

Як роздільною вибираємо рядок, якій відповідає мінімальне відношення:

, де- номер роздільною рядки. Таким чином,- дозволяє елемент.

Після того, як дозволяє елемент знайдений, робимо крок модифікованого жорданова виключення з напрямних елементом

і переходимо до наступної симплексного таблиці.

2. У разі присутності обмежень-рівностей і "вільних" змінних надходять у такий спосіб.

Вибирають дозволяє елемент в "0-рядку" і роблять крок модифікованого жорданова виключення, після чого викреслюють цей дозволяє стовпець. Дану послідовність дій продовжують до тих пір, поки в симплексній таблиці залишається хоча б одна "0-рядок" (при цьому таблиця скорочується).

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

Виродженість в задачах лінійного програмування

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

позитивних компонент, де- число обмежень у задачі. У виродженим опорному плані число позитивних компонент виявляється менше числа обмежень: деякі базисні змінні, відповідні даному опорному плану, приймають нульові значення. Використовуючи геометричну інтерпретацію для найпростішого випадку, коли(Число небазисних змінних дорівнює 2), легко відрізнити вироджену завдання від невироджених. У вироджених задачі в одній вершині багатогранника умов перетинається більше двох прямих, що описуються рівняннями виду. Це означає, що одна або кілька сторін багатокутника умов стягуються в точку.

А

налогічная прив ви-пик-денної задачі в одній вершині перетинається більше 3-х площин.

У припущенні про невирож-ден-ності завдання знаходилося тільки одне значення

, по кото-рому визначався індекс виведеного з базису вектора умов (виведеної з числа базисних змінної). У вироджених завданнюможе досягатися на декількох індекс інфляції-сах відразу (для декількох рядків). В цьому випадку в находиме опорному плані кілька базисних змінних будуть нульовими.

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

Один із прийомів боротьби з виродженням полягає в перетворенні завдання шляхом "незначного" зміни вектора правих частин системи обмежень на величини

, таким чином, щоб задача стала невирож-денної, і, в той же час, щоб ця зміна не вплинуло реально на оптимальний план завдання.

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

нехай змінну

необхідно зробити базисної. Розглянемо мно-дружність індексів, що складається з тих, для яких досягається. безліч індексів, для яких виконується дана умова позначимо через. якщоскладається з одного елемента, то з базису виключається вектор умов(зміннаробиться небазисной).

якщо

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

Практично правилом треба користуватися, якщо зациклення вже виявлено.