Metoda de transformare simplex. Un exemplu de rezolvare a unei probleme. Metoda simplex pentru rezolvarea ZLP
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 variabilele inițiale ale problemei x 1 , x 2 ,..., x n sunt nebazice. 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 acceptabile solutie de baza
găsit și ar trebui să treceți la pasul 5 al algoritmului, corespunzător 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 | ... | F(x)max | ... | -c 1 |
-c 2
-c n
aceste. 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 din pasul precedent și sunt marcate cu un prim, i.e. 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 sunt de asemenea împărțite la elementul conducător, dar sunt luate 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.
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 în linia de jos tabele 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 este găsită solutie optima
sau se ajunge la concluzia că 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ă de sus și F max ->&∞. Dacă, la următorul pas al căutării 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 produc selecție aleatorie
noua solutie de baza.
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.
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ârfului ODZP din Fig. 1. 2 Elementul de conducere este conturat și selectat în conformitate cu pasul 5 al algoritmului de rezolvare a problemelor. Masă 4 corespunde soluției optime a problemei, prin urmare: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Orez. 2. Soluție grafică sarcini
Una dintre metodele de rezolvare probleme de optimizare (asociată de obicei cu găsirea minimului sau maximului) programare liniară numit . Metoda simplex include un întreg grup de algoritmi și metode pentru rezolvarea problemelor de programare liniară. Una dintre aceste metode, care presupune înregistrarea datelor sursă și recalcularea lor într-un tabel special, se numește metoda tabulară simplex.
Să luăm în considerare algoritmul metodei simplex tabulare folosind exemplul soluției sarcina de productie , care se rezumă la găsirea unui plan de producție care să asigure profit maxim.
Date de intrare pentru problema metodei simplex
Compania produce 4 tipuri de produse, prelucrandu-le pe 3 masini.
Standardele de timp (min./buc) pentru prelucrarea produselor pe mașini sunt specificate de matricea A:
Fondul de timp de funcționare a mașinii (min.) este specificat în matricea B:
Profitul din vânzarea fiecărei unități de produs (RUB/buc) este dat de matricea C:
Scopul sarcinii de producție
Întocmește un plan de producție care să maximizeze profitul întreprinderii.
Rezolvarea problemei folosind metoda simplex tabelar
(1) Să notăm cu X1, X2, X3, X4 numărul planificat de produse de fiecare tip. Apoi planul dorit: ( X1, X2, X3, X4)
(2) Să notăm constrângerile planului sub forma unui sistem de ecuații:
(3) Atunci profitul tinta este:
Adică, profitul din îndeplinirea planului de producție ar trebui să fie maxim.
(4) Pentru a rezolva problema rezultată pe extremă condițională, înlocuim sistemul de inegalități cu sistemul ecuații liniare prin introducerea de variabile suplimentare nenegative în el ( X5, X6, X7).
(5) Să acceptăm următoarele plan de referință:
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Să introducem datele în tabel simplex:
În ultima linie introducem coeficienții funcției obiectiv și valoarea acesteia însăși cu semnul opus;
(7) Selectați în ultima linie cel mai mare (modulo) este un număr negativ.
Să calculăm b = N / Elemente_din_coloana_selectată
Dintre valorile calculate ale lui b alegem cel mai puţin.
Intersecția coloanei și rândului selectate ne va oferi elementul de rezolvare. Schimbăm baza într-o variabilă corespunzătoare elementului de rezolvare ( X5 la X1).
- Elementul de rezolvare în sine se transformă în 1.
- Pentru elementele liniei de rezoluție – a ij (*) = a ij / RE ( adică împărțim fiecare element la valoarea elementului de rezoluție și obținem date noi).
- Pentru elementele coloanei de rezoluție, acestea sunt pur și simplu resetate la zero.
- Recalculăm elementele rămase ale tabelului folosind regula dreptunghiului.
a ij (*) = a ij – (A * B / RE)
După cum puteți vedea, luăm celula curentă care este recalculată și celula cu elementul de rezolvare. Ele formează colțuri opuse ale dreptunghiului. Apoi, înmulțim valorile din celulele celorlalte 2 colțuri ale acestui dreptunghi. Această lucrare ( O * B) împărțiți la elementul de rezolvare ( RE). Și scade din celula curentă care este recalculată ( a ij) Ce s-a întâmplat. Obținem o nouă valoare - a ij (*).
(9) Verificați din nou ultima linie ( c) pe prezența numerelor negative. Dacă nu sunt acolo - plan optim găsit, du-te la ultima etapa rezolvarea problemei. Dacă există, planul nu este încă optim și tabelul simplex trebuie recalculat din nou.
Deoarece avem din nou numere negative în ultima linie, începem o nouă iterație de calcule.
(10) Deoarece nu există elemente negative în ultima linie, asta înseamnă că am găsit planul optim de producție! Și anume: vom produce acele produse care s-au mutat în coloana „Base” - X1 și X2. Cunoaștem profitul din producția fiecărei unități de producție ( matricea C). Rămâne să înmulțim volumele de producție găsite ale produselor 1 și 2 cu profit pe 1 bucată, obținem finalul ( maxim! ) profit pentru un plan de producție dat.
RĂSPUNS:
X1 = 32 buc., X2 = 20 buc., X3 = 0 buc., X4 = 0 buc.
P = 48 * 32 + 33 * 20 = 2.196 rub.
Galyautdinov R.R.
© Copierea materialului este permisă numai dacă există un hyperlink direct către
Iată o soluție manuală (nu un applet) a două probleme folosind metoda simplex (asemănătoare cu soluția applet) cu explicații detaliate pentru a înțelege algoritmul de rezolvare a problemelor folosind metoda simplex. Prima problemă conține semne de inegalitate doar „≤” (problema cu bază inițială), a doua poate conține semne „≥”, „≤” sau „=” (problema cu bază artificială), acestea 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 inegalitate-constrângeri „≤”).
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 de rezolvat 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, așa că putem aplica metoda simplex. Să creăm 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” î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 metodei simplex 0
|
Atitudine |
|||||||
Pentru a îmbunătăți soluția, să trecem la următoarea iterație metoda simplex, 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 a metodei simplex. Este selectat de cel mai mare coeficient negativ absolut din rândul z (în problema maximă) - în iterația inițială a metodei simplex 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 a metodei simplex. 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 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 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ția 0” la elementul de rezolvare (în acest caz este egal cu 1) din acest tabel, obținem rândul x 2 în tabelul „Iterația 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țineți 0 6 0 0 6 120 și adăugați acest rând cu primul rând (z - rând) al 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 1 - 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 necesar. 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:
Rând nou = Rând vechi – (Coeficient de coloană de rezoluție a rândului vechi)* (Rând de rezoluție nou).
De exemplu, pentru un șir z avem:
Vechi șir z (-4 -6 0 0 0 0) -(-6)*Șir nou de rezolvare -(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 |
|||||||
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 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.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | Prin urmare, a fost determinat elementul care va sta la baza. În continuare numărăm. | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| R 1 x 1 = 0 x 2 = 0 S 1 = 0 |
S 2 = 15 S 3 = 4 R 1 = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Prin urmare, a fost determinat elementul care va sta la baza. În continuare numărăm. | Pasul #1 | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | Sf. membru | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 1 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | Pasul #1 | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | W - 0 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | W - 0 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 1 |
| F - 13 S 1 = 0 S 2 = 0 |
x 1 = 3 x 2 = 4 S 3 = 6 |
funcțiile F. Este luat în considerare un exemplu de rezolvare a unei probleme folosind metoda simplex, precum și un exemplu de soluție.
dubla problema
Pentru a vinde trei grupe de bunuri, o întreprindere comercială are 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 a mărfurilor, resursa de primul tip este consumată în valoare de 11 = 2 unități, resursa de al doilea tip în valoare de 21 = 4 unități, resursa 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 se consumă în funcție de resursa primului tip în valoare de a 12 = 3, a 13 = 6 unități, resursa de al doilea tip în cantitate 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 . Profitați din vânzarea a trei grupuri de mărfuri pentru 1 mie de ruble. cifra de afaceri este respectiv c 1 = 4, c 2 = 5, c 3 = 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 cifrei de afaceri, rezolvate prin metoda simplex, compune dubla problema programare liniară.
Instala perechi conjugate de variabile probleme directe și duble.
După perechi conjugate de variabile, din soluția problemei directe obținem rezolvarea problemei duale, în care este produs evaluarea resurselor, cheltuită pentru vânzarea de bunuri.
Rezolvarea problemei folosind metoda simplex
Fie x 1, x 2, x 3 numărul de mărfuri vândute, în mii de ruble, 1, 2, respectiv 3 grupuri. Apoi model matematic sarcina are forma:F = 4 x 1 + 5 x 2 + 4 x 3 ->max
0)))(~)" title="delim(lbrace)(matrice(4)(1)((2x_1 + 3x_2 + 6x_3= 0)))(~)">!}
Rezolvăm metoda simplex.
Introducem variabile suplimentare x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0 pentru a transforma inegalitățile în egalități.
Să luăm ca bază x 4 = 240; x 5 = 200; x 6 = 160.
Introducem datele în tabel simplex
Tabel simplex nr. 1
0 240 + 0 200 + 0 160 = 0
Calculăm estimări folosind formula:
Δ 1 = 0 2 + 0 4 + 0 4 - 4 = - 4
Δ 2 = 0 3 + 0 2 + 0 6 - 5 = - 5
Δ 3 = 0 6 + 0 4 + 0 8 - 4 = - 4
Δ 4 = 0 1 + 0 0 + 0 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 0 0 - 0 = 0
Δ 6 = 0 0 + 0 0 + 0 1 - 0 = 0
Deoarece există estimări negative, planul nu este optim. Cel mai mic scor:
Introducem variabila x 2 în bază.
Definim o variabilă care reiese din bază. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x2.
= 26.667
Cel mai mic nenegativ: Q 3 = 26,667. Deducem variabila x 6 din bază
Împărțiți a treia linie la 6.
Din prima linie, scădeți a treia linie, înmulțită cu 3
Din a 2-a linie, scădeți a 3-a linie, înmulțită cu 2
Calculam:
Primim masa noua:
Tabel Simplex nr. 2
Funcția obiectivă:
0 160 + 0 440/3 + 5 80/3 = 400/3
Calculăm estimări folosind formula:
Δ 1 = 0 0 + 0 8/3 + 5 2/3 - 4 = - 2/3
Δ 2 = 0 0 + 0 0 + 5 1 - 5 = 0
Δ 3 = 0 2 + 0 4/3 + 5 4/3 - 4 = 8/3
Δ 4 = 0 1 + 0 0 + 5 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 5 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1)/3 + 5 1/6 - 0 = 5/6
Deoarece există o estimare negativă Δ 1 = - 2/3, planul nu este optim.
Introducem variabila x 1 în bază.
Definim o variabilă care reiese din bază. Pentru a face acest lucru, găsim cel mai mic raport nenegativ pentru coloana x 1.
Cel mai mic nenegativ: Q 3 = 40. Deducem variabila x 2 din bază
Împărțiți a treia linie la 2/3.
Din a 2-a linie, scădeți a 3-a linie, înmulțită cu 8/3
Calculam:
Primim un tabel nou:
Tabel simplex nr. 3
Funcția obiectivă:
0 160 + 0 40 + 4 40 = 160
Calculăm estimări folosind formula:
Δ 1 = 0 0 + 0 0 + 4 1 - 4 = 0
Δ 2 = 0 0 + 0 (-4) + 4 3/2 - 5 = 1
Δ 3 = 0 2 + 0 (-4) + 4 2 - 4 = 4
Δ 4 = 0 1 + 0 0 + 4 0 - 0 = 0
Δ 5 = 0 0 + 0 1 + 4 0 - 0 = 0
Δ 6 = 0 (-1)/2 + 0 (-1) + 4 1/4 - 0 = 1
Deoarece nu există evaluări negative, planul este optim.
Soluția problemei:
Răspuns
x 1 = 40; x2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x6 = 0; F max = 160Adică, este necesar să vindeți primul tip de mărfuri în valoare de 40 de mii de ruble. Nu este nevoie să vindeți bunuri de tipul 2 și 3. În acest caz, profitul maxim va fi F max = 160 de mii de ruble.
Rezolvarea problemei duale
Problema duală are forma:
Z = 240 y 1 + 200 y 2 + 160 y 3 ->min
Title="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 transforma 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 = Δ 4 = 0; y2 = Δ5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y5 = Δ2 = 1; y 6 = Δ 3 = 4;
