Мис. 4.2: Симплексний алгоритм
Мис. 4.: Симплексний алгоритм професор доктор Петра Мутцель Кафедра інженерного алгоритму, факультет комп’ютерних наук Л.С., Дортмундська література Література для цього ВО В. Чватал: Лінійне програмування D. ertsimas: Лінійне програмування 4.-7. VO A&D WS 08/09 .- 6.008 Огляд 3. Симплексний алгоритм 4. Симплексний алгоритм Введення базового методу обмінного курсу Табличний стандартний симплекс Перероблений симплексний метод з факторизацією Правила вибору стовпців і рядків Термінація Аналіз часу виконання На практиці лінійні програми вирішуються за допомогою симплексного алгоритму [Dantzig 955]. Макс. 3x + x + x 3 За умови x + x 3 8 x + x 7 x + xx, x, x 3 0 3 4 Візуалізація симплексного алгоритму Симплексний алгоритм Max z 3x + x + x 3 x 3 0.0, 8 0,6,8,5,6 z 8 0,6,0 z 0,5,0 7,0, z 3 Оптимально! x Дано: LP з розв’язком багатогранника P est узгоджують довільний кут початкового кута v від P. Якщо немає покращення ребра, що падає до v зупинки: v є оптимальним. 3 Послідовність будь-якого вдосконалюючого краю e v. Якщо e необмежене, тобто не має іншої зупинки кінцевої точки: LP є необмеженим. 4 Нехай u - інша кінцева точка e. Встановити ву. Перейдіть до x 7,0,0 z
eweis: a b b A - результат A, замінивши r-й стовпець на A qs. Ми маємо AAF, де F 0 0 ā s. 0 0 ā r, s ā rs ā r +, s 0 0. ā ms 0 0 Оскільки: ми маємо Ā s A і тому A qs s-й стовпець AF рівний A Ā s AAA s A qs та всі інші стовпці залишаються такими, як у A. Маємо ā rs> 0, тому F регулярний, а отже, A є асідою. 4 5 Крім того, x A b F A b F x F b з 0 0 ас. 0 0 ar, s F Отже, для i. m: r-й стовпець Якщо ā> 0: xb pi i āis br bi āis bi 0 āis, зокрема, для ir: xb pr r br 0 нова неосновна змінна Якщо ā дорівнює 0: xb pi i āis br bi 0 і x br 0 qs нова базова змінна So x є можливим базовим рішенням базису. ār +, с. āms 0 0. 0 0 b3 нероджений випадок: λ 0> 0: 6 7 метод таблиці симплексного алгоритму починається з допустимої asis Ітераційне застосування речення: a STOP, оптимальність b STOP, необмежена зміна бази: pivot with pivot column s і опорна лінія r значення цільової функції значення основних змінних - c TA b A bc NT c TAANAAN t 00 t 0. t 0n зменшені витрати Варіанти: метод Таблиці Стандартний симплекс Перероблений метод t 0 t. t n. t m0 t m. t mn Таблиця допустима, якщо t i0 0 для всіх i. Таблиця є оптимальною, якщо t 0j 0 для всіх j. 3
Правила розрахунку з розрахунку базового курсу of A A N: A A N A F A N F A A N A N відрізняється від A N лише тим, що r-й стовпець належить до змінної з індексом p r. Правила розрахунку з основного курсу обміну Для перерахунку Ā, Ā по суті потрібно помножити на F; Виняток становлять r-й стовпець і s-й рядок. Те саме стосується обчислення b і c. Елемент ā rs називається опорним елементом. Це призводить до наступних правил розрахунку: 0 ff fff спостереження за симплексним алгоритмом У кожній ітерації одне базове рішення замінюється іншим. Лише дуже мала частина таблиці використовується для обчислення нового базового рішення x: вам потрібні A -, bx і c, а також s-й стовпець A. Ідея: Замість того, щоб кожен раз обчислювати всю матрицю, обчисліть лише ту частину, яка дійсно потрібен, і цей симплексний метод 4 переглянуто безпосередньо з вихідних даних
Переглянутий метод симплексу 6 7 Те саме, що і раніше з 4, 5, N, 3, c 3, 5, 4, 0, 0, 0 x4 3 0 A, x 0, A x 5 5 4 0. Ітерація: y TA c T: y TF rx - це зменшені витрати x відбувається cy T 0 0 0 0 y 0 0 c 5. Тато Це дає нам нове базове та основне рішення: x 3 x: x4 x 5, 5 N, 4, 3 3 x: Застосовується наступне: AA старий F 3 3 5 0 0 0 0 0 t 3 і x4 вихід. 9. Ітерація Скорочені витрати: y T 0 5 5, 0 y 0 x: 3 5, 0 0 x 4: 0 5, 0 5 0 0 x 3: 4 5, 0 3 4 x 3 in t 3 і x 5 out . A d a: x 3 3 x: 0 d d 4 3 x x 5 3 7 6 3 3 0, 3, N, 4, 5 7 6 x: 3 0 Застосовується наступне: A A old F 0 3 4 30 3 5
Порівняння часу виконання таблиці та переглянутого методу симплексу Час виконання за ітерацію для малонаселених матриць: Оцінка за Chvatal-uch: Припущення: стовпці та рядки таблиці містять m/або n/ненульові елементи; Матриці факторизації k: m ненульових елементів; Стовпці Eta: приблизно 5% -50% щільного FTRAN: приблизно 0m, TRAN: приблизно 0m Вибір вхідних змінних: Розрахунок вихідних змінних: m Оновлення x та: m Загальний час переглянутого симплексу: 3m + 0n Загальний час Табличний метод: mn/4 8