Iată o rezolvare manuală (nu applet) a două probleme prin metoda simplex (asemănătoare soluției applet) cu explicații detaliate pentru a înțelege algoritmul de rezolvare a problemelor cu metoda simplex. Prima problemă conține doar semne de inegalitate " ≤ " (o problemă cu o bază inițială), a doua poate conține semne " ≥ ", " ≤ " sau " = " (o problemă cu o bază artificială), acestea sunt rezolvate în diferite moduri. moduri.
Metoda simplex, rezolvarea unei probleme cu o bază inițială
1)Metoda simplex pentru o problemă cu o bază inițială (toate semnele inegalităților de constrângere sunt „≤”).
Să scriem problema în canonic formă, adică rescriem constrângerile de inegalitate ca egalități, adăugând bilanţuri 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 pentru care se foloseşte 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, așa că putem aplica metoda simplex. Compilați primul tabel simplex (Iterația 0) pentru a rezolva problema metoda simplex, 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” - coloana părților din dreapta ale ecuațiilor sistemului. Soluția nu este optimă, pentru că există coeficienți negativi în linia z.
iterația metodei simplex 0
|
Atitudine |
|||||||
Pentru a îmbunătăți soluția, să trecem la următoarea iterație metoda simplex, obținem următorul tablou simplex. Pentru asta trebuie să alegi activați coloana, adică o variabilă care va intra în bază la următoarea iterație a metodei simplex. Este ales de cel mai mare coeficient negativ din rândul z (în problema maximă) - în iterația inițială a metodei simplex, aceasta este coloana x 2 (coeficient -6).
Atunci alege șir de permisiuni, adică o variabilă care va lăsa baza la următoarea iterație a metodei simplex. Este selectat după cel mai mic raport al coloanei „Decizie” la elementele pozitive corespunzătoare ale coloanei de rezolvare (coloana „Ratio”) - în iterația inițială, acesta este rândul s 3 (coeficientul 20).
Element permisiv este situat 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 a metodei simplex, variabila x 2 va înlocui s 1 în bază. Rețineți că relația nu este căutată în șirul z, acolo este pusă o liniuță „-”. Dacă există rapoarte minime identice, atunci se alege oricare dintre ele. 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 activare x2 într-o singură coloană (cu unul în loc de elementul de activare și zerouri în loc de restul elementelor).
1) Calcularea rândului 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ția 0” la elementul de rezolvare (în acest caz este egal cu 1) din acest tabel, obținem rândul x 2 din tabelul „Iterația 1” . pentru că elementul de rezolvare în acest caz este egal cu 1, atunci rândul s 3 din tabelul „Iterația 0” se va potrivi 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 tabelului „Iterația 0” după cum urmează:
2) Calculul rândului z al tabelului „Iterația 1”. În locul lui -6 în primul rând (rând z) î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țim 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 a apărut zero 0, scopul a fost atins. Elementele coloanei de permisiuni 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 din tabelul „Iterația 0” ar trebui să fie 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul "Iterația 1" 0 1 0 0 1 20 cu -1, obținem 0 -1 0 0 -1 -20 și adăugăm acest rând cu s 1 - rândul tabelului „Iterația 0” 2 1 1 0 0 64, obținem rândul 2 0 1 0 -1 44. 0 necesar se obține în coloana x 2.
4) Calculul rândului s 2 din tabelul „Iterația 1”. În loc de 3 în rândul s 2 din tabelul „Iterația 0” ar trebui să fie 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul "Iterația 1" 0 1 0 0 1 20 cu -3, obținem 0 -3 0 0 -3 -60 și adăugăm acest rând cu s 1 - rândul tabelului „Iterația 0” 1 3 0 1 0 72, obținem rândul 1 0 0 1 -3 12. 0 necesar se obține în coloana x 2. Coloana x 2 din tabelul „Iterația 1” are devin singur, conține unul 1 și restul 0.
Rândurile tabelului „Iterația 1” sunt obținute conform următoarei reguli:
Rând nou = Rând vechi - (Factor de permisiune pentru rând vechi)*(Rând nou).
De exemplu, pentru linia z avem:
Vechi șir z (-4 -6 0 0 0 0) -(-6)*Nou z-șir -(0 -6 0 0 -6 -120) = Nou z-șir (-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 metodei simplex 1
|
Atitudine |
|||||||
Coloana permisivă x 1 , rândul permisiv 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 se obține un tabel cu toți coeficienții pozitivi din rândul z. Acesta este un semn al unei mese optime.
iterația metodei simplex 2
|
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 metodei simplex 3
|
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.
Pentru a permite rularea applet-ului pe computer, faceți următoarele - faceți clic pe Start>Panou de control>Programe>Java. În fereastra Panoului de control Java, selectați fila Securitate, faceți clic pe butonul Editare listă site-uri, butonul de adăugare și inserați calea către această pagină din bara de adrese a browserului în câmpul liber. Apoi, apăsați butonul OK, apoi reporniți computerul.
Pentru a rula appletul, faceți clic pe butonul „Simplex”. Dacă butonul „Simplex” nu este vizibil deasupra acestei linii, Java nu este instalat pe computer.
După ce faceți clic pe butonul „Simplex”, se afișează prima fereastră pentru introducerea numărului de variabile și a numărului de restricții ale problemei pe metoda simplex.
După apăsarea butonului „ok”, se afișează o fereastră pentru introducerea restului datelor sarcinii pentru metoda simplex: modul de afișare ( zecimale sau obișnuit), tip de sarcină criteriu min sau max , introducerea coeficienților funcției obiectiv și a coeficienților sistemului de constrângeri cu semnele „≤”, „≥” sau „=”, restricțiile de forma х i ≥ 0 nu necesită a fi introdus, le ia în considerare în algoritm.
După ce faceți clic pe butonul „Rezolvare”, se afișează o fereastră cu rezultatele rezolvării problemei .Fereastra este formată din două părți, în partea superioară există un câmp de text care conține o descriere a reducerii problemei inițiale la forma 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 în partea de jos care indică coloana de activare, rândul de activare și alte informații care fac programul educațional. În fila cu tabelul optim (ultimul), soluția optimă obținută a problemei este afișată în câmpul de text.
Vă rugăm să trimiteți orice erori și comentarii despre applet către [email protected] sau sunați la 8 962 700 77 06, pentru care vă vom fi foarte recunoscători.
Program cu metoda M
Program pentru rezolvarea problemei transportului
Iată o soluție manuală (nu applet) a două probleme prin metoda simplex (asemănătoare soluției applet) cu explicații detaliate pentru a înțelege algoritmul de rezolvare a problemelor. Prima problemă conține doar semne de inegalitate " ≤ " (o problemă cu o bază inițială), a doua poate conține semne " ≥ ", " ≤ " sau " = " (o problemă cu o bază artificială), acestea sunt rezolvate în diferite moduri. moduri.
Metoda simplex, rezolvarea unei probleme cu o bază inițială
1)Metoda simplex pentru o problemă cu o bază inițială (toate semnele inegalităților de constrângere sunt „≤”).
Să scriem problema în canonic formă, adică rescriem constrângerile de inegalitate ca egalități, adăugând bilanţuri 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 pentru care se folosește metoda simplex trebuie să aibă următoarele două proprietăți:
-sistemul de constrângeri trebuie să fie un sistem de ecuaţii cu o 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. Compilați 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” - coloana părților din dreapta ale ecuațiilor sistemului. Soluția nu este optimă, pentru că există coeficienți negativi în linia 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 asta trebuie să alegi activați coloana, adică o variabilă care va intra în bază la următoarea iterație. Este selectat de cel mai mare coeficient negativ din rândul z (în problema maximă) - în iterația inițială, aceasta este coloana x 2 (coeficient -6).
Atunci alege șir de permisiuni, adică o variabilă care va părăsi baza la următoarea iterație. Este selectat după cel mai mic raport al coloanei „Decizie” la elementele pozitive corespunzătoare ale coloanei de rezolvare (coloana „Ratio”) - în iterația inițială, acesta este rândul s 3 (coeficientul 20).
Element permisiv este situat la intersecția coloanei de rezolvare și a rândului de rezoluție, 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 pusă o liniuță „-”. Dacă există rapoarte minime identice, atunci se alege oricare dintre ele. 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 activare x2 într-o singură coloană (cu unul în loc de elementul de activare și zerouri în loc de restul elementelor).
1) Calcularea rândului 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ția 0” la elementul de rezolvare (în acest caz este egal cu 1) din acest tabel, obținem rândul x 2 din tabelul „Iterația 1” . pentru că elementul de rezolvare în acest caz este egal cu 1, atunci rândul s 3 din tabelul „Iterația 0” se va potrivi 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 tabelului „Iterația 0” după cum urmează:
2) Calculul rândului z al tabelului „Iterația 1”. În locul lui -6 în primul rând (rând z) î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țim 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 a apărut zero 0, scopul a fost atins. Elementele coloanei de permisiuni 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 din tabelul „Iterația 0” ar trebui să fie 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul "Iterația 1" 0 1 0 0 1 20 cu -1, obținem 0 -1 0 0 -1 -20 și adăugăm acest rând cu s 1 - rândul tabelului „Iterația 0” 2 1 1 0 0 64, obținem rândul 2 0 1 0 -1 44. 0 necesar se obține în coloana x 2.
4) Calculul rândului s 2 din tabelul „Iterația 1”. În loc de 3 în rândul s 2 din tabelul „Iterația 0” ar trebui să fie 0 în tabelul „Iterația 1”. Pentru a face acest lucru, înmulțim toate elementele rândului x 2 din tabelul "Iterația 1" 0 1 0 0 1 20 cu -3, obținem 0 -3 0 0 -3 -60 și adăugăm 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. 0 necesar se obține în coloana x 2. Coloana x 2 din tabelul „Iterația 1” are devin singur, conține unul 1 și restul 0.
Rândurile tabelului „Iterația 1” sunt obținute conform următoarei reguli:
Rând nou = Rând vechi - (Factor de permisiune pentru rând vechi)*(Rând nou).
De exemplu, pentru linia z avem:
Vechiul z-string (-4 -6
0
0
0
0)
-(-6)*Șir de permisiuni nou -(0-6
0
0
-6
-120)
= Rând 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 | ||||||
Coloana permisivă x 1 , rândul permisiv 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 se obține un tabel cu toți coeficienții pozitivi din 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 bază artificială (cel puțin un semn de inegalități-restricții " ≥ " sau " = ").
Scriem problema în formă canonică (sub forma unui sistem de ecuații, care necesită metoda simplex), pentru aceasta introducem două variabile x 3 ≥ 0 și x 4 ≥ 0, obținem:
Sistemul de constrângeri oferă o singură variabilă de bază validă x 4 , doar că este inclusă într-o singură ecuație din 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 Deci că metoda simplex poate fi aplicată ecuațiile de constrângere de sistem 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 este R 1, R 2 și x 4. Avem așa-numita problemă 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 aplicată pentru a rezolva problema. Să scriem 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ă. Prin valoarea absolută a coeficientului negativ al rândului „Evaluare”, coloana rezoluției este determinată în timp ce se află în tabel. Când rândul „Scor” 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ă în funcție de cea mai mare estimare negativă (-7). Rândul de rezolvare R 2 este ales în funcție de cel mai mic raport al coloanei „Soluție” la elementele pozitive corespunzătoare ale coloanei de rezolvare, ca în problema fără variabile artificiale. Aceasta înseamnă că la următoarea iterație variabila x 2 va trece de la liber la bază, iar variabila R2 de la bază la liberă. 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ă aceea, nu mai există variabile artificiale în bază, deci nu există un rând „Scor” î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 la variabila artificială R1, care nu afectează optimitatea atunci când variabilele artificiale sunt în afara bazei. Prin urmare, se obține soluția optimă x 1 = 6/5; x 2 \u003d 3/5; zmax = 72/5.
Cazuri speciale de aplicare a metodei simplex
1) Când linia (dacă se consideră o problemă de programare liniară bidimensională, și în cazul general un hiperplan) care reprezintă funcția obiectiv este paralelă cu dreapta (hiperplanul) corespunzătoare uneia dintre inegalitățile de constrângere (care este îndeplinită la punct optim ca egalitate exactă), funcția obiectiv ia unul și de asemenea valoare optimă pe un set de puncte de la limita regiunii soluţiilor fezabile. Aceste soluții se numesc soluții alternative optime. Prezența soluțiilor alternative poate fi determinată din tabelul simplex optim. Dacă există zero coeficienți ai variabilelor nebaze în rândul z al tabelului optim, 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ă alegeți rândul de rezolvare, în acest caz soluția este nelimitată.
3) Dacă constrângerile unei probleme de programare liniară sunt inconsecvente (adică nu pot fi executate simultan), atunci problema nu are soluții fezabile. O astfel de situație nu poate apărea dacă toate inegalitățile care alcătuiesc sistemul de constrângeri sunt de tip „≤” cu laturile drepte nenegative, deoarece în acest caz, variabilele suplimentare pot constitui o soluție validă. Pentru alte tipuri de constrângeri se folosesc variabile artificiale. Dacă problema are o soluție, atunci nu există variabile artificiale (R i) în tabelul optim din bază. Dacă sunt acolo, atunci problema nu are soluții.
11.4. METODA DUAL SIMPLEX
Din rezultatele subsecțiunilor anterioare rezultă că, pentru a obține o soluție la problema inițială, se poate trece la problema duală și, folosind estimări ale designului optim al acesteia, se poate determina soluția optimă a problemei inițiale.
Trecerea la problema duală nu este necesară, deoarece dacă luăm în considerare primul tablou simplex cu o bază suplimentară de unitate, atunci este ușor de observat că coloanele conțin problema inițială, iar problema duală este scrisă în rânduri.
După cum sa arătat, la rezolvarea problemei directe la orice iterație, diferența, adică magnitudinea -coeficient cu o variabilă, este egală cu diferența dintre partea dreaptă și stângă a constrângerii corespunzătoare problemei duale. Dacă, la rezolvarea unei probleme directe cu o funcție obiectiv maximizabilă, iterația nu conduce la o soluție optimă, atunci pentru cel puțin o variabilă și numai în optim pentru toate diferență .
Având în vedere această condiție cu dualitate luată în considerare, putem scrie
.
Astfel, dacă, apoi . Aceasta înseamnă că atunci când soluția problemei primare nu este optimă, soluția problemei duale este invalidă. Pe de altă parte 
la . Aceasta implică că soluția optimă a problemei primare corespunde unei soluții admisibile a problemei duale.
Acest lucru a făcut posibilă dezvoltarea unei noi metode de rezolvare a problemelor de programare liniară, atunci când se utilizează, la început, o soluție inacceptabilă, dar „mai bună decât optimă” (în metoda simplex obișnuită, mai întâi admisibilă, dar suboptimal soluţie). O nouă metodă numită metoda dual simplex, asigură îndeplinirea condiției de optimitate a soluției și „aproximarea” sistematică a acesteia la zona soluțiilor fezabile. Când soluția obținută se dovedește a fi admisibilă, procesul iterativ de calcule se încheie, deoarece această soluție este și ea optimă.
Metoda dual simplex permite rezolvarea problemelor de programare liniară ale căror sisteme de constrângeri, cu bază pozitivă, conțin termeni liberi de orice semn. Această metodă face posibilă reducerea numărului de transformări ale sistemului de constrângeri, precum și dimensiunea tabelului simplex. Luați în considerare aplicarea metodei dual simplex folosind un exemplu.
Exemplu. Găsiți minimul unei funcții 
sub restricții
.
Să trecem la forma canonică:
sub restricții
Tabloul simplex inițial are forma
|
De bază variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
Soluţie |
|
X 3 X 4 X 5 |
–3 –4 |
–1 –3 |
–3 –6 |
|||
|
–2 |
–1 |
Soluție de bază inițialăoptim, dar inacceptabil.
La fel ca metoda simplex obișnuită, metoda de soluționare luată în considerare se bazează pe utilizarea condițiilor de admisibilitate și optimitate.
Condiție de admisibilitate. Ca variabilă exclusă este aleasă cea mai mare variabilă de bază negativă în valoare absolută (dacă există alternative, alegerea se face în mod arbitrar). Dacă toate variabilele de bază sunt nenegative, procesul de calcul se încheie, deoarece soluția rezultată este fezabilă și optimă.
Condiție optimitatea. Variabila inclusă în bază este selectată dintre variabilele care nu sunt de bază, după cum urmează. Se calculează rapoartele coeficienților din stânga-ecuaţii la coeficienţii corespunzători ai ecuaţiei asociate cu variabila exclusă. Nu se iau în considerare relațiile cu numitori pozitivi sau zero. În problema minimizării variabilei de intrare trebuie să corespundă cel mai mic dintre rapoartele indicate, iar în problema maximizării, raportul cu cea mai mică valoare absolută (dacă există alternative, alegerea se face arbitrar). Dacă numitorii tuturor rapoartelor sunt zero sau pozitivi, problema nu are soluții fezabile.
După alegerea variabilelor care urmează să fie incluse în bază și să fie excluse, se efectuează operația obișnuită de transformare a rândurilor tabelului simplex pentru a obține următoarea soluție.
În acest exemplu, variabila exclusă este. Rapoartele calculate pentru a determina noua variabilă de bază sunt prezentate în următorul tabel:
|
Variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
Ecuația X 4 - ecuație |
–2 –4 |
–1 –3 |
|||
|
Atitudine |
Variabila care trebuie inclusă este X 2. Conversia ulterioară a șirurilor are ca rezultat un nou tabel simplex:
|
De bază variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
Soluţie |
|
X 3 X 2 X 5 |
–1 –1 |
|||||
Soluție nouă de asemenea optim, dar încă invalid. Ca o nouă variabilă exclusă, alegem (arbitrar) X 3 . Să definim o variabilă inclusă.
|
Variabile |
X 1 |
X 2 |
X 3 |
X 4 |
X 5 |
|
Ecuația X 4 - ecuație |
|||||
|
atitudine |
Dacă trebuie să rezolvați o problemă de programare liniară folosind tabele simplex, atunci serviciul nostru online vă va fi de mare ajutor. Metoda simplex implică o enumerare secvențială a tuturor vârfurilor regiunii valorilor admisibile pentru a găsi vârful în care funcția ia o valoare extremă. În prima etapă, se găsește o soluție, care se îmbunătățește la fiecare pas ulterior. O astfel de soluție se numește de bază. Iată o secvență de acțiuni atunci când rezolvați o problemă de programare liniară folosind metoda simplex:
Primul pas. În tabelul compilat, în primul rând, trebuie să vă uitați la coloana cu membri liberi. Dacă conține elemente negative, atunci este necesar să treceți la a doua etapă, dacă nu, atunci la a cincea.
Al doilea pas. La al doilea pas, este necesar să se decidă ce variabilă să se excludă din bază și pe care să o includă pentru a recalcula tabelul simplex. Pentru a face acest lucru, ne uităm la coloana cu membri liberi și găsim un element negativ în ea. O linie cu un element negativ va fi numită cea de conducere. În el găsim elementul negativ maxim în valoare absolută, coloana corespunzătoare acestuia fiind adeptul. Dacă există valori negative printre membrii liberi, dar nu în rândul corespunzător, atunci un astfel de tabel nu va avea soluții. Variabila din rândul principal, care se află în coloana de membri liberi, este exclusă din bază, iar variabila corespunzătoare coloanei principale este inclusă în bază.
Tabelul 1.
| variabile de bază | Membri gratuiti în restricții | Variabile nebazice | |||||
| x 1 | x2 | ... | x l | ... | x n | ||
| xn+1 | b 1 | un 11 | un 12 | ... | un 1l | ... | un 1n |
| xn+2 | b 2 | un 21 | un 22 | ... | un 2l | ... | un 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+r | b2 | un r1 | un r2 | ... | un rl | ... | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| xn+m | b m | un m1 | un m2 | ... | un ml | ... | amn |
| F(x)max | F0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Al treilea pas. La al treilea pas, recalculăm întregul tabel simplex folosind formule speciale, aceste formule pot fi văzute folosind .
Al patrulea pas. Dacă, după recalculare, elemente negative rămân în coloana de membri liberi, atunci treceți la primul pas, dacă nu există, atunci treceți la al cincilea.
Al cincilea pas. Dacă ați ajuns la al cincilea pas, atunci ați găsit o soluție acceptabilă. Cu toate acestea, acest lucru nu înseamnă că este optim. Va fi optim numai dacă toate elementele din rândul F sunt pozitive. Dacă nu este cazul, atunci este necesară îmbunătățirea soluției, pentru care găsim rândul și coloana de început pentru următoarea recalculare conform următorului algoritm. Inițial, găsim numărul minim negativ în rândul F, excluzând valoarea funcției. Coloana cu acest număr va fi prima. Pentru a găsi rândul de început, găsim raportul dintre membrul liber corespunzător și elementul din coloana principală, cu condiția ca acestea să fie pozitive. Raportul minim va determina linia de conducere. Recalculam tabelul conform formulelor, i.e. treceți la pasul 3.
Se are în vedere un exemplu de rezolvare a problemei prin metoda simplex, precum și un exemplu de rezolvare a problemei duale.
ConţinutSarcina
Pentru implementarea a trei grupe de bunuri, o întreprindere comercială dispune de trei tipuri de resurse materiale și monetare limitate în valoare de b 1 = 240, b 2 = 200, b 3 = 160 de unități. În același timp, pentru vânzarea unui grup de mărfuri pentru 1 mie de ruble. cifra de afaceri, o resursă de primul tip este consumată în valoare de 11 = 2 unități, o resursă de al doilea tip în valoare de 21 = 4 unități, o resursă de al treilea tip în valoare de 31 = 4 unitati. Pentru vânzarea a 2 și 3 grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri este cheltuită, respectiv, resursa de primul tip în valoare de a 12 = 3, a 13 = 6 unități, resursa de al doilea tip în valoare de a 22 = 2, a 23 = 4 unități, resursa de al treilea tip în valoare de a 32 = 6, a 33 = 8 unități . Profit din vânzarea a trei grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri este, respectiv, c 1 \u003d 4, c 2 \u003d 5, c 3 \u003d 4 (mii de ruble). Determinați volumul planificat și structura cifrei de afaceri comerciale astfel încât profitul întreprinderii comerciale să fie maximizat.
La problema directă a planificării circulației mărfurilor, metoda simplex rezolvabilă, Compune dubla problema programare liniară.
Instalare perechi conjugate de variabile probleme directe și duale.
După perechi conjugate de variabile, din rezolvarea problemei directe, se obține soluție dublă a problemei, in care estimarea resurselor cheltuită pentru vânzarea de bunuri.
Rezolvarea problemei simplex prin metoda
Fie x 1, x 2, x 3 - numărul de mărfuri vândute, în mii de ruble, 1, 2, respectiv 3 grupuri. Atunci modelul matematic al problemei are forma:F = 4 x 1 + 5 x 2 + 4 x 3 ->max
0)))(~)" title="(!LANG:delim(lbrace)(matrice(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
Rezolvăm simplexul prin metoda.
Introducem variabile suplimentare x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 pentru a converti inegalitățile în egalități.
Ca bază, luăm x 4 \u003d 240; x5 = 200; x6 = 160.
Datele sunt introduse tabel simplex
Tabelul Simplex numărul 1
Funcția țintă:
0 240 + 0 200 + 0 160 = 0
Calculăm scorurile după formula:
Δ 1 \u003d 0 2 + 0 4 + 0 4 - 4 \u003d - 4
Δ 2 \u003d 0 3 + 0 2 + 0 6 - 5 \u003d - 5
Δ 3 \u003d 0 6 + 0 4 + 0 8 - 4 \u003d - 4
Δ 4 \u003d 0 1 + 0 0 + 0 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 0 0 - 0 \u003d 0
Δ 6 \u003d 0 0 + 0 0 + 0 1 - 0 \u003d 0
Deoarece există estimări negative, planul nu este optim. Evaluare cea mai mică:
Introducem variabila x 2 în bază.
Definim o variabilă care părăsește baza. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x 2 .
= 26.667
Cel mai mic nenegativ: Q 3 = 26,667. Deducem variabila x 6 din bază
Împărțiți linia 3 la 6.
Din primul rând scădeți al treilea rând înmulțit cu 3
Din al 2-lea rând scădeți al 3-lea rând înmulțit cu 2
Calculam:
Primim un nou tabel:
Tabelul Simplex numărul 2
Funcția țintă:
0 160 + 0 440/3 + 5 80/3 = 400/3
Calculăm scorurile după formula:
Δ 1 \u003d 0 0 + 0 8/3 + 5 2/3 - 4 \u003d - 2/3
Δ 2 \u003d 0 0 + 0 0 + 5 1 - 5 \u003d 0
Δ 3 \u003d 0 2 + 0 4/3 + 5 4/3 - 4 \u003d 8/3
Δ 4 \u003d 0 1 + 0 0 + 5 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 5 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) / 3 + 5 1/6 - 0 \u003d 5/6
Deoarece există o estimare negativă Δ 1 = - 2/3, planul nu este optim.
Introducem variabila x 1 în bază.
Definim o variabilă care părăsește baza. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x 1 .
Cel mai mic nenegativ: Q 3 \u003d 40. Deducem variabila x 2 din bază
Împărțiți al 3-lea rând la 2/3.
Din al 2-lea rând scădeți al 3-lea rând înmulțit cu 8/3
Calculam:
Primim un nou tabel:
Tabelul Simplex numărul 3
Funcția țintă:
0 160 + 0 40 + 4 40 = 160
Calculăm scorurile după formula:
Δ 1 \u003d 0 0 + 0 0 + 4 1 - 4 \u003d 0
Δ 2 \u003d 0 0 + 0 (-4) + 4 3/2 - 5 \u003d 1
Δ 3 \u003d 0 2 + 0 (-4) + 4 2 - 4 \u003d 4
Δ 4 \u003d 0 1 + 0 0 + 4 0 - 0 \u003d 0
Δ 5 \u003d 0 0 + 0 1 + 4 0 - 0 \u003d 0
Δ 6 \u003d 0 (-1) / 2 + 0 (-1) + 4 1/4 - 0 \u003d 1
Deoarece nu există estimări negative, planul este optim.
Rezolvarea problemei:
x 1 = 40; x2 = 0; x 3 \u003d 0; x 4 = 160; x5 = 40; x6 = 0; F max = 160
Adică, este necesar să se vinde bunuri de primul tip în valoare de 40 de mii de ruble. Bunurile de tipul 2 și 3 nu trebuie vândute. În acest caz, profitul maxim va fi F max = 160 de mii de ruble.
Rezolvarea problemei duale
Problema dublă arată astfel:
Z = 240 y 1 + 200 y 2 + 160 y 3 ->min
Title="(!LANG:delim(lbrace)(matrix(4)(1)((2y_1 + 4y_2 + 4y_3>=4) (3y_1 + 2y_2 + 6y_3>=5) (6y_1 + 4y_2 + 8y_3>=4) (y_1, y_2, y_3>= 0)))(~)">!}
Introducem variabile suplimentare y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0 pentru a converti inegalitățile în egalități.
Perechile conjugate de variabile ale problemelor directe și duale au forma:
Din ultimul tabel simplex nr. 3 al problemei directe, găsim soluția problemei duale:
Z min = F max = 160;
y 1 \u003d Δ 4 \u003d 0; y 2 \u003d Δ 5 \u003d 0; y 3 \u003d Δ 6 \u003d 1; y 4 \u003d Δ 1 \u003d 0; y 5 \u003d Δ 2 \u003d 1; y 6 \u003d Δ 3 \u003d 4;
Y1=0; y2 = 0; y 3 = 1; Z min = 160;
Se încarcă...