Нос. 4.2: Симплекс алгоритъм

Нос. 4.: Симплекс алгоритъм професор д-р Петра Мутцел Катедра по алгоритъмно инженерство, LS Факултет по компютърни науки, TU Dortmund Литература за този VO V. Chvatal: Линейно програмиране 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 stop: v е оптимален. 3 Последователност на всеки подобряващ ръб e от v. Ако e е неограничен, т.е. stop няма друга крайна точка: LP е неограничен. 4 Нека u е другата крайна точка на e. Задайте vu. Отидете на x 7,0,0 z

симплекс метод

eweis: a b b A се получава от A, като се заменя r-тата колона с A qs. Прилага се A A F, където 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 и всички останали колони остават както в А. Той държи ā rs> 0, така че F е редовен и следователно A е асис. 4 5 Освен това, x A b F A b F x F b с 0 0 as. 0 0 ar, s F Така че за i. m: r-та колона Ако ā е> 0: xb pi i āis br bi āis bi 0 āи по-специално за ir: xb pr r br 0 нова неосновна променлива Ако ā е 0: xb pi i āis br bi 0 и x br 0 qs нова базова променлива So x е възможно базово решение за база. ar +, s. āms 0 0. 0 0 b3 недегенериран случай: λ 0> 0: 6 7 метод на таблица от симплекс алгоритъм стартира с допустима asis Итеративно приложение на изречението: а СТОП, оптималност b СТОП, неограничена промяна на базата: ос с въртяща се колона и въртяща се линия 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

Правила за изчисляване от изчислението на основния обменен курс на Ā 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 old F 3 3 5 0 0 0 0 0 t 3 и x4 out. 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 стар 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