мального значення) крім стоїть на місці (вільного шпальти), то значить, що
оптимальне рішення отримано . В іншому випадку, переходимо до нової симплекс таблиці по вище описаним алгоритмом.
Розглянемо порядок вирішення задачі за допомогою симплекс-таблиць на прикладі.
Якщо у щойно розглянутої задачі перше ж отримане без жодних зусиль базисне рішення виявилося допустимим, то в ряді завдань вихідне базисне рішення може мати одну, дві і т.д. негативних компонент, тобто бути неприпустимим. У таких завданнях треба спочатку застосувати перший етап симплексного методу, тобто з його допомогою знайти яке-небудь допустиме рішення (або встановити несумісні системи обмежень), а потім вже шукати оптимальне рішення (зробити висновок про суперечність умов задачі). При цьому треба пам'ятати, що на першому етапі застосування симплексного методу, тобто доки ми шукаємо допустиме базисне рішення, лінійна форма не розглядається, а всі перетворення відносяться тільки до системи обмежень. p align="justify"> Нехай задача лінійного програмування задана в канонічної формі, що складається з m незалежних рівнянь з n змінними (або ж вона приведена до такого виду після введення додаткових невід'ємних змінних).
Виберемо групу m основних змінних, які дозволяють знайти початкове базисне рішення (не порушуючи спільності, можемо вважати, що основними змінними є перші m змінних). Висловивши ці основні змінні через неосновні, отримаємо наступну систему обмежень:
В
Цьому способу розбиття змінних на основні та неосновні відповідає базисне рішення ( k 1, k 2 , ..., k m, 0, 0, ..., 0 ). Розглянемо загальний випадок, коли це рішення є неприпустимим. Від отриманого базисного рішення слід спочатку перейти до якомусь допустимому базисного рішенням. Причому не обов'язково, щоб цей перехід здійснювався відразу, за один крок.
За припущенням вихідне базисне рішення неприпустимо. Отже, серед вільних членів системи обмежень (2.16) є хоча б один негативний (число негативних вільних членів цієї системи збігається з числом негативних компонент вихідного базисного рішення). Нехай їм є вільний член i -го рівняння k i, тобто основна мінлива x i у відповідному базисному р...
