Metoda Gomory, programare întreg

Interpretarea economică și geometrică a problemei de programare întreg. variabile de sarcini extreme care iau numai valori întregi, numit problema de programare întreg.

Modelul matematic al problemei de programare întreg ca funcția obiectiv, iar sistemul de limitare a funcției poate fi liniar, neliniar și se amestecă. Numai cazul în care funcția obiectiv și sistemul de constrângere a problemei sunt liniare.

În magazinul compania a decis să instaleze echipamente suplimentare, pentru care zona alocata de cazare. Achiziționarea de echipamente, compania poate cheltui 10 de mii. Frecați. în timp ce se poate cumpăra două tipuri de echipamente. Setul de echipamente I costă un fel de 1000 de ruble. și de tip II - 3000 ruble. Achiziționarea de un set de echipamente de tip I poate crește producția pe schimb cu 2 unități. și un set de tip echipamente II - 4 unități. Știind că un set de echipament trebuie să introduc 2 m 2 zonă, și tipul de aparate II - 1 m 2 zonă pentru a defini un set de echipamente suplimentare, ceea ce face posibilă pentru a maximiza de ieșire

Decizie. Am construit modelul matematic al problemei. Să presupunem că societatea va achiziționa seturi x1 de echipamente de tip I și tip II seturi de echipamente. Apoi variabilele x1 și trebuie să îndeplinească următoarele inegalități:

În cazul în care societatea va dobândi numărul specificat de echipamente, creșterea totală a producției va fi

În variabilele de conținut economic x1 și poate lua numai valori întregi ne-negative, adică. E.

Astfel, ajungem la următoarea problemă matematică: a găsi o valoare maximă a funcției liniare (71) atunci când îndeplinirea condiției (70), (72) și (73). Având în vedere că necunoscutul poate lua numai valori întregi, atunci problema (70) - (73) este o problemă de programare întreg. Deoarece numărul de necunoscute ale problemei este de două, problema poate fi găsit prin utilizarea interpretarea geometrică. Pentru acest construct în primul rând un poligon de soluții care constau în determinarea valorii maxime a funcției lineare (71) în condițiile (70) și (72) (Fig. 11). Coordonatele tuturor punctelor soluțiilor poligon OAEVS satisfac sistemul de inegalități liniare (70) și starea de non-negativitate variabilelor (72). Cu toate acestea, condiția (73), t. E. Integralitatea variabile condiție coordonatele satisfac doar 12 puncte marcate în Fig. 11. Pentru a găsi un punct ale căror coordonate sunt determinate de soluția problemei inițiale, înlocuiți poligonul poligon OABC OKEMNF. care conține toate punctele valide cu coordonate întregi și astfel încât coordonatele fiecărui nod sunt numere întregi. Deci, dacă găsiți punctul funcției maxime (71), pe un OKEMNF poligon. coordonatele acestui punct și pentru a determina programul optim al problemei.

Pentru a face acest lucru, vom construi un vector și o linie care trece prin deciziile poligon OKEMNF (numărul 12 este arbitrar). Construcția de Direct se mută într-o direcție a vectorului, atâta timp cât nu trece prin ultimul punct în comun cu datele sale de poligon. Coordonatele acestui punct și a determina cel mai bun plan, iar valoarea funcției obiectiv este maximizată.

În acest caz, un punct E dorit (1, 3), în care funcția țintă presupune o valoare maximă C. fost consistente, coordonatele punctului E se determină problema optimă (70) - (73). În conformitate cu acest plan, compania trebuie să achiziționeze un set de echipamente de tip 1 și tip II trei seturi de echipamente. Acest lucru va oferi companiei cu restricțiile sale existente privind instalațiile de producție și fonduri de creșterea maximă a producției de 14 de unități. pe schimb.

Pentru munca poate fi folosit pentru a cere mecanisme. Performanță i-lea mecanism atunci când lucrarea J--lea este. Presupunând că fiecare mecanism poate fi utilizat numai pentru un singur loc de muncă, și fiecare loc de muncă poate fi efectuată de către un singur mecanism, mecanismele de securizare a determina care poate oferi cele mai bune performanțe. Construirea unui model matematic al problemei.

Decizie. Introducem Xij variabilă. a cărei valoare este de 1, dacă este utilizat mecanismul th j- atunci când operațiunea j--lea, și este 0 altfel. Apoi, condițiile de utilizare a fiecărui mecanism este doar un loc de muncă poate fi exprimată prin ecuații

precum și condițiile de muncă este doar un singur mecanism - egalitati

Astfel, problema este de a determina valorile necunoscutelor care satisfac sistemul de ecuații (74) și (75) și condiția (76), la care valoarea maximă a funcției

Problema formulată este o problemă de programare întreg.

Determinarea problemei optime de programare planul întreg. Luați în considerare problema de programare întreg în care atât funcția țintă, și funcția în sistemul de constrângeri sunt liniare. În acest sens, formulăm problema de bază a programării liniare, în care variabilele pot lua numai valori întregi. În termeni generali, această problemă poate fi scrisă după cum urmează: a găsi maximul funcției

