Metoda simplex

A nu se confunda cu „metoda simplex” - o metodă de optimizare a unei funcții arbitrare. Vezi Metoda Nelder-Mead

Metoda simplex este un algoritm pentru rezolvarea unei probleme de optimizare a programării liniare prin enumerarea vârfurilor unui poliedru convex într-un spațiu multidimensional.

Esența metodei: construcția soluțiilor de bază, pe care funcționalul liniar scade monoton, până la situația în care sunt îndeplinite condițiile necesare de optimitate locală.

În lucrarea lui L. V. Kantorovich „Metode matematice de organizare și planificare a producției” (1939), au fost expuse pentru prima dată principiile unei noi ramuri a matematicii, care mai târziu a devenit cunoscută sub numele de programare liniară. [unu]

Din punct de vedere istoric, problema generală a programării liniare a fost pusă pentru prima dată în 1947 de George Bernard Dantzig , Marshall Wood și colaboratorii lor din Departamentul Forțelor Aeriene din SUA. În acel moment, acest grup investiga posibilitatea utilizării metodelor matematice și conexe pentru probleme militare și de planificare. Ulterior, un grup de cercetare numit Project SCOOP a fost organizat în Forțele Aeriene pentru a dezvolta aceste idei. Prima soluție de succes a unei probleme de programare liniară pe un calculator SEAC a fost realizată în ianuarie 1952 [2] .

Descriere

Problema programării liniare este că este necesar să se maximizeze sau să se minimizeze unele funcționale liniare pe un spațiu multidimensional sub anumite constrângeri liniare.

Rețineți că fiecare dintre inegalitățile liniare ale variabilelor delimitează o jumătate de spațiu în spațiul liniar corespunzător. Ca urmare, toate inegalitățile restricționează un poliedru convex (posibil infinit), numit și complex poliedric . Ecuația W ( x ) = c , unde W ( x ) este o funcțională liniară maximizată (sau minimizată), generează un hiperplan L(c) . Dependența de c generează o familie de hiperplane paralele. Atunci problema extremală capătă următoarea formulare: se cere să se găsească cel mai mare c astfel încât hiperplanul L(c) să intersecteze poliedrul cel puțin într-un punct. Rețineți că intersecția unui hiperplan optim și a unui poliedru va conține cel puțin un vârf și va fi mai mult de unul dacă intersecția conține o muchie sau o față k -dimensională. Prin urmare, maximul funcționalului poate fi căutat la vârfurile poliedrului. Principiul metodei simplex este că se alege unul dintre vârfurile poliedrului, după care începe mișcarea de-a lungul marginilor sale de la vârf la vârf în direcția creșterii valorii funcționalei. Când trecerea de-a lungul muchiei de la vârful curent la un alt vârf cu o valoare mai mare a funcționalului este imposibilă, se consideră că s- a găsit valoarea optimă a lui c .

Secvența de calcule prin metoda simplex poate fi împărțită în două faze principale :

găsirea vârfului inițial al mulțimii de soluții fezabile,
tranziție secvențială de la un vârf la altul, conducând la optimizarea valorii funcției obiectiv.

Mai mult decât atât, în unele cazuri, soluția inițială este evidentă sau definiția ei nu necesită calcule complexe, de exemplu, atunci când toate constrângerile sunt reprezentate de inegalități de forma „mai mică sau egală cu” (atunci vectorul zero este cu siguranță o soluție fezabilă , deși, cel mai probabil, este departe de a fi cel mai optim) . În astfel de probleme, prima fază a metodei simplex poate fi omisă cu totul. Metoda simplex, respectiv, este împărțită în monofazată și , respectiv, în două faze .

Algoritmul metodei simplex

Declarație de problemă consolidată

Luați în considerare următoarea problemă de programare liniară :

c^{T}x\to \max ,Ax\leqslant b,x\geqslant 0,b\geqslant 0.

Să punem acum această problemă într-o formă îmbunătățită echivalentă . Este necesar să se maximizeze Z , unde:

{\begin{bmatrix}1&-c^{T}&0\\0&A&E\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{ bmatrix}0\\b\end{bmatrix}},x,x_{s}\geqslant 0

Aici x sunt variabile din funcțional liniar original, x s sunt variabile noi care le completează pe cele vechi în așa fel încât inegalitatea să se transforme în egalitate, c sunt coeficienții funcționalei liniare originale, Z este variabila de maximizat. Semi- spațiile și la intersecție formează un poliedru reprezentând mulțimea soluțiilor fezabile. Diferența dintre numărul de variabile și ecuații ne oferă numărul de grade de libertate. Mai simplu spus, dacă luăm în considerare vârful unui poliedru, atunci acesta este numărul de muchii de-a lungul căruia ne putem deplasa în continuare. Apoi putem atribui o valoare de 0 acestui număr de variabile și le putem numi „non-bazice” . În acest caz, variabilele rămase vor fi calculate în mod unic și vor fi numite „de bază” . Același set de aceste variabile se numește bază . Punctul rezultat va fi vârful de la intersecția hiperplanurilor corespunzătoare variabilelor nebazice. Pentru a găsi așa-numitul. soluția inițială admisibilă (vârful de la care ne vom deplasa), vom atribui valoarea 0 tuturor variabilelor inițiale x și le vom considera nebaze, iar toate cele noi vor fi considerate de bază. În acest caz, soluția admisibilă inițială se calculează unic: . $x\geqslant 0$ $x_{s}\geqslant 0$ ${\mathbf {x}}_{{si}}={\mathbf {b}}_{i}$

Algoritm

Acum prezentăm pașii algoritmului. La fiecare pas, vom schimba seturile de vectori de bază și nebazici (deplasați-vă de-a lungul marginilor), iar matricea va arăta astfel:

{\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmatrix}}{\begin{bmatrix}Z\\x\\x_{s}\end{bmatrix}}={\begin{bmatrix}c_{B} ^{T}B^{{-1}}b\\B^{{-1}}b\end{bmatrix}},

unde sunt coeficienții vectorului corespunzător variabilelor de bază (variabilele corespund cu 0), sunt coloanele corespunzătoare variabilelor de bază. Matricea formată din coloanele rămase se notează cu . De ce va avea această formă matricea va fi explicat în descrierea pașilor algoritmului. $c_{B}$ $c$ $x_{s}$ $B$ $[{\mathbf {A}}{\mathbf {E}}]$ $D$

Primul pas .

Alegem valoarea inițială validă, așa cum este indicat mai sus. La prima etapă , matricea de identitate, deoarece variabilele de bază sunt . este un vector nul din aceleași motive. $B$ $x_{s}$ $c_{B}$

Al doilea pas

Să arătăm că în expresie numai variabilele nebazice au un coeficient diferit de zero. Rețineți că din expresie variabilele de bază sunt exprimate unic în termeni de cele nebazice, deoarece numărul de variabile de bază este egal cu numărul de ecuații. Fie variabile de bază și nebaze la o iterație dată. Ecuația poate fi rescrisă ca . Să o înmulțim cu în stânga: . Astfel, am exprimat variabilele de bază în termeni de variabile nebazice, iar în expresia echivalentă cu partea stângă a egalității, toate variabilele de bază au coeficienți unitari. Prin urmare, dacă adăugăm egalitate la egalitate , atunci în egalitatea rezultată toate variabilele de bază vor avea un coeficient zero - toate variabilele de bază de forma x vor fi reduse, iar variabilele de bază de forma x s nu vor fi incluse în expresia . $(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ $Ax+x_{s}=b$ $X'$ $X''$ $Ax+x_{s}=b$ $Bx'+Dx''=b$ $B^{{-1}}$ $x'+B^{{-1}}Dx''=B^{{-1}}b$ $B^{{-1}}Ax+B^{{-1}}x_{s}$ $Zc^{T}x=0$ $c_{B}^{T}B^{{-1}}Ax+c_{B}^{T}B^{{-1}}x_{s}$ $c_{B}^{T}B^{{-1}}x_{s}$

Să alegem o margine de-a lungul căreia ne vom deplasa. Deoarece dorim să maximizăm Z , este necesar să alegem o variabilă care va scădea cel mai mult expresia

$(c_{B}^{T}B^{{-1}}Ac^{T})x+(c_{B}^{T}B^{{-1}})x_{s}$ .

Pentru a face acest lucru, alegem o variabilă care are cel mai mare coeficient negativ în modul [3] . Dacă nu există astfel de variabile, adică toți coeficienții acestei expresii sunt nenegativi, atunci am ajuns la vârful dorit și am găsit soluția optimă. În caz contrar, vom începe să creștem această variabilă nebază, adică să ne deplasăm de-a lungul marginii corespunzătoare acesteia. Să numim această variabilă intrare .

Al treilea pas

Acum trebuie să înțelegem care variabilă de bază va ajunge mai întâi la zero pe măsură ce variabila de intrare crește. Pentru a face acest lucru, este suficient să luați în considerare sistemul:

{\begin{bmatrix}B^{-1}A&B^{-1}\end{bmatrix}}{\begin{bmatrix}x\\x_{s}\end{bmatrix}}=B^{ -1}b

Pentru valorile fixe ale variabilelor care nu sunt de bază, sistemul este solubil în mod unic în raport cu variabilele de bază, astfel încât să putem determina care dintre variabilele de bază va fi prima care va ajunge la zero atunci când intrarea crește. Să numim această ieșire variabilă . Aceasta va însemna că am atins un nou vârf. Acum haideți să schimbăm variabilele de intrare și de ieșire - cea de intrare va „intra” în cea de bază, iar variabila de ieșire le va „părăsi” pe cele care nu sunt de bază. Acum rescriem matricea B și vectorul c B în conformitate cu noile seturi de variabile de bază și nebazice, după care revenim la pasul al doilea. X''

Deoarece numărul de vârfuri este finit, algoritmul se va termina într-o zi. Vârful găsit va fi soluția optimă.

Metoda simplex în două faze

Motive pentru utilizare

Dacă în condiția unei probleme de programare liniară nu toate constrângerile sunt reprezentate prin inegalități de tip „≤”, atunci vectorul zero nu va fi întotdeauna o soluție validă. Cu toate acestea, fiecare iterație a metodei simplex este o tranziție de la un vârf la altul, iar dacă nu se cunoaște niciun vârf, algoritmul nu poate fi pornit deloc.

Procesul de găsire a vârfului inițial nu este mult diferit de metoda simplex monofazată, dar poate ajunge să fie mai dificil decât optimizarea ulterioară.

Modificări de restricții

Toate constrângerile sarcinilor sunt modificate conform următoarelor reguli:

restricțiile de tip „≤” se traduc în egalități prin crearea unei variabile suplimentare cu coeficientul „+1”. Această modificare este efectuată și în metoda simplex monofazată, variabilele suplimentare sunt utilizate în continuare ca bază inițială.
constrângerile de tip „≥” sunt completate de o variabilă cu coeficientul „ −1 ”. Deoarece o astfel de variabilă nu poate fi utilizată în baza originală din cauza unui coeficient negativ, este necesar să se creeze încă o variabilă auxiliară . Variabilele auxiliare sunt întotdeauna create cu un factor de „+1”.
restricțiile de tip „=" sunt completate cu o variabilă auxiliară.

În consecință, vor fi create o serie de variabile suplimentare și auxiliare. În baza inițială, variabilele suplimentare sunt selectate cu un coeficient de „+1” și toate cele auxiliare. Atenție: soluția căreia îi corespunde această bază nu este admisibilă.

Diferențele dintre variabilele suplimentare și auxiliare

În ciuda faptului că atât variabilele suplimentare, cât și cele auxiliare sunt create artificial și utilizate pentru a crea baza inițială, valorile lor în soluție sunt foarte diferite:

variabilele suplimentare raportează cât de „subutilizate” este constrângerea lor corespunzătoare. Valoarea variabilei suplimentare, egală cu zero, corespunde egalității valorilor părților din dreapta și din stânga constrângerii.
variabilele auxiliare spun cât de departe este condiția dată de acceptabilă (față de o anumită constrângere). Dacă valoarea variabilei auxiliare este mai mare decât zero, atunci această soluție nu îndeplinește o anumită constrângere și, prin urmare, nu este validă.

Adică, o valoare diferită de zero a variabilei suplimentare poate (dar nu ar trebui) să semnaleze că soluția nu este optimă . O valoare diferită de zero a variabilei auxiliare indică faptul că soluția este invalidă .

Fazele deciziei

După ce condiția a fost modificată, este creată o funcție obiectiv auxiliară . Dacă variabilele auxiliare au fost desemnate ca , , atunci definim funcția auxiliară ca $y_{i}$ $i\in \left\{1,\dots ,k\right\)$

z'=\sum _{{i=1}}^{k}y_{i}\la min

După aceea, metoda simplex obișnuită este efectuată în raport cu funcția obiectiv auxiliară. Deoarece toate variabilele auxiliare cresc valoarea lui , în timpul algoritmului ele vor fi deduse una câte una din bază, iar după fiecare tranziție, noua soluție va fi mai aproape de mulțimea soluțiilor fezabile. $z'$

Când se găsește valoarea optimă a funcției obiectiv auxiliare, pot apărea două situații:

valoarea optimă este mai mare decât zero. Aceasta înseamnă că cel puțin una dintre variabilele auxiliare a rămas în bază. În acest caz, putem concluziona că nu există soluții fezabile la această problemă de programare liniară. $z'$
valoarea optimă este zero. Aceasta înseamnă că toate variabilele auxiliare au fost scoase din bază și soluția curentă este valabilă. $z'$

În al doilea caz, avem un temei admisibil, sau, cu alte cuvinte, o soluție admisibilă inițială. Este posibil să se efectueze o optimizare ulterioară ținând cont de funcția obiectiv originală, fără a acorda atenție variabilelor auxiliare. Aceasta este a doua fază a soluției.

Metoda simplex modificată

În metoda modificată, matricea

${\begin{bmatrix}1&c_{B}^{T}B^{{-1}}Ac^{T}&c_{B}^{T}B^{{-1}}\\0&B^{{- 1}}A&B^{{-1}}\end{bmatrix}}$

nu este recalculată, doar matricea este stocată și recalculată . Restul algoritmului este similar cu cel descris mai sus. $B^{{-1}}$

1. Calculați variabile duale $d=c_{B}^{T}B^{{-1}}$

2. Verificarea optimității. este convertit în . $c_{B}^{T}B^{{-1}}Ac^{T}$ $d^{T}Ac^{T}$

Verificarea constă în calculul pentru toate coloanele . O coloană cu o valoare < 0 poate fi introdusă în bază. $d^{T}A_{n}-c_{n}$ $n\în N$

Adesea alegeți valoarea minimă, dar pentru aceasta trebuie să repetați peste toate coloanele.

Mai des alegeți o valoare mai mică decât o valoare dată $-\varepsilon$

Dacă o astfel de coloană nu este găsită, valoarea absolută maximă găsită este luată ca fiind cea găsită și coloana corespunzătoare este introdusă în bază. $\varepsilon$ $A_{J}$

3. Definirea ieșirii.

Fie coloana de intrare corespunzătoare variabilei Planul de bază este soluția sistemului Creștere . $A_{J}$ $x_{J}$ $A_{B}p=b$ $A_{B}p+\vartheta A_{J}=b$

Înmulțiți în stânga cu , adică . $B^{{-1}}$ $B^{{-1}}A_{B}p+\vartheta B^{{-1}}A_{J}=B^{{-1}}b$

Aici este planul de bază, este extinderea coloanei de intrare în ceea ce privește baza. $B^{{-1}}b$ $q=B^{{-1}}A_{J}$

Găsiți valoarea maximă pentru care toate valorile sunt nenegative. Dacă se poate lua arbitrar mare, soluția este nemărginită. În caz contrar, unul dintre elemente va ajunge la zero. Deducem din bază coloana corespunzătoare. $\vartheta$ $\vartheta$

4. Recalcularea planului de referință (de bază).

Calculăm un nou plan de referință folosind formula deja dată cu valoarea găsită . $x=p+\vartheta B^{{-1}}A_{J}$ $\vartheta$

5. Recalculăm inversul bazei . $B^{{-1}}$

Fie coloana de ieșire. $B^{{-1}}A_{F}$

Matricea B poate fi reprezentată ca $[B_{G}A_{F}]$

unde este matricea de bază fără coloana de ieșire. $B_{G}$

După schimbarea coloanei, matricea de bază va arăta ca $[B_{G}A_{J}]$

Trebuie să găsim o matrice astfel încât $B_1$

$[B_{G},A_{J}]B_{1}^{{-1}}=E$ => => => $[B^{{-1}}B_{G}B_{1}^{{-1}},B^{{-1}}A_{J}]=B^{{-1}}$ $[B^{{-1}}B_{G},q]B_{1}^{{-1}}=B^{{-1}}$

${\begin{bmatrix}E&q'\\0&q_{f}\end{bmatrix}}B_{1}^{{-1}}=B^{{-1}}$

Unde $B_{1}^{{-1}}={\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix}}B^{{-1}}$

Cometariu.

Recalcularea matricei acumulează erori de rotunjire. Pentru a evita erorile mari, matricea este recalculată complet din când în când. Acest proces se numește „repetiție”. $B^{{-1}}$

O versiune multiplicativă a metodei simplex

În versiunea multiplicativă, matricea nu este stocată, sunt stocați doar factorii $B^{{-1}}$ ${\begin{bmatrix}E&-q'/q_{f}\\0&1/q_{f}\end{bmatrix))$

La rezolvarea problemelor economice, matricea de constrângeri este adesea rară , caz în care opțiunea multiplicativă obține avantaje suplimentare - puteți stoca multiplicatori într-o formă comprimată (nu stocați zerouri).

Alte variante ale metodei simplex

Descompunerea LU a matricei poate fi utilizată pentru a evita acumularea erorilor de rotunjire .

Cu numărul copleșitor de restricții de tip „inegalitate”, poate fi utilizată metoda bazei variabile . [patru]

Metoda se bazează pe faptul că matricea de bază poate fi reprezentată ca

${\begin{bmatrix}A_{B}&0\\A_{E}&E\end{bmatrix}}$

Inversul său are forma

${\begin{bmatrix}A_{B}^{{-1}}&0\\-A_{B}^{{-1}}A_{E}&E\end{bmatrix}}$

Cu dimensiuni relativ mici ale matricei, restul matricei poate să nu fie stocat. $A_{B}^{{-1}}$

Această abordare poate rezolva probleme cu zeci de milioane de șiruri de restricții (de exemplu, din teoria jocurilor).

Metoda dual simplex

Pentru implementarea metodei duale este necesar să trecem de la problemă la minim la problemă la maxim (sau invers) prin transpunerea matricei de coeficienți. La trecerea de la sarcină la minim, funcția obiectiv va lua forma:

$g=\sum _{{i=1}}^{n}b_{i}y_{i}\la max$

sub restricții

$\sum _{i=1}^{n}a_{ij}y_{i}\leq c_{j}$ .

Teorema dualității . Dacă una dintr-o pereche de probleme duale are un plan optim, atunci cealaltă are o soluție, iar valorile extreme ale funcțiilor liniare ale acestor probleme sunt egale.

Dacă funcția liniară a uneia dintre probleme nu este limitată, atunci cealaltă nu are soluție.

Eficiență computațională

Metoda simplex este surprinzător de eficientă în practică, dar în 1972 Klee și Minty [5] au dat un exemplu în care metoda simplex a iterat peste toate vârfurile simplexului, arătând convergența exponențială a metodei în cel mai rău caz. De atunci, pentru fiecare variantă a metodei, s-a găsit un exemplu pe care metoda s-a comportat excepțional de prost.

Observațiile și analiza eficacității metodei în aplicații practice au condus la dezvoltarea altor modalități de măsurare a eficacității.

Metoda simplex are o convergență polinomială medie cu o gamă largă de distribuție a valorilor în matrice aleatoare. [6] [7]

Eficiența de calcul este de obicei estimată folosind doi parametri:

numărul de iterații necesare pentru a obține o soluție;
costurile de timp ale mașinii.

În urma experimentelor numerice s-au obținut următoarele rezultate.

Numărul de iterații în rezolvarea problemelor de programare liniară în forma standard cu constrângeri și variabile este între și . Numărul mediu de iterații . Limita superioară a numărului de iterații este . $m$ $n$ $m$ $3m$ $2m$ $2m+n$
Timpul necesar al mașinii este proporțional cu . $m^{3}$

Numărul de restricții afectează eficiența de calcul mai mult decât numărul de variabile, prin urmare, atunci când se formulează probleme de programare liniară, ar trebui să ne străduim să reducem numărul de restricții, chiar dacă prin creșterea numărului de variabile.

Metode de îmbunătățire a eficienței

Una dintre cele mai consumatoare de timp în metoda simplex este căutarea unei coloane introduse în bază. Pentru o convergență mai bună, s-ar părea că trebuie să alegeți o variabilă cu cel mai bun rezidual, dar aceasta necesită o scanare completă, adică trebuie să înmulțiți o coloană de variabile duale (uneori numite prețuri umbră) cu toate coloanele matricei. [8] . Această abordare funcționează bine pentru problemele mici care sunt rezolvate manual. Mai mult, respectarea strictă a regulii de alegere a reziduului maxim în modul se poate dovedi a fi suboptimă în ceea ce privește numărul total de iterații necesare pentru a obține un extremum. Câștigul maxim la o iterație poate duce la o scădere lentă a valorii funcției obiectiv la pașii următori și, prin urmare, poate încetini procesul de rezolvare a problemei [9] .

Cu matrice de constrângeri mari, procedura de căutare a unei variabile de intrare începe să dureze mult timp și se încearcă deseori să se evite analizarea tuturor coloanelor matricei, pentru care se pot folosi următoarele metode:

Bariera . De îndată ce discrepanța variabilei este suficient de diferită de zero (depășește o anumită valoare numită barieră), variabila este introdusă în bază. Dacă toate reziduurile s-au dovedit a fi mai mici decât bariera, variabila cu cel mai mic reziduu este selectată ca intrare, în timp ce bariera în sine este redusă conform unei anumite reguli (de exemplu, jumătate din cel mai mic reziduu). Bariera este adesea folosită cu următoarea tehnică. O abordare similară este descrisă în cartea lui Murtaugh, vezi secțiunea 3.6.2. Evaluarea parțială a cărții [10] . Vedere ciclului . Căutarea unei variabile de intrare începe de la poziția care urmează variabilei introduse la iterația anterioară. Selectarea grupului (În cartea lui Murtaugh, această tehnică se numește evaluare multiplă . Vezi secțiunea 3.6.3. Evaluare multiplă [11] .) Când se caută o variabilă de intrare, nu este selectată o variabilă, ci mai mulți candidați. La următoarele iterații, vizualizarea se efectuează numai printre candidații selectați, în timp ce candidatul poate fi șters din listă. Scopul cântarilor . Variabilelor li se atribuie ponderi. Vezi secțiunea 3.6.4 Metoda de punctare DEVEX de Murtafa [12] . Căutați cea mai abruptă coastă a Goldfarb și Reed. Vezi secțiunea 3.6.5 Metoda de estimare a muchiei celei mai abrupte din cartea lui Murtaugh [13] .

Sunt posibile și alte trucuri, cum ar fi regula Zadeh .

Note

↑ Kantorovich L. V. Metode matematice pentru organizarea planificării producției // Ediția Universității de Stat din Leningrad. - Leningrad, 1939.
↑ S. Gass. Programare liniară (metode și aplicații). - Moscova: Editura de Stat de Literatură Fizică și Matematică, 1961. - (Biblioteca de fizică și matematică a inginerului).
↑ Această recomandare se găsește adesea în manuale, dar nu este întotdeauna corectă. Consultați #Metode pentru îmbunătățirea eficienței
↑ V.I. Muravyov. Metodă de îmbunătățire secvențială cu bază de dimensiune variabilă pentru probleme de programare liniară. — Colecția „Cercetare operațiuni și metode de modelare statistică”. - Leningrad: Universitatea de Stat din Leningrad, 1972.
↑ Klee, Victor; Minty, George J. Cât de bun este algoritmul simplex? // Inequalities III (Proceedings of the Third Symposium on Inequalities ținut la Universitatea din California, Los Angeles, California, 1–9 septembrie 1969, dedicat memoriei lui Theodore S. Motzkin) (engleză) / Shisha, Oved . - New York-Londra: Academic Press , 1972. - P. 159-175.
↑ Alexander Schrijver, Teoria programării liniare și întregi . John Wiley & Sons, 1998, ISBN 0-471-98232-6 (matematic)
↑ Algoritmul simplex ia în medie D pași pentru un cub. Borgwardt, Karl-Heinz. Metoda simplex: O analiză probabilistă . - Berlin: Springer-Verlag , 1987. - Vol. 1. - P.xii+268. - (Algoritmi și combinatorice (texte de studiu și cercetare)). - ISBN 3-540-17096-0 .
↑ Recomandarea de a alege valoarea modulo maximă a reziduului poate fi găsită adesea în descrierile metodei simplex, de exemplu, în articolele Algoritm pentru metoda simplex Arhivat 17 martie 2018 pe Wayback Machine și METODĂ DE PROGRAMARE LINEAR SIMPLEX Arhivat 17 martie 2018 pe Wayback Machine
↑ Shamray, 2009 , p. 44.
↑ Murtaf, 1984 .
↑ Murtaf, 1984 , p. 61.
↑ Murtaf, 1984 , p. 62.
↑ Murtaf, 1984 , p. 63.

Literatură

Hemdy A. Taha. Capitolul 3. Metoda Simplex // Introducere în Cercetarea operațională = Cercetarea operațională: o introducere. - Ed. a VII-a. - M . : „Williams” , 2007. - S. 95-141. — ISBN 0-13-032374-8 .
Akulich I.L. Capitolul 1. Probleme de programare liniara // Programarea matematica in exemple si probleme. - M . : Şcoala superioară , 1986. - 319 p. — ISBN 5-06-002663-9 .
Thomas H. Kormen și colab.Capitolul 29 Programarea liniară // Algoritmi: Construcție și Analiză = INTRODUCERE ÎN ALGORITMI. - Ed. a II-a. - M .: „Williams” , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
V. N. Şevcenko, N. Yu. Zolotykh. Programare liniară liniară și întregă . - Nijni Novgorod: Editura Universității de Stat Nijni Novgorod. N.I. Lobachevsky, 2004. - P. 63 -66 (secțiunea 2.8. Observații privind complexitatea rezolvării LLP). — ISBN 5-85746-761-6 .
Shamray Natalya Borisovna. Programare liniară practică pentru economiști . - Vladivostok: Editura Universității din Orientul Îndepărtat, 2009. - P. 44. - ISBN 978-5-7444-2215-8 . Arhivat pe 17 martie 2018 la Wayback Machine
Murtaf B. Programare liniară modernă. - Moscova: Mir, 1984.

Link -uri

Dicționare și enciclopedii	Britannica (online)
În cataloagele bibliografice	GND : 4181488-5 J9U : 987007546249105171 LCCN : sh85122745

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică