ом ЛП. Алгоритм симплекс-методу носить ітераційний характер.
Симплекс-метод дозволяє переходити від одного допустимого базисного рішення до іншого, причому так, що значення цільової функції безперервно зростають. Алгоритми симплекс-методу дозволяють також встановити, чи є завдання ЛЗ вирішуваною.
Перехід від одного базису до іншого дозволяє знаходити рішення майже всіх задач ЛП. Визначивши всі крайні точки, можна обчислити значення цільової функції і знайти оптимальне рішення. Однак для великих значень m і n це практично неможливо. [1 c.15]
Алгоритм розв'язання задачі ЛП табличним симплексом-методом складається з наступних етапів:
1. розраховують і заповнюють початкову симплекс-таблицю з допустимим одиничним базисом, включаючи індексну рядок.
2. знаходять дозволяючий стовпець;
3. знаходять роздільну рядок;
4. розраховують методом Жордана-Гаусса всі параметри матриці;
5. аналізують отримані дані в індексному рядку.
Таблиці симплекс-методу необхідно будувати до тих пір, поки не буде отриманий оптимальний план. План буде вважатися оптимальним, якщо в останній індексного рядку симплекс-таблиці будуть лише нулі і позитивні числа. [1 c.20-22]
При побудові симплексного методу передбачалося, що всі опорні плани невироджені, що забезпечувало отримання оптимального плану за кінцеве кількість кроків. У разі виродженого плану обчислення виробляють аналогічно, але в цьому випадку можливе повернення до старого базису, що приводь до так званому зациклення. p> Метод штучного базису застосовується при наявності в обмеженні знаків "дорівнює", "більше або дорівнює", "менше або дорівнює" і є модифікацією табличного методу. Рішення системи виробляється шляхом введення штучних змінних зі знаком, що залежать від типу оптимуму, тобто для виключення з базису цих змінних останні вводяться в цільову функцію з великими негативними коефіцієнтами m, а в задачі мінімізації - з позитивними m. Таким чином, з вихідної виходить нова m - завдання. p> Якщо в оптимальному рішенні m - завдання немає штучних змінних, це рішення є оптимальне рішення вихідної задачі. Якщо ж в оптимальному рішенні m - завдання хоч одна з штучних змінних буде відмінна від нуля, то система обмежень вихідної задачі несовместна і вихідна задача нерозв'язна.
В основу модифікованого симплекс - методу покладені такі особливості лінійної алгебри, які дозволяють у ході рішення задачі працювати з частиною матриці обмежень. Іноді метод називають методом зворотної матриці. p> У процесі роботи алгоритму відбувається спонтанне звернення матриці обмежень по частинах, відповідними поточними базисних векторах. Зазначена здатність робить вельми привабливою машинну реалізацію обчислень внаслідок економії пам'яті під проміжні змінні і значного скорочення часу рахунку. Гарний для ситуацій, коли число змінних n значно перевищує число обмежень m.
У цілому, метод відображає традиційні риси з...