Dacă găsiți o soluție la problema (78) - (81) metoda simplex, acesta poate fi fie un număr întreg sau nu (un exemplu al problemei de programare liniară a cărei soluție este întotdeauna un număr întreg, este o problemă de transport.). În cazul general, pentru a determina programul optim al problemei (78) - (81) necesita tehnici speciale. În prezent, există mai multe astfel de metode, dintre care cel mai cunoscut este metoda de Gomory. bazat pe metoda simplex descrisă mai sus.

Metoda Gomory. Găsirea de soluții ale problemei programării întregi prin Gomory începe cu o definiție a metodei simplex programul optim al problemei (78) - (80) fără variabile întregi. Odată ce acest plan este găsit, componentele sale de navigare. Dacă există, printre componentele numerelor fracționare, a găsit planul este cel mai bun plan de problemă de programare număr întreg (78) - (81). Dacă în planul optim al problemei (78) - (80) variabilă este o valoare fracțională, atunci sistemul de ecuații (79) se adaugă la inegalitatea

și de a găsi o soluție la problema (78) - (80) (82).

În (82), și - valorile de referință transformate și valorile care sunt luate din ultimul tabel simplex, a și - fracțiuni de numere întregi (o porțiune fracționată a unui număr de bine înțeles cel mai mic număr întreg nenegativ b astfel încât diferența dintre a și b este un număr întreg). Dacă în planul optim al problemei (78) - (80) valori fracționare iau mai multe variabile, inegalitate suplimentară (82) este determinată de cea mai mare fracțiune.

Dacă în ceea ce privește rezultatele (78) - (80), (82), variabilele sunt valori fracționare, apoi se adaugă din nou una de restricție suplimentară și procesul de calcul se repetă. Printr-un număr finit de iterații, sau pentru a obține cel mai bun plan pentru problema de programare întreg (78) - (81), sau setați-l nerezolvat.

În cazul în care cererea este întreg (81) se aplică numai anumitor variabile, astfel de sarcini sunt numite întreg mixte. Ele sunt, de asemenea, soluții consistente pentru aceste probleme, fiecare dintre acestea fiind obținute din cea anterioară prin introducerea unor constrângeri suplimentare. În acest caz, o astfel de limitare este de forma

care sunt determinate de următoarele relații:

1) care poate accepta valori non-întregi,

2), care poate presupune numai valori întregi,

Rezultă din cele de mai sus rezultă că procesul de determinare a planului optim întreg problemă de programare metoda Gomori include următorii pași.

1. Folosind metoda simplex, găsiți soluția problemei (78) - (80), fără a lua în considerare cerințele unei variabile întregi.

2. Se aduce constrângere suplimentară pentru variabila în planul optim al problemei (78) - (80) are o valoare fracțională maximă, iar planul optim al problemei (78) - (81) trebuie să fie un număr întreg.

3. Utilizând metoda dublă simplex. găsi o soluție la problema, care se obține din problema (78) - (80), ca urmare a aderării suplimentare restricții.

4. Dacă este necesar, constituie o altă restricție suplimentară și să continue procesul iterativ până când problema optimă (78) - (81) sau pentru a stabili insolubilității sale.

Metoda Gomory pentru a găsi valoarea maximă a funcției

Dă o interpretare geometrică a soluției.

Decizie. Pentru a determina programul optim al problemei (86) - (89) să găsim mai întâi programul optim al problemei (86) - (88) (Tabelul 22.).

Acum vom găsi valoarea maximă (86) în condițiile (87), (88) și (90) (tabelul. 23).

văzut din Tabelul 23 că problema inițială a programării întreg este planul optim w i-lea acest sens, valoarea funcției obiectiv este egală. Să ne dea o interpretare geometrică a soluției. Domeniul de aplicare a soluțiilor admisibile ale problemei (86) - (88) este OABCD poligon (fig.12.). Fig. 12 arată că valoarea maximă a funcției țintă presupune punctul C (19/2; 7/2), t e .. X = (19/2, 7/2, 0, 0, 34) este planul optim. Este imediat clar din tabelul 22. Deoarece X = (19/2, 7/2, 0, 0, 34) nu este un program optim (86) - (89) (și numere - fracționată), se introduce constrângerea suplimentară . Excluderea din ea și înlocuind valorile respective ale acestor constrângeri ale sistemului ecuații (87), obținem din obturatoare triunghi poligon OABCD EFC.

După cum se poate observa din Fig. 12, zona de soluții fezabile care rezultă problema este OABEFD poligon. La punctul E (9, 4) al poligonului functiei obiectiv a problemei ia valoarea maximă. Deoarece coordonatele punctelor E - întregi și necunoscut, și primesc o valoare întreagă atunci când este substituită în ecuația (87) valorile și planul optim este problema (86) - (89). Rezultă din tabelul 23.

Metoda Gomory pentru a găsi o soluție la problema a fost de a determina valoarea maximă a funcției

Dă o interpretare geometrică a soluției.

Decizie. Formulați problema rescris după cum urmează: a găsi valoarea maximă a funcției

Problema (95) - (98) este parte integrantă, deoarece variabilele și pot accepta valori non-întregi.

Găsiți soluția metoda simplex zadayai (95) - (97) (Tabelul 24).