. Це правило складає основу використовуваного в обчислювальної
схемою симплекс-методу умови оптимальності , яке полягає в
тому , що , якщо в задачі максимізації всі небазисні змінні в
Z - рівнянні мають невід'ємні коефіцієнти , отримане пробне рішення є оптимальним . В іншому випадку в ка-
честве нової базисної змінної слід вибрати ту , яка має
найбільший за абсолютною величиною негативний коефіцієнт .
Застосовуючи умова оптимальності до початкової таблиці , виберемо
в якості змінної , що включається в базис , змінну Х 2 . Исклю-
чаемая змінна повинна бути обрана з сукупності базисних
змінних S 1 , S 2 . Процедура вибору исключаемой змінної передбачає перевірку умови допустимості , вимагає , щоб в якості исключаемой змінної вибиралася та з пере-
сних поточного базису , яка першою звертається в нуль при збіль-
ліченіі включаемой змінної X 2 аж до значення , відповідного суміжною екстремальній точці .
Цікавить нас ставлення (фіксує шукану точку пе-ресечения і ідентифікує исключаемую змінну) можна
визначити з симплекс-таблиці. Для цього в стовпці, відповідному введеної змінної X 2 , викреслюються негативні і нульові елементи обмежень . Потім обчислюються відносини постійних , що фігурують у правих частинах цих обмежень , до решти елементам стовпця , відповідного введеної перемінної X 2 . виключаємо змінної буде та змінна поточного базису, для якої вказане вище відношення мінімально.
Початкова симплекс-таблиця для нашої задачі, одержувана після перевірки умови допустимості (тобто після обчислення відповідних відносин та визначення исключаемой змінної), відтворена нижче. Для зручності опису обчислювальних процедур, здійснюваних на наступній ітерації, введемо ряд необхідних визначень. Стовпець симплекс-таблиці, асоційований з введеної перемінної, будемо називати провідним стовпцем. Рядок, відповідну исключаемой змінної, назвемо провідною рядком (рівнянням), а елемент таблиці, що знаходиться на перетині ведучого шпальти і ведучою рядка, будемо називати провідним елементом.
Після того, як визначені включається і исключаемая пере-
менниє (з використанням умов оптимальності і допустимості),
наступна ітерація (пошук нового базисного рішення) здійснюва-
ється методом виключення змінних, або методом Гаусса - Жордана. Цей процес зміни базису включає обчислювальні процедури двох типів.
Тип 1 (формування провідного рівняння).
Нова ведуча рядок = Попередня ведуча рядок / Провідний елемент
Тип 2 (формування всіх інших рівнянь , Включаючи Z - y рівняння).
Нове рівняння = Попереднє рівняння -
Г© Коефіцієнт Г№
ГЄ ведучого шпальти ГЄ * ( Нова провідна рядок).
ГЄ попереднього ГЄ
Г« рівняння Г»
Виконання процедури типу 1 призводить до того, що в новому
провідному рівнянні провідний елемент стає рівним одиниці.
У результаті здійснення процедури типу 2 всі інші коеф-
вантаження, що фігурують у провідному стовпці, стають рівними
нулю. Це еквівалентно одержанню базисного рішення шляхом ис-
ключения введеної перемінної із всіх рівнянь, крім ведучого.
Застосовуючи до початкової таблиці процедуру 1, ми ділимо S 2 - рівняння на провідний елемент , рівний 1.
Базисні змінні
Z
X 1
X 2
S 1
S 2
Рішення
Z
В В В В В В
S 1
В В В В В В
S 2
0
-...
