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