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

Кејп. 4.: Симплекс алгоритам Професор Др. Петра Муцел Стол за алгоритамско инженерство, ЛС Факултет за компјутерски науки, ТУ Дортмунд Литература за ова VO V. Чватал: Линеарно програмирање Д.ертсимас: Линеарно програмирање 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 Визуелизација на алгоритмот на симплекс Алгоритам на симплекс Макс 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 Дадено: ЛП со раствор полиедрон P се согласува со произволен агол првичен агол v на P. Ако нема подобар инцидент на работ до v стоп: v е оптимално. 3 Низа на кој било подобар раб на v. Ако e е неограничен, т.е. нема друга крајна точка на запирање: LP е неограничен. 4 Нека ти биде другата крајна точка на д. Постави ву. Одете на x 7,0,0 z

симплекс

евеи: 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 AA s AAA s A qs и сите други колони остануваат како во A. Имаме ā rs> 0, така што F е редовно и затоа А е асис. 4 5 Понатаму, x A b F A b F x F b со 0 0 ās. 0 0,r, 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 ās br br 0 и x br 0 qs нова базна променлива Значи x е изводливо базно решение за база. +r +, s. 0 не 0 0 и стожерна линија 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 Набationsудувања на алгоритмот на симплекс Во секоја повторување, едно основно решение се заменува со друго. Само многу мал дел од табелата се користи за пресметување на новото основно решение 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 се случуваат за T 0 0 0 0 y 0 0 c 5. Татко Ова ни го дава новото основно и основно решение: x 3 x: x4 x 5, 5 N, 4, 3 3 x: Се применува следново: АА стара 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 во т 3 и x 5 надвор . 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

Траење на компарацијата на табелата и ревидираниот метод на симплекс Траење по итерација за ретко населените матрици: Проценка според Чватал-уч: Претпоставка: колоните и линиите на табелата содржат елементи m/или n/не-нула; Факторизација на матрици на k: m не-нула елементи; Ета колони: приближно 5% -50% густа FTRAN: приближно 0m, TRAN: приближно 0m Избор на влезни варијабли: Пресметка на излезните променливи: m Ажурирање на x и: m Вкупно време на ревидиран симплекс: 3m + 0n Вкупно време Метод на табела: mn/4 8