Stare Optimalitate program de sprijin - studopediya
vizualizare Tabelul ZLP. Simplex - tabel.
ZLP Metoda simplex SOLUȚII
3.1. Caracteristici generale și principalele etape ale metodei simplex -
Fondatorii metodei simplex este un matematician sovietic LV KANTOROVICH și matematicianul american John. Danzig.
Metoda simplex poate fi folosit pentru a rezolva orice ZLP sau detecta de nerezolvat. Multe clase speciale ZLP pot fi rezolvate prin alte metode, mai eficiente pentru aceste clase. Cu toate acestea, avantajul metodei simplex - universalitatea acesteia. Aproape toate programele de calculator sunt proiectate pentru soluțiile standard ZLP simplex - metoda.
Vom descrie o idee generală a metodei simplex.
Noi credem că ZLP înregistrate în forma canonică și funcția obiectiv care urmează să fie reduse la minimum. După cum știm deja, ar trebui să fie căutat printre programele de sprijin ZLP planul optim. Metoda simplex nu are suport prin toate planurile (care ar de multe ori nu este posibil din cauza numărului lor mare), și pornind de la unele programe de sprijin inițial, a transferat în mod constant la alte programe de sprijin cu o scădere a funcției obiectiv. Metoda Simplex se oprește de lucru în cazul în care fie se dovedește a fi optim programul de sprijin sau set insolubilitatea problemei.
La metoda de decizie ZLP simplex următoarele etape:
1) aducerea ZLP în formă canonică;
2) aducerea sistemului de ecuații liniare în formă Jordan cu laturile dreaptă nenegative cu verificarea simultană pe insolubilitate ZLP datorită incoerență sistemului de constrângeri liniare;
3) studiază programul de sprijin pentru optimality;
4) Studiu privind ZLP nerezolvabil datorită fundul nelimitarea din SDT funcției obiectiv;
5) Trecerea la o „mai bună“ nou program de sprijin.
Pentru a reduce și de a simplifica înregistrările de la metoda simplex de decizie ZLP utilizează așa-numitul tabel simplex. Pentru a utiliza tabelul simplex ZLP trebuie să aducă la afișarea tabelului. Iată cum.
Să ZLP scris în formă canonică (2,3-2,5). Pentru a aduce ZLP referitor la sistemul de masă (2.4) trebuie să producă mai întâi forma Jordan cu laturi drepte nenegative. Să presupunem că forma Jordan are forma (2.6). Ne exprimăm (2.6) prin intermediul variabilelor de bază libere:
Substituind în funcția obiectiv (2.3) în locul variabilelor de bază, expresia prin variabile libere prin formulele (3.1), excluzând astfel din funcția obiectiv variabile de bază. Funcția obiectiv ia forma:
În formă de tabel funcția obiectiv este scris după cum urmează:
Rețineți următoarele caracteristici ZLP formă de tabel:
a) sistemul de ecuații liniare este dată de forma Jordan cu laturi drepte nenegative;
b) a funcției obiective a variabilelor de bază sunt excluse și este scris sub forma (3.3).
Ne întoarcem acum la descrierea tabelului simplex. Să ZLP înregistrate sub formă de tabel:
tabel simplex Apoi completat arată.
Planul de referință ZPL :. Se numește program de sprijin corespunzător acestui tabel simplex. După cum se vede din formula (3.2), valoarea funcției obiectiv cu planul de referință este egală cu # 947; 0.
Să considerăm un exemplu. Se aduce la masa medie cu următorul text și completați tabelul ZLP simplex:
Inițial ZLP ar trebui să fie adus la forma canonică. Pentru această funcție fnuzhno înlocuiește cu - f:
Sistemul de ecuații trebuie să fie scrise în forma Jordan cu laturile din dreapta nenegative. Recepție În general, prin care se realizează acest lucru va fi considerat mai târziu (a se vedea punctul 3.7). În exemplul nostru, această formă Iordania este deja variabilă și de bază. Noi elimina variabilele de bază ale funcției obiectiv - f. În acest scop, noi le exprimăm prin liberă și substituie aceste expresii în funcția obiectiv.
Vedere Tabelul ZLP urmează:
Completați tabelul simplex (pentru înregistrările reduce din prima coloană este intitulată „B“, ultima coloană - „Q“).
Valoarea funcției obiectiv la planul de referință, tabelul corespunzător simplex este 6. Scriem funcția obiectiv în formă de tabel, în cazul în care. Deoarece pentru orice soluție fezabilă variabile ZLP sunt numai valori non-negative ale ultimei înregistrări a funcției obiectiv se poate observa că valoarea sa, în orice punct al SDT nu este mai mic de 6. Prin urmare, valoarea minimă a funcției obiectiv pe SDT este 6 și se realizează la planul de referință, corespunzătoare tabelul simplex.
3.4. Stare unsolvability ZLP nelimitarea datorită partea de jos a SDT funcției obiectiv.
În cazul în care masa de ZLP simplex este umplut, SDT nu este sarcina goală, astfel încât programul de sprijin, corespunzător tabelul simplex aparține SDT. Totuși ZLP poate fi insolubil datorită SDT este nemarginita sub funcția țintă.
Condiția este formulată ca imprecizie.
În cazul în care tabelul simplex conține cel puțin o coloană, care este diferită de extrema dreaptă, a cărei linie de fund este în valoare de un număr pozitiv, și toate celelalte linii ale coloanei - numărul non-pozitiv, ZLP de nerezolvat din cauza SDT este nemărginită sub funcția țintă.
Pentru a utiliza din nou exemplul studiului.
Coloana din rândul de jos cuprinde un număr pozitiv, iar în celelalte linii - numărul nonpositive. Să ne dovedească ZLP imprecizie.
Scriem Iordania forma de masa simplex corespunzătoare și se transferă termenii care cuprind, pe partea dreapta. obținem
Să o - orice număr pozitiv. Evident, ZLP are următoarea soluție fezabilă :. Se calculează valoarea funcției obiectiv la soluția fezabilă același timp. Din tabelul 3.4, avem:
. Atunci când este indicată soluție fezabilă f = 4 - 2a. De aici vedem că valoarea funcției obiectiv poate fi arbitrar de mici pentru suficient de mare o. Cu alte cuvinte, funcția obiectiv nu este delimitat de mai jos pe S & DT. În consecință, ZLP de nerezolvat.
3.5. Trecerea la noul program de sprijin.
Să presupunem că nu sunt îndeplinite condițiile de optimalitate și imprecizie. Apoi, metoda simplex se mută la un nou program de sprijin. Această tranziție se datorează îndepărtării de la baza uneia dintre variabilele de bază și introducerea în baza uneia dintre variabilele libere. trebuie să fie îndeplinite următoarele două condiții:
1) bază noi trebuie să fie în continuare valabile, și anume, dreapta corespunde formei Jordan trebuie să fie în continuare non-negativ;
2) atunci când o nouă valoare de referință a termenilor funcției obiectiv nu trebuie să depășească valoarea anterioară la planul de referință.
Masa Column simplex, în care există o variabilă introdusă în bază, numită coloana generală. Un șir în care există o variabilă de ieșire de la bază, numită linia generală. Elementul de la intersecția liniei generale și coloana generală, numitul element general.
Regula generală pentru alegerea elementului.
Numărul pozitiv stă ca o coloană generală selectați orice coloană a tabelului simplex este diferită de extrema dreaptă, care are pe linia de jos. numai rândurile din tabel simplex este apoi considerat a fi distinct de jos, în care, la intersecția cu coloana generală sunt numere pozitive. În picioare în master pentru fiecare coloană a unor astfel de linii este termenul constant calculat legat de elementul. String, care este raportul dintre minimul este selectat ca general. Element la intersecția liniei generale și coloana generală și va elementul general.
Să ilustrăm această regulă de exemplu.
După cum puteți alege fie o coloană sau o coloană ca o coloană generală. Am ales (cel mai adesea alege coloana în care partea de jos a unui mare număr pozitiv). Acum vom proceda la alegerea liniei generale. Pentru aceasta considerăm două linii - și. Este un raport de 4: 2 și 8: 3. La fel de important este raportul de 4: 2, asa ca am ales prima linie ca un general. Prin urmare, elementul este de 2 - este la intersecția coloanei și rând.
După ce selectați elementul General aveți nevoie pentru a merge la un nou program de sprijin, în care variabila este de bază și x1 variabilă - gratuit. Coeficientul noului formular Jordan trebuie să fie egală cu 1. Prin urmare, primul rând din Tabelul 3.5 se împarte la 2 și apoi înmulțind primul rând ca rezultat (3) și adăugarea la a doua linie, exclude din a doua ecuație. În mod similar, utilizând procedura regula Jordan și din a treia ecuație a funcției obiectiv (acesta din urmă necesită o vedere ZLP tabular).
Ca rezultat, obținem tabelul de mai jos.