n + m - додаткові змінні. Всі додаткові змінні ми прийняли як базисні, а вихідні змінні як небазисних (додаткові записані в перший стовпець симплекс-таблиці а вихідні в перший рядок). При кожній ітерації елементи симплекс-таблиці перераховують за певними правилами.
Алгоритм симплекс-методу.
Підготовчий етап
Наводимо задачу ЛП до канонічного виду
=a 0,1 x 1 + a 0,2 x 2 +. a 0, n x n + b 0? max 1,1 x 1 + a 1,2 x 2 +. a 1, n x n + x n + 1=b 12,1 x 1 + a 2,2 x 2 +. a 2, n x n + x n + 2=b 2
.......... m, 1 x 1 + am, 2 x 2 +. a m, n x n + x n + m=b m
У разі якщо у вихідній задачі необхідно знайти мінімум - знаки коефіцієнтів цільової функції F змінюються на протилежні a 0, n=-a 0, n. Знаки коефіцієнтів обмежуючих умов зі знаком ? Raquo; так само змінюються на протилежні. У разі якщо умова містить знак ? Raquo;- Коефіцієнти запишуться без змін.
Крок 0. Складаємо сімплексну таблицю, що відповідає вихідній задачі
Крок 1. Перевірка на допустимість.
Перевіряємо на позитивність елементи стовпця b (вільні члени), якщо серед них немає негативних то знайдено допустиме рішення (рішення відповідне одній з вершин багатогранника умов) і ми переходимо до кроку 2. Якщо в стовпці вільних членів є негативні елементи то вибираємо серед них максимальний по модулю - він задає провідний рядок k. У цьому рядку так само знаходимо максимальний по модулю негативний елемент ak, l - він задає провідний стовпець - l і є провідним елементом. Змінна, відповідна провідною рядку виключається з базису, змінна відповідна ведучому стовпцю включається в базис. Перераховуємо симплекс-таблицю згідно з правилами.
Якщо ж серед вільних членів є негативні елементи - а у відповідному рядку - ні то умови задачі несумісні і рішень у неї немає.
Якщо після перерахунку в стовпці вільних членів залишилися негативні елементи, то переходимо до першого кроку, якщо таких немає, то до другого.
Крок 2. Перевірка на оптимальність.
На попередньому етапі знайдено допустиме рішення. Перевіримо його на оптимальність Якщо серед елементів симплексного таблиці, находщіхся в рядку F (не беручи до уваги елемент b 0 - поточне значення цільової функції) немає негативних, то знайдено оптимальне рішення.
Якщо в рядку F є негативні елементи то рішення вимагає поліпшення. Вибираємо серед негативних елементів рядка F максимальний по модулю (виключаючи значення функції b 0)
0, l=min {a 0, i}
- стовпець в якому він знаходиться буде ведучим. Для того, що б знайти провідну рядок, знаходимо відношення соответсвующего вільного члена та елементу з ведучого шпальти, за умови, що вони ненегативні.
k/ak, l=min {bi/ai, l} при ai, l gt; 0, bi gt; 0
- Рядок, для якої це відношення мінімально - ведуча. Елемент ak, l - ведучий (що дозволяє). Змінна, відповідна провідною рядку (xk) виключається з базису, змінна відповідна ведучому стовпцю (xl) включається в базис.
Перераховуємо симплекс-таблицю за формулами. Якщо в новій таблиці після перерахунку в рядку F залишилися негативні елементи переходимо до кроку 2
Якщо неможливо знайти провідну рядок, так як немає позитивних елементів у провідному стовпці, то функція в області допустимих рішень задачі не обмежена - алгоритм завершує роботу.
Якщо в рядку F і в стовпці вільних членів всі елементи позитивні, то знайдено оптимальне рішення.
Правила перетворень симплексної таблиці.
При складанні нової симплекс-таблиці в ній відбуваються такі зміни:
· Замість базисної змінної xk записуємо xl; замість небазисной змінної xl записуємо xk.
· провідний елемент замінюється на зворотну величину ak, l '= 1/ak, l
· всі елементи ведучого шпальти (крім ak, l) множаться на - 1/ak, l
· всі елементи провідного рядка (крім ak, l) множаться на 1/ak, l
· залишилися елементи симплекс-таблиці перетворюються за формулою ai, j '= ai, j - ai, lxak, j/ak, l
Схему перетворення елементів симплекс-таблиці (крім провідного рядка і ведучого шпальти) називають схемою прямокутника.
Перетворювані елемент ai, j і відповідні йому три сомножителя якраз і є вершинами прямокутника.
8. Зіставлення отриманих результатів з результатами аналогічних робіт
Автори аналоги?? них робіт виконав програмну части...
