Варианти и подобрения на симплекс метода - Mathepedia

Избор на шарнирния елемент

пивотната колона има положително намалени разходи и
линията на въртене води отново до допустимо основно решение.

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

Изберете първата подходяща колона. Това е най-простият вариант, но често води до голям брой повторения и следователно не се използва на практика.
Методът, първоначално предложен от Dantzig, избира една от колоните с най-голяма намалена стойност на разходите. Този вариант може да отнеме много изчислително време с много променливи.
The най-стръмни цени е комбинация от избор на колона и ред, които заедно носят най-голям напредък за целевата функция. Този вариант е много сложен във всяка итерация, но често води до малко итерации.
The ценообразуване на devex е приближение на, предложено от Пола Харис през 1974 г. най-стръмни цени и една от стандартните процедури в днешните LP решатели. Колоните на матрицата и намалените разходи се мащабират до единен стандарт преди избора, за да се увеличи информативната стойност на намалените разходи.
В частично ценообразуване разделя набора от променливи на блокове и прилага един от предишните методи към блок. Следващият блок се разглежда само ако там не е намерена подходяща променлива.
The множество цени търси веднъж набор от подходящи променливи, които след това за предпочитане се разглеждат като кандидати в следващите итерации. Само когато никой от тези кандидати няма положително намалени разходи, се вземат предвид другите променливи.
The частично многократно ценообразуване е комбинация от последните два варианта, която винаги определя нови кандидати от част от всички налични променливи. Тази стратегия е следващата ценообразуване на devex днес към стандартните стратегии.
В хибридно ценообразуване няколко стратегии се използват последователно в зависимост от ситуацията. Някои LP решаватели също използват числови критерии при избора на колони, за да ограничат проблемите, причинени от грешките в закръгляването.

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

Изберете първия подходящ ред. Въпреки че този вариант е много бърз за итерация, той често води до много итерации и е числено нестабилен.
The правило за лексикографски подбор избира (недвусмислено) лексикографски най-малката линия от всички възможни редове. Това правило не е особено добро от гледна точка на скоростта, но предотвратява посещаването на таблици няколко пъти и алгоритъмът да се придвижва. Поради тази причина той може да се използва, например, за няколко итерации, за да се измъкне от основното решение, преди да се върне към други методи за избор.
Предложената от Пола Харис през 1973г Тест на коефициента на Харис, което е една от стандартните процедури днес, позволява новото решение да бъде леко недопустимо поради съображения за числена стабилност.

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

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

В хода на методите на рязане на равнината или методите за разклоняване и отрязване много често се променя променлива граница в току-що решен LP или се добавя неравенство, което не е удовлетворено от старото решение, и LP след това се решава отново. Тъй като старото основно решение вече не е допустимо, е нарушено едно от основните условия на първичната симплекс таблица, така че методът на първичния симплекс трябва да бъде стартиран от самото начало, за да се реши новата LP. Ако нищо не е променено в целевата функция, старото двойно решение все още е допустимо, така че с няколко двойни симплексни стъпки от старата начална основа, обикновено се намира оптимално решение за модифицирания LP след няколко повторения. При големите LP-та тази разлика често се отразява много ясно в общото време на работа.
Ако в хода на алгоритъма възникнат числени затруднения или няма прогрес в целевата функция в продължение на много дълго време, може да бъде полезно временно да се позволи леко нарушаване на променливите граници, за да се премести от критичния ъгъл на многоъгълника. След това това може да бъде отстранено с няколко двойни симплексни стъпки.
Ако линейната програма има определени структури, можете директно да зададете първоначално недопустима, но двойно допустима начална основа, без да се налага да я изчислявате. В такъв случай можете да започнете фаза 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.
Ако няколко променливи са били фиксирани към определен диапазон от стойности, възможно е някои неравенства винаги да са изпълнени или вече да не могат да бъдат изпълнени. В първия случай неравенството може да бъде премахнато, във втория случай незабавно се показва недопустимостта на LP и може да се спре.

време на работа

история

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