Metoda Gomory pentru rezolvarea problemelor de programare liniară

Decizia de problema LP Gomory

Vă mulțumim pentru lectură și pentru partajarea cu alții

Sarcinile am rezolvat anterior dat întotdeauna răspunsul întreg. Acest lucru se datorează faptului că datele originale a fost selectat într-un mod special. Dar acest lucru nu este întotdeauna cazul.

Este mult mai probabil să răspundă cu valori de fracționare corespunzătoare - de exemplu, necesitatea de a produce 2,5 unități de produs A și 3,44 unități de produs B. dacă decizia este acceptabilă? Totul depinde de condițiile problemei. Dacă vom produce, cum ar fi făină și zahăr în kilograme - această soluție este destul de acceptabil. 2,5 unități de produs A - este de 2 kg făină 500 grame și 3,44 unități de produs B este de 3 kg 440 grame de zahăr. Cu toate acestea, imaginați-vă că produsul A - este un computer, iar produsul B - este MP3-playere. Cum pot face 3,44 unități de MP3-player? Este evident că în nici un fel. În astfel de cazuri noi spunem că este necesar pentru a rezolva problema de programare liniară întreg, ceea ce înseamnă că răspunsul trebuie să se întoarcă numere întregi.

Pentru a rezolva problemele pe întreg au dezvoltat o metodă specială numită metoda Gomory. De fapt, metoda de Gomory este doar o „suprastructură“ de mai sus metoda simplex obișnuită, pe care le-am învățat în capitolele anterioare. Ideea metodei de Gomory este că puteți rezolva problema metodei convenționale simplex, având (eventual) soluție non-număr întreg, și apoi pentru fiecare variabilă neîntreg pentru a adăuga o restricție „corecție“, care, în primul rând, fac din acest număr întreg variabilă, și în al doilea rând, influențează minim valoarea funcției obiectiv.

Deci, este clar că noi trebuie mai întâi doar pentru a rezolva problema prin metoda simplex, și apoi pentru fiecare variabilă neîntreg în decizia de un pic „tweak“ valoarea sa. Aceasta este, de circuit metoda Gomory similară cu următoarea:

Rezolva problema inițială de fabricație metoda convențională simplex;
Asigurați-vă că răspunsul este primit non-integral. Dacă este un număr întreg, atunci problema este rezolvată;
Înmulțind această valoare în ultimul rând (rândul F) la -1;
Până în prezent, răspunsul a rămas variabile non-întregi, procedați în felul următor:
1. Printre valorile neîntreg în decizia rezultată pentru a selecta variabila pentru care doriți să faceți o constrângere suplimentară (cum se face acest lucru va fi explicat în exemplul de mai jos);
2. Pentru problema originală pentru a adăuga o limită de compus special pentru variabila selectată (din nou, va fi prezentat în exemplul exact cum să facă acest lucru). Acest lucru va avea ca rezultat o variabilă auxiliară suplimentară;
3. Pentru această problemă la un pas de a aplica metoda simplex, variabila auxiliară care apare pentru a elimina și se adaugă o parte din pornire (care este de asemenea explicată în exemplu).
etapa anterioară (etapa 4) trebuie efectuată până când toată soluția nu devine un întreg. Metoda Gomory asigură faptul că la un moment dat se va întâmpla cu siguranță.

Metoda Gomory va rezolva aceleași probleme de producție care trebuie rezolvate înainte de metoda simplex, dar schimbați-un singur număr - soluția folosind metoda simplex a transformat non-integral:

Acum, a doua linie de bază ne exprimăm variabila $ $ X_A, pentru că într-adevăr, în coloana $ $ X_A o valoare este de 1, iar restul - 0. Iterația se face.

iterație 3

Înainte de a efectua urmatoarea iteratie, trebuie să verificați dacă soluția noastră este optimă? Ultima linie este nici un element negativ, prin urmare, soluția noastră este optimă. Dacă vom scrie valoarea variabilelor de interes $ x_A, x_B, $ x_C, descoperim că $ x_A = \ frac; x_B = 0; x_C = \ frac $. se obține o valoare neîntreg. Prin urmare, trebuie să se aplice metoda Gomory. Prin metoda din Gomory trebuie să adăugăm încă o restricție la problema noastră. În primul rând aveți nevoie pentru a determina pentru unele variabile noninteger vom fi o constrângere suplimentară. Avem două variabile neîntreg - $ x_C $ și $ x_A $. Pentru a determina exact ceea ce este necesar pentru a găsi părțile fracționare ale numerelor care apar în rândul corespunzător, coloana B.

Numărul din șirul de $ x_C $, coloana B este egal cu $ \ frac $. O putem scrie ca $ 9 \ frac $. Partea sa fracționată este egal cu $ \ frac $
Numărul din string $ $ X_A, coloana B este egal cu $ \ frac $. Puteți să-l înregistreze ca $ 6 \ frac $. Partea sa fracționată este egal cu $ \ frac $

Printre părțile fracționare a datelor pentru a găsi cea mai mare, și este pentru această variabilă, vom fi o constrângere suplimentară. Cu toate acestea, vom obține părți fracționare egale, astfel încât să ia doar prima - $ x_C $. Ne pregătim pentru variabila $ limita x_C $. Se va arăta:

Pentru orice altă variabilă va fi exact aceeași formulă, numai cu indicii de coeficienți $ q $ $ nu va fi C $, iar alte

Vom intelege ce e ceea ce. Evident, $ x_A, x_B, x_C, x_1, x_2, x_3 $ - variabile ale problemei noastre. Pentru a găsi coeficienții $ $ q folosim numărul primului rând, din moment ce este în cazul în care un instantaneu al variabilei noastre $ x_C $. Înțeles $ q_C $ este pur și simplu partea fracționară a numărului în șirul de $ x_C $ și coloana B. Valoarea membrilor liberi ai celulei este egal cu $ \ frac = 9 \ frac $. Evident, întreaga parte este 9, iar fracțională $ \ frac $. În consecință, $ q_C = \ frac $.

Coeficientul de $ qjndex $ este partea fracționară a numărului stocat în rândul $ x_C $, coloana $ x_A $. Există un număr de 0, și este evident că partea fracționată este, de asemenea, egal cu 0. $ qjndex = 0 $
Coeficientul de $ qjndex $ este partea fracționară a numărului stocat în rând $ x_C $, coloana de $ x_B $. Există un număr de $ \ $ Frac, și este evident că aceasta este, de asemenea, egal cu partea fracționară $ \ frac $. $ Q _ = \ frac $
Coeficientul de $ qjndex $ este partea fracționară a numărului stocat în rândul $ x_C $, coloana $ x_C $. Există un număr de 1, și este evident că partea sa fracționară este 0. $ qjndex = 0 $
Coeficientul de $ qjndex $ este partea fracționară a numărului stocat în rând $ x_C $, coloana de $ x_1 $. Există un număr de $ \ $ Frac, și este evident că aceasta este, de asemenea, egal cu partea fracționară $ \ frac $. $ Q _ = \ frac $
Coeficientul de $ qjndex $ este partea fracționară a numărului stocat în rând $ x_C $, coloana de $ x_2 $. Există un număr de $ - \ frac $. Pentru numere negative, partea fracționată este determinată nu atât de puțin la pozitiv și egală cu diferența dintre următoarea noastră număr întreg și un număr negativ, mai mic decât al nostru. Pentru numărul $ - \ frac $ următorul număr întreg negativ minim este de $ $ 1, și, prin urmare, $ q _ = - \ frac - (- 1) = \ frac $
Coeficientul de $ qjndex $ este partea fracționară a numărului stocat în rând $ x_C $, coloana de $ x_3 $. Există un număr de 0, și este evident că partea fracționată este, de asemenea, egal cu 0. $ qjndex = 0 $

Substituind coeficienții, obținem o altă limitare:

Cu toate acestea, această restricție este sub formă de inegalitate, și avem toate constrângerile în formă de ecuații. Prin urmare, această restricție se va transforma în ecuație, adăugând un alt non-negativ variabila $ x_4 $:

Listate restricția de o altă linie în tabelul simplex, în plus, nu uitați că există o nouă coloană $ X_4 $, precum și a schimba semnul ultima linie - așa cum se face întotdeauna la începutul activității pe o metodă de Gomory:

Verificați dacă ați primit, am număr întreg soluție. Da, am luat-o. Avem solutia $ x_A = 6, x_B = 1, x_C = $ 9, iar valoarea funcției obiectiv (celula din dreapta jos a tabelului cu semnul opus) este 83, care, întâmplător, coincide cu valoarea țintă a funcției în original (non-integer) probleme. Prin urmare, putem spune că tranziția la valoarea întreagă nu se schimba veniturile companiei. Deci, cu toate acestea, nu se întâmplă întotdeauna, iar cea mai mare parte a veniturilor societății în timpul tranziției la număr întreg de biți scade.

Deci, avem o soluție întreg, atunci problema este rezolvată. Dacă oricare dintre variabilele ar din nou nonintegral, procesul a trebuit să fie repetate - găsiți una dintre variabilele non-întregi, creează o constrângere suplimentară pentru ea prin obtinerea o altă variabilă auxiliară și apoi o etapă a metodei simplex, îndepărtați-l de la bază. După câțiva pași, am fi luat o soluție întreg (ca în acest caz).

Am învățat pentru a rezolva problemele de producție. și suntem capabili să dea un rezultat care să maximizeze profitul. Cu toate acestea, noi nu considerăm reziduuri în depozite. Aceasta este, desigur, va garantam ca nu folosim mai multe resurse decât este, dar este posibil ca surplusul va rămâne în depozit. Ceea ce face de obicei compania în cazul în care au resurse sunt formate în exces în depozite? De fapt, puteți face o mulțime de lucruri:

Aveți posibilitatea să le vândă, și, astfel, creșterea profitului (funcția obiectiv);
Unele resurse pot fi schimbate pentru alte (dacă este posibil), și poate fi, atunci profitul va crește;
Vă puteți gândi la lansarea unui nou produs, care consumă doar o resursă, care avem un surplus. Poate atunci profiturile noastre creștere.

Probleme de producție medie de rezolvare nu dă răspunsuri la întrebări de acest gen. Cu toate acestea, există metode pentru a obține aceste răspunsuri. Una dintre aceste metode - decizie problema „dublă“. Acesta va fi discutat în secțiunea următoare.

utile legate

fost MatByuro pe piață pentru rezolvarea problemelor matematice timp de 11 ani. Toți acești ani, menținem o reputație excelentă și cele mai bune condiții, „preț-calitate“.

Va oferim:
soluție corectă și detaliată pentru un cost rezonabil.

De asemenea, puteți:

Peste Număr 30000
terminat
ordinele
Prețurile sunt rezonabile și
împământat
prețurile
Experiența îi ajută pe elevi
în rezolvarea problemelor
11 ani
Credo de calitate
responsabilitate
și respect
Și ne bucurăm
efectua
comanda