3. 4. Алгоритм симплексного методу.

 Розглянемо сутність процедур симплекс-методу. З цією метою попередньо запишемо модель задачі “про фарби” в стандартній формі та визначимо початковий допустимий розв’язок. Ввівши до лівої частини кожного обмеження (крім обмежень на знак змінних) залишкову змінну, отримаємо модель у стандартному вигляді:

Z=3x1+2x2 ® max

 

Залишкові змінні x3, x4, x5, x6 мають одиничний коефіцієнт в одному з чотирьох обмежень і відсутні в трьох інших, причому кожне обмеження містить лише одну залишкову змінну. Отже, ці змінні створюють одиничний базис системи лінійних рівнянь. Крім того, всі залишкові змінні є невід’ємними, а отже створений ними базисний розв’язок є допустимим.

У даному початковому допустимому розв’язку значення цільової функції дорівнює 0. Перетворимо рівняння цільової функції так, щоб його права частина містила лише сталу величину: z - 3x1-2x2=0.

Тепер праві частини всіх рівнянь (у тому числі z-рівняння та обмежень) повністю характеризують початковий розв’язок. Це має місце в усіх випадках, коли початковий базис складається із залишкових змінних. Початковий розв’язок задачі подамо у вигляді таблиці 3.2.

Таблиця 3.2 Симплекс-таблиця з початковим розв’язком задачі “про фарби”

Перший стовпець таблиці містить назви змінних початкового базису, значення яких наведені в стовпці «Розв’язок». При цьому вважається, що небазисні змінні x1 і x2 дорівнюють нулю. Значення цільової функції z=3´0+2´0+0´1+0´2+0´6+0´8=0, що й показано в останньому стовпці таблиці.

Необхідно перевірити, чи не є даний розв’язок оптимальним. У z-рівнянні обидві небазисні змінні x1 і x2 мають від’ємні коефіцієнти, що еквівалентно наявності додатних коефіцієнтів у вихідній цільовій функції. Отже, збільшення значення x1 або x2 призведе до покращання (збільшення) значення цільової функції. Проте логічно зробити припущення, що збільшення x1 забезпечить більш скоре зростання цільової функції. Це правило складає основу умови оптимальності, яке застосовується в процедурі симплекс-методу.

УМОВА ОПТИМАЛЬНОСТІ. На кожному кроці симплексного методу для включення до нового базису має бути обрана змінна, що має в рівнянні цільової функції найбільший за модулем від’ємний коефіцієнт (в задачі на максимум) або найбільший додатній коефіцієнт (в задачі на мінімум). Розв’язок буде оптимальним, якщо в z-рівнянні всі коефіцієнти є невід’ємними (в задачі максимізації) або невід’ємними (в задачі мінімізації).

Введення x1 до базису означає збільшення значення цієї змінної. Збільшувати x1 можна лише до деякої границі, вище якої розв’язок стає недопустимим. Покажемо, що це дійсно так.

У задачі, що розглядається, з кожного обмеження виразимо змінні поточного базису через змінну x1 (ту, що вводиться до нового базису):

x3=1+ x1, x4=2, x5=6-x1, x6=8-2x1.

Очевидно, що збільшення x1 не може зробити змінну x3 від’ємною й ніяк не впливає на значення x4. При збільшенні x1 вище x1=4 змінна x6 набуде від’ємного значення, а одержаний при цьому розв’язок буде недопустимим.

Сформулюємо тепер правило вибору змінної, що виключається з базису, або «умову допустимості».

УМОВА ДОПУСТИМОСТІ. В задачах максимізації та мінімізації для виключення з базису вибирається така поточна базисна змінна, для якої виконується умова: відношення правої частини відповідного обмеження до додатного коефіцієнта при змінній, що включається до базису, є мінімальним. У випадку рівності цього відношення для двох або декількох змінних вибір проводиться довільно.

Для реалізації однієї ітерації симплекс-методу після визначення змінної, що включається до базису, необхідно виконати перетворення вихідної симплексної таблиці методом Жордана-Гауса. На перетині стовпця змінної, що включається (ведучий стовпець), і рядка змінної, що виключається (ведучий рядок), знаходиться так званий розв’язувальний елемент. Відносно цього елементу виконуються перетворення елементів симплекс-таблиці методом Гауса.

Розрахунок елементів нової симплекс-таблиці слід виконувати за однією з двох наступних формул:

 

де a¢ij - елемент нової симплекс-таблиці; aij - елемент поточної симплекс-таблиці; k - номер ведучого рядка; s - номер ведучого стовпця; aks – розв’язувальний елемент.

Знайдемо тепер оптимальний розв’язок задачі «про фарби» за допомогою симплексного методу. Остаточний і всі проміжні розв’язки будемо оформляти у вигляді таблиць.

Отриманий після першої ітерації розв’язок (див. табл. 3.2 ) є кращим від початкового, оскільки йому відповідає більше значення цільової функції z=12. Ту ж саму величину одержимо, підставляючи до рівняння цільової функції значення змінних, взятих із стовпця “Розв’язок”: z=3´4+2´0+0´5+0´2+0´2+0´0=12.

Оскільки стовпець z не змінюється в результаті перетворень, надалі будемо його опускати.

Після другої ітерації симплекс-методу одержимо розв’язок, що є оптимальним. Про це свідчить відсутність від’ємних коефіцієнтів у z-рядку відповідної сиплекс-таблиці. Таким чином, максимально допустиме значення цільової функції z=122/3 досягається при x1=10/3=3 4/3 і x2=4/3=1 1/3.

Таблиця 3.4

Очевидно, що розв'язок, отриманий алгебраїчно, збігається з результатом застосування графічного методу.