Lucrul cu tabelul simplex - studopediya

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

pentru a accesa algoritmul tabelul următor este:

vezi tabelul de ultima linie (index), iar între acest șir de coeficienți (cu excepția coloanei de termeni constanți) este selectat cel mai mic număr negativ în găsirea max. sau mai pozitivă atunci când sarcina de la min. Dacă nu există nici o este, atunci soluția inițială de bază este optimă, iar acest tabel este ultima;
coloană vizibilă a tabelului. corespunzând unui negativ selectat factor (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ă. și linia în care este o cheie;
în continuare variabila de bază. linie de celule permisive corespunzătoare, care urmează să fie transferat în descărcare-free. iar elementul liber variabil coloanei corespunzătoare rezolvată este introdusă într-un număr de baze. 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. cu excepția înainte. el vsegdaraven 1.
coloană. care are o linie cheie 0, în noul tabel budettakim fel.
line. în care într-o coloană cheie este 0, noul tabel va fi la fel.
rămânând în noile celule de masă stocate elemente de rezultate de conversie de masă vechi:

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

Dacă tocmai a discutat prima problemă este obținută fără nici o dificultate soluție de bază sa dovedit valabilă, atunci o serie de probleme de soluții originale de bază poate avea una, două și așa mai departe. Componente E. negative, adică. E. fi inacceptabile. În astfel de probleme, trebuie să se aplice mai întâi prima etapă a metodei simplex, t. E. Folosindu-l să se găsească o soluție fezabilă (sau un set inconsistența sistemului de constrângeri), și apoi uita-te pentru cea mai bună soluție (pentru a trage o concluzie despre contradicția problemei). În același timp, trebuie să ne amintim că la prima aplicare etapă a metodei simplex, t. E. In timp ce cautam o solutie de bază validă, forma liniară nu este considerată, iar toate modificările se aplică numai la sistemul de constrângeri.
Lăsați problema de programare liniară este dată sub forma canonică constând din m ecuații cu variabile independente n (sau este dat la o formă după administrarea de variabile non-suplimentare negative).
Alegeți un grup de variabile m de bază care ne permit să găsim soluția de bază inițială (fără pierderi de generalitate, putem presupune că primele m variabile sunt variabile de bază). Exprimându aceste variabile de bază în ceea ce privește non-core, obținem următoarele constrângeri de sistem:

Această metodă de partiționare variabilelor în bază și non-bază corespunde soluție bazică (k1. K2. Km. 0, 0. 0). Luați în considerare cazul general, în cazul în care decizia nu este validă. Din soluția de bază rezultată, trebuie să mergeți mai întâi la orice soluție de bază admisibilă. Și nu neapărat că această tranziție a fost efectuată la o dată, într-un singur pas.
În ipoteza soluției de bază inițială este inacceptabilă. De aceea, printre elementul de sistem liber constrângere (2.16) are cel puțin un negativ (numărul de membri liberi negative ale sistemului coincide cu numărul de componente de bază negativ originale ale soluției). Lăsați-i un membru ki gratuit i-lea ecuație. t. e. xi variabila de bază în soluția de bază corespunzătoare este negativ.
Pentru tranziția la noua soluție de bază este necesară: selectați variabila pe care doriți să convertiți de la non-core la bază; pentru a stabili ce variabila principală, în acest caz, va merge la un număr de variabile non-core. La transferul variabilă non-core din valoarea sa de bază, de obicei, crește în loc de zero în soluția inițială de bază, va fi pozitiv în noua soluție de bază (cu excepția cazului degenerate). Ne întoarcem la ecuația i-lea al sistemului (2.16), conținând negativ k1 liber membru. Aceasta arată că valoarea xi crește odată cu creșterea valorilor variabilelor non-primare, care, în această ecuație sunt coeficienți pozitivi. Rezultă că, în principal, se poate traduce aceste variabile nonbasic în sistemul de ecuații (2.16) cu un termen constant negativ sunt coeficienți pozitivi.

Pot exista trei rezultate:

în sistemul de ecuații i-lea (2.16) au variabilele de bază cu coeficienți pozitivi r. e. toți coeficienții bi, m + j (ca ki termen liber) sunt negative. În acest caz, sistemul este constrângeri inconsistente, nu are nici o soluție fezabilă și, în consecință, optimă;
în ecuația i-lea, există o variabilă xm + j. la care coeficientul b este pozitiv. În acest caz, este această variabilă este transferată în principal;
în ecuația i-lea, există mai multe variabile cu coeficienți pozitivi bi, m + j. În acest caz, în principal, puteți traduce oricare dintre ele.

În continuare, trebuie să se stabilească ce variabila principală care urmează să fie transformat în numărul de non-core la locul transferat în principal. Traduce non-core este variabila principală care devine primul zero la o creștere zero în variabila non-primare, traduse în principal. Cu alte cuvinte, folosim aceeași regulă care a fost stabilită anterior. Sunt relații de membru liber la coeficienții variabilei, traduse în principal, din toate ecuațiile, în cazul în care membrii liberi și acești coeficienți au semne opuse, ia valoarea absolută a acestor relații și au ales cel mai puțin (în cazul în care semnează anumite ecuații de membri liberi și acești factori coincid Or unele ecuații care pot fi transformate în variabila principală lipsește, atunci raportul este considerat a fi egal).
Ecuația care se obține din raportul dintre cea mai mică, este selectată. Ecuația dedicată și arată unele dintre variabilele cheie ar trebui să fie transferate non-core. Exprimându noi variabile de bază în ceea ce privește non-core, trece la următoarea soluție de bază.
Dacă ecuația selectată ar fi negativ, cu un termen liber, noua soluție de bază numărul de componente negative vor fi una mai mică decât originalul. Dacă ecuația selectată va fi pozitiv (sau zero) membrul liber, o nouă soluție de bază numărul de componente negative, rămân la fel cum a fost în soluția inițială de bază.
Astfel, trecerea la noua soluție de bază este avantajoasă pentru ecuația selectată dovedit cu un termen constant negativ, iar în cazul în care există o alegere, o preferință trebuie să se acorde un astfel de schimb de variabile în care ecuația selectată este un termen negativ constant.
Deci, vom obține o soluție nouă, îmbunătățită de bază, care este mai aproape de zona de sistem fezabil soluții restricții. Dacă este invalid, atunci pentru el să se aplice din nou aceeași schemă. Ca urmare, după un număr finit de pași vom obține o soluție de bază validă. De îndată ce soluția de bază admisibilă este găsită, se procedează la a doua etapă a metodei simplex, esența care este considerat în rezolvarea problemei din exemplul 2.4.1.
După ce a luat primul mod de a găsi o soluții de bază acceptabile, orice problemă de programare liniară poate avea dificultăți de natură decât de calcul.