Punerea în aplicare a metodei simplex

Deci, în coloana din stânga sunt scrise principalele variabile (de bază), toate variabilele problemei sunt enumerate în primul rând al tabelului. Coloana conține termeni constanți din extrema dreaptă sistem de restricție b1. b2. bm. În ultimul rând al tabelului (denumit estimat) coeficienții stocate funcției obiectiv și valoarea funcției obiectiv (cu semn opus) ca soluție actuală L de bază = -f (x). Zona de lucru a mesei (începând cu al doilea rând și coloana a doua) enumerate coeficienții ij cu sistem de restricție variabilă.

NOTĂ! Vezi tabel pot fi diferite, dar nu se schimba fluxul de lucru.

În prima soluție de bază variabile libere x1. .... xn este egal cu zero. Variabilele de bază sunt diferite de zero, și pot fi obținute ca urmare a limitărilor soluției: xn + 1 = b1; xn + 2 = b2; ...; xn + m = bm. Această soluție de bază este valabilă. Firește, valoarea funcției obiectiv în acest caz este egal cu zero, ca și în formarea funcției obiective care implică variabile care pentru baza de soluții sunt minoritari.

4 Condiții de testare: toate cj ≤ 0. Dacă „NU“ - o tranziție de la pasul 5, în cazul în care „DA“ - problema este rezolvata. Astfel, acest pas controale pentru elemente pozitive în ultimul rând al tabelului simplex. În cazul în care aceste elemente sunt necesare pentru a continua decizia.

5 Selectați coloana soluționare (variabilă introdusă în bază). Se lasă coloana selectată în conformitate cu următoarea condiție: cr = maxcj>, j = 1, ..., n + m, unde r - numărul rezolvarea coloanei. Astfel, în determinarea coloanei care permite vizualizarea ultima linie a tabelului de simplex și este cercetat elementul cel mai pozitiv.

6 Condiții de testare: toate ≤ aer 0. Dacă „DA“ - funcția obiectiv este nemarginit, și nu există nici o soluție, în cazul în care „NU“ - du-te la pasul 7. Trebuie să verificați elementele care permit coloanei. Dacă nici unul dintre ei este pozitiv, atunci problema este de nerezolvat.

7 Selectarea șir rezolvarea (variabilă de ieșire de la linia de bază), la următoarea condiție:

pentru aer> 0, în cazul în care s - numărul liniei de rezoluție.

Astfel, pentru acele rânduri în cazul în care elementele care permit o coloană pozitivă, este necesar să se găsească bi element de câtul (ultima coloană a tabelului) de elementul situat în coloana de eliberare. Ca rezoluția selectată, rândul pentru care rezultatul acestei diviziuni va fi cel mai mic. Elementul de la intersecția liniei de rezoluție și permițând coloanei, numit membru permisiv.

8 Contele de membri din tabel simplex (tranziția la noua soluție de bază).

Pentru elementele rezolvarea șir utilizează următoarea formulă:

în cazul în care s - rezolvarea numărul rând, r - coloana număr rezolvare. - Noi valori sunt elemente recalculate, ASJ. bs - elemente de valoare vechi se recalculează, ASR - element de valoare care permite vechi. Când se face conversia elementelor liniei de soluționare a fiecărui element împărțit la elementul de autorizare.

Elementele care permit coloanei cu excepția elementului de separare, care este 1, sunt setate la zero: = 0,

Elementele care nu sunt deținute permițând coloane și rânduri. tradus cu ajutorul așa-numita regulă dreptunghi: dreptunghi evidențiat mental, în care elementul care urmează să fie recalculată, și permițând elementului pentru a forma una dintre diagonalele. Formula va fi după cum urmează:

în cazul în care ,,, - valori noi sunt traduse articole

AIJ. bi. cj. L - valorile vechi sunt traduse elemente.

Lucrul cu tabelul simplex

Primul tabel simplex suferă o transformare, a cărei esență este de a trece la o nouă soluție de suport.

Reguli pentru trecerea la tabelul următor:

linie index vizibil (ultima) a tabelului și între coeficienții liniei (cu excepția coloanei de termeni constanți) este selectat cel mai mic număr negativ în găsirea maxim, sau cel mai pozitiv în rezolvarea problemei pe min. Dacă nu există nici o este, atunci soluția inițială de bază este optimă, iar acest tabel este ultima;

vizualizate coloană a tabelului care corespunde factorului negativ selectat (pozitiv) în ultima coloană cheie stroke-, iar această coloană sunt alese coeficienți pozitivi. În cazul în care nu există nici unul, funcția obiectiv este nemarginit pe valorile de toleranță ale variabilelor și problema nu are nici o soluție;

printre coloana selectată selectați coeficienții pentru care valoarea absolută a raportului membrului liber corespunzător (aflat în coloana membrilor) la elementul este minim. Acest raport se numește permisivă, iar șirul în care aceasta este o cheie;

în continuare variabila de bază linie de celule permisive corespunzătoare este transferată în variabila de descărcare și fără liber elementul coloană permisiva corespunzător este introdus în numărul de bază. Construiește un nou tabel care conține noile nume de variabile de bază:

împărțiți fiecare element șir cheie (cu excepția coloanei membri liber) la un element permite și valorile obținute scrise în rândul cu tabelul variabil de bază modificat este nou simplex.

line permite elementul împărțit elementul și șirul rezultat este scris la noul tabel în același loc.

un nou tabel al tuturor elementelor coloanei cheie = 0 în afară de permițându-i este întotdeauna 1.

coloană, care are o linie cheie 0, în noul tabel va fi la fel.

line, care are o coloană cheie 0, în noul tabel va fi la fel.

Celulele rămase în noile elemente tabelă vechi tabel stocate rezultat de conversie: element nou este egal cu elementul vechi minus o fracțiune, din care numărătorul este produsul liniei curente și permiterea elementului coloană la un rând de elemente de rezoluție și coloana curentă, iar numitorul - permițând elementului.

Rezultatul este un nou tabel simplex care corespunde noilor soluții de bază.

Exemplu de calcul al metodei simplex

Pe a doua foaie de MS Excel registru de lucru vom obține soluția problemei, folosind ideile simplex - metoda. Scriem problema în formă canonică. Am găsit prima soluție fezabilă. Sistemul este compatibil cu restricție. Locul său r = 4, prin urmare, numărul de variabile libere k = 6-4 = 2. Ca liber alege x1 și x2, 0-le echivaleze, adică, x1 = 0 și x2 = 0. Valorile de bază ale necunoscutelor se calculează de constrângerile sistemului. Rezultatele sunt prezentate în figură.

Prima soluție valabilă pentru problema

Valoarea rezultatelor funcției obiectiv în decizia este 0. analiza dacă este posibil prin schimbarea x1 și x2 atinge f crescut. Din funcția țintă de înregistrare care poate fi din cauza creșterea x1 sau x2. Noi crestem x1 (x1 intră în funcția obiectiv cu coeficientul b lshim -7) până la limitele observate. Din ecuația x3 = 19-2x1-3x2 rezultă că x1 poate fi mărită până la 19/2 = 9,5, x4 ecuația = 13-2x1 - x2 - 13/2 = 6,5, X5 ecuația = 15-3x2 - 15/0 = ∞, X6 ecuația = 18-3x1- la 18/3 = 6. Alegerea o valoare minimă de 6 x1 și x6 traduce în variabile libere și x1 - baza. Recalculeze sistem restricție de ecuații care exprimă x6 = 18-3x1 x1 și x1 = 6-1 inlocuind / 3x6 alte constrângeri ale ecuației sistemului. Rezultatul este prezentat în Fig.

Rafinat soluție fezabilă pentru problema

Noua soluție este mai bună decât ultima, deoarece valoarea funcției obiectiv a crescut. Aplicarea ideii simplex - metoda efectuează o secvență de două etape pentru a obține soluția optimă.

A treia foaie rezolva problema, în conformitate cu manipularea simplex - tabele. Simplex - tabel care corespunde primei soluții admisă este prezentată în fig.

Simplex inițială - tabel

Selectați elementul General - αsr. αsr = 3. Găsim  = 1 / αsr .Zanosim într-o nouă foaie de calcul în caseta corespunzătoare elementului general. Noul tabel de elemente care formează șirurile rezolvarea în conformitate cu regula: să ia o valoare din tabelul precedent și se înmulțește cu . Elementele care permit numărul de coloana de regula: valoarea din tabelul anterior înmulțit cu -. Celulele rămase sunt umplute conform regulii: valoarea tabelului anterior am scade valoarea  produs din rândul anterior tabelul din rezoluția și coloana curentă și valoarea din tabelul anterior în linia curentă și coloana permisivă. Sequential simplex - tabelul de calcul prezentat în Fig.

Soluție folosind simplex - tabele

În pagina a patra registru de lucru MS Excel respectă decizia problemei prin utilizarea „căutarea unei soluții.“

Completarea celulelor foaie MS Excel: