Algoritmul Simplex

Algoritmul simplex , inventat de americanul George Dantzig în 1947 , este o metodă numerică pentru rezolvarea problemelor de programare liniară . Este citat de revista americană Computing in Science and Engineering ca unul dintre cei mai buni zece algoritmi ai secolului. ^[1]

Acest algoritm folosește conceptul de simplex , adică un politop al $N+1$ ${\ displaystyle N + 1}$ $N + 1$ vârfuri în $Nu.$ ${\ displaystyle N}$ $Nu.$ dimensiuni, adică un segment de linie într-o dimensiune, un triunghi în două dimensiuni, un tetraedru în trei dimensiuni.

Programare liniară

Același subiect în detaliu: programare liniară .

O problemă de programare liniară constă în maximizarea sau minimizarea unei funcții liniare definite pe setul de soluții ale unui sistem de inegalități liniare , numite constrângeri .

De exemplu, problema:

{\begin{cases}\max \quad x+2y\\x-y\leq 4\\x\geq 0\\y\geq 0\end{cases}}

{\ displaystyle {\ begin {cases} \ max \ quad x + 2y \\ xy \ leq 4 \\ x \ geq 0 \\ y \ geq 0 \ end {cases}}}

{\ displaystyle {\ begin {cases} \ max \ quad x + 2y \\ x-y \ leq 4 \\ x \ geq 0 \\ y \ geq 0 \ end {cases}}}

este o problemă de programare liniară.

Constrângerile definesc regiunea fezabilă (adică setul de puncte care satisfac toate constrângerile problemei, în engleză „feasible region”). În cazul programării liniare, regiunea fezabilă este un poliedru care poate fi gol, limitat sau nelimitat. Funcția care trebuie minimizată sau maximizată este „ funcția obiectivă ”: în practică calculează „costul” fiecărei soluții a constrângerilor.

Prin urmare, obiectivul de a rezolva o astfel de problemă este de a găsi printre soluțiile care satisfac constrângerile, cea care corespunde costului minim (sau maxim, dacă este un venit).

Algoritmul

Un sistem de inegalități liniare definește un politop ca o regiune fezabilă. Algoritmul simplex începe de la un vârf inițial și se deplasează de-a lungul laturilor politopului până când ajunge la vârful soluției optime.

Algoritmul simplex este capabil să determine ce fel de poliedru este și găsește soluția optimă, care este, sub ipoteze adecvate, un vârf al poliedrului, dacă problema are o soluție optimă finită.

Algoritmul este de obicei formulat pe probleme formulate în așa-numita formă standard în care trebuie să maximizăm o funcție liniară supusă (în engleză „subject to” abreviată st) constrângerilor de egalitate și în care variabilele sunt pozitive sau nule:

Maximizează

{\boldsymbol {\gamma }}^{T}\mathbf {x}

${\ displaystyle {\ boldsymbol {\ gamma}} ^ {T} \ mathbf {x}}$ $\ boldsymbol {\ gamma} ^ T \ mathbf {x}$ Sf

{\boldsymbol {\mathrm {A} }}\mathbf {x} =\mathbf {b}

${\ displaystyle {\ boldsymbol {\ mathrm {A}}} \ mathbf {x} = \ mathbf {b}}$ $\ boldsymbol {\ Alpha} \ mathbf {x} = \ mathbf {b}$ Și

x_{i}\geq 0

${\ displaystyle x_ {i} \ geq 0}$ $x_i \ ge 0$ , unde este

\mathbf {A}

{\ displaystyle \ mathbf {A}}

\ mathbf {A}

este o matrice ,

\mathbf {b} ,\mathbf {x} ,{\boldsymbol {\gamma }}

${\ displaystyle \ mathbf {b}, \ mathbf {x}, {\ boldsymbol {\ gamma}}}$ $\ mathbf {b}, \ mathbf {x}, \ boldsymbol {\ gamma}$ sunt vectori de coloană , le

x_{i}

{\ displaystyle x_ {i}}

x_i

este

n

{\ displaystyle n}

n

componente ale

\mathbf {x}

