, що оптимальний план знайдений і значення функції.
1.2 Характеристика симплекс-методу
При вирішенні задач лінійного програмування найбільш поширені 2 способи - графічний і симплекс-метод.
Використання графічного способу зручно лише за рішенні завдань ЛЗ з двома змінними. При більшому числі змінних необхідно застосування алгебраїчного апарату. Інформація, яку можна отримати за допомогою симплекс-методу, не обмежується лише оптимальними значеннями змінних. Симплекс-метод фактично дозволяє дати економічну інтерпретацію отриманого рішення і провести аналіз моделі. p align="justify"> Процес рішення задачі лінійного програмування носить ітераційний характер: однотипні обчислювальні процедури в певній послідовності повторюються до тих пір, поки не буде отримано оптимальне рішення. Процедури, реалізовані у межах симплекс-методу, вимагають застосування обчислювальних машин - могутнього засобу вирішення завдань лінійного програмування. p align="justify"> Симплекс-метод - це характерний приклад ітераційних обчислень, використовуваних при вирішенні більшості оптимізаційних завдань.
При вирішенні задачі ЛП симплекс-методом реалізується упорядкований процес, при якому, починаючи з деякої вихідної припустимою кутовий точки (зазвичай початок координат), здійснюються послідовні переходи від однієї допустимої екстремальної точки до іншої до тих пір, поки що не знайдено точка, відповідна оптимального рішення.
Для знаходження оптимального рішення необхідно від однієї кутової точки переходити до іншої, тобто від вихідного базисного рішення до іншого, при цьому значення функції має рости, якщо завдання на максимум і спадати, якщо завдання на мінімум.
Вибір кожної наступної екстремальній (кутовий) точки при використанні симплекс-методу визначається наступними двома правилами:
). Кожна наступна кутова точка повинна бути суміжній з попередньою. Цей перехід здійснюється по межах (ребрах) простору рішень
). Зворотний перехід до попередньої екстремальній точці не може проводитися. Таким чином, відшукання оптимального рішення починається з деякою допустимої кутової точки, і всі переходи здійснюються тільки до суміжних точкам, причому перед новим переходом кожна з отриманих точок перевіряється на оптимальність. br/>
1.3 Математичний опис алгоритму симплекс-методу
Математично алгоритм симплекс-методу можна представити у декілька кроків:
Крок 1. Побудувати і заповнити вихідну симплекс-таблицю (табл. 1).
Таблиця 1. Вихідна таблиця
Базис ...... СВ ... ...... ... ...
