Тема 2.4. Симплекс-метод лінійного програмування.
Двовимірні задачі лінійного програмування вирішуються графічно. Для випадку N = 3 можна розглянути тривимірний простір і цільова функція буде досягати своє оптимальне значення в одній з вершин багатогранника.
У загальному вигляді, коли в завданні беруть участь N-невідомо, можна сказати, що область допустимих рішень, що задається системою обмежуючих умов, представляється опуклим многогранником в n-мірному просторі і оптимальне значення цільової функції досягається в одній або декількох вершинах. Вирішити ці завдання графічно, коли кількість змінних більше 3 вельми скрутно. Існує універсальний спосіб вирішення завдань лінійного програмування, званий симплекс-методом.
Симплекс-метод є основним в лінійному програмуванні. Рішення завдання починається з розглядів однієї з вершин багатогранника умов. Якщо досліджувана вершина не відповідає максимуму (мінімуму), то переходять до сусідньої, збільшуючи значення функції мети при вирішенні задачі на максимум і зменшуючи при вирішенні задачі на мінімум. Таким чином, перехід від однієї вершини до іншої покращує значення функції мети. Так як число вершин багатогранника обмежена, то за кінцеве число кроків гарантується знаходження оптимального значення або встановлення того факту, що завдання нерозв'язна.
Цей метод є універсальним, застосовним до будь-якого завдання лінійного програмування в канонічної формі. Система обмежень тут - система лінійних рівнянь, в якій кількість невідомих більша за кількість рівнянь. Якщо ранг системи дорівнює r. то ми можемо вибрати r невідомих, які висловимо через інші невідомі. Для визначеності припустимо, що обрані перші, що йдуть підряд, невідомі X 1. X 2. X r. Тоді наша система рівнянь може бути записана як
До такого виду можна навести будь-яку спільну систему. наприклад, методом Гаусса. Правда, не завжди можна висловлювати через інші перші r невідомих (ми це зробили для визначеності записи). Однак такі r невідомих обов'язково знайдуться. Ці невідомі (змінні) називаються базисними, інші вільними.
Надаючи певні значення вільним змінним і обчислюючи значення базисних (виражених через вільні), ми будемо отримувати різні рішення нашої системи обмежень. Таким чином, можна отримати будь-яке її рішення. Нас будуть цікавити особливі рішення, одержувані в разі, коли вільні змінні дорівнюють нулю. Такі рішення називаються базисними. їх стільки ж, скільки різних базисних видів у даної системи обмежень. Базисне рішення називається допустимим базисним рішенням або опорним рішенням. якщо в ньому значення змінних невід'ємні. Якщо в якості базисних взяті змінні X 1. X 2. X r. то рішення 1. b 2. b r. 0. 0> буде опорним за умови, що b 1. b 2. b r ≥ 0.
Симплекс-метод заснований на теоремі, яка називається фундаментальною теоремою симплекс-методу. Серед оптимальних планів задачі лінійного програмування в канонічної формі обов'язково є опорне рішення її системи обмежень. Якщо оптимальний план завдання единственен, то він збігається з деяким опорним рішенням. Різних опорних рішень системи обмежень кінцеве число. Тому рішення задачі в канонічній формі можна було б шукати перебором опорних рішень і вибором серед них того, для якого значення F найбільше. Але, по-перше, все опорні рішення невідомі і їх потрібно знаходити, a, по-друге, в реальних задачах цих рішень дуже багато і прямий перебір навряд чи можливий. Симплекс-метод являє собою деяку процедуру спрямованого перебору опорних рішень. Виходячи з деякого, знайденого заздалегідь опорного рішення за певним алгоритмом симплекс-методу ми підраховуємо нове опорне рішення, на якому значення цільової функції F не менше, аніж на старому. Після ряду кроків ми приходимо до опорного рішення, яке є оптимальним планом.
Отже, симплексний метод вносить певний порядок як при знаходженні першого (вихідного) базисного рішення, так і при переході до інших базисним рішенням. Його ідея полягає в наступному.
Імеясістему обмежень. наведену до загального вигляду, тобто до системи m лінійних рівнянь з n змінними (m