Поняття виродженості задач лінійного програмування та спосіб усунення зациклювання у симплекс-методі

 

В пункті 1.4.1 алгоритм симплекс-методу розглядався у припущенні, що задача невироджена.

Нехай тепер дана КЗЛП, для якої , яка має допустимі розв’язки, , але умова невиродженості усіх базисних розв’язків не виконана. Задача лінійного програмування, яка має хоча б один вироджений розв’язок, називається виродженою, у протилежному випадку – невиродженою.

Нехай - будь-який базисний розв’язок, - його базис. Розглянемо спочатку випадок невиродженої ЗЛП.

У випадку невиродженої ЗЛП симплекс-метод за скінчену кількість кроків дає можливість одержати оптимальний розв’язок або встановити факт нерозв’язуваності задачі. Це випливає з того, що кожному базисному розв’язку відповідає свій базис. Кількість базисів не перевищує , де - кількість змінних задачі, - ранг матриці . Отже кількість базисних розв’язків також скінченна. У невиродженому випадку значення цільової функції ЗЛП зростає на кожному кроці. Тобто гарантується неможливість повернення до попередніх планів. Таким чином для невиродженої ЗЛП за скінченну кількість кроків прийдемо до результату.

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

Наприклад, розглянемо задачу

,

,

,

,

.

Вектор є виродженим початковим базисним планом, якому відповідає як базис з векторів та , так і базис, що складається з векторів та . Це означає, що у випадку виродженості може повторюватися значення цільової функції навіть при зміні базисів і тому не завжди вдається знайти оптимальний розв’язок ЗЛП.

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

Тоді, вводячи в базис вектор замість вектора , де — один з номерів, для яких досягається мінімум , ми прийдемо до виродженого розв’язку.

Нехай , де — початковий, або поточний вироджений базисний, розв’язок, — його базис . .

Припустимо, що для нього існує від’ємна оцінка , для якої є додатні .

Переходимо до нового базису, замінюючи вектором один з тих векторів для якого .

Але, якщо хоча б одне з чисел додатне, тоді .

А повний базисний розв’язок

,

.

Тобто, нові значення базисних координат співпадають із старими значеннями, і значення цільової функції після цієї ітерації залишається незмінним.

Отже, змінився лише базис: замість базису маємо базис .

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

Оскільки число наборів базисних векторів скінчене, то після деякого числа “холостих” ітерацій приходимо до одного з висновків:

а) розв’язок оптимальний;

б) задача нерозв’язувана;

в) отриманий базисний розв’язок був на попередніх ітераціях.

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

Нехай .

Якщо , то вектор виводиться з базису.

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

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

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

Приклад 1.14.

,

,

,

.

Приведемо задачу до канонічної форми:

,

.

,

.

Початковим опорним розв’язком є вектор з базисом . Розв’язування задачі наведено у таблиці 1.21.

Таблиця 1.21.

№	Базис
				-2	-5
				1/3		1/3
				1/3		-2/3
				-1/3		2/3
							-1
						-2

 

На першій ітерації . Виникла неоднозначна ситуація з вибором вектора, який треба вивести з базису. Тоді вибір такого вектора можна зробити довільно – або , або . Виберемо . У наступному опорному плані змінна , залишаючись базисною, набуває нульове значення. А тому цей опорний план є виродженим. Критерій оптимальності для нього не виконується. Відповідно на наступній ітерації , а це означає, що попереднє значення цільової функції не зміниться, .

Оптимальним розв’язком буде вектор .

Розглянемо геометричну інтерпретацію цього прикладу

 

 

Рис.1.4.

 

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