б один позитивний елемент (Якщо всі коефіцієнти при змінних негативні, а вільні члени невід'ємні, то невід'ємне рішення єдино: це (0, ..., 0));
) нехай у дозволяючому стовпці кілька позитивних елементів. Знайдемо відносини відповідних вільних членів до цих елементів і за розв'язний елемент візьмемо той з них, для якого це відношення найменше (якщо в стовпці один позитивний елемент, то він і буде дозволяючим). Потім здійснимо перерахунок елементів таблиці. Таке перетворення носить назву симплексного.
Додамо, що якщо знайдено хоча б одне невід'ємне базисне рішення, то за допомогою симплексного перетворення можна перейти до іншого Ненегативна базисного рішенням (якщо таке є).
Правило прямокутника. Правило для перебування елемента перетвореної таблиці, що не належить дозволяючим стовпцю або рядку, називають правилом прямокутника.
Алгоритм перетворення:
) елементи роздільної рядка виходять з відповідних елементів колишньої рядки поділом на дозволяє елемент;
) всі елементи дозволяє стовпця перетвореної таблиці, крім дозволяє елемента, дорівнюють нулю;
всі інші елементи перераховуються за правилом прямокутника: виділяємо прямокутник в таблиці 7.2 так, що елемент підлягає перерахунку (5), і дозволяє елемент (2) утворюють одну з діагоналей. А потім з твору цих елементів віднімаємо твір елементів, що утворюють іншу діагональ, і отриману різницю ділимо на дозволяючий елемент.
Приклад. За допомогою Симплекс-таблиці знайти мінімальне значення
цільової функції (7.15):
F (x1, x2)=-f (x1, x2)=- 10 · x1- 12 · x2- 0 · x3 - 0 · x4 - 0 · x5 ® min
при даних обмеженнях (7.14)
· x1 + 5 · x2 + x3=300
· x1 + x2 + x4=100
· x1 + 3 · x2 + x5=160
x1,2,3,4,5? 0
Рішення. Коефіцієнти при змінних переписуємо в сімплексні таблиці (Табл. 7.2). У цьому завданню вихідним базисним рішенням є: (0; 0; 300; 100; 160). Цільову функцію запишемо в наступному вигляді:
+ 10 · x1 + 12 · x2 + 0 · x3 + 0 · x4 + 0 · x5 ® min.
Таблиця 7.2
Базисні х 1 х 2 х 3 х 4 х 5 Вільні
змінні члени
х 3 4 5 1 0 0300
х 4 1 лютого 0 1 0100
х 5 2 3 0 0 1160
F 10 12 0 0 0 0
Дозволяє елемент таблиці є а12=2. Для знаходження дозволяє елемента в стовпці з позитивним значенням коефіцієнта цільової функцій с1=10 вибираються позитивні елементи a11=4, a12=2, а13=2; складаються відносини b1/a11=300/4, b2/a12=100/2 і b3/a13=160/2; з отриманих відносин вибирається найменше.
Змінна х1 повинна замінити у вихідному базисі змінну х4. Після відповідних перетворень таблиця буде мати такий вигляд:
Таблиця 7.3
Базисні х 1 х 2 х 3 х 4 х 5 Вільні
змінні члени
х 3 0 3 1 0 0 +100
х 1 1 0,5 0 0,5 0 50
х 5 0 2 0 - 1 1- 60
F 0 7 0 - 5 0 - 500
У рядку коефіцієнтів цільової функцій F таблиці 7.3 елемент c2=7 позитивний. Дозволяє елемент таблиці є А23=2. Для знаходження дозволяє елемента в стовпці вибираються позитивні елементи a21=3, a22=0,5, А23=2; складаються відносини b1/a21=100/3, b2/a22=50/0,5 і b3/a23=60/2; з отриманих відносин вибирається найменше. Мінлива х2 повинна замінити у вихідному базисі змінну ...
