Transformarea Jordan-Gauss și metoda simplex în Excel. Rezolvarea unei probleme de producție folosind metoda simplex tabelar
Metoda Gauss-Jordan este destinată rezolvării sistemelor liniare ecuații algebrice(SLAU). Este o modificare a metodei Gauss. Dacă metoda Gauss este efectuată în două etape (înainte și înapoi), atunci metoda Gauss-Jordan vă permite să rezolvați sistemul într-o singură etapă. Detalii și aplicarea directă a metodei Gauss-Jordan sunt descrise în exemple.
În toate exemplele, $A$ denotă matricea sistemului, $\widetilde(A)$ matricea sistemului extins. Puteți citi despre forma matriceală de înregistrare SLAE.
Exemplul nr. 1
Rezolvați SLAE $ \left\( \begin(aligned) & 4x_1-7x_2+8x_3=-23;\\ & 2x_1-4x_2+5x_3=-13;\\ & -3x_1+11x_2+x_3=16. \end(aligned) ) \right.$ prin metoda Gauss-Jordan.
Să trecem de la ultima matrice pe care am primit-o la sistem:
$$ \left\( \begin(aligned) & 0\cdot x_1+1\cdot x_2+0\cdot x_3=1;\\ & 1\cdot x_1+0\cdot x_2+0\cdot x_3=-2; \\ & 0\cdot x_1+0\cdot x_2+1\cdot x_3=-1. \end(aliniat) \right. $$
Simplificand sistemul rezultat, avem:
$$ \left\( \begin(aligned) & x_2=1;\\ & x_1=-2;\\ & x_3=-1. \end(aligned) \right. $$
Soluție completă fara explicatii arata asa:
Deși această metodă de selectare a elementelor de rezoluție este destul de acceptabilă, este de preferat să se selecteze elemente diagonale ale matricei sistemului ca elemente de rezoluție. Ne vom uita la această metodă mai jos.
Selectarea elementelor de rezoluție pe diagonala principală a matricei sistemului.
Deoarece această metodă de soluție este complet similară cu cea anterioară (cu excepția selecției elementelor de activare), vom omite explicațiile detaliate. Principiul selectării elementelor de activare este simplu: în prima coloană selectăm elementul din primul rând, în a doua coloană luăm elementul din al doilea rând, în a treia coloană luăm elementul din al treilea rând și așadar pe.
Primul pas
În prima coloană, selectați elementul din primul rând, adică. avem ca element de rezolvare elementul 4. Înțeleg că alegerea numărului 2 pare mai de preferat, deoarece acest număr este tot mai mic decât 4. Pentru ca numărul 2 din prima coloană să treacă pe primul loc, să schimbăm primul și al doilea rând:
$$ \left(\begin(array) (ccc|c) 4 & -7 & 8 & -23\\ 2 & -4& 5 & -13 \\ -3 & 11 & 1 & 16 \end(array) \ dreapta)\rightarrow \left(\begin(array) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(array ) \dreapta) $$
Deci, elementul de activare este reprezentat de numărul 2. În același mod ca și înainte, împărțiți primul rând la 2, apoi resetați elementele primei coloane la zero:
$$ \left(\begin(array) (ccc|c) 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end(array) \ dreapta) \begin(array) (l) I:2 \\\phantom(0) \\ \phantom(0) \end(array) \rightarrow \left(\begin(array) (ccc|c) 1 & - 2& 5/2 & -13/2 \\4 & -7 & 8 & -23\\ -3 & 11 & 1 & 16 \end(array) \right) \begin(array) (l) \phantom(0 ) \\ II-4\cdot I\\ III+3\cdot I \end(array) \rightarrow \left(\begin(array) (ccc|c) 1 & -2& 5/2 & -13/2\ \0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end(array) \right). $$
Al doilea pas
Al doilea pas necesită reducerea la zero a elementelor celei de-a doua coloane. Selectăm elementul din a doua linie ca element de rezolvare, adică. 1. Elementul de activare este deja egal cu unu, așa că nu vom schimba niciun rând. Apropo, dacă am vrea să schimbăm rândurile, nu am atinge primul rând, deoarece era deja folosit în primul pas. Dar a doua și a treia linie pot fi schimbate cu ușurință. Cu toate acestea, repet, în această situație nu este nevoie să schimbați liniile, deoarece elementul de rezolvare este deja optim - este egal cu unul.
$$ \left(\begin(array) (ccc|c) 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/ 2 \end(array) \right) \begin(array) (l) I+2\cdot II \\ \phantom(0)\\ III-5\cdot II \end(array) \rightarrow \left(\begin (matrice) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end(array) \dreapta). $$
Al doilea pas este finalizat. Să trecem la al treilea pas.
Al treilea pas
Al treilea pas necesită eliminarea la zero a elementelor celei de-a treia coloane. Ca element de rezolvare, selectăm elementul din a treia linie, adică. 37/2. Să împărțim elementele celui de-al treilea rând la 37/2 (astfel încât elementul de rezolvare să devină egal cu 1), apoi să resetăm elementele corespunzătoare din a treia coloană la zero:
$$ \left(\begin(array) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37 /2 \end(array) \right) \begin(array) (l) \phantom(0)\\ \phantom(0)\\ III:\frac(37)(2) \end(array) \rightarrow \ stânga(\begin(array) (ccc|c) 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 1 & -1 \end(array) \right) \begin(array) (l) I+2\cdot III\\II+3/2\cdot III\\ \phantom(0) \end(array) \rightarrow \left(\begin(array) ( ccc|c) 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1 \end(array) \right). $$
Răspuns primit: $x_1=-2$, $x_2=1$, $x_3=-1$. Soluția completă fără explicații arată astfel:
Toate celelalte exemple de pe această pagină vor fi rezolvate exact în al doilea mod: vom selecta elementele diagonale ale matricei sistemului ca rezolutive.
Răspuns: $x_1=-2$, $x_2=1$, $x_3=-1$.
Exemplul nr. 2
Rezolvați SLAE $ \left\( \begin(aligned) & 3x_1+x_2+2x_3+5x_4=-6;\\ & 3x_1+x_2+2x_4=-10;\\ & 6x_1+4x_2+11x_3+11x_4=-27; \\ & -3x_1-2x_2-2x_3-10x_4 = 1. \end(aligned) \right.$ prin metoda Gauss-Jordan.
Să scriem matricea extinsă a acestui sistem: $\widetilde(A)=\left(\begin(array) (cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1& 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \end(array) \right)$.
Vom selecta elemente diagonale ale matricei sistemului ca elemente de rezoluție: la primul pas vom lua elementul din primul rând, la al doilea pas vom lua elementul din al doilea rând și așa mai departe.
Primul pas
Trebuie să resetam elementele corespunzătoare din prima coloană. Să luăm elementul din prima linie ca element de rezolvare, adică. 3. În consecință, prima linie va trebui împărțită la 3, astfel încât elementul de rezolvare să devină egal cu unu. Și apoi resetați toate elementele primei coloane, cu excepția celei care permite:
$$ \left(\begin(array)(cccc|c) 3 & 1 & 2 & 5 & -6\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\ \ -3 & -2 & -2 & -10 & 1\end(array)\right) \begin(array) (l) I:3\\ \phantom(0)\\\phantom(0)\\\ phantom(0)\end(array) \rightarrow \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end(array)\right) \begin(array) (l) \phantom(0) \\ II-3\cdot I\\III-6\cdot I\\IV+3\cdot I\end(array) \rightarrow\\ \rightarrow\left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & - 5 și -5\end(matrice)\dreapta). $$
Al doilea pas
Se trece la zero elementele corespunzătoare din a doua coloană. Am fost de acord să luăm elementul din a doua linie ca element de rezolvare, dar nu putem face acest lucru, deoarece elementul necesar egal cu zero. Concluzie: vom schimba liniile. Prima linie nu poate fi atinsă, deoarece a fost deja folosită în primul pas. Alegerea nu este bogată: fie schimbăm a doua și a treia linie, fie schimbăm a patra și a doua. Deoarece a patra linie conține (-1), atunci lăsați a patra linie să ia parte la „schimb”. Deci, schimbați a doua și a patra linie:
$$ \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end(array)\right)\rightarrow \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4 \end(matrice)\right) $$
Acum totul este normal: elementul de rezoluție este egal cu (-1). Se întâmplă, de altfel, că schimbarea pozițiilor liniilor este imposibilă, dar despre asta vom discuta în următorul exemplu nr. 3. Pentru moment, împărțim al doilea rând cu (-1), apoi resetam elementele coloanei a doua. Vă rugăm să rețineți că în a doua coloană elementul situat în al patrulea rând este deja egal cu zero, așa că nu vom atinge al patrulea rând.
$$ \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(array)\right) \begin(array) (l) \phantom(0)\\II:(-1) \\\phantom(0)\\\phantom(0)\end(array) \rightarrow \left(\begin(array)(cccc|c) 1 & 1/3 & 2/3 & 5/3 & -2 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end(array)\right) \begin(array) (l) I-1/3\cdot II\\ \phantom(0) \\III-2\cdot II\\\phantom(0)\end(array) \rightarrow\\ \rightarrow\left(\begin( matrice)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(matrice)\dreapta). $$
Al treilea pas
Să începem să procesăm a treia coloană. Am convenit să luăm elementele diagonale ale matricei sistemului ca element de rezolvare. Pentru al treilea pas, aceasta înseamnă selectarea elementului situat pe al treilea rând. Totuși, dacă pur și simplu luăm elementul 7 ca element de rezolvare, atunci întreaga linie a treia va trebui împărțită la 7. Mi se pare că împărțirea la (-2) este mai simplă. Prin urmare, să schimbăm a treia și a patra linie, iar apoi elementul de rezolvare va deveni (-2):
$$ \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end(array)\right) \rightarrow \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end(array)\right) $$
Element de rezoluție - (-2). Împărțiți al treilea rând cu (-2) și resetați elementele corespunzătoare din a treia coloană:
$$ \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & - 3 & -4\\ 0 & 0 & 7 & -9 & -25\end(array)\right) \begin(array) (l) \phantom(0)\\ \phantom(0) \\III:( -2)\\\phantom(0)\end(array)\rightarrow \left(\begin(array)(cccc|c) 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 7 & -9 & -25\end(array)\right) \begin(array) (l) I-2 /3\cdot III\\ \phantom(0) \\ \phantom(0)\\IV-7\cdot III\end(array)\rightarrow\\ \rightarrow\left(\begin(array)(cccc|c ) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & - 39\end(matrice)\dreapta). $$
Al patrulea pas
Să trecem la zero a patra coloană. Elementul de activare este situat în a patra linie și egală cu numărul$-\frac(39)(2)$.
$$ \left(\begin(array)(cccc|c) 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2 \\ 0 & 0 & 0 & -39/2 & -39\end(array)\right) \begin(array) (l) \phantom(0)\\ \phantom(0) \\ \phantom(0) \\IV:\left(-\frac(39)(2)\right) \end(array)\rightarrow \left(\begin(array)(cccc|c) 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & 1 & 2\end(array)\right) \begin(array) (l ) I+IV\\ II-5\cdot IV \\ III-3/2\cdot IV \\ \phantom(0) \end(array)\rightarrow\\ \rightarrow\left(\begin(array)(cccc |c) 1 & 0 & 0 & 0 & -3\\ 0 & 1 & 0 & 0 & -5\\ 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 1 & 2\end (matrice)\dreapta). $$
Decizia s-a terminat. Răspunsul este: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$. Soluție completă fără explicații:
Răspuns: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$.
Exemplul nr. 3
Rezolvați SLAE $\left\(\begin(aligned) & x_1-2x_2+3x_3+4x_5=-5;\\ & 2x_1+x_2+5x_3+2x_4+9x_5=-3;\\ & 3x_1+4x_2+7x_3+4x_4 +14x_5=-1;\\ & 2x_1-4x_2+6x_3+11x_5=2;\\ & -2x_1+14x_2-8x_3+4x_4-7x_5=20;\\ & -4x_1-7x_2-9x_3-6x_4-21x_5= 9. \end(aligned)\right.$ prin metoda Gauss-Jordan Dacă sistemul este incert, indicați solutie de baza.
Exemple similare sunt discutate în subiectul „Soluții generale și de bază ale SLAE-urilor”. În partea a doua a subiectului menționat acest exemplu rezolvate folosind metoda Gauss. O vom rezolva folosind metoda Gauss-Jordan. Nu vom descompune soluția pas cu pas, deoarece acest lucru a fost deja făcut în exemplele anterioare.
$$ \left(\begin(array)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\\ 2 & 1 & 5 & 2 & 9 & -3\\ 3 & 4 & 7 & 4 & 14 & -1\\ 2 & -4 & 6 & 0 & 11 & 2\\ -2 & 14 & -8 & 4 & -7 & 20\\ -4 & -7 & -9 & -6 & -21 & -9 \end(array)\right) \begin(array) (l) \phantom(0) \\ II-2\cdot I\\ III-3\cdot I\\ IV-2\cdot I \\ V+2\cdot I\\VI+4\cdot I \end(array) \rightarrow \left(\begin(array)(ccccc|c) 1 & -2 & 3 & 0 & 4 & -5\ \\ 0 & 5 & -1 & 2 & 1 & 7\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(array)\right) \begin(array) (l) \phantom(0) \\ II:5 \\ \ phantom(0)\\ \phantom(0)\\ \phantom(0) \\ \phantom(0)\end(array) \rightarrow \\ \left(\begin(array)(ccccc|c) 1 & - 2 & 3 & 0 & 4 & -5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end(array)\right) \ începe (matrice) (l) I+2\cdot II \\ \phantom(0)\\ III-10\cdot II\\ IV:3\\ V-10\cdot II\\VI+15\cdot II \ final (matrice) \rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2 /5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & - 4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(array)\right). $$
Cred că una dintre transformările făcute necesită încă o explicație: $IV:3$. Toate elementele celei de-a patra linii sunt complet divizibile cu trei, așa că din motive de simplificare, am împărțit toate elementele acestei linii în trei. Al treilea rând din matricea transformată a devenit zero. Să tăiem linia zero:
$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(matrice)\right) $$
Este timpul să trecem la pasul al treilea, la care elementele coloanei a treia ar trebui să fie resetate. Cu toate acestea, elementul diagonal (al treilea rând) este zero. Și schimbarea pozițiilor liniilor nu va face nimic. Am folosit deja prima și a doua linie, așa că nu le putem atinge. Dar nu are rost să atingem liniile a patra și a cincea, deoarece problema ca elementul de rezoluție să fie egal cu zero nu va dispărea.
În această situație, problema poate fi rezolvată într-un mod extrem de simplu. Nu ne descurcăm cu a treia coloană? Bine, să trecem la numărul patru. Poate că în a patra coloană elementul celui de-al treilea rând nu va fi egal cu zero. Totuși, a patra coloană suferă de aceeași problemă ca a treia. Al treilea element de rând din a patra coloană este zero. Și schimbarea din nou a locurilor liniilor nu va da nimic. Nu putem procesa nici a patra coloană? Bine, să trecem la numărul cinci. Dar în a cincea coloană, elementul celui de-al treilea rând nu este nici măcar zero. Este egal cu unu, ceea ce este destul de bun. Deci, elementul de rezolvare din a cincea coloană este egal cu 1. Elementul de rezolvare a fost selectat, așa că vom efectua transformări ulterioare ale metodei Gauss-Jordan:
$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end(array)\right) \begin(array) (l) I-22/5\cdot III \\ II-1/5\cdot III \\ \phantom(0)\\ IV+III\\ V+ 2 \cdot III \end(array) \rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1 / 5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end(matrice)\right) \rightarrow \\ \rightarrow\left|\text(Eliminarea liniilor zero)\right|\rightarrow \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(array)\ dreapta )$$
Am redus matricea de sistem și matricea de sistem extinsă la o formă în trepte. Rangurile ambelor matrici sunt egale cu $r=3$, i.e. trebuie să alegeți 3 variabile de bază. Numărul de necunoscute este $n=5$, așa că trebuie să alegem variabile libere $n-r=2$. Din moment ce $r< n$, то согласно следствию из теоремы Кронекера-Капелли данная система является неопределённой (т.е. имеет бесконечное количество решений). Для нахождения решений системы составим "ступеньки":
Pe „trepte” există elemente din coloanele nr. 1, nr. 2, nr. 5. În consecință, variabilele de bază vor fi $x_1$, $x_2$, $x_5$. Variabilele libere, respectiv, vor fi $x_3$, $x_4$. Vom muta coloanele nr. 3 și nr. 4, corespunzătoare variabilelor libere, dincolo de linie, fără a uita, desigur, să le schimbăm semnele.
$$ \left(\begin(array)(ccccc|c) 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end(array)\right)\rightarrow \left(\begin(array)(ccc|ccc) 1 & 0 & 0 & -99/5 & -13/5 & -4/5\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5\\ 0 & 0 & 1 & 4 & 0 & 0\end(array)\right) . $$
Din ultima matrice obținem soluția generală: $\left\(\begin(aligned) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5) )x_4; \\ & x_2=\frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\ în R; \\ & x_5=4. \end(aligned)\right.$ Găsim soluția de bază luând variabilele libere egale cu zero, adică $x_3=0$, $x_4=0$:
$$ \left\(\begin(aligned) & x_1=-\frac(99)(5);\\ & x_2=\frac(3)(5);\\ & x_3=0;\\ & x_4= 0;\\ & x_5=4.\end(aliniat)\right.$$
Problema este rezolvată, rămâne doar să notăm răspunsul.
Răspuns: Soluție generală: $\left\(\begin(aligned) & x_1=-\frac(99)(5)-\frac(13)(5)x_3-\frac(4)(5)x_4;\\ & x_2=\frac(3)(5)+\frac(1)(5)x_3-\frac(2)(5)x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4.\end(aligned)\right.$, soluție de bază: $\left\(\begin(aligned) & x_1=-\frac(99)(5);\\ & x_2=\frac(3) (5);\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end(aliniat)\right.$.
Cu condiția să nu existe „0-rânduri” (restricții de egalitate) și variabile „libere” (adică variabile care nu sunt supuse cerinței de non-negativitate).
2. În cazul prezenței constrângerilor de egalitate și a variabilelor „libere”, procedați după cum urmează.
Selectați un element de rezolvare în „rândul 0” și efectuați un pas modificat de eliminare Jordan, după care această coloană de rezolvare este tăiată. Această secvență de acțiuni este continuată până când tabel simplex rămâne cel puțin un „rând 0” (în acest caz tabelul este redus).
Dacă există și variabile libere, atunci este necesar să facem aceste variabile de bază. Și după ce variabila liberă devine de bază, în procesul de determinare a elementului de rezolvare la căutarea planurilor de referință și optime linie dată neluat în calcul (dar convertit).
Degenerarea în problemele de programare liniară
Având în vedere metoda simplex, am presupus că problema programare liniară este nedegenerată, adică fiecare plan de referinţă conţine exact 
componente pozitive, unde 
– numărul de constrângeri în problemă. Într-un plan de suport degenerat, numărul de componente pozitive se dovedește a fi mai mic decât numărul de restricții: unele variabile de bază care corespund unui plan de suport dat iau valori zero. Folosind interpretarea geometrică pentru cel mai simplu caz, când 
(numărul de variabile nebazice este 2), este ușor să distingem o problemă degenerată de una nedegenerată. Într-o problemă degenerată, la un vârf al poliedrului de condiții se intersectează mai mult de două drepte, descrise prin ecuații de forma 
. Aceasta înseamnă că una sau mai multe laturi ale poligonului de condiție sunt contractate la un punct.
A 
impozabil când 
într-o problemă degenerată, mai mult de 3 plane se intersectează la un vârf 
.
În ipoteza că problema nu a fost degenerată, a existat o singură valoare 
, prin care s-a determinat indicele vectorului de condiții derivat din bază (derivat din numărul de variabile de bază). Într-o problemă degenerată 
poate fi realizat pe mai mulți indici deodată (pentru mai multe rânduri). În acest caz, în planul de referință găsit, mai multe variabile de bază vor fi zero.
Dacă problema de programare liniară se dovedește a fi degenerată, atunci cu o alegere proastă a vectorului de condiții derivat din bază, poate apărea o mișcare infinită de-a lungul bazelor aceluiași plan de referință. Așa-numitul fenomen de ciclism. Deși bucla este un fenomen extrem de rar în problemele practice de programare liniară, posibilitatea acestuia nu poate fi exclusă.
Una dintre metodele de combatere a degenerării este transformarea problemei prin modificarea „minică” a vectorului părților drepte ale sistemului de restricții asupra cantităților. 
, în așa fel încât problema să devină nedegenerată, și, în același timp, astfel încât această modificare să nu afecteze cu adevărat planul optim al problemei.
Algoritmii implementați mai des includ câteva reguli simple care reduc probabilitatea ca o buclă să apară sau să fie depășită.
Lasă variabila 
trebuie făcută de bază. Luați în considerare un set de indici 
, format din acelea 
, pentru care se realizează 
. O mulțime de indici 
, pentru care această condiție este îndeplinită, o notăm prin 
. Dacă 
constă dintr-un element, atunci vectorul condițiilor este exclus din bază 
(variabil 
este făcută nebază).
Dacă 
este format din mai mult de un element, apoi se formează o mulțime 
, care constă din 
, pe care se realizează 
. Dacă 
constă dintr-un singur indice 
, atunci variabila este derivată din bază 
. În caz contrar, se formează un set 
etc.
În practică, regula ar trebui utilizată dacă ciclismul a fost deja detectat.
Pentru a permite applet-ului să ruleze pe computer, trebuie să faceți următoarele - faceți clic pe Start>Panou de control>Programe>Java. În fereastra Java Panou de control selectați fila Securitate, faceți clic pe butonul Editare listă site, butonul adăugare și inserați calea către această pagină din câmpul liber bara de adresa browser. Apoi, faceți clic pe OK, apoi reporniți computerul.
Pentru a lansa appletul, faceți clic pe butonul „Simplex”. Dacă butonul „Simplex” nu este vizibil deasupra acestei linii, atunci Java nu este instalat pe computer.
După ce faceți clic pe butonul „Simplex”, apare prima fereastră pentru introducerea numărului de variabile și a numărului de constrângeri ale problemei pe metoda simplex.
După ce faceți clic pe butonul „ok”, apare o fereastră pentru introducerea datelor rămase ale sarcinii metodei simplex: modul de afișare ( zecimale sau obișnuit), tipul sarcinii criteriul min sau max, introducerea coeficienților funcției obiectiv și a coeficienților sistemului de restricții cu semnele „≤”, „≥” sau „=”, restricțiile de forma x i ≥ 0 nu fac trebuie introduse, le ia în considerare în algoritmul său.
După ce faceți clic pe butonul „Rezolvare”, apare o fereastră cu rezultatele rezolvării problemei .Fereastra este formată din două părți; în partea de sus există un câmp de text care conține o descriere a reducerii problemei inițiale la formă canonică, care este folosit pentru a compila primul tabel simplex. În partea de jos a ferestrei, într-un panou cu file, există tabele simplex ale fiecărei iterații cu un mic câmp de text mai jos indicând coloana de autorizare, rândul de autorizare și alte informații, ceea ce face programul educațional. În fila cu tabelul optim (ultimul) în câmpul de text este dat rezultatul soluție optimă sarcini.
Trimiteți orice erori pe care le observați și comentarii despre applet la: [email protected] sau sunați la 8 962 700 77 06, pentru care vă vom fi foarte recunoscători.
Program cu metoda M
Program de rezolvat problema de transport
Iată o soluție manuală (nu un applet) a două probleme folosind metoda simplex (similar cu soluția applet) cu explicatii detaliate pentru a înțelege algoritmul de rezolvare a problemelor. Prima problemă conține doar semne de inegalitate „≤” (problema cu o bază inițială), a doua poate conține semne „≥”, „≤” sau „=" (problema cu baza artificiala), sunt rezolvate diferit.
Metoda simplex, rezolvarea unei probleme cu o bază inițială
1)Metoda simplex pentru o problemă cu o bază inițială (toate semnele de constrângeri de inegalitate „ ≤ „).
Să scriem problema în canonic formă, adică rescriem restricțiile inegalității sub formă de egalități, adăugând bilanț variabile:
Acest sistem este un sistem cu o bază (baza s 1, s 2, s 3, fiecare dintre ele este inclusă într-o singură ecuație a sistemului cu un coeficient de 1), x 1 și x 2 sunt variabile libere. Problemele care trebuie rezolvate prin metoda simplex trebuie să aibă următoarele două proprietăți:
-sistemul de constrângeri trebuie să fie un sistem de ecuaţii cu bază;
-termenii liberi ai tuturor ecuatiilor din sistem trebuie sa fie nenegativi.
Sistemul rezultat este un sistem cu o bază și termenii săi liberi sunt nenegativi, deci se poate aplica metoda simplex. Să creăm primul tabel simplex (Iterația 0), adică. un tabel de coeficienți ai funcției obiectiv și un sistem de ecuații pentru variabilele corespunzătoare. Aici „BP” înseamnă coloana variabilelor de bază, „Soluție” înseamnă coloana părților din dreapta ale ecuațiilor sistemului. Soluția nu este optimă, pentru că există coeficienți negativi în rândul z.
iterația 0
BP |
Soluţie | Atitudine | |||||
Pentru a îmbunătăți soluția, trecem la următoarea iterație și obținem următorul tabel simplex. Pentru a face acest lucru, trebuie să selectați activați coloana, adică o variabilă care va fi inclusă în bază la următoarea iterație. Este selectat de cel mai mare coeficient negativ absolut din rândul z (în problema maximă) - în iterația inițială aceasta este coloana x 2 (coeficientul -6).
Apoi selectați activați șirul, adică o variabilă care va părăsi baza la următoarea iterație. Este selectat după cel mai mic raport al coloanei „Decizie” față de elementele pozitive corespunzătoare ale coloanei de rezoluție (coloana „Ratio”) - în iterația inițială acesta este rândul s 3 (coeficientul 20).
Element permisiv se află la intersecția coloanei de rezolvare și a rândului de rezolvare, celula sa este evidențiată în culoare, este egală cu 1. Prin urmare, la următoarea iterație, variabila x 2 va înlocui s 3 în bază. Rețineți că relația nu este căutată în șirul z; acolo este plasată o liniuță „-”. Dacă există relații minime identice, atunci oricare dintre ele este selectată. Dacă toți coeficienții din coloana rezoluției sunt mai mici sau egali cu 0, atunci soluția problemei este infinită.
Să completăm următorul tabel „Iterația 1”. O vom obține din tabelul „Iterație 0”. Scopul transformărilor ulterioare este de a transforma coloana de rezoluție x2 într-o coloană de unitate (cu un unu în loc de elementul de rezoluție și cu zerouri în loc de elementele rămase).
1) Calculați rândul x 2 din tabelul „Iterația 1”. În primul rând, împărțim toți membrii rândului de rezolvare s 3 din tabelul „Iterație 0” la elementul de rezolvare (este egal cu 1 în în acest caz,) din acest tabel, obținem rândul x 2 din tabelul „Iterațiile 1”. Deoarece elementul de rezolvare în acest caz este egal cu 1, apoi rândul s 3 din tabelul „Iterația 0” va coincide cu rândul x 2 din tabelul „Iterația 1”. Rândul x 2 din tabelul Iterația 1 am obținut 0 1 0 0 1 20, rândurile rămase din tabelul Iterația 1 vor fi obținute din acest rând și rândurile din tabelul Iterația 0 după cum urmează:
2) Calculul rândului z al tabelului „Iterația 1”. În locul lui -6 în primul rând (z-rând) în coloana x2 a tabelului Iterația 0, ar trebui să existe un 0 în primul rând al tabelului Iterația 1. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu 6, obținem 0 6 0 0 6 120 și adăugăm acest rând cu primul rând (z - rând) din tabelul „Iterația 0” -4 -6 0 0 0 0, obținem -4 0 0 0 6 120. În coloana x 2 apare un zero 0, scopul este atins. Elementele coloanei de rezoluție x 2 sunt evidențiate cu roșu.
3) Calculul rândului s 1 din tabelul „Iterația 1”. În loc de 1 în s 1 rând al tabelului „Iterația 0” ar trebui să existe un 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -1, obțineți 0 -1 0 0 -1 -20 și adăugați acest rând cu s 1 - rândul tabelul „Iterația 0” 2 1 1 0 0 64, obținem rândul 2 0 1 0 -1 44. În coloana x 2 obținem 0 necesar.
4) Calculați rândul s 2 din tabelul „Iterația 1”. În locul 3 în rândul s 2 al tabelului „Iterația 0” ar trebui să fie 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțiți toate elementele rândului x 2 din tabelul „Iterația 1” 0 1 0 0 1 20 cu -3, obțineți 0 -3 0 0 -3 -60 și adăugați acest rând cu s 2 - rândul tabelului „Iterația 0” 1 3 0 1 0 72, obținem rândul 1 0 0 1 -3 12. În coloana x 2 se obține 0. Coloana x 2 din tabelul „Iterația 1” a devenit o unitate , conține unul 1 și restul 0.
Rândurile tabelului „Iterația 1” se obțin conform următoarei reguli:
Linie nouă = Linie veche– (Coeficientul coloanei de rezoluție rând vechi)*(Rând de rezoluție nou).
De exemplu, pentru un șir z avem:
Vechiul z-string (-4 -6
0
0
0
0)
-(-6)*Linie de rezoluție nouă -(0-6
0
0
-6
-120)
= șir Z nou(-4
0
0
0
6
120)
.
Pentru următoarele tabele, recalcularea elementelor de tabel se face într-un mod similar, așa că o omitem.
iterația 1
| Soluţie | Atitudine | ||||||
Rezolvarea coloanei x 1, rezolvarea rândului s 2, s 2 părăsește baza, x 1 intră în bază. Exact în același mod, obținem tabelele simplex rămase până când obținem un tabel cu toți coeficienții pozitivi în rândul z. Acesta este un semn al unei mese optime.
Iterația 2
| Soluţie | Atitudine | ||||||
Rezolvând coloana s 3, rezolvând rândul s 1, s 1 părăsește baza, s 3 intră în bază.
Iterația 3
| Soluţie | Atitudine | ||||||
În rândul z, toți coeficienții sunt nenegativi, prin urmare, se obține soluția optimă x 1 = 24, x 2 = 16, z max = 192.
Metoda simplex, rezolvarea unei probleme pe bază artificială
2) Să rezolvăm problema pe o bază artificială (cel puțin un semn de constrângere de inegalitate „≥” sau „=”).
Să scriem problema în formă canonică (sub forma unui sistem de ecuații, care necesită metoda simplex), pentru a face acest lucru introducem două variabile x 3 ≥ 0 și x 4 ≥ 0, obținem:
Sistemul de restricții oferă o singură variabilă de bază admisibilă x 4, doar că este inclusă într-o singură ecuație în a treia cu coeficient de 1, deci adăugăm variabilele artificiale R 1 ≥ 0 și R 2 ≥ 0 la prima și a doua ecuație. pentru ca metoda simplex să poată fi aplicată, ecuațiile de constrângere a sistemului trebuie să fie un sistem cu o bază, i.e. în fiecare ecuație trebuie să existe o variabilă cu coeficient de 1, care este inclusă într-o singură ecuație a sistemului, în cazul nostru acestea sunt R 1, R 2 și x 4. Am primit așa-numita sarcină M:
Acest sistem este un sistem cu o bază în care R 1, R 2 și x 4 sunt variabile de bază, iar x 1, x 2 și x 3 sunt variabile libere, termenii liberi ai tuturor ecuațiilor sunt nenegativi. Prin urmare, metoda simplex poate fi folosită pentru a rezolva problema. Să notăm tabelul simplex inițial:
iterația 0
| Soluţie | Atitudine | |||||||
| -16 | ||||||||
Linia „Evaluare” a fost adăugată la tabel pentru probleme cu o bază artificială. Se obține prin însumarea coeficienților corespunzători ai rândurilor cu variabile artificiale (R) cu semnul opus. Acesta va fi prezent în tabel atâta timp cât cel puțin una dintre variabilele artificiale este în bază. Pe baza celui mai mare coeficient modulo negativ al liniei „Evaluare”, coloana de rezolvare este determinată în timp ce se află în tabel. Când rândul „Evaluare” părăsește tabelul (nu există variabile artificiale în bază), coloana de rezolvare va fi determinată de rândul z, ca în problema cu baza inițială. În acest tabel, coloana de rezolvare este x 2, este selectată pe baza celui mai mare scor negativ absolut (-7). Rândul de rezolvare R 2 este selectat pe baza celui mai mic raport dintre coloanele „Soluție” și elementele pozitive corespunzătoare ale coloanei de rezolvare, ca în problema fără variabile artificiale. Aceasta înseamnă că la următoarea iterație variabila x2 va trece de la liber la bază, iar variabila R2 va trece de la bază la liberă. Să scriem următorul tabel simplex:
Rezolvând coloana x 1, rezolvând rândul R 1, R 1 părăsește baza, x 1 intră în bază. După aceasta, nu mai există variabile artificiale în bază, deci nu există nicio linie „Evaluare” în următorul tabel:
iterația 2
| Soluţie | Atitudine | |||||||
Apoi, coloana de rezoluție este selectată de rândul z. În rândul z, toți coeficienții sunt nenegativi, cu excepția coeficientului pentru variabila artificială R 1, care nu afectează optimitatea atunci când variabilele artificiale părăsesc baza. În consecință, se obține soluția optimă x 1 = 6/5; x 2 = 3/5; z max = 72/5.
Cazuri speciale de utilizare a metodei simplex
1) Când o linie dreaptă (dacă este luată în considerare o problemă de programare liniară bidimensională, iar în caz general hiperplan) reprezentând funcția obiectiv este paralelă cu linia dreaptă (hiperplan) corespunzătoare uneia dintre constrângerile de inegalitate (care în punctul optim este satisfăcută ca o egalitate exactă) funcție obiectivă acceptă același lucru valoare optimă pe un anumit set de puncte de la limita regiunii soluţiilor fezabile. Aceste soluții se numesc soluții alternative optime. Disponibilitate solutii alternative poate fi determinată din tabelul simplex optim. Dacă rândul z al tabelului optim conține zero coeficienți ai variabilelor nebaze, atunci există soluții alternative.
2) Dacă în coloana de rezoluție a tabelului simplex toți coeficienții sunt mai mici sau egali cu zero, atunci este imposibil să selectați un rând de rezolvare, în acest caz soluția este nelimitată.
3) Dacă constrângerile unei probleme de programare liniară sunt inconsistente (adică nu pot fi satisfăcute simultan), atunci problema nu are soluții fezabile. Această situație nu poate apărea dacă toate inegalitățile care alcătuiesc sistemul de restricții sunt de tipul „≤” cu laturile drepte nenegative, deoarece în acest caz, variabilele suplimentare pot constitui o soluție fezabilă. Pentru alte tipuri de constrângeri se folosesc variabile artificiale. Dacă problema are o soluție, atunci în tabelul optim nu există variabile artificiale (R i) în bază. Dacă sunt acolo, atunci problema nu are soluții.
Dacă enunțul problemei conține restricții cu semnul ≥, atunci acestea pot fi reduse la forma ∑a ji b j prin înmulțirea ambelor părți ale inegalității cu -1. Să introducem m variabile suplimentare x n+j ≥0(j =1,m) și să transformăm restricțiile în formă de egalități
(2)
Să presupunem că toate inițiale variabilele sarcinii x 1 , x 2 ,..., x n – nebază. Atunci variabilele suplimentare vor fi de bază, iar o anumită soluție a sistemului de constrângeri are forma
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m. (3)
Deoarece în acest caz valoarea funcției obiectiv F 0 = 0, putem reprezenta F(x) după cum urmează:
F(x)=∑c i x i +F 0 =0 (4)
Tabelul simplex inițial (tabelul simplex 1) este compilat pe baza ecuațiilor (2) și (4). Dacă variabilele suplimentare x n+j sunt precedate de semnul „+”, ca în (2), atunci toți coeficienții din fața variabilelor x i și termenul liber b j sunt introduși în tabelul simplex fără modificări. La maximizarea funcției de obiectiv, coeficienții sunt introduși în rândul de jos al tabelului simplex cu semne opuse. Termenii liberi din tabelul simplex determină soluția problemei.
Algoritmul de rezolvare a problemei este următorul:
primul pas. Membrii coloanei de membri liberi sunt vizualizați. Dacă toate sunt pozitive, atunci a fost găsită o soluție de bază admisibilă și trebuie să treceți la pasul 5 al algoritmului, care corespunde găsirii soluției optime. Dacă tabelul inițial simplex are termeni liberi negativi, atunci soluția nu este validă și ar trebui să treceți la pasul 2.
al 2-lea pas. Pentru a găsi o soluție admisibilă, se efectuează și este necesar să se decidă care dintre variabilele nebazice să includă în bază și ce variabilă să se elimine din bază.
Tabelul 1.
| variabile de bază | Membri gratuiti sub restricții | Variabile non-bazice | |||||
| x 1 | x 2 | ... | x l | ... | x n|||
| x n+1 | b 1 | un 11 | un 12 | ... | un 1l | ... | un 1n |
| x n+2 | b 2 | un 21 | un 22 | ... | un 2l | ... | un 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | un r1 | un r2 | ... | un rl | ... | arn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | un m1 | un m2 | ... | un ml | ... | un mn |
| F(x)max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Pentru a face acest lucru, selectați oricare dintre elementele negative ale coloanei de termeni liberi (fie b 2 conducător sau rezolvător. Dacă nu există elemente negative în rândul cu un termen liber negativ, atunci sistemul de constrângeri este inconsecvent și problema nu are rezolvare.
În același timp, variabila care este prima care își schimbă semnul atunci când NP x l selectat crește este exclusă din BP. Acesta va fi x n+r, al cărui indice r este determinat din condiție
acestea. variabila care are cel mai mic raport dintre termenul liber și elementul coloanei principale selectate. Această relație se numește relație simplex. Trebuie luate în considerare numai relațiile simplex pozitive.
Se numește linia corespunzătoare variabilei x n+r conduce sau permite. Elementul tabelului simplex a rl, situat la intersecția rândului principal și a coloanei principale, se numește element de conducere sau de rezoluție. Găsirea elementului conducător încheie munca cu fiecare tabel simplex obișnuit.
al 3-lea pas. Se calculează un nou tabel simplex, ale cărui elemente sunt recalculate din elementele tabelului simplex pasul anteriorși sunt marcate cu un prim, adică b" j , a " ji , c " i , F" 0 . Elementele sunt recalculate folosind următoarele formule:
Mai întâi, noul tabel simplex va completa rândul și coloana care conduceau în tabelul simplex anterior. Expresia (5) înseamnă că elementul a" rl în locul elementului conducător este egal cu reciproca elementului din tabelul simplex anterior. Elementele rândului a ri sunt împărțite la elementul conducător, iar elementele coloana a jl se împarte şi la elementul conducător, dar se iau cu semnul opus. Elementele b" r şi c" l se calculează după acelaşi principiu.
Restul formulelor pot fi scrise cu ușurință folosind .
Dreptunghiul este construit conform vechiului tabel simplex în așa fel încât una dintre diagonalele sale să fie formată din elementele recalculate (a ji) și conducătoare (a rl) (Fig. 1). A doua diagonală este determinată în mod unic. Pentru a găsi un nou element a" ji, produsul dintre elementele diagonalei opuse împărțit la elementul principal este scăzut din elementul a ji (acesta este indicat de semnul „-” de lângă celulă). Elementele b" j, (j≠r) și c" i sunt recalculate în același mod. (i≠l).
al 4-lea pas. Analiza noului tabel simplex începe cu primul pas al algoritmului. Acțiunea continuă până când se găsește o soluție de bază fezabilă, de ex. toate elementele coloanei flotante trebuie să fie pozitive.
al 5-lea pas. Considerăm că a fost găsită o soluție de bază admisibilă. Ne uităm la coeficienții dreptei funcției obiectiv F(x) . Un semn al optimității unui tabel simplex este nenegativitatea coeficienților pentru variabilele nebazice din rândul F.
Orez. 1. Regula dreptunghiulară
Dacă printre coeficienții rândului F există și negativi (cu excepția termenului liber), atunci trebuie să treceți la o altă soluție de bază. La maximizarea funcției obiectiv, baza include una dintre variabilele nebaze (de exemplu x l), a cărei coloană corespunde valorii absolute maxime a coeficientului negativ c l din rândul de jos al tabelului simplex. Acest lucru vă permite să selectați variabila a cărei creștere duce la o îmbunătățire a funcției de obiectiv. Coloana corespunzătoare variabilei x l se numește coloană principală. În același timp, acea variabilă x n+r este exclusă din bază, al cărei indice r este determinat de relația simplex minimă:
Rândul corespunzător lui x n+r se numește lider, iar elementul tabelului simplex a rl, care se află la intersecția rândului principal și coloanei principale, se numește element conducător.
al 6-lea pas. conform regulilor prezentate la pasul 3. Procedura continuă până când se găsește o soluție optimă sau se ajunge la concluzia că aceasta nu există.
În timpul optimizării soluției, dacă toate elementele din coloana principală sunt nepozitive, atunci rândul principal nu poate fi selectat. În acest caz, funcția din regiunea soluțiilor fezabile ale problemei nu este mărginită mai sus și F max ->&∞.
Dacă, la următorul pas de căutare a unui extremum, una dintre variabilele de bază devine egală cu zero, atunci soluția de bază corespunzătoare se numește degenerată. În acest caz, apare o așa-numită buclă, caracterizată prin faptul că o anumită frecvență aceeași combinație de BP începe să se repete (se păstrează valoarea funcției F) și este imposibil să treci la o nouă soluție de bază admisibilă. Loopingul este unul dintre principalele dezavantaje ale metodei simplex, dar este relativ rar. În practică, în astfel de cazuri, de obicei refuză să introducă în bază variabila a cărei coloană corespunde valorii absolute maxime a coeficientului negativ din funcția de obiectiv și selectează aleatoriu o nouă soluție de bază.
Exemplul 1. Rezolvați problema
max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)
Folosind metoda simplex și dați o interpretare geometrică a procesului de rezolvare.
O interpretare grafică a soluției problemei este prezentată în Fig. 2. Valoarea maximă a funcției obiectiv se realizează la vârful ODZP cu coordonatele . Să rezolvăm problema folosind tabele simplex. Să înmulțim a doua constrângere cu (-1) și să introducem variabile suplimentare pentru a aduce inegalitățile sub formă de egalități, apoi
Luăm variabilele inițiale x 1 și x 2 ca nebaze și considerăm x 3, x 4 și x 5 suplimentare ca fiind de bază și compunem un tabel simplex (tabelul simplex 2). Soluția corespunzătoare tabelului simplex. 2, nu este valabil; elementul conducător este conturat și selectat în conformitate cu pasul 2 al algoritmului anterior. Următorul tabel simplex. 3 definește o soluție de bază admisibilă, vârful ODZP din Fig. 1 îi corespunde. 2 Elementul de conducere este conturat și selectat în conformitate cu pasul 5 al algoritmului de rezolvare a problemelor. Masa 4 corespunde soluției optime a problemei, deci: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Orez. 2. Soluție grafică sarcini
Citeste si:
|
Teorema (despre alegerea unui element de rezolvare)
Dacă mai multe coloane ale rândului z au elemente negative, atunci coloana de rezolvare trebuie aleasă să fie coloana cu produsul maxim valoare absolută coeficientul în rândul z și raportul simplex minim această coloană.
Dovada:
Fie elementul elementul care permite. Ca rezultat al pasului de eliminare Jordan modificat, termenul liber din rândul z va fi numărul egal cu . Deoarece și , paranteza din această expresie va fi întotdeauna pozitivă. Și întrucât valoarea funcționalului este întotdeauna egală cu termenul liber, această paranteză reprezintă adunarea la funcțional care se obține ca urmare a pasului făcut.
Cu cât este mai mare creșterea pe care o primește funcționalitatea la fiecare pas, cu atât mai puțini pași (adică, calcule) vor fi necesari pentru a atinge optimul. Mărimea acestui increment depinde de valoarea absolută a coeficientului și de valoarea celui mai mic raport simplex. Adică, coloana de rezolvare va fi coloana care are maximul acestui produs.
Exemplu: programare liniară:
Să găsim maximul funcției
sub restricții
Soluție: Să creăm un tabel Jordan.
Deoarece membrii săi liberi sunt pozitivi, planul este unul de susținere. Cu toate acestea, nu este optim deoarece coeficienții rândului z sunt negativi. Alegem dintre ele pe cel cu cel mai mare produs de valoare absolută și cel mai mic raport simplex. A treia coloană este considerată rezolvată, deoarece are cea mai mare valoare absolută 8 și relații simplex: respectiv ( , deci elementul 1 din coloana a treia se va rezolva). Facem pasul de eliminare Jordan modificat și ajungem la următorul tabel.
Judecând după coeficienții rândului z, tabelul rezultat nu a obținut soluția optimă. Luăm a doua coloană cu un coeficient negativ în rândul z ca coloană de rezoluție (doar prima poate fi rândul de rezolvare). Cu elementul 5 găsit, facem următorul pas.
În rândul z, toți coeficienții sunt pozitivi; proiectul obținut prin echivalarea variabilelor superioare la zero și a variabilelor laterale la termeni liberi este optim. Scriem valorile principalelor necunoscute din tabel: calculăm valoarea maximă a funcționalului în ultima celulă a tabelului:
În tabelul final, toți determinanții sunt nenegativi. Acest lucru sugerează că pentru valori necunoscute funcționalitatea atinge un maxim
De obicei, se presupune că nu există puncte în setul de planuri probleme la care numitorul funcției obiectiv să fie egal cu zero. Fără a pierde generalitatea, putem presupune că .
Într-o problemă de programare liniară fracțională, extremul funcției obiectiv este realizat la vârful poliedrului soluție. Această asemănare cu programarea liniară permite rezolvarea problemelor liniare fracționale folosind metoda Stiefel.
Calculele sunt prezentate sub formă de tabele Jordan. În acest caz, două linii inferioare sunt alocate pentru funcțional: în prima dintre ele scriem coeficienții numărătorului, iar în a doua - numitorul. Sarcina originală corespunde tabelului 1:
| –X 1 | –X 2 | … | –x j | … | –x n | ||
| y 1 | A 11 | A 12 | … | A 1 j | … | A 1 n | A 1 |
| … | ……………………………………… | … | |||||
| y eu | un i 1 | un i 2 | … | a ij | … | a in | un i |
| … | ……………………………………… | … | |||||
| y m | a m 1 | a m 2 | … | un mj | … | un mn | a m |
| z 1 | –p 1 | –p 2 | … | –pijamale | … | –p n | |
| z 2 | –q 1 | –q 2 | … | –q j | … | –qn |
Prin y eu diferențele dintre părțile din dreapta și din stânga ale sistemului de restricții sunt indicate:
y eu= un i–un i 1 X 1 – un i 2 X 2 –un i 3 X 3 – … – a în x n ³ 0.
Vom numi variabile libere variabilele situate în rândul superior de titlu al tabelului Jordan. Oferirea de variabile libere valori zero, obținem soluția de bază originală: . Acest vector nu poate fi un plan de referință, deoarece numitorul obiectivului funcțional de pe acesta este egal cu zero ( z 2 = 0). Prin urmare, printre membrii liberi ai sistemului de restricții A 1 ,…, a m cu siguranta au numere negative(în caz contrar, soluția de bază ar fi planul de referință).
Prin pași de eliminări Jordan modificate, în același mod ca la rezolvarea unei probleme de programare liniară (vezi), găsim planul original al problemei. Ca urmare k pașii ajungem la tabelul 2:
| –y 1 | … | –x j | … | –x n | ||
| X 1 | b 11 | … | b 1 j | … | b 1 n | b 1 |
| .… | ……………………………………… | |||||
| y eu | b i 1 | … | b ij | … | cos | b i |
| …. | ……………………………………. | |||||
| y m | b m 1 | … | b mj | … | b mn | b m |
| z 1 | f 1 | … | f j | … | fn | F |
| z 2 | g 1 | … | g j | … | g n | G |
În tabelul 2 toți membrii liberi b i sunt nenegative, ceea ce asigură nenegativitatea variabilelor de bază X 1 ,…, y m. În plus (datorită numitorului pozitiv al funcției obiectiv z 2 pe un set de planuri de referință). Planul de referință inițial este un vector cu coordonate. Valoarea funcției obiectiv pe planul de referință inițial este de .
Rețineți că, dacă la unul dintre pașii de eliminare Jordan, vreunul dintre termenii gratuiti b voi fi negativ și toate celelalte elemente i randurile vor fi nenegative, atunci problema nu va avea o solutie din lipsa planurilor.
Să vedem cum se schimbă funcția obiectiv la trecerea de la un plan de referință al problemei la altul. Se pare că semnul diferenței dintre noile și vechile valori ale funcției coincide cu semnul determinantului. Dacă. Deoarece Deoarece poliedrul soluție conține doar un număr finit de planuri de sprijin, atunci într-un număr finit de pași vom ajunge la planul de sprijin optim.
Acest proces poate fi împiedicat doar de nelimitarea poliedrului de soluții. În acest caz, funcția obiectiv poate avea un așa-numit extremum asimptotic (în acest caz, un maxim). Maximul asimptotic al unei probleme de programare liniară fracțională este limita superioară exactă a funcției obiectiv pe un set de planuri, care nu este atinsă pe niciunul dintre planuri. În cazul în care problema are un maxim asimptotic, în zona planurilor este întotdeauna posibil să se găsească un plan (nu unul de referință) pe care funcția obiectiv ia o valoare arbitrar apropiată de maximul asimptotic.
Metoda Stiefel vă permite să găsiți nu numai maximul, ci și maximul asimptotic al unei probleme de programare liniară fracțională. Să aruncăm o privire mai atentă asupra tranziției de la plan la plan și să aflăm. Selectarea elementului de rezolvare în j coloana, trebuie să ne ghidăm după principiul relației simplex minime. Acestea. element de activare în j Coloana --a trebuie să fie în rândul pentru care relația simplex este pozitivă și minimă.
Deoarece după găsirea planului de referință inițial, toate părțile din dreapta b i devin nenegative, apoi elementul de rezolvare j Coloana a treia poate fi unul dintre elementele sale pozitive (). Dacă la fiecare pas al etapei de căutare a planului de referință optim există (cel puțin un) element pozitiv în coloana de rezoluție selectată, atunci o astfel de problemă are maximum (eventual mai mult de unul).
Cu toate acestea, dacă la unul dintre pași, o estimare este mai mică decât zero și toate elementele j a coloana. Apoi, în această coloană, ghidată de principiul relației simplex minime, elementul de rezolvare nu poate fi selectat. Creșterea valorilor variabilei libere x j de la 0 la (vezi Tabelul 2), rămânem tot timpul în zona planurilor. Acest lucru se datorează faptului că o creștere a variabilei x j nu provoacă o schimbare a semnului în minus pentru oricare dintre variabilele de bază.
Să notăm prin M limita spre care, crescând monoton, funcţia obiectiv tinde la: . Acest număr este maximul asimptotic.
| 2 |
