Вибір таких змінних виконується за певними правилами, що забезпечує максимально швидке збільшення цільової функції.
Розглянемо алгоритм пошуку оптимального рішення на основі симплекс-таблиць:
1. Будується вихідна симплекс-таблиця. p> 2. Симплекс-таблиця будується за такими правилами:
• у першому рядку перераховуються всі змінні завдання, як вихідні (X1, X2, ..., X n ), так і додаткові, введені при приведенні до стандартної форми (X n +1, X n +2, ..., Xk). Для завдань, що містять тільки обмеження В«менше або дорівнюєВ», додаткові змінні X n +1, X n +2, ..., Хк ~ це залишкові змінні;
• у першій колонці таблиці (В«БазисВ») перераховуються змінні, складові початковий базис завдання. Їх кількість завжди дорівнює кількості обмежень. Для завдань, що містять тільки обмеження В«менше або дорівнюєВ», початковий базис складається з залишкових змінних X n +1, X n +2, ..., Xk . У цій же колонці вказується позначення цільової функції E;
• у рядку цільової функції вказуються коефіцієнти цільової функції з протилежним знаком. Для змінних, що не входять в цільову функцію (Наприклад, для залишкових змінних X n +1, X n +2, ..., Xk), вказуються нулі;
• у рядках базисних змінних вказуються коефіцієнти обмежень, в які входять ці змінні. Для змінних, що не входять в обмеження, вказуються нульові коефіцієнти;
• в останньому стовпці («гшенняВ») вказуються значення базисних змінних (вони рівні правим частинам обмежень), а також початкове значення цільової функції (0).
Якщо таблиця побудована правильно, то в стовпці кожної базисної змінної має бути присутня тільки одна одиниця (у рядку обмеження, в яке входить ця змінна); інші коефіцієнти - нульові.
2. Якщо все коефіцієнти в рядку цільової функції невід'ємні, то оптимальне рішення знайдено, і алгоритм завершується. Інакше здійснюється перехід до етапу 3. p> 3. З числа поточних небазисних змінних вибирається змінна, що включається в новий базис. У якості такої змінної вибирається змінна, якій відповідає максимальний по модулю негативний коефіцієнт у рядку цільової функції. Вибір максимального за модулем від'ємного елемента означає включення в базис змінної, збільшення якої призводить до максимального зростання цільової функції.
4. З числа поточних небазисних змінних вибирається змінна, виключається з базису. Для цього обчислюються так звані симплекс-відносини елементів поточного рішення до елементам ведучого шпальти. Мінлива, якій відповідає мінімальне ставлення, виключається з базису. Рядок, відповідну исключаемой змінної, називають провідною рядком, а елемент на перетині провідного рядка і шпальти - провідним елементом.
5. Виконується перетворення симплекс-таблиці за...
