якщо визначник m-го порядку, складений з коефіцієнтів при змінних
x 1 , x 2 , ..., x m не дорівнює нулю (Д? 0).
Надаючи неосновним (незалежним) змінним довільні числові значення, отримаємо деяке рішення даної системи, причому кожному набору значень незалежних змінних буде відповідати одне певне рішення системи.
Основні (залежні, невільні) змінні будемо називати базисними, неосновні (незалежні, вільні) - небазисними змінними.
Можна скласти незліченна безліч різних наборів значень незалежних змінних. З усіх цих рішень у лінійному програмуванні нас буде цікавити так звані допустимі базисні рішення. p> Допустиме базисне рішення системи лінійних рівнянь за m < n - це таке рішення, в якому неосновним (незалежним, небазисной) змінним дано нульові значення, а значення базисних змінних є невід'ємними ( рішення на межі або вершині симплекса ).
У теорії лінійного програмування доводиться, що якщо оптимальне рішення задачі існує, то воно збігається принаймні з одним із допустимих базисних рішень.
Пошук і спрямовані переходи від одних допустимих базисних рішень до інших з метою визначення оптимального рішення може бути виконаний чисельним методом. Один з них розглянемо нижче. p> Розглянемо обчислювальні та логічні процедури, що забезпечують пошук рішення задачі лінійного програмування симплекс-методом. Процедури пояснюються в процесі вирішення конкретного завдання: знайти сукупність значень, що задовольняють системі нерівностей:
Таким чином, ідея симплекс-методу перетворення моделі полягає в такому інтерактивному направленому переході від одного допустимого базисного рішення до іншого, при якому послідовно поліпшується значення лінійної форми.
Симплекс-метод розв'язання задач лінійного програмування
Симплекс-метод є найбільш поширеним універсальним методом. Існує кілька варіантів цього методу, розглянемо один з них. p align="justify"> Необхідно заздалегідь виконати наступні етапи:
- привести математичну модель до канонічного виду;
визначити початкове допустиме базисне рішення задачі;
Приклад:
L = 3x 1 +2 x 2 В® max
x 1 -x 2 < span align = "justify"> ВЈ 2,
x 1 + x 2 < span align = "justify"> ВЈ 6,
x 1 , x 2 < span align = "justify"> Ві 0
Наведемо задану модель до канонічного виду, ввівши вільні змінні x 3 і x 4 , що перетворюють нерівності в рівності. Змінні x 3 і x 4 входять в рівняння з коефіцієнтом одиниця і тільки один раз:
L = 3x 1 +2 x 2 В® max 1 -x 2 + x 3 = 2,
x 1 + x 2 < span align = "justify"> + x 4 = 6, j Ві 0
де x 3 , x 4 - додаткові змінні, x 1 , x 2 - вільні змінні, A 3, A 4 - початковий базис, A 0 -вектор обмежень.
Складемо симплекс - таблицю, відповідну канонічного виду:
