7.1.3. Симплексний метод рішення.

Нехай потрібно мінімізувати цільову функцію при обмеженнях (4). Приведемо (4) до стандартного виду (2). Для цього до лівої частини кожного обмеження, що має вид нерівності ≤, добавляємо додатну змінну: . Якщо обмеження у виді нерівності ≥, то з лівої частини віднімаємо . Система прийме вигляд:

Усього змінних . Усі повинні бути додатними. Якщо , то дане рівняння потрібно помножити на (-1). Так як цільова функція не має стаціонарних точок, то своїх максимального і мінімального значень вона досягає на границі області.

Th. Нехай область припустимих рішень - обмежений замкнутий багатогранник, тоді мінімальне (максимальне) значення цільової функції досягається в кутовій точці.

Так як число невідомих більше числа рівнянь , то частина невідомих покладається базисними. Вільні змінні переносяться в праву частину. Система вирішується відносно базисних змінних. Така система сумісна, якщо визначник, що складається з коефіцієнтів при базисних невідомих у системі обмежень відмінний від нуля, чи якщо вектори , що відповідають базисним змінним, є незалежними.

Визначення. Рішення називається базисним, якщо вільні змінні рівні 0.

Кожне базисне рішення відповідає кутовій точці. Кількість базисних рішень:

Таким чином, щоб знайти оптимальне рішення, потрібно обчислити значення цільової функції у всіх кутових точках і вибрати точку, у якій значення цільової функції мінімально (максимально); якщо n велике, то кількість кутових точок велике число.

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

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

Базисні змінні: ; інші - вільні. Нехай вільні змінні рівні 0, отримуємо нульове базисне рішення: .

Далі виникає необхідність перевірити, чи не є знайдене базисне рішення оптимальним. Помітимо, що вектори системи обмежень мають вигляд:

; ;…;; ;…;.

Вектори ,…, – одиничні і утворюють базис у – вимірному просторі, тобто кожний з векторів можна розкласти за даним базисом:

Так як базис одиничний, то . Кожному розкладанню відповідає єдине значення :

Th: (критерій оптимальності) Якщо для деякого базисного рішення розкладання усіх векторів задовольняють умові , то план оптимальний, інакше потрібно вибрати новий базис і шукати нове базисне рішення.