Metoda Simplex explicație simplă. Rezolvarea problemei folosind metoda simplex tabelar. Rezolvarea problemei folosind metoda simplex
Dacă trebuie să rezolvi o problemă programare liniară folosind tabele simplex, apoi noastre serviciu online vă va fi de mare ajutor. Metoda simplex implică enumerarea secvenţială a tuturor vârfurilor regiunii 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. În tabelul compilat, în primul rând, trebuie să vă uitați la coloana cu membri liberi. Dacă există elemente negative în el, atunci este necesar să treceți la a doua etapă, dacă nu, atunci la a cincea.
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 | -c 2 | ... | -c 1 | ... | -c n |
Al treilea pas. În al treilea pas, recalculăm întregul tabel simplex folosind formule speciale; aceste formule pot fi văzute folosind.
Al patrulea pas. Dacă după recalculare au rămas elemente negative în coloana termenilor liberi, atunci treceți la primul pas; dacă nu există, atunci 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ă îmbunătățirea soluției, pentru care găsim pentru următoarea recalculare rândul și coloana de început conform la următorul algoritm. Initial, gasim minimul un număr negativîn linia 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. Recalculăm din nou tabelul folosind formulele, adică. treceți la pasul 3.
. 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 țintă la următoarea vedere:
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 incompatibilitate al sistemului de constrângeri (semnul 1) nu este identificat (adică nu există nicio linie cu un număr liber negativ (cu excepția liniei). funcție obiectivă), în care nu ar exista cel puțin un element negativ (adică un 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 rezolvare; linia care corespunde celui mai mic raport de evaluare pozitivă este acceptată ca rezolvată.
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 variabilă de bază și una liberă care trebuie schimbate în tabelul simplex pentru a trece la noua variabilă „îmbunătățită”. solutie de baza. ÎN î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 efectuează 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 în 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 în 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 ia în considerare această caracteristică).
Răspuns: valoare optimă funcţia 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ă-l aducem la formă canonică prin introducerea în fiecare dintre constrângerile de inegalitate a unei variabile suplimentare nenegative, 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.
Metoda simplex este un proces iterativ de rezolvare direcționată a unui sistem de ecuații pas cu pas, care începe cu o soluție de referință și în căutarea cea mai buna varianta se deplasează de-a lungul punctelor de colț ale zonei de soluție fezabilă, îmbunătățind valoarea funcției obiectiv până când funcția obiectiv atinge valoarea optimă.Scopul serviciului. Serviciul este destinat soluții online Probleme de programare liniară (LPP) folosind metoda simplex în următoarele forme de notație:
- sub forma unui tabel simplex (metoda de transformare Jordan); formular de înregistrare de bază;
- metoda simplex modificată; sub formă de coloană; în formă de linie.
Instrucțiuni. Selectați numărul de variabile și numărul de rânduri (număr de constrângeri). Soluția rezultată este stocată în Fișier Wordși Excel.
În acest caz, nu țineți cont de restricții precum x i ≥ 0. Dacă nu există restricții în sarcină pentru unele x i, atunci ZLP trebuie convertit în KZLP sau utilizați acest serviciu. La rezolvare, utilizarea este determinată automat M-metoda(metoda simplex pe bază artificială) și metoda simplex în două etape.Următoarele sunt, de asemenea, utilizate cu acest calculator:
Metodă grafică de rezolvare a ZLP
Rezolvarea problemei transportului
Rezolvarea unui joc de matrice
Folosind serviciul în modul online puteți determina prețul unui joc matrice (limitele inferioare și superioare), verificați disponibilitatea punct de șa, găsiți o soluție la o strategie mixtă folosind următoarele metode: minimax, simplex, grafică (geometrică), metoda 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 |
Algoritmul metodei simplex include următorii pași:
- Întocmirea primului plan de bază. Trecerea la forma canonică a problemei de programare liniară prin introducerea unor variabile de echilibru suplimentare nenegative.
- Verificarea optimității planului. Dacă există cel puțin un coeficient de linie index mai mic decât zero, atunci planul nu este optim și trebuie îmbunătățit.
- Determinarea coloanei și rândului de început. Dintre coeficienții negativi ai liniei index, este selectat cel mai mare valoare absolută. Apoi, elementele coloanei membre libere a tabelului simplex sunt împărțite în elemente de același semn al coloanei principale.
- Construirea unui nou plan de referință. Tranziția la un nou plan se realizează ca urmare a recalculării tabelului simplex folosind metoda Jordan-Gauss.
Dacă este necesar să găsim extremul funcției obiectiv, atunci despre care vorbim despre căutare valoarea minima(F(x) → min , vezi un exemplu de soluție pentru minimizarea unei funcții) și valoarea maximă ((F(x) → max , vezi un exemplu de soluție pentru maximizarea unei funcții)
O soluție extremă se realizează la limita regiunii soluțiilor fezabile la unul dintre vârfurile punctelor de colț ale poligonului sau pe segmentul dintre două puncte de colț adiacente.
Teorema fundamentală a programării liniare. Dacă funcția obiectiv ZLP atinge o valoare extremă la un moment dat în regiunea soluțiilor fezabile, atunci ea ia această valoare în punctul de colț. Dacă funcția obiectiv ZLP atinge o valoare extremă la mai mult de un punct de colț, atunci ia aceeași valoare la oricare dintre combinațiile liniare convexe ale acestor puncte.
Esența metodei simplex. Deplasarea către punctul optim se realizează prin trecerea dintr-un punct de colț în cel vecin, ceea ce aduce mai aproape și mai rapid de X opt. O astfel de schemă de enumerare a punctelor, numită metoda simplex, sugerat de R. Danzig.
Punctele de colț sunt caracterizate de m variabile de bază, astfel încât tranziția de la un punct de colț la unul vecin poate fi realizată prin schimbarea unei singure variabile de bază din bază la o variabilă dintr-o non-bază.
Implementarea metodei simplex în vigoare diverse caracteristiciși declarații de problemă, LP are diverse modificări.
Construcția tabelelor simplex continuă până la obținerea soluției optime. Cum puteți folosi un tabel simplex pentru a determina că soluția la o problemă de programare liniară este optimă?
Dacă ultima linie(valorile funcției obiective) nu conține elemente negative, prin urmare, va găsi planul optim.
Observație 1. Dacă una dintre variabilele de bază este egală cu zero, atunci punctul extrem corespunzător unei astfel de soluții de bază este degenerat. Degenerarea apare atunci când există ambiguitate în alegerea liniei de ghidare. Este posibil să nu observați deloc degenerarea problemei dacă alegeți o altă linie ca ghid. În caz de ambiguitate, rândul cu cel mai mic indice trebuie selectat pentru a evita bucla.
Observația 2. Fie într-un punct extrem ca toate diferențele simplex să fie nenegative D k ³ 0 (k = 1..n+m), adică. se obține o soluție optimă și există A k - un vector nebază pentru care D k = 0. Atunci maximul se atinge cel puțin în două puncte, adică. există o alternativă optimă. Dacă introducem această variabilă x k în bază, valoarea funcției obiectiv nu se va modifica.
Observație 3. Soluție dubla problema este în ultimul tabel simplex. Ultimele m componente ale vectorului diferențelor simplex (în coloanele variabilelor de echilibru) sunt soluția optimă a problemei duale. Valorile funcțiilor obiective ale problemelor directe și duale în punctele optime coincid.
Observația 4. La rezolvarea problemei de minimizare, se introduce în bază vectorul cu cea mai mare diferență pozitivă simplex. În continuare, se aplică același algoritm ca și pentru problema de maximizare.
Dacă este specificată condiția „Este necesar ca materiile prime de tip III să fie complet consumate”, atunci condiția corespunzătoare este o egalitate.
Este necesar să se rezolve o problemă de programare liniară.
Funcție obiectivă:
2x 1 +5x 2 +3x 3 +8x 4 →min
Conditii limitative:
3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1
Să aducem sistemul de restricții la forma canonică; pentru aceasta este necesar să trecem de la inegalități la egalități, cu adăugarea de variabile suplimentare.
Deoarece problema noastră este o problemă de minimizare, trebuie să o transformăm într-o problemă de căutare maximă. Pentru a face acest lucru, schimbăm semnele coeficienților funcției obiectiv cu cele opuse. Scriem elementele primei inegalități neschimbate, adăugând o variabilă suplimentară x 5 și schimbând semnul „≤” în „=". Deoarece a doua și a treia inegalități au semnele „≥”, este necesar să se inverseze semnele coeficienților lor și să se introducă variabile suplimentare x 6 și, respectiv, x 7 în ele. Ca rezultat, obținem o problemă echivalentă:
3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1
Se trece la formarea tabelului simplex inițial. Coeficienții funcției obiectiv cu semnul opus sunt introduși în rândul F al tabelului.
Membru gratuit |
|||||
| F | |||||
| X5 | |||||
| X6 | |||||
| X7 |
În tabelul pe care l-am compilat există elemente negative în coloana termenilor liberi, printre ele găsim maximul în modul - acesta este elementul: -6, stabilește rândul de început - X6. În această linie găsim și elementul negativ maxim în modul: -10 se află în coloana X3, care va fi coloana principală. Variabila din rândul principal este exclusă din bază, iar variabila corespunzătoare coloanei principale este inclusă în bază. Să recalculăm tabelul simplex:
| X1 | X2 | X6 | X4 | Membru gratuit | |
| F | 0.8 | 8.9 | 0.3 | 6.5 | -1.8 |
| X5 | 4.6 | 0.8 | -0.4 | 3 | 14.4 |
| X3 | 0.4 | -1.3 | -0.1 | 0.5 | 0.6 |
| X7 | -2.6 | -8.3 | -0.1 | 0.5 | -0.4 |
În tabelul pe care l-am compilat există elemente negative în coloana de termeni liberi, printre ele găsim maximul în modul - acesta este elementul: -0,4, stabilește rândul de început - X7. În această linie găsim și elementul negativ maxim în modul: -8,3 este situat în coloana X2, care va fi coloana de conducere. Variabila din rândul principal este exclusă din bază, iar variabila corespunzătoare coloanei principale este inclusă în bază. Să recalculăm tabelul simplex:
| X1 | X7 | X6 | X4 | Membru gratuit | |
| F | -1.988 | 1.072 | 0.193 | 7.036 | -2.229 |
| X5 | 4.349 | 0.096 | -0.41 | 3.048 | 14.361 |
| X3 | 0.807 | -0.157 | -0.084 | 0.422 | 0.663 |
| X2 | 0.313 | -0.12 | 0.012 | -0.06 | 0.048 |
Deoarece nu există elemente negative în coloana termenilor liberi, s-a găsit o soluție admisibilă.Rândul F conține elemente negative, ceea ce înseamnă că soluția rezultată nu este optimă. Să definim coloana principală. Pentru a face acest lucru, vom găsi în rândul F elementul negativ cu modulul maxim - acesta este -1,988 Rândul principal va fi cel pentru care raportul dintre termenul liber și elementul corespunzător al coloanei principale este minim. Rândul principal este X2 și elementul principal este: 0,313.
| X2 | X7 | X6 | X4 | Membru gratuit | |
| F | 6.351 | 0.31 | 0.269 | 6.655 | -1.924 |
| X5 | -13.895 | 1.763 | -0.577 | 3.882 | 13.694 |
| X3 | -2.578 | 0.152 | -0.115 | 0.577 | 0.539 |
| X1 | 3.195 | -0.383 | 0.038 | -0.192 | 0.153 |
Deoarece nu există elemente negative în șirul F, s-a găsit soluția optimă. Deoarece sarcina originală a fost o căutare a minimului, atunci soluție optimă va fi un membru liber al șirului F, luat cu semnul opus. F=1,924
cu valori variabile egale: x 3 = 0,539, x 1 = 0,153. Variabilele x 2 și x 4 nu sunt incluse în bază, deci x 2 =0 x 4 =0.
| - | 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 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | Sf. membru | Θ |
| -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 | W - 1 | |
| -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 - 0 |
| - | 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 | Sf. membru | Θ |
| -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 | F - 1 | |
| -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 | F - 1 | |
| 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 - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
