xn), називається опорним планом, якщо він відповідає крайній точці багатогранника рішень.
План Х = (x 1; ...; xn), який доставляє функцію в екстремум називається оптимальним.
Так ось суть симплекс - методу полягає в упорядкованому переборі тільки опорних планів при якому значення цільової функції зростає. Таким чином ми поступово приходимо до оптимального плану (якщо завдання можна вирішити). p align="justify"> Зауважимо також, що будь-яка здійсненне завдання лінійного програмування може бути зведена до канонічної формі. Зведення нерівностей до рівності досягається введенням додаткових невід'ємних змінних, що входять в цільову функцію з нульовими коефіцієнтами. Для привиди системи обмежень нерівностей до канонічного виду, необхідно в системі обмежень виділити одиничний базис. ol>
Обмеження виду В«?В» - ресурсні обмеження. Справа знаходиться те, що ми використовуємо на виробництві, ліворуч - те, що отримуємо. За таких обмеження вводять додаткові змінні з коефіцієнтом В«+1В», що утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом В«0В». Ці змінні несуть певний економічний зміст. Зазвичай вони відображають недорасхода ресурсів (залишок).
Обмеження виду В«=В». Часто буває, незважаючи на те, що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. У цьому випадку вводяться штучні змінні для створення одиничного базису. У систему обмежень вони входять з коефіцієнтом В«1В», а в цільову функцію з коефіцієнтом В«MВ», які прагнуть до нескінченності (при Fmin - В«+ MВ», при Fmax - В«-MВ»). (Метод штучного базису).
Обмеження виду В«?В» - Планові обмеження. Додаткові змінні (X), що несуть певний економічний сенс - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом В«-1В», в цільову функцію - з коефіцієнтом В«0В». А штучні змінні як у попередньому випадку.
Рішення ЗЛП найбільш раціонально можна виконувати в табличній формі. Такі таблиці називаються симплексними. У різній літературі побудови симплекс таблиць трохи відрізняються один від одного. Найбільш прийнятними на мій погляд є таблиці, описані в табл. 1. br/>
Таблиця 1
БПСП1-x m +1 ................. - X m + s ............. -X nx 1 = x k = x m = b 11 ...................... b 1s ................ b 1, nm b k1 ........................ b ks ................ b k, n-m b m1 ...................... b ms ............... bm, n-mb 10 b k0 b m0f = b 01 ...................... b0s ................. b 0, n-mb 00
1.2 Метод штучного базису
Як вже говорилося вище, часто бувають проблеми з виділенням одиничного базису. У такому випадку кращим є метод штучного бази...
