3.3.  Загальна ідея симплекс-методу та його графічна інтерпретація.

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

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

Загальну ідею симплекс-методу можна проілюструвати на прикладі моделі задачі «про фарби». Простір розв’язків цієї задачі представлено на рис. Вихідною точкою алгоритму є початок координат (точка А на рис. 3.1). Розв’язок, що відповідає цій точці, прийнято нази¬вати початковим розв’язком. 

           

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 3.1. Графічна інтерпретація симплекс-методу.

 

Від вихідної точки здійснюється перехід до деякої суміжної кутової точки, в аналізованому випадку це може бути точка В або точка F. Вибір точки залежить від коефіцієнтів цільової функції. Оскільки коефіцієнт цільової функції при х1 більший від коефіцієнту при х2 , а цільова функція підлягає максимізації, то необхідний напрямок переходу відповідає збільшенню х1 , що приводить до екстремальної точки В. Після цього зазначений процес повторюється, щоб з'ясувати, чи існує інша екстремальна точка, що відповідає кращому допустимому розв’язку (у даному випадку більшому значенню цільової функції). Використовуючи, як і раніше, інформацію про цільову функцію, можна визначити, чи є на даному кроці алгоритму така точка. В результаті такий ітеративний процес дозволяє знайти оптимальну кутову точку С.

Вибір наступної екстремальної точки визначається такими правилами.

1. Кожна наступна кутова точка має бути суміжною з попередньою. Наприклад, у просторі розв’язків, зображеному на рис.1, неможливий прямий перехід від точки А до точки С. Цей перехід здійснюється по границях (ребрах) простору розв’язків: від точки А до точки В і лише потім від точки В до точки С.

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

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

Для того, щоб формально описати розглянуті процедури, необхідно геометричним поняттям «простір розв’язків» та «кутові точки» поставити у відповідність їх алгебраїчні визначення (див. Табл. 3.1.)

Таблиця 3.1

Геометричне

Визначення

(графічний метод)     Алгебраїчне  визначення

(симплекс-метод)

 

Простір розв’язків

 

Кутові точки               

Обмеження моделі в стандартній формі

 

Базисні розв’язки задачів стандартній формі