ь. Базисне рішення називається
допустимим базисним рішенням або
опорним рішенням < 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 не менше, аніж на старому. Після низки кроків ми приходимо до опорного рішенням, яке є оптимальним планом.
1.3 Приклад рішення лінійного рівняння симплекс-методом
лінійний симплекс рівняння
До такого виду можна навести будь-яку спільну систему , наприклад, методом Гаусса. Правда, не завжди можна виражати через інші перші r невідомих (ми це зробили для визначеності запису). Однак такі r невідомих обов'язково знайдуться. Ці невідомі (змінні) називаються базисними, решта вільними.
Надаючи певні значення вільним змінним і обчислюючи значення базисних (виражених через вільні), ми будемо отримувати різні рішення нашої системи обмежень. Таким чином, можна отримати бу...
