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

 

Нехай дана задача лінійного програмування у канонічному виді:

, , , … , .

(1.4.1)

 

Або у векторній формі

,

,

,

де , .

Припустимо, що задача (1.4.1) має допустимий розв’язок і ранг матриці дорівнює . Якщо , то це твердження не має сенсу.

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

Припустимо, що .

Введемо необхідні означення.

Ненульовий допустимий розв’язок задачі (1.4.1) називається базисним або опорним, якщо вектори , які відповідають відмінним від 0 координатам , лінійно незалежні.

Набір векторів називається лінійно незалежним, якщо умова виконується лише при .

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

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

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

Приклад 1.7. Нехай обмеження ЗЛП мають вигляд

,

,

.

В цьому прикладі .

Допустимими розв’язками будуть, наприклад, такі вектори:

.

Вектори та - базисні розв’язки, вектор не є базисним розв’язком.

Для лише вектор зв’язаний з додатною координатою. Цей розв’язок вироджений і його базисом можуть бути пари векторів: .

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

Для базисного невиродженого розв’язку прикладу 1.7 .

Теорема 1.4.1. Вектор тоді і тільки тоді є базисним розв’язком ЗЛП, коли точка — вершина допустимого многогранника.

Доведення.

Необхідність. Нехай — базисний розв’язок задачі (1.4.1). Припустимо, що перші координат більші нуля, тобто .

Тоді і — лінійно незалежні вектори.

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

Але тоді

, і

.

(1.4.2)

З (1.4.2) отримаємо

.

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

Достатність. Нехай — вершина допустимого многогранника . Покажемо, що — базисний розв’язок. Якщо , то — базисний розв’язок. Нехай тепер і .

Нам треба довести, що — лінійно незалежні. Припустимо, що ці вектори лінійно залежні, тобто існують , не всі нульові і такі що

.

(1.4.3)

За умовою — допустимий розв’язок, тоді

.

(1.4.4)

Помноживши ліву і праву частини рівності (1.4.3) на і додаючи до (1.4.4), дістанемо

( - параметр).

Вибираючи настільки малим, щоб , дістанемо, що вектори

і

-

допустимі розв’язки ЗЛП (1.4.1).

Крім того, .

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

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

Перехід від однієї вершини до іншої — це перехід від одного базисного розв’язку до іншого.

Лема 1.4.1. Нехай дано систему -вимірних векторів рангу і

-	(1.4.5)

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

(1.4.6)

за базисом коефіцієнт при відмінний від нуля: .

Доведення.

Необхідність. Якщо , тоді — лінійно залежні і не можуть бути базисом. Отже, .

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

.

Зауважимо, що , інакше б вектори були б лінійно залежними, а це неможливо, бо ці вектори складають частину базису (1.4.5). Тоді

.

(1.4.7)

Тобто, для вектора існує інший, відмінний від (1.4.6), розклад по базису (1.4.5). У розкладі (1.4.7) коефіцієнт при дорівнює нулю, а у розкладі (1.4.5) . Прийшли до протиріччя. Отже — лінійно незалежні і утворюють базис.

Знайдемо тепер координати усіх векторів у певному базисі . З (1.4.6) маємо

.

(1.4.8)

Нехай — -та координата вектора у новому базисі:

.

(1.4.9)

Нехай — розклад у старому базисі. Отримаємо координати цього вектора у новому базисі.

.

Тоді

.

Так

, .

(1.4.10)

Для введеного до базису вектора :

,

.

Формули (1.4.9) також можна отримати із загальних (1.4.10). Дійсно, для

.

Тоді

,

.

Надалі коефіцієнт будемо називати ведучим елементом, а — основним множником.

Тоді ; — -та координата у новому базисі.

При обчисленнях нових координат зручно користуватися таблицями (табл.1.2). Тут у клітинках наведені відповідні координати вектора, до якого відноситься даний стовпець, у старому базисі; вертикальною стрілкою (зверху) відмічено вектор (), який вводиться в базис, а горизонтальною стрілкою (зліва) — вектор (), який виводиться з базису. Вектори нового базису записані у тому ж стовпці, що і вектори старого (лише місце виведеного вектору у ньому займає вектор ). Ведучий елемент будемо обводити колом.

Таблиця 1.2.

↓

№

Базис

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

+ — ←

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

 

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

Для того, щоб у відповідності з формулами (1.4.10) отримати будь-яку, наприклад, -ту координату вектора , треба виділити на таблиці прямокутник, одна з діагоналей (головна) якого з’єднує клітинку з клітинкою , а інша діагональ (додаткова) — клітинку з клітинкою .