${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ si

T.

{\ displaystyle T}

T.

ad exponent este operatorul de transpunere .

Această formulare este ușor atinsă, prin adăugarea sau scăderea, după caz, a unei variabile numite „slack” (dacă se adaugă) sau „surplus” (dacă se scade) la o problemă formulată în formă canonică ${\boldsymbol {\gamma }}^{T}\mathbf {x}$ ${\ displaystyle {\ boldsymbol {\ gamma}} ^ {T} \ mathbf {x}}$ $\ boldsymbol {\ gamma} ^ T \ mathbf {x}$ Sf ${\boldsymbol {\mathrm {A} }}\mathbf {x} \leq \mathbf {b}$ ${\ displaystyle {\ boldsymbol {\ mathrm {A}}} \ mathbf {x} \ leq \ mathbf {b}}$ $\ boldsymbol {\ Alpha} \ mathbf {x} \ le \ mathbf {b}$ Și $x_{i}\geq 0$ ${\ displaystyle x_ {i} \ geq 0}$ $x_i \ ge 0$ . Poate fi rezumată într-un tablou de tip ${\begin{pmatrix}\mathbf {A} \;\,\mathbf {b} \\{\boldsymbol {\gamma }}^{T}\;0\end{pmatrix}}$ ${\ displaystyle {\ begin {pmatrix} \ mathbf {A} \; \, \ mathbf {b} \\ {\ boldsymbol {\ gamma}} ^ {T} \; 0 \ end {pmatrix}}}$ $\ begin {pmatrix} \ mathbf {A} \; \, \ mathbf {b} \\ \ boldsymbol {\ gamma} ^ {T} \; 0 \ end {pmatrix}$ Algoritmul este împărțit în următorii pași aplicați tabloului:

Verificarea optimității. O condiție suficientă pentru ca masa să fie optimă este aceea ${\boldsymbol {\gamma }}_{i}\leq 0,$ ${\ displaystyle {\ boldsymbol {\ gamma}} _ {i} \ leq 0,}$ ${\ displaystyle {\ boldsymbol {\ gamma}} _ {i} \ leq 0,}$ pentru fiecare $i=1,\ldots ,n$ ${\ displaystyle i = 1, \ ldots, n}$ ${\ displaystyle i = 1, \ ldots, n}$ (dacă este o problemă maximă, e ${\boldsymbol {\gamma }}_{i}\geq 0,$ ${\ displaystyle {\ boldsymbol {\ gamma}} _ {i} \ geq 0,}$ ${\ displaystyle {\ boldsymbol {\ gamma}} _ {i} \ geq 0,}$ pentru fiecare $i=1,\ldots ,n$ ${\ displaystyle i = 1, \ ldots, n}$ ${\ displaystyle i = 1, \ ldots, n}$ dacă este minim).
Dacă nu aveți încă un tabel grozav, aleg o coloană $h$ ${\ displaystyle h}$ $h$ corespunzător maximului de $\gamma _{i}\geq 0$ ${\ displaystyle \ gamma _ {i} \ geq 0}$ $\ gamma_i \ ge0$ (costuri reduse pozitive) (vor exista cel puțin unul altfel ne-am fi oprit la punctul 1).
Verificarea nelimitătii. O condiție suficientă pentru ca problema să fie nelimitată este cea din coloană $h$ ${\ displaystyle h}$ $h$ identificat avem doar valori negative în matrice, adică $\mathbf {a} _{ih}<0,\;\forall i=1,\ldots ,n$ ${\ displaystyle \ mathbf {a} _ {ih} <0, \; \ forall i = 1, \ ldots, n}$ ${\ displaystyle \ mathbf {a} _ {ih} <0, \; \ forall i = 1, \ ldots, n}$ . Prin urmare, problema este nelimitată în această direcție.
Dacă nu suntem în prezența unei probleme nelimitate, aleg pivotul care generează raportul minim între termenul cunoscut și coeficientul variabilei relative din coloană $h$ ${\ displaystyle h}$ $h$ a matricei $\mathbf {A}$ ${\ displaystyle \ mathbf {A}}$ $\ mathbf {A}$ , acesta este $i'=\min \left\{{\frac {\mathbf {b} _{i}}{\mathbf {a} _{ih}}}\;\mathbf {:} \;\mathbf {a} _{ih}>{0},\;\forall i=1,\ldots ,n\right\}$ ${\ displaystyle i '= \ min \ left \ {{\ frac {\ mathbf {b} _ {i}} {\ mathbf {a} _ {ih}}} \; \ mathbf {:} \; \ mathbf { a} _ {ih}> {0}, \; \ forall i = 1, \ ldots, n \ right \}}$ ${\ displaystyle i '= \ min \ left \ {{\ frac {\ mathbf {b} _ {i}} {\ mathbf {a} _ {ih}}} \; \ mathbf {:} \; \ mathbf { a} _ {ih}> {0}, \; \ forall i = 1, \ ldots, n \ right \}}$ și aplic operația de balama.

Operațiunea pivotă este operația care vă permite să vă deplasați de-a lungul unei direcții admisibile pentru un anumit pas, astfel încât noua soluție să fie, de asemenea, admisibilă, dar mai bună decât cea anterioară.

Criteriu de verificare a optimității / oprire

Având în vedere problema programării liniare $\min \left\{\gamma \left(\mathbf {x} \right):=\mathbf {c} ^{T}\mathbf {x} :A\mathbf {x} =\mathbf {b} ,\mathbf {x} \geq \mathbf {0} \right\}$ ${\ displaystyle \ min \ left \ {\ gamma \ left (\ mathbf {x} \ right): = \ mathbf {c} ^ {T} \ mathbf {x}: A \ mathbf {x} = \ mathbf {b }, \ mathbf {x} \ geq \ mathbf {0} \ right \}}$ $\ min \ left \ {\ gamma \ left (\ mathbf {x} \ right): = \ mathbf {c} ^ {T} \ mathbf {x}: A \ mathbf {x} = \ mathbf {b}, \ mathbf {x} \ geq \ mathbf {0} \ right \}$ se ia în considerare baza admisibilă $B.$ ${\ displaystyle B}$ $B.$ conținând coloane liniar independente de $LA$ ${\ displaystyle A}$ $LA$ . Relația poate fi rescrisă $A\mathbf {x} =\mathbf {b}$ ${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$ $A \ mathbf {x} = \ mathbf {b}$ ca:

B\mathbf {x} _{B}+F\mathbf {x} _{F}=\mathbf {b}

{\ displaystyle B \ mathbf {x} _ {B} + F \ mathbf {x} _ {F} = \ mathbf {b}}

{\ displaystyle B \ mathbf {x} _ {B} + F \ mathbf {x} _ {F} = \ mathbf {b}}

cu $F.$ ${\ displaystyle F}$ $F.$ matrice conținând coloanele din $LA$ ${\ displaystyle A}$ $LA$ excluse din baza eligibilă $B.$ ${\ displaystyle B}$ $B.$ .

Din nou, putem rescrie relația anterioară ca:

B\mathbf {x} _{B}=\mathbf {b} -F\mathbf {x} _{F}\Rightarrow \mathbf {x} _{B}=B^{-1}\mathbf {b} -B^{-1}F\mathbf {x} _{F}

{\ displaystyle B \ mathbf {x} _ {B} = \ mathbf {b} -F \ mathbf {x} _ {F} \ Rightarrow \ mathbf {x} _ {B} = B ^ {- 1} \ mathbf {b} -B ^ {- 1} F \ mathbf {x} _ {F}}

{\ displaystyle B \ mathbf {x} _ {B} = \ mathbf {b} -F \ mathbf {x} _ {F} \ Rightarrow \ mathbf {x} _ {B} = B ^ {- 1} \ mathbf {b} -B ^ {- 1} F \ mathbf {x} _ {F}}

și, înlocuind relația din funcția obiectivă față de problema inițială, avem:

\mathbf {c} ^{T}\mathbf {x} =\left[{\begin{bmatrix}\mathbf {c} _{B}^{T}&\mathbf {c} _{F}^{T}\end{bmatrix}}\right]\left[{\begin{bmatrix}\mathbf {x} _{B}\\\mathbf {x} _{F}\end{bmatrix}}\right]\Rightarrow

{\ displaystyle \ mathbf {c} ^ {T} \ mathbf {x} = \ left [{\ begin {bmatrix} \ mathbf {c} _ {B} ^ {T} & \ mathbf {c} _ {F} ^ {T} \ end {bmatrix}} \ right] \ left [{\ begin {bmatrix} \ mathbf {x} _ {B} \\\ mathbf {x} _ {F} \ end {bmatrix}} \ right ] \ Sageata dreapta}

{\ displaystyle \ mathbf {c} ^ {T} \ mathbf {x} = \ left [{\ begin {bmatrix} \ mathbf {c} _ {B} ^ {T} & \ mathbf {c} _ {F} ^ {T} \ end {bmatrix}} \ right] \ left [{\ begin {bmatrix} \ mathbf {x} _ {B} \\\ mathbf {x} _ {F} \ end {bmatrix}} \ right ] \ Sageata dreapta}

\mathbf {c} ^{T}\mathbf {x} =\left[{\begin{bmatrix}\mathbf {c} _{B}^{T}&\mathbf {c} _{F}^{T}\end{bmatrix}}\right]\left[{\begin{bmatrix}B^{-1}\mathbf {b} -B^{-1}F\mathbf {x} _{F}\\\mathbf {x} _{F}\end{bmatrix}}\right]\Rightarrow

{\ displaystyle \ mathbf {c} ^ {T} \ mathbf {x} = \ left [{\ begin {bmatrix} \ mathbf {c} _ {B} ^ {T} & \ mathbf {c} _ {F} ^ {T} \ end {bmatrix}} \ right] \ left [{\ begin {bmatrix} B ^ {- 1} \ mathbf {b} -B ^ {- 1} F \ mathbf {x} _ {F} \\\ mathbf {x} _ {F} \ end {bmatrix}} \ right] \ Rightarrow}

{\ displaystyle \ mathbf {c} ^ {T} \ mathbf {x} = \ left [{\ begin {bmatrix} \ mathbf {c} _ {B} ^ {T} & \ mathbf {c} _ {F} ^ {T} \ end {bmatrix}} \ right] \ left [{\ begin {bmatrix} B ^ {- 1} \ mathbf {b} -B ^ {- 1} F \ mathbf {x} _ {F} \\\ mathbf {x} _ {F} \ end {bmatrix}} \ right] \ Rightarrow}

\mathbf {c} ^{T}\mathbf {x} =\mathbf {c} _{B}^{T}B^{-1}\mathbf {b} +\left(\mathbf {c} _{F}^{T}-\mathbf {c} _{B}^{T}B^{-1}F\right)\mathbf {x} _{F}=\mathbf {c} ^{T}\mathbf {x} +k

{\ displaystyle \ mathbf {c} ^ {T} \ mathbf {x} = \ mathbf {c} _ {B} ^ {T} B ^ {- 1} \ mathbf {b} + \ left (\ mathbf {c } _ {F} ^ {T} - \ mathbf {c} _ {B} ^ {T} B ^ {- 1} F \ right) \ mathbf {x} _ {F} = \ mathbf {c} ^ { T} \ mathbf {x} + k}

{\ displaystyle \ mathbf {c} ^ {T} \ mathbf {x} = \ mathbf {c} _ {B} ^ {T} B ^ {- 1} \ mathbf {b} + \ left (\ mathbf {c } _ {F} ^ {T} - \ mathbf {c} _ {B} ^ {T} B ^ {- 1} F \ right) \ mathbf {x} _ {F} = \ mathbf {c} ^ { T} \ mathbf {x} + k}

cu $k$ ${\ displaystyle k}$ $k$ valoare constantă e $\mathbf {c} ^{T}:=\mathbf {c} _{F}^{T}-\mathbf {c} _{B}^{T}B^{-1}A$ ${\ displaystyle \ mathbf {c} ^ {T}: = \ mathbf {c} _ {F} ^ {T} - \ mathbf {c} _ {B} ^ {T} B ^ {- 1} A}$ ${\ displaystyle \ mathbf {c} ^ {T}: = \ mathbf {c} _ {F} ^ {T} - \ mathbf {c} _ {B} ^ {T} B ^ {- 1} A}$ vector al costurilor reduse.

În aceste condiții, dacă vectorul costurilor reduse este negativ, soluția de bază fezabilă asociată cu $LA$ ${\ displaystyle A}$ $LA$ se dovedește a fi excelent. Aceasta înseamnă că valoarea asumată de funcția obiectivă $\gamma \left(\mathbf {x} \right)$ ${\ displaystyle \ gamma \ left (\ mathbf {x} \ right)}$ $\ gamma \ left (\ mathbf {x} \ right)$ este minimul global pentru funcția din domeniul considerat.

Performanţă

În practică, algoritmul funcționează foarte bine ^{[ fără sursă ]} , dar în teorie nu este polinomial și se pot construi exemple speciale în care algoritmul necesită să viziteze un număr exponențial de vârfuri cu privire la dimensiunea problemei. Concurenții reali ai metodei simplex pentru probleme mari sunt metodele punctuale interne .

Tipuri de simplex

Descrierea dată mai sus este destul de generică: ideea generală a lui Dantzig a fost apoi aplicată la multe probleme practice de cercetare a operațiilor , astfel încât în cele din urmă aceasta a produs o serie lungă de algoritmi simplex, fiecare pentru o problemă specifică.

Iată câteva dintre principalele metode simplex:

Notă

^ Computing in Science and Engineering, volumul 2, nr. 1, 2000

Elemente conexe

linkuri externe

(EN) Eric W. Weisstein, Metoda Simplex , în MathWorld Wolfram Research.
( EN ) EG Gol'shtein, metoda Simplex , în Enciclopedia Matematicii , Springer și European Mathematical Society, 2002.
( EN ) Algoritmul Simplex , de Elmer G. Wiens. Demonstrați algoritmul de detaliu, utilizând tabloul simplex .
Rezolvarea problemelor de programare liniară utilizând metoda simplex , pe Operations Research Group , Universitatea din Trieste (arhivat din adresa URL originală la 25 februarie 2008) .

Controlul autorității	LCCN (EN) sh85122745 · GND (DE) 4181488-5

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Computing in Science and Engineering, volumul 2, nr. 1, 2000

[1]