Pentru a produce două tipuri de produse A și B, se folosesc trei tipuri de echipamente tehnologice. Pentru a produce o unitate de produs A, echipamentele de primul tip sunt utilizate timp de 1 oră, echipamente de al doilea tip – 3 ore, echipamente de al treilea tip – 3 ore.
Pentru a produce o unitate de produs B, se utilizează echipamente de primul tip timp de 2 ore, echipamente de al doilea tip – 3 ore, echipamente de al treilea tip – 1 oră.
Pentru a fabrica toate produsele, o întreprindere poate folosi echipamente de primul tip timp de cel mult 32 de ore, echipamente de al doilea tip - 60 de ore, echipamente de al treilea tip - 50 de ore.
Profitul din vânzarea unei unități de produs finit A este de 4 unități monetare, iar produsul B este de 2 unități monetare.
Întocmește un plan de producție pentru produsele A și B care să asigure profit maxim din vânzarea acestora.
1) Creați un model matematic al problemei
2) Rezolvați grafic
3) Rezolvați folosind metoda simplex prin transformarea tabelelor simplex
Soluţie
În fața noastră este o problemă clasică de programare liniară. Un plan de producție este înțeles ca răspuns la o întrebare simplă: câte produse A și câte produse B trebuie produse pentru ca profitul să fie maximizat.
Profitul se calculează folosind formula: .
Să notăm modelul matematic al problemei:
Pentru a ilustra utilizarea metodei simplex pentru rezolvarea acestei probleme, să o rezolvăm grafic.
Pentru a face acest lucru, construim pe plan arii descrise de constrângeri de inegalitate și o linie dreaptă, care se numește funcție obiectiv.
Cele trei inegalități scrise mai sus limitează un poligon pe plan (construit cu roșu), delimitat în stânga și mai jos de axele de coordonate (întrucât numărul necesar de produse este pozitiv).
Graficul funcției obiectiv (construit în albastru) se mișcă în direcția indicată de săgeată (științific, în direcția gradientului său) până când ajunge la punctul limită al poligonului - în cazul nostru, acesta este punctul - (15 ; 5). În acest moment funcția obiectiv va atinge maximul.
Acum să rezolvăm această problemă folosind metoda simplex. Pentru a face acest lucru, să trecem de la constrângerile de inegalitate la constrângerile de egalitate prin introducerea de variabile suplimentare.
Tabelul simplex este compilat după cum urmează:
În coloana Bază se scriu vectorii variabilelor considerate de bază. La prima etapă acestea sunt A3, A4, A5. Variabilele de bază vor fi acelea, fiecare dintre acestea fiind inclusă într-o singură ecuație a sistemului și nu există o ecuație care să nu includă cel puțin una dintre variabilele de bază.
În coloana următoare se înregistrează coeficienții funcției obiectiv corespunzători fiecărei variabile. Coloană IN - coloana membrilor liberi. Urmează coloanele de coeficienți Аi pentru variabila i-a.
Trebuie remarcat faptul că estimările pentru vectorii de bază sunt întotdeauna zero.
Tabelul simplex este convertit după cum urmează:
Pasul 1: Se verifică criteriul de optimitate, a cărui esență este că toate estimările trebuie să fie nenegative. În cazul nostru, acest criteriu nu este îndeplinit, așa că trecem la pasul al doilea.
Pasul 2: Pentru estimări negative, se calculează următoarele valori:
Dintre aceste elemente se selectează cel pentru care produsul calculat este minim, în cazul nostru minim, prin urmare, ca așa-numitul element de rezolvare este selectat al treilea element al primei coloane, 3 (evidențiat în tabel).
Pasul 3: Al treilea rând al tabelului este împărțit la 3 și scade din primul și al doilea rând. În esență, se utilizează o metodă de eliminare a necunoscutelor, cunoscută sub numele de metoda Jordan–Gauss.
Astfel, A3, A4, A1 devin noile variabile de bază.
Revenim la pasul 1 și repetăm întregul proces.
Estimarea inițială este scrisă în coloana Membrii liberi
Estimările rămase sunt scrise sub coloanele vectorilor corespunzători.
Trebuie remarcat faptul că estimările pentru vectorii de bază sunt întotdeauna zero.
Răspunsurile obținute prin diferite metode sunt aceleași.
. Algoritmul metodei simplex
Exemplul 5.1. Rezolvați următoarea problemă de programare liniară folosind metoda simplex:
Soluţie:
eu repetare:
x3, x4, x5, x6 x1,x2. Să exprimăm variabilele de bază în termeni de cele libere:
Să reducem funcția obiectiv la următoarea formă:
Pe baza problemei obținute, vom forma tabelul simplex inițial:
Tabelul 5.3
Tabel simplex original
Relații evaluative |
||||
Conform definiției soluției de bază, variabilele libere sunt egale cu zero, iar valorile variabilelor de bază sunt egale cu valorile corespunzătoare ale numerelor libere, adică:
Etapa 3: verificarea compatibilității sistemului de restricții PAP.
La această iterație (în Tabelul 5.3), semnul de inconsecvență al sistemului de constrângeri (semnul 1) nu este identificat (adică nu există o linie cu un număr liber negativ (cu excepția liniei funcției obiectiv) în care să nu existe să fie cel puțin un element negativ (adică coeficient negativ pentru o variabilă liberă)).
La această iterație (în Tabelul 5.3), semnul de nemărginire al funcției obiectiv (semnul 2) nu a fost identificat (adică nu există nicio coloană cu un element negativ în rândul funcției obiectiv (cu excepția coloanei numerelor libere). ) în care nu ar exista cel puţin un element pozitiv) .
Deoarece soluția de bază găsită nu conține componente negative, este admisibilă.
Etapa 6: verificarea optimității.
Soluția de bază găsită nu este optimă, deoarece conform criteriului de optimitate (semnul 4) nu ar trebui să existe elemente negative în linia funcției obiectiv (numărul liber al acestei linii nu este luat în considerare la considerarea acestui criteriu). Prin urmare, conform algoritmului metodei simplex, trecem la etapa 8.
Întrucât soluția de bază găsită este admisibilă, vom căuta coloana de rezolvare după următoarea schemă: determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.3, există două astfel de coloane: coloana „ x1„și coloana” x2" Din astfel de coloane se selectează cel care conține cel mai mic element din rândul funcției țintă. Ea va fi cea permisivă. Coloana " x2" conține cel mai mic element (–3) în comparație cu coloana " x1
Pentru a determina linia de rezolvare, găsim rapoartele pozitive estimate ale numerelor libere la elementele coloanei de rezoluție se acceptă ca fiind rezolvată linia care corespunde celui mai mic raport de evaluare pozitivă;
Tabelul 5.4
Tabel simplex original
În tabelul 5.4, cea mai mică relație de evaluare pozitivă corespunde liniei „ x5„, prin urmare, va fi permisiv.
Elementul situat la intersecția coloanei de activare și a rândului de activare este acceptat ca activator. În exemplul nostru, acesta este elementul care se află la intersecția liniei „ x5„și coloane” x2».
Elementul de rezolvare arată o bază și o variabilă liberă care trebuie schimbate în tabelul simplex pentru a trece la o nouă soluție de bază „îmbunătățită”. În acest caz, acestea sunt variabile x5Şi x2, în noul tabel simplex (Tabelul 5.5) le schimbăm.
9.1. Transformarea elementului rezolutiv.
Elementul de rezoluție din tabelul 5.4 este convertit după cum urmează:
Introducem rezultatul rezultat într-o celulă similară din Tabelul 5.5.
9.2. Conversie șir de rezoluție.
Împărțim elementele rândului de rezolvare a tabelului 5.4 la elementul de rezolvare al acestui tabel simplex, rezultatele se încadrează în celule similare ale noului tabel simplex (tabelul 5.5). Transformările elementelor șirului de rezoluție sunt date în Tabelul 5.5.
9.3. Conversia coloanei de rezoluție.
Împărțim elementele coloanei de rezoluție din tabelul 5.4 la elementul de rezoluție al acestui tabel simplex, iar rezultatul este luat cu semnul opus. Rezultatele obținute se încadrează în celule similare ale noului tabel simplex (Tabelul 5.5). Transformările elementelor coloanei de rezoluție sunt date în Tabelul 5.5.
9.4. Transformarea elementelor rămase ale tabelului simplex.
Transformarea elementelor rămase ale tabelului simplex (adică elementele care nu sunt situate în rândul de rezolvare și coloana de rezolvare) se realizează conform regulii „dreptunghi”.
De exemplu, luați în considerare transformarea unui element situat la intersecția liniei " x3„ și coloanele „”, îl vom desemna condiționat „ x3" În tabelul 5.4, desenăm mental un dreptunghi, al cărui vârf se află în celula a cărei valoare o transformăm (adică în celula „ x3"), iar celălalt (vertex diagonal) este într-o celulă cu un element de rezoluție. Celelalte două vârfuri (ale celei de-a doua diagonale) sunt determinate în mod unic. Apoi valoarea transformată a celulei " x3" va fi egală cu valoarea anterioară a acestei celule minus fracția, în numitorul căreia se află elementul de rezoluție (din tabelul 5.4), iar în numărător este produsul altor două vârfuri neutilizate, adică:
« x3»: .
Valorile altor celule sunt convertite în mod similar:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
Ca urmare a acestor transformări, a fost obținut un nou tabel simplex (Tabelul 5.5).
II repetare:
Etapa 1: întocmirea unui tabel simplex.
Tabelul 5.5
Tabel simplexII iterații
Estimată relaţie |
||||
| ||||
|
|
Etapa 2: determinarea soluției de bază.
Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.5):
După cum puteți vedea, cu această soluție de bază valoarea funcției obiectiv = 15, care este mai mare decât cu soluția de bază anterioară.
Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.5 nu a fost identificată.
Etapa 4: verificarea mărginirii funcției obiectiv.
Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.5 nu este dezvăluită.
Etapa 5: verificarea admisibilității soluției de bază găsite.
Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.5) conține un element negativ: –2 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru caracteristică). Prin urmare, trecem la etapa 8.
Etapa 8: determinarea elementului rezolutiv.
8.1. Definiția coloanei de rezoluție.
Soluția de bază găsită este acceptabilă determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.5, există o singură astfel de coloană: „ x1" Prin urmare, îl acceptăm așa cum este permis.
8.2. Definiția unui șir de activare.
Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.6, minimul este relația corespunzătoare liniei „ x3" Prin urmare, îl acceptăm așa cum este permis.
Tabelul 5.6
Tabel simplexII iterații
Estimată relaţie |
||||
3/1=3 – min |
||||
Etapa 9: transformarea tabelului simplex.
Transformările tabelului simplex (Tabelul 5.6) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.7.
III repetare
Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:
Tabelul 5.7
Tabel simplexIII iterații
Estimată relaţie |
||||
| ||||
|
|
Etapa 2: determinarea soluției de bază.
Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.7):
Etapa 3: verificarea compatibilității sistemului de restricții.
Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.7 nu a fost identificată.
Etapa 4: verificarea mărginirii funcției obiectiv.
Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.7 nu este dezvăluită.
Etapa 5: verificarea admisibilității soluției de bază găsite.
Soluția de bază găsită în conformitate cu criteriul 3 este acceptabilă, deoarece nu conține componente negative.
Etapa 6: verificarea optimității soluției de bază găsite.
Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.7) conține un element negativ: –3 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru). caracteristică). Prin urmare, trecem la etapa 8.
Etapa 8: determinarea elementului rezolutiv.
8.1. Definiția coloanei de rezoluție.
Soluția de bază găsită este acceptabilă determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.7, există o singură astfel de coloană: „ x5" Prin urmare, îl acceptăm așa cum este permis.
8.2. Definiția unui șir de activare.
Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.8, minimul este relația corespunzătoare liniei „ x4" Prin urmare, îl acceptăm așa cum este permis.
Tabelul 5.8
Tabel simplexIII iterații
Estimată relaţie |
||||
5/5=1 – min |
||||
Etapa 9: transformarea tabelului simplex.
Transformările tabelului simplex (Tabelul 5.8) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.9.
IV repetare
Etapa 1: construirea unei noi mese simplex.
Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:
Tabelul 5.9
Tabel simplexIV iterații
Estimată relaţie |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Etapa 2: determinarea soluției de bază.
Ca urmare a transformărilor simplex s-a obţinut o nouă soluţie de bază conform Tabelului 5.9, soluţia este următoarea:
Etapa 3: verificarea compatibilității sistemului de restricții.
Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.9 nu a fost identificată.
Etapa 4: verificarea mărginirii funcției obiectiv.
Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.9 nu este dezvăluită.
Etapa 5: verificarea admisibilității soluției de bază găsite.
Soluția de bază găsită în conformitate cu criteriul 3 este acceptabilă, deoarece nu conține componente negative.
Etapa 6: verificarea optimității soluției de bază găsite.
Soluția de bază găsită în conformitate cu caracteristica 4 este optimă, deoarece nu există elemente negative în linia funcției obiectiv a tabelului simplex (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se ia în considerare această caracteristică) .
Etapa 7: verificarea alternativei soluției.
Soluția găsită este unică, deoarece nu există elemente zero în linia funcției obiectiv (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se consideră această caracteristică).
Răspuns: valoarea optimă a funcţiei obiectiv a problemei luate în considerare =24, care se realizează la.
Exemplul 5.2. Rezolvați problema de programare liniară de mai sus, cu condiția ca funcția obiectiv să fie minimizată:
Soluţie:
eu repetare:
Etapa 1: formarea tabelului simplex inițial.
Problema originală de programare liniară este dată în formă standard. Să o aducem la forma canonică prin introducerea unei variabile suplimentare nenegative în fiecare dintre constrângerile de inegalitate, i.e.
În sistemul de ecuații rezultat luăm ca variabile permise (de bază). x3, x4, x5, x6, atunci variabilele libere vor fi x1,x2. Să exprimăm variabilele de bază în termeni de cele libere.
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ă căutarea secvențială prin toate vârfurile intervalului de valori acceptabile 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 este îmbunătățită la fiecare pas ulterior. Această soluție se numește de bază. Iată secvența de acțiuni atunci când se rezolvă o problemă de programare liniară folosind metoda simplex:
Primul pas.
Al doilea pas.
La a doua etapă, este necesar să se decidă ce variabilă să se excludă din bază și pe care să se includă pentru a recalcula tabelul simplex. Pentru a face acest lucru, căutați prin coloana cu termeni liberi și găsiți un element negativ în ea. Linia cu un element negativ se va numi lider. În el găsim elementul negativ maxim în modul, coloana corespunzătoare este cea slave. Dacă există valori negative printre termenii liberi, dar nu există niciunul în rândul corespunzător, atunci un astfel de tabel nu va avea soluții. Variabila din rândul de început situat în coloana de termeni liberi este exclusă din bază, iar variabila corespunzătoare coloanei de început este inclusă în 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 | ... | F 0 | ... | -c 2 |
-c n
Al treilea pas.
În al treilea pas, recalculăm întregul tabel simplex utilizând formule speciale care pot fi văzute folosind.
| - | Al patrulea pas. | + | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | - | Al cincilea pas. | = | 1 | ||||||||||
| Al patrulea pas. | +3 | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | + | 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 șirul F sunt pozitive. Dacă nu este cazul, atunci este necesar să îmbunătățim soluția, pentru care găsim rândul și coloana de început pentru următoarea recalculare folosind următorul algoritm. Inițial, găsim numărul minim negativ în șirul 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 termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie pozitive. Raportul minim vă va permite să determinați linia de conducere. Recalculam din nou tabelul folosind formulele, i.e. treceți la pasul 3. | = | 15 | |||||||||||
| - | 2 | Al patrulea pas. | + | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | + | x 1 | = | 4 |
| - | Al patrulea pas. | + | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | - | Al cincilea pas. | + | Prin urmare, a fost determinat elementul care va sta la baza. În continuare numărăm. | = | 1 | |||||||||||
| Al patrulea pas. | +3 | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | + | 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 șirul F sunt pozitive. Dacă nu este cazul, atunci este necesar să îmbunătățim soluția, pentru care găsim rândul și coloana de început pentru următoarea recalculare folosind următorul algoritm. Inițial, găsim numărul minim negativ în șirul 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 termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie pozitive. Raportul minim vă va permite să determinați linia de conducere. Recalculam din nou tabelul folosind formulele, i.e. treceți la pasul 3. | = | 15 | ||||||||||||||
| - | 2 | Al patrulea pas. | + | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | + | x 1 | = | 4 |
| R 1 x 1 = 0 x 2 = 0 S 1 = 0 |
S 2 = 15 S 3 = 4 R 1 = 1 |
| Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi 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 șirul F sunt pozitive. Dacă nu este cazul, atunci este necesar să îmbunătățim soluția, pentru care găsim rândul și coloana de început pentru următoarea recalculare folosind următorul algoritm. Inițial, găsim numărul minim negativ în șirul 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 termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie pozitive. Raportul minim vă va permite să determinați linia de conducere. Recalculam din nou tabelul folosind formulele, i.e. treceți la pasul 3. | x 1 | 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 |
| - | Al patrulea pas. | + | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | - | Al cincilea pas. | = | 1 | ||||||||||
| 4 | Al patrulea pas. | + | 3 | 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 șirul F sunt pozitive. Dacă nu este cazul, atunci este necesar să îmbunătățim soluția, pentru care găsim rândul și coloana de început pentru următoarea recalculare folosind următorul algoritm. Inițial, găsim numărul minim negativ în șirul 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 termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie pozitive. Raportul minim vă va permite să determinați linia de conducere. Recalculam din nou tabelul folosind formulele, i.e. treceți la pasul 3. | = | 12 | |||||||||
| - | Al patrulea pas. | + | Al cincilea pas. | + | x 1 | = | 3 |
| Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi 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 șirul F sunt pozitive. Dacă nu este cazul, atunci este necesar să îmbunătățim soluția, pentru care găsim rândul și coloana de început pentru următoarea recalculare folosind următorul algoritm. Inițial, găsim numărul minim negativ în șirul 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 termenul liber corespunzător și elementul din coloana de început, cu condiția ca acestea să fie pozitive. Raportul minim vă va permite să determinați linia de conducere. Recalculam din nou tabelul folosind formulele, i.e. treceți la pasul 3. | x 1 | 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 |
se bazează pe teoria dualității (vezi soluția problemei duale) și este folosit pentru a rezolva probleme de programare liniară, ai căror termeni liberi b i pot lua orice valoare, iar sistemul de restricții este specificat prin inegalități de semnificație „≤”, „≥” sau egalitatea „=”. Scopul serviciului . Calculator online folosit pentru rezolvarea problemelor de programare liniară P-metoda
în următoarele forme de înregistrare: forma de înregistrare de bază a metodei simplex, sub formă de tabel simplex, în metoda simplex modificată. Instructiuni pentru rezolvarea problemelor metoda dual simplex
Următorul În același timp, restricții precum x i ≥ 0nu iei in calcul.
Următoarele sunt, de asemenea, utilizate cu acest calculator:
Metodă grafică de rezolvare a ZLP
Rezolvarea problemei transportului
Folosind serviciul online, puteți determina prețul unui joc matrice (limitele inferioare și superioare), puteți verifica prezența unui punct de șa, puteți găsi o soluție la o strategie mixtă folosind următoarele metode: minimax, metoda simplex, grafică (geometrică). ), metoda lui Brown.
Extremul unei funcții a două variabile
Probleme de programare dinamică
Distribuiți 5 loturi omogene de mărfuri între trei piețe astfel încât să obțineți venituri maxime din vânzarea acestora. Veniturile din vânzări pe fiecare piață G(X) depind de numărul de loturi vândute de produs X și sunt prezentate în tabel.
| Volumul produsului X (în loturi) | Venitul G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
În metoda P, planul optim se obține prin deplasarea de-a lungul pseudoplanurilor. Pseudoplan- un plan în care sunt îndeplinite condițiile de optimitate, iar printre valorile variabilelor de bază x i se numără numere negative. Algoritm pentru metoda dual simplex include următorii pași:
- Întocmirea unui pseudo-plan. Sistemul de constrângeri al problemei inițiale conduce la un sistem de inegalități cu sensul „≤”.
- Verificarea optimității planului. Dacă condiția de optimitate nu este satisfăcută în planul de referință rezultat, atunci problema este rezolvată folosind metoda simplex.
- Selectarea rândului și coloanei de început. Dintre valorile negative ale variabilelor de bază, sunt selectate cele mai mari în valoare absolută. Linia corespunzătoare acestei valori este cea din frunte.
- Calculul unui nou plan de referință. Noul plan se obține prin recalcularea tabelului simplex folosind metoda Jordan-Gauss. Apoi, treceți la etapa 2.
Exemplu. Întreprinderea trebuie să producă unități A1, unități A2 și unități A3 conform planului de producție. Fiecare tip de produs poate fi produs pe două mașini.
Cum să distribuiți munca mașinilor astfel încât timpul total petrecut pentru executarea planului să fie minim? Sunt date matricea costurilor și resursele de timp ale fiecărei mașini. Notați modelul operației studiate într-o formă care să permită utilizarea metodei P.
Se știe că conținutul de n nutrienți A, B și C din dietă ar trebui să fie de cel puțin m1, m2, respectiv m3 unități. Trei tipuri de alimente conțin acești nutrienți. Conținutul de unități nutritive într-un kilogram din fiecare tip de produs este prezentat în tabel. Stabiliți o dietă zilnică care să ofere cantitatea necesară de nutrienți la un cost minim.
Sarcină: Rezolvați problema utilizând algoritmul metodei dual simplex.
Să reducem sistemul de restricții la sistemul de inegalități de sens ≤ prin înmulțirea dreptelor corespunzătoare cu (-1).
Să determinăm valoarea minimă a funcției obiectiv F(X) = 4x 1 + 2x 2 + x 3 în următoarele condiții de constrângere.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Pentru a construi primul plan de referință, reducem sistemul de inegalități la un sistem de ecuații prin introducerea de variabile suplimentare (tranziție la forma canonică).
În prima inegalitate de sens (≤), introducem variabila de bază x 4 . În a doua inegalitate de sens (≤), introducem variabila de bază x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Matricea de coeficienți A = a(ij) a acestui sistem de ecuații are forma:
| A= |
|
x 4, x 5,
Presupunând că variabilele libere sunt egale cu zero, obținem primul proiect de referință:
X1 = (0,0,0,-10,8)
| Bază | B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
Iterația #1
Planul 0 dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
Linia principală va fi prima linie, iar variabila x 4 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde coloanei a 2-a, adică. variabila x 2 trebuie introdusă în bază.
| Bază | B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| x 4 | -10 | -1 | -1 | 0 | 1 | 0 |
| x 5 | 8 | 2 | 1 | -1 | 0 | 1 |
| F(X0) | 0 | -4 | -2 | -1 | 0 | 0 |
| θ | 0 | -4: (-1) = 4 | -2: (-1) = 2 | - | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări ale tabelului simplex folosind metoda Jordano-Gauss.
| Bază | B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
Să prezentăm calculul fiecărui element sub forma unui tabel:
| B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| -10: -1 | -1: -1 | -1: -1 | 0: -1 | 1: -1 | 0: -1 |
| 8-(-10 1):-1 | 2-(-1 1):-1 | 1-(-1 1):-1 | -1-(0 1):-1 | 0-(1 1):-1 | 1-(0 1):-1 |
| 0-(-10 -2):-1 | -4-(-1 -2):-1 | -2-(-1 -2):-1 | -1-(0 -2):-1 | 0-(1 -2):-1 | 0-(0 -2):-1 |
Iterația #2
1. Verificarea criteriului de optimitate.
Planul 1 dintr-un tabel simplex este un pseudo-plan, așa că determinăm rândul și coloana de început.
2. Definirea unei noi variabile libere.
Dintre valorile negative ale variabilelor de bază, o selectăm pe cea mai mare în valoare absolută.
A doua linie va fi lider, iar variabila x 5 ar trebui derivată din bază.
3. Definirea unei noi variabile de bază. Valoarea minimă a lui θ corespunde celei de-a treia coloane, adică. variabila x 3 trebuie introdusă în bază.
La intersecția rândului principal și coloanei există un element de rezoluție (RE) egal cu (-1).
| Bază | B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | 10 | 1 | 1 | 0 | -1 | 0 |
| x 5 | -2 | 1 | 0 | -1 | 1 | 1 |
| F(X0) | 20 | -2 | 0 | -1 | -2 | 0 |
| θ | 0 | - | - | -1: (-1) = 1 | - | - |
4. Recalcularea tabelului simplex. Efectuăm transformări.
| Bază | B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
| B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| 10-(-2 0):-1 | 1-(1 0):-1 | 1-(0 0):-1 | 0-(-1 0):-1 | -1-(1 0):-1 | 0-(1 0):-1 |
| -2: -1 | 1: -1 | 0: -1 | -1: -1 | 1: -1 | 1: -1 |
| 20-(-2 -1):-1 | -2-(1 -1):-1 | 0-(0 -1):-1 | -1-(-1 -1):-1 | -2-(1 -1):-1 | 0-(1 -1):-1 |
În coloana de bază, toate elementele sunt pozitive. Să trecem la algoritmul principal al metodei simplex.
Iterația #3
1. Verificarea criteriului de optimitate.
Nu există valori pozitive printre valorile șirului de index. Prin urmare, acest tabel determină planul optim pentru problemă.
| Bază | B | Al patrulea pas. | Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | x 3 | x 4 | x 5 |
| Dacă după recalculare au rămas elemente negative în coloana de termeni liberi, atunci treceți la primul pas, dacă nu există, apoi la al cincilea. | 10 | 1 | 1 | 0 | -1 | 0 |
| x 3 | 2 | -1 | 0 | 1 | -1 | -1 |
| F(X1) | 22 | -3 | 0 | 0 | -3 | -1 |
Planul optim poate fi scris astfel: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22