Елементи головної діагоналі перемножуються (причому у ведучій клітинці використовується нове значення 1) і з цього добутку віднімається добуток елементів додаткової діагоналі (причому у відповідній клітинці ведучої строчки знову береться нове значення).

Тобто, .

Приклад 1.8. Нехай

.

Вектори утворюють базис даної системи векторів. Необхідно переконатися, що вектори також утворюють базис і знайти координати усіх векторів у новому базисі.

Базисна матриця, складена з векторів , така

.

Координати будь-якого вектора у даному базисі можна знайти по формулі

,

(1.4.11)

де - вектор-стовпець , - обернена матриця до базисної матриці ,

- вектор-стовпець шуканих координат вектора . У нашому випадку

.

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

Отже,

.

Підрахуємо тепер координати векторів :

,

.

Переконаємося, що заміна у початковому базисі вектора вектором знову приводить до базису. Згідно леми 1.4.1, для цього достатньо перевірити відмінність від нуля координати вектора , відповідної вектору . Оскільки вектор займає третє місце в базисі, то потрібно перевірити третю координату вектора , тобто : .

У нашому випадку і ведучий елемент .

Тоді координати векторів у новому базисі будуть такими:

,

,

,

,

,

.

Координати базисних векторів відомі.

.

Проводячи обчислення по таблиці прийдемо до тих же результатів:

Таблиця 1.3.

↓

№

Базис

←

 

Координати векторів у новому базисі наведені у таблиці 1.4.

Таблиця 1.4.

№	Базис

 

 

Введемо поняття оцінки вектора. Нехай вектори утворюють базис. Позначимо через таку суму

або . Тоді оцінкою вектора називається різниця:

.

Для усіх базисних векторів оцінки дорівнюють нулеві. Дійсно, якщо — базисний вектор, що займає -те місце у базисі, то для цього вектора і .

Нехай дана КЗЛП (1.4.1) і припустимо, що всі її базисні розв’язки невироджені. Надалі назвемо ЗЛП невиродженою, якщо всі її базисні розв’язки невироджені.

Теорема 1.4.2. (про можливість поліпшення базисного розв’язку)

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

.

Доведення.

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

.

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

Координати вектора у новому базисі будуть:

,

де — координати вектора у старому базисі, тобто .

Для того, щоб новий базисний розв’язок

, де

, а інші координати нульові, був невиродженим необхідно, щоб .

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

Якщо ж , то (згідно умови теореми). Тобто, новий базисний розв’язок невироджений.

Знайдемо тепер значення цільової функції при новому базисному розв’язку:

.

Додаючи до цієї суми і згрупувавши доданки, дістанемо:

.

Або .

Оскільки і , то , що і треба було довести.

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

Теорема 1.4.3. (критерій оптимальності базисного розв’язку)

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

Доведення.

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

Візьмемо інший допустимий розв’язок .

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

Покажемо, що .

Оскільки і , то

.

(1.4.12)

Оскільки — допустимий розв’язок, то

.

Але і

.

Але ж — також допустимий розв’язок, то

.

Оскільки розклад будь-якого вектора по базису єдиний, то

.

Підставляючи це в (1.4.12), дістанемо

,

що і треба було довести.

Теорема 1.4.4. (ознака необмеженості цільової функції)

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

Доведення.

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

Розглянемо вектор з координатами , де - довільне додатне число.

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

.

Підрахуємо тепер значення цільової функції для побудованого допустимого розв’язку

.

(1.4.13)

 

Оскільки , то згідно (1.4.13) цільову функцію можна збільшувати необмежено, залишаючись у допустимій області. Теорему доведено.

Зауваження. Теореми 1.4.3 та 1.4.4 справедливі і без припущення невиродженості базисних розв’язків. Дійсно, легко бачити по доведенням, що фактично використовувалась не умова , а .

Розглянемо тепер випадок, коли умови теореми 1.4.2 не виконані: хоча і є таке, що серед чисел є додатні, але досягається не при одному, а при декількох значеннях .

Покажемо, що якщо дана задача невироджена (що ми і припускали), то такого випадку просто не може бути.

Дійсно, нехай

.

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

.

Очевидно, що і . Але при маємо , бо .

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

Отже, для невироджених ЗЛП можливі лише три випадки:

1. Усі і, таким чином, розв’язок оптимальний.

2. Існує така, що усі . Тоді задача не має оптимального розв’язку. Її цільова функція не обмежена зверху на допустимій множині.

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

.

Переходячи у випадку 3 до нового базису, можемо по формулам (1.4.10) знайти новий базисний розв’язок і координати усіх