Variante și îmbunătățiri ale metodei simplex - Mathepedia

Selectarea elementului pivot

coloana pivot are costuri pozitive reduse și
linia pivot duce din nou la o soluție de bază admisibilă.

Selectarea coloanei

Alegeți prima coloană corespunzătoare. Aceasta este cea mai simplă variantă, dar de multe ori duce la un număr mare de iterații și, prin urmare, nu este utilizată în practică.
Metoda propusă inițial de Dantzig alege una dintre coloanele cu cea mai mare valoare a costurilor reduse. Această variantă poate dura mult timp cu multe variabile.
cele mai abrupte prețuri este o combinație de selecție de coloane și rânduri, care împreună aduc cel mai mare progres pentru funcția obiectivă. Această variantă este foarte complexă în fiecare iterație, dar duce adesea la câteva iterații.
prețuri devex este o aproximare de. propusă de Paula Harris în 1974 cele mai abrupte prețuri și una dintre procedurile standard în rezolvatorii LP de astăzi. Coloanele matricei și costurile reduse sunt reduse la un standard uniform înainte de selecție pentru a crește valoarea informativă a costurilor reduse.
La prețuri parțiale împarte setul de variabile în blocuri și aplică una dintre metodele anterioare unui bloc. Următorul bloc este luat în considerare numai dacă nu se găsește o variabilă adecvată acolo.
prețuri multiple caută o dată un set de variabile adecvate, care sunt apoi preferabil considerate ca candidați în următoarele iterații. Celelalte variabile sunt luate în considerare numai atunci când niciunul dintre acești candidați nu are costuri reduse pozitive.
prețuri multiple parțiale este o combinație a ultimelor două variante, care determină doar candidați noi dintr-o parte din toate variabilele disponibile. Această strategie aparține în continuare prețuri devex astăzi la strategiile standard.
La prețuri hibride mai multe strategii sunt utilizate alternativ în funcție de situație. Unii rezolvatori LP folosesc, de asemenea, criterii numerice la selectarea coloanelor pentru a limita problemele cauzate de erorile de rotunjire.

Selectarea liniei

Alegeți prima linie corespunzătoare. Deși această variantă este foarte rapidă pe iterație, de multe ori duce la multe iterații și este instabilă numeric.
regula de selectie lexicografica selectează (fără ambiguitate) cea mai mică linie din punct de vedere lexicografic dintre toate liniile posibile. Această regulă nu este deosebit de bună din punct de vedere al vitezei, dar împiedică vizitarea de mai multe ori a tablourilor și algoritmul de a merge pe bicicleta. Din acest motiv, poate fi folosit, de exemplu, pentru câteva iterații pentru a scăpa de o soluție de bază înainte de a reveni la alte metode de selecție.
Cel propus de Paula Harris în 1973 Testul coeficientului Harris, care este una dintre procedurile standard de astăzi, permite ca noua soluție să fie ușor inadmisibilă din motive de stabilitate numerică.

Limite variabile

Metoda dual simplex

În cursul metodelor planului de tăiere sau al metodelor de ramificare și tăiere, o limită variabilă este foarte des modificată într-un LP care tocmai a fost rezolvat sau se adaugă o inegalitate care nu este satisfăcută de vechea soluție, iar LP-ul este apoi rezolvat din nou. Întrucât vechea soluție de bază nu mai este permisă, una dintre condițiile de bază ale tabelului simplex primar a fost încălcată, astfel încât metoda simplex primară trebuie repornită pentru a rezolva noul LP. Dacă nu s-a schimbat nimic în funcția țintă, vechea soluție duală este încă permisă, astfel încât, cu câțiva pași duali simplex față de vechea bază de pornire, o soluție optimă pentru LP modificat este de obicei găsită după câteva iterații. În cazul LP-urilor mari, această diferență se reflectă adesea foarte clar în timpul total de funcționare.
Dacă apar dificultăți numerice în cursul algoritmului sau nu există progrese în funcția obiectivă pentru o perioadă foarte lungă de timp, poate fi util să permită temporar o ușoară încălcare a limitelor variabile pentru a ieși dintr-un colț critic al politopului. Acest lucru poate fi apoi remediat cu câțiva pași dual simplex.
Dacă programul liniar are anumite structuri, puteți specifica direct o bază de pornire primară nepermisă, dar admisibilă dublă, fără a fi nevoie să o calculați. Într-un astfel de caz, puteți începe faza II cu pași dual simplex direct din această bază și vă puteți salva faza I.

Metoda simplex revizuită

Descompuneri LR

Preprocesare

Dacă o linie este liniar dependentă de alte linii, aceasta este de prisos și poate fi eliminată. Cu toate acestea, în afară de cazul special că o linie este un multiplu scalar al unei alte linii, acest lucru este în general dificil de detectat cu un efort rezonabil.
Foarte des, variabilele sunt limitate la un anumit interval de valori din cauza condițiilor sau specificate de alte variabile. De exemplu, ecuația x 1 + x 2 = 1 x_ + x_ = 1 x 1 + x 2 = 1 și condițiile de non-negativitate restricționează ambele variabile la intervalul [0, 1] [0,1] [0, 1] . Cunoașterea acestei limite poate accelera procesul soluției. În plus, valoarea x 2 x_ x 2 este determinată de valoarea x 1 x_ x 1. Aceasta înseamnă că, în toate condițiile în care apare x 2 x_ x 2, această variabilă poate fi înlocuită cu 1 - x 1 1 - x_ 1 - x 1 și x 2 x_ x 2 poate fi eliminată din LP.
Dacă mai multe variabile au fost fixate la un anumit interval de valori, este posibil ca unele inegalități să fie întotdeauna îndeplinite sau să nu mai poată fi îndeplinite. În primul caz, inegalitatea poate fi înlăturată, în al doilea caz se arată imediat inadmisibilitatea LP și se poate opri.

timpul pentru alergat

poveste

Bunul Dumnezeu a creat numerele întregi, orice altceva este lucrare umană.