= min {bi/ai, l} при ai, l> 0, bi> 0
- дані для, для якої це відношення мінімально - ведуча. Елемент ak, l - ведучий (дозволяючий). Мінлива, відповідна провідною рядку (xk) виключається з базису, мінлива відповідна ведучому колонки (xl) включається в базис. p> Перераховуємо симплекс-таблицю за формулами <# "justify"> 1. Якщо в новій таблиці після перерахунку в рядку F залишилися негативні елементи переходимо до кроку 2
2. Якщо неможливо знайти провідну рядок, так як немає позитивних елементів у провідному стовпці, то функція в області допустимих рішень задачі не обмежена - алгоритм завершує роботу.
. Якщо в рядку F і в стовпці вільних членів всі елементи позитивні, то знайдено оптимальне рішення.
Правила перетворень симплексной таблиці.
При складанні нової симплекс-таблиці в ній відбуваються такі зміни:
1) Замість базисної змінної xk записуємо xl; замість небазисной змінної xlзапісиваем xk.
2) провідний елемент замінюється на зворотну величину ak, l '= 1/ak, l
3) всі елементи ведучого шпальти (крім ak, l) множаться на -1/ak, l
4) всі елементи провідного рядка (крім ak, l) множаться на 1/ak, l
5) залишилися елементи симплекс-таблиці перетворяться по формулі ai, j '= ai, j-ai, lx ak, j/ak, l
Схему перетворення елементів симплекс-таблиці (крім провідною рядки і ведучого шпальти) називають схемою прямокутника .
В
Перетворювані елемент ai, j і відповідні йому три множники якраз і є вершинами прямокутника .
1. Рішення задачі ЛП
1.1 Гeометріческая інтерпретація двовимірної задачі ЛП і її рішення
Розглянемо двовимірну задачу:
(1)
Необхідно знайти максимальне значення цільової функції F = x1 + x2? max, при системі обмежень (1). Побудуємо область допустимих рішень, тобто вирішимо графічно систему нерівностей. Для цього побудуємо кожну пряму і визначимо півплощини, задані нерівностями (півплощини позначені штрихом) (Малюнок 1). br/>В
Малюнок 1-Межі області допустимих рішень.
Перетином півплощин буде область, координати точок якого задовольняють умові неравенствам системи обмежень задачі.
Позначимо границі області багатокутника рішень (Малюнок 2).
В
