Metoda lui Homori. Rezolvarea problemelor de programare întreg

Multe probleme de natură economică, probleme de planificare și chiar soluționarea întrebărilor din alte sfere ale activității umane sunt legate de variabile care se referă la numere întregi. Ca urmare a analizei lor și a căutării unor metode optime de soluționare, a apărut conceptul unei probleme extreme. Caracteristicile sale sunt caracteristica de mai sus pentru a lua o valoare intreg, iar problema in sine este tratata in matematica ca programare intreg.

Ca direcție principală de utilizare a sarcinilor cu variabile care iau valori întregi, este optimizarea. O metodă care utilizează un număr întreg programarea liniară, numită încă metoda de tăiere.

Metoda Gomory a fost numit după matematicianul, primul dezvoltat in 1957-1958 algoritm este încă utilizat pe scară largă pentru a rezolva întregi probleme de programare liniară. Forma canonică a problemei de programare întregă face posibilă descoperirea pe deplin a avantajelor acestei metode.

Metoda Gomori pentru programarea liniară complică în mod semnificativ problema găsirii valorilor optime. La urma urmei, întregul este condiția principală, pe lângă toți parametrii problemei. Nu este neobișnuit pentru o problemă, atunci când are un plan fezabil (întreg), dacă funcții obiective restricțiile privind setul admis, nu ating maximul în soluție. Acest lucru se datorează absenței soluțiilor întregi. Fără această condiție, ca regulă, un vector adecvat este sub forma unei soluții.

Pentru a justifica algoritmi numerici în rezolvarea problemelor, este necesar să se suprapună diferite condiții suplimentare.

Folosind metoda Gomori, setul de planuri de probleme este de obicei considerat a fi un numit așa-numit polytope de soluții. De aici rezultă că setul tuturor planurilor integrale pentru problema în cauză are o valoare finită.

De asemenea, pentru a garanta integeritatea unei funcții, se presupune că coeficienții valorilor sunt și numere întregi. În ciuda severității acestor condiții, ele pot fi trimise puțin.

Metoda lui Homori, de fapt, implică construirea unor constrângeri care întrerupe deciziile care nu sunt non-intregi. În acest caz, nu există nici o tăiere a oricărei soluții la planul întreg.

Algoritm pentru rezolvarea problemei implică găsirea opțiunilor corespunzătoare metoda simplex, fără a lua în considerare condițiile întregului. Dacă în toate componentele planului optim există soluții legate de numere întregi, atunci putem presupune că obiectivul programării întregi este atins. Este posibil ca o nedeclarabilitate a problemei să fie dezvăluită, deci avem o dovadă că problema programării întregului nu are nicio soluție.

O variantă este posibilă atunci când există numere non-întregi în componentele soluției optime. În acest caz, se adaugă o nouă restricție la toate constrângerile sarcinii. Pentru o nouă restricție, un număr de proprietăți sunt caracteristice. Mai întâi, trebuie să fie liniară, trebuie să taie planul non-întreg din setul optim găsit. Nu ar trebui să se piardă nici o singură soluție întregă, tăiată.

Atunci când se construiește constrângerea, este necesar să se aleagă componenta planului optim cu cea mai mare parte fracționată. Această restricție va fi adăugată la tabela simplă deja existentă.

Găsim soluția problemei obținute folosind transformări simplex obișnuite. Verificăm soluția problemei pentru prezența unui plan optim întreg, dacă condiția este satisfăcută, atunci problema este rezolvată. Dacă rezultatul a fost obținut din nou cu prezența unor soluții non-integer, atunci introducem o restricție suplimentară și repetăm ​​procesul de calcul.

După ce a efectuat un număr finit de iterații, vom realiza un program optim al problemei puse în fața programării întreg, sau dovedesc insolubilitatea problemei.