Način Homori. Rješavanje problema s programom cijelih brojeva

Masa problema ekonomske prirode, planiranje problema, pa čak i rješavanje pitanja iz drugih sfera ljudske životne aktivnosti povezano je s varijablama koje se odnose na cijele brojeve. Kao rezultat njihove analize i traženja optimalnih metoda rješavanja pojavio se pojam ekstremnog problema. Njegove značajke su gore navedena značajka za uzimanje cijele vrijednosti, a sam problem se tretira u matematici kao cjelobrojnom programiranju.

Glavni smjer korištenja zadataka s varijablama koje uzimaju cijele vrijednosti je optimizacija. Metoda koja koristi cjelobrojno linearno programiranje naziva se i metoda clippinga.

Metoda Homori je dobila ime po imenu matematičara, koji je prvi put razvio 1957-1958 algoritam, koji je i dalje široko korišten za rješavanje cjelobrojnih linearnih problema u programiranju. Kanonski oblik cijelog programskog problema omogućava potpuno otkrivanje prednosti ove metode.

Gomori metoda za linearno programiranje značajno komplicira problem pronalaženja optimalnih vrijednosti. Uostalom, cijeli broj je glavni uvjet, uz sve parametre problema. Nije neuobičajeno za neki problem, kada postoji izvediv (cijeli plan), ako objektna funkcija ima ograničenja na dopušten skup, rješenje ne postiže maksimalnu vrijednost. To je zbog nedostatka cjelovitih rješenja. Bez ovog istog stanja, u pravilu, pogodan je vektor u obliku rješenja.

Kako bi potkrijepili numeričke algoritme u rješavanju problema, postaje potrebno nadopuniti različite dodatne uvjete.

Koristeći Gomori metodu, skup planova problema obično se smatra ograničenim tzv. Polytope rješenja. Iz toga proizlazi da skup cjelovitih planova za predmetni problem ima konačnu vrijednost.

Također, kako bi se osigurala cjelovitost funkcije, pretpostavlja se da su vrijednosti koeficijenata također cijeli brojevi. Unatoč ozbiljnosti takvih stanja, oni se mogu poslati na malo.

Homorijeva metoda zapravo uključuje izgradnju ograničenja koja odbijaju odluke koje nisu cjelovite. U ovom slučaju, ne postoji odstupanje od bilo kakvog rješenja za cijeli cijeli plan.

Algoritam za rješavanje problema uključuje pronalaženje odgovarajućih varijanti jednostavnom metodom, bez uzimanja u obzir cjelovitih uvjeta. Ako u svim komponentama optimalnog plana postoje rješenja koja se odnose na cijele brojeve, tada možemo pretpostaviti da je cilj cjelovitog programiranja postignut. Moguće je otkriti neodlučivost problema, tako da dobivamo dokaz da problem cjelovitog programiranja nema rješenje.

Varijacija je moguća kada u sastavnim dijelovima optimalnog rješenja postoje nebrojni brojevi. U ovom slučaju, novo ograničenje dodaje se svim ograničenjima zadatka. Novo ograničenje karakterizira prisutnost niza svojstava. Prije svega, on mora biti linearan, mora odrezati ne-cjelobrojni plan iz pronađenog optimalnog skupa. Nijedna cjelovita rješenja ne smije biti izgubljena, odsječena.

Prilikom konstruiranja ograničenja, trebate odabrati komponentu optimalnog plana s najvećim djelomičnim dijelom. To je ovo ograničenje koje će biti dodano postojećoj jednostavnoj tablici.

Otkrijemo dobiveni problem pomoću običnih jednostavnih transformacija. Provjeravamo rješenje problema za prisutnost cjelobrojnog optimalnog plana, ako je uvjet zadovoljen, tada se problem riješi. Ako se ponovno dobije rezultat s prisutnošću ne-cjelovitih rješenja, onda uvodimo dodatno ograničenje i ponavljamo postupak izračuna.

Nakon provedenog konačnog broja iteracija dobivamo optimalan plan problema koji se postavlja prije integer programiranja ili dokazati nerješivost problema.