Варијанти и подобрувања на методот на симплекс - Матепедија

Избор на стожерен елемент

стожерната колона има позитивно намалени трошоци и
стожерната линија повторно доведува до дозволено основно решение.

Избор на колона

Изберете ја првата соодветна колона. Ова е наједноставната варијанта, но честопати доведува до голем број повторувања и затоа не се користи во пракса.
Методот првично предложен од Данциг избира една од колоните со најголема намалена вредност на трошоците. Оваа варијанта може да потрае многу компјутерско време со многу варијабли.
На најстрмни цени е комбинација на избор на колони и редови, кои заедно носат најголем напредок за целната функција. Оваа варијанта е многу сложена во секоја повторување, но честопати доведува до неколку повторувања.
На девекс цени е апроксимација на. предложена од Пола Харис во 1974 година најстрмни цени и една од стандардните процедури во денешните решенија за ЛП. Колоните на матрицата и намалените трошоци се зголемуваат на единствен стандард пред изборот, со цел да се зголеми информативната вредност на намалените трошоци.
Кај делумно утврдување на цените го дели множеството варијабли во блокови и применува еден од претходните методи на блок. Следниот блок се разгледува само ако таму не се најде соодветна променлива.
На повеќекратни цени еднаш бара збир на соодветни променливи, кои потоа се претпочитаат да се сметаат за кандидати во следните повторувања. Разгледуваат другите варијабли само кога никој од овие кандидати нема позитивно намалени трошоци.
На делумно повеќекратно утврдување на цените е комбинација од последните две варијанти, што само некогаш одредува нови кандидати од дел од сите достапни варијабли. Оваа стратегија припаѓа следно девекс цени денес до стандардните стратегии.
Кај хибридни цени неколку стратегии се користат наизменично во зависност од ситуацијата. Некои LP-решавачи користат и нумерички критериуми при избор на колони со цел да ги ограничат проблемите предизвикани од грешките во заокружувањето.

Избор на линија

Изберете ја првата соодветна линија. Иако оваа варијанта е многу брза по повторување, таа честопати доведува до многу повторувања и е бројно нестабилна.
На правило за лексикографска селекција ја избира (недвосмислената) лексикографски најмала линија од сите можни редови. Ова правило не е особено добро од гледна точка на брзината, но спречува повеќе пати да се посетуваат висорамнини и да се вози велосипед со алгоритмот. Поради оваа причина, може да се користи, на пример, за неколку повторувања за да се тргне од основното решение пред да се вратите на други методи на избор.
Оној што го предложи Паула Харис во 1973 година Тест за количник Харис, што е една од стандардните процедури денес, овозможува новото решение да биде малку недопуштено од причини на нумеричка стабилност.

Променливи граници

Метод на двоен симплекс

Во текот на методите на сечење рамнина или методите на разгранување и сечење, променливата граница многу често се менува во ЛП што е само решен или се додава нееднаквост што не е задоволена од старото решение, а ЛП повторно се решава. Бидејќи старото основно решение веќе не е дозволено, еден од основните услови на табелата на примален симплекс е прекршен, така што методот на примарен симплекс треба да се започне од самиот почеток за да се реши новиот ЛП. Ако ништо не е променето во целната функција, старото двојно решение е сè уште дозволено, така што со неколку двојни симплекс чекори од старата почетна основа, обично се наоѓа оптимално решение за изменетиот ЛП по неколку повторувања. Со големи ЛП, оваа разлика честопати многу јасно се рефлектира во вкупното време на траење.
Ако се појават нумерички потешкотии во текот на алгоритмот или нема напредок во целната функција за многу долго време, може да биде корисно привремено да се дозволи мало нарушување на променливите граници со цел да се исели од критичниот агол на политопот. Ова потоа може да се поправи со неколку двојни чекори на симплекс.
Ако линеарната програма има одредени структури, можете директно да наведете примарно недозволена, но двојна допуштена почетна основа без да мора да ја пресметате. Во таков случај, можете да ја започнете фазата II со двојни симплекс чекори директно од оваа база и може да се зачувате во фаза I.

Ревидиран метод на симплекс

LR распаѓања

Пред-обработка

Ако една линија е линеарно зависна од други линии, таа е излишна и може да се отстрани. Меѓутоа, освен посебниот случај дека линијата е скаларен множител од друга линија, ова е генерално тешко да се препознае со разумен напор.
Многу често, променливите се ограничени на одреден опсег на вредности поради услови или наведени од други променливи. На пример, равенката x 1 + x 2 = 1 x_ + x_ = 1 x 1 + x 2 = 1 и ненегативните услови ги ограничуваат обете променливи на опсегот [0, 1] [0,1] [0, 1] . Познавањето на оваа граница може да го забрза процесот на решавање. Покрај тоа, вредноста на x 2 x_ x 2 се определува со вредноста на x 1 x_ x 1. Ова значи дека во сите услови во кои се јавува x 2 x_ x 2, оваа променлива може да се замени со 1 - x 1 1 - x_ 1 - x 1 и x 2 x_ x 2 може да се отстрани од LP.
Ако неколку променливи се фиксирани на одреден опсег на вредности, можно е некои нееднаквости секогаш да се исполнети или повеќе да не можат да бидат исполнети. Во првиот случај нееднаквоста може да се отстрани, во вториот случај веднаш е прикажана недопуштеноста на ЛП и може да се запре.

време на трчање

приказна

Добриот Бог ги создаде целите броеви, сè друго е дело на човекот.