У табл. 2 отримали опорний план, бо у колонці вільних елементів немає від’ємних елементів, але не оптимальний, тому що у цільовому рядку є від’ємні елементи.
Переходимо до знаходження оптимального плану.
Критерієм оптимальності задачі на максимум є невід’ємність коефіцієнтів цільового рядка таблиці.
Теорема (ознака необмеженості цільової функції зверху): якщо у симплексній таблиці при знаходженні оптимального плану знайдеться колонка з від’ємним елементом цільового рядка, а всі інші елементи цієї колонки будуть недодатні, то функція мети цієї задачі буде на множині планів задачі з боку максимуму необмеженою
(Z → ∞).
Теорема (ознака необмеженості цільової функції знизу): якщо у симплексній таблиці при знаходженні оптимального плану знайдеться колонка з додатнім елементом цільового рядка, а всі інші елементи цієї колонки будуть недодатні, то цільова функція задачі буде на множині планів задачі з боку мінімуму необмеженою
(Z → - ∞).
Алгоритм знаходження оптимального плану задачі на max:
Проглядаємо цільовий рядок таблиці. Якщо немає від’ємних елементів, то план оптимальний. Якщо є кілька від’ємних елементів, то вибирають найменший або більший за модулем. Вибраний від’ємний елемент визначить розв’язуючу колонку.
Складаємо невід’ємні співвідношення колонки вільних елементів до розв’язуючої колонки і знаменник меншого з них приймемо за розв’язуючий елемент.
Виконуємо повні виключення Жордана-Гауса.
Алгоритм повторюємо доти, поки не буде знайдено оптимальний план.
Таблиця 3.
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
1 |
х2 |
0 |
1 |
-2 |
-3/5 |
0 |
-2/5 |
=18/5 |
х5 |
0 |
0 |
-1 |
-1/5 |
1 |
-4/5 |
=6/5 |
х1 |
1 |
0 |
2 |
2/5 |
0 |
3/5 |
=18/5 |
Z |
0 |
0 |
7 |
9/5 |
0 |
11/5 |
=36/5 |
Знайдено оптимальний план для задачі на max.
Критерієм оптимальності задачі на мінімум є недодатність коефіцієнтів цільового рядка таблиці.
Алгоритм знаходження оптимального плану задачі на min:
Проглядаємо цільовий рядок таблиці. Якщо немає додатніх елементів, то план оптимальний. Якщо є кілька додатніх елементів, то вибирають найбільший додатній елемент. Вибраний додатній елемент визначає розв’язуючу колонку.
Складаємо невід’ємні співвідношення колонки вільних елементів до розв’язуючої колонки і знаменник меншого з них приймаємо за розв’язуючий елемент.
Виконуємо повні виключення Жордана-Гауса.
Алгоритм повторюємо доти, поки не буде знайдено оптимальний план. Слід сказати, що оптимальний план (на min чи на max) знаходять після знаходження опорного плану, що у даному випадку відповідає таблиці 2. Повернемося до вказаної таблиці і продовжимо обчислення.
Таблиця 2. (опорний план)
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
1 |
х4 |
2/3 |
1 |
-2/3 |
-1/3 1/3 2/3 |
0 |
0 |
=6 |
х5 |
4/3 |
0 |
5/3 |
1 |
0 |
=6 |
|
х2 |
5/3 |
0 |
10/3 |
0 |
1 |
=6 |
|
Z |
-11/3 |
0 |
-1/3 |
1 |
0 |
0 |
=-6 |
/3
Від табл. 2 почнемо знаходити оптимальний план задачі математичного програмування на мінімум (оскільки у цільовому рядку є додатній елемент, що визначає розв’язуючу колонку).
Отже, min (6/1/3; 6/2/3) = (18; 9)= 9 – розв’язуючий елемент (2/3).
Робимо крок повних жорданових вилучень і переходимо до табл. 4, де знайдено оптимальний план задачі на min.
Таблиця 4.
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
1 |
х2 |
3/2 |
1 |
1 |
0 |
0 |
1/2 |
=9 |
х5 |
1/2 |
0 |
0 |
0 |
1 |
-1/2 |
=3 |
х4 |
5/2 |
0 |
5 |
1 |
0 |
3/2 |
=9 |
Z |
-9/2 |
0 |
-2 |
0 |
0 |
-1/2 |
=-9 |
