дь-яке її рішення. Нас будуть цікавити особливі рішення, одержувані у випадку, коли вільні змінні дорівнюють нулю. Такі рішення називаються
базисними , їх стільки ж, скільки різних базисних видів у даної системи обмежень. Базисне рішення називається
припустимим базисним рішенням або
опорним рішенням < span align = "justify">, якщо в ньому значення змінних ненегативні. Якщо в якості базисних взяті змінні
X 1 , X 2 , ..., X r , те рішення
{b 1 , b 2 , ..., b r , 0, ..., 0 } буде опорним за умови, що
b 1 < b align = "justify">, b
2 , ..., b r ? 0 .
Симплекс-метод заснований на теоремі, яка називається фундаментальною теоремою симплекс-методу. Серед оптимальних планів задачі лінійного програмування в канонічній формі обов'язково є опорне рішення її системи обмежень. Якщо оптимальний план задачі единственен, то він збігається з деяким опорним рішенням. Різних опорних рішень системи обмежень кінцеве число. Тому рішення задачі в канонічній формі можна було б шукати перебором опорних рішень і вибором серед них того, для якого значення F найбільше. Але, по-перше, всі опорні рішення невідомі і їх потрібно знаходити, a, по-друге, в реальних завданнях цих рішень дуже багато і прямий перебір навряд чи можливий. Симплекс-метод являє собою деяку процедуру направленого перебору опорних рішень. Виходячи з деякого, знайденого заздалегідь опорного рішення за певним алгоритмом симплекс-методу ми підраховуємо нове опорне рішення, на якому значення цільової функції F не менше, аніж на старому. Після низки кроків ми приходимо до опорного рішенням, яке є оптимальним планом.
Отже, симплексний метод вносить певний порядок як при знаходженні першого (вихідного) базисного рішення, так і при переході до інших базисним рішенням. Його ідея полягає в наступному. p align="justify"> Маючи систему обмежень , наведену до загального вигляду, тобто до системи m лінійних рівнянь з n змінними (m , знаходять будь базис...
