нлива, переводимая в основні, відсутня, то зазначене відношення вважається рівним). p align="justify"> Рівняння, з якого отримано найменше відношення, виділяється. Виділене рівняння і покаже, яка з основних змінних повинна бути переведена в неосновні. Висловивши нові основні змінні через неосновні, перейдемо до наступного базисного рішенням. p align="justify"> Якщо виділеним виявиться рівняння з негативним вільним членом, то в новому базисному рішенні число негативних компонент буде на одиницю менше, ніж у вихідному. Якщо ж виділеним виявиться рівняння з позитивним (або рівним нулю) вільним членом, то в новому базисному рішенні число негативних компонент збережеться таким же, яким воно було у вихідному базисному рішенні. p align="justify"> Таким чином, при переході до нового базисного рішенням вигідно, щоб виділеним виявилося рівняння з негативним вільним членом, і якщо є можливість вибору, то перевагу слід віддати такому обміну змінних, при якому виділеним виявляється рівняння з негативним вільним членом. p align="justify"> Отже, ми отримаємо нове, покращене базисне рішення, яке ближче до області допустимих рішень системи обмежень. Якщо воно неприпустиме, то до нього слід застосувати ту ж схему ще раз. У результаті через кінцеве число кроків ми отримаємо допустиме базисне рішення. Як тільки буде знайдено допустиме базисне рішення, переходять до другого етапу симплексного методу, сутність якого розглянута при вирішенні завдання
Після оволодіння способом знаходження першого допустимого базисного рішення будь-яка задача лінійного програмування може мати труднощі лише обчислювального характеру.
2. Алгоритм симплекс-методу
Посилена постановка завдання
Розглянемо таку задачу лінійного програмування:
В
Тепер поставимо це завдання в еквівалентній посиленою формі. Необхідно максимізувати Z, де:
В
Тут x - змінні з вихідного лінійного функціоналу, x s - нові змінні, що доповнюють старі таким чином, що нерівність переходить в рівність, c - коефіцієнти вихідного лінійного функціоналу, Z - мінлива, яку необхідно максимізувати. Півпростору і в перетині утворюють багатогранник, який представляє безліч допустимих рішень. Різниця між числом змінних і рівнянь дає нам число ступенів свободи. Простіше кажучи, якщо ми розглядаємо вершину багатогранника, то це число ребер, за якими ми можемо продовжувати рух. Тоді ми можемо присвоїти цьому числу змінних значення 0 і назвати їх В«непростимиВ». Інші змінні при цьому будуть обчислюватися однозначно і називатися В«простимиВ». Отримана точка буде вершиною в перетині відповідних непростим змінним гіперплоскостей. Для того, щоб знайти т.з.. початкове допустиме рішення (вершину, з якої ми почнемо...
