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

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

Kako je glavni smjer korištenja zadataka s varijablama koje uzimaju cijele vrijednosti, to je optimizacija. Metoda koja koristi cijeli broj linearno programiranje, još uvijek nazivamo metodom clippinga.

Metoda Homory dobio je ime pod imenom 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 znatno komplicira problem pronalaženja optimalnih vrijednosti. Uostalom, cijeli broj je glavni uvjet, uz sve parametre problema. Nije neuobičajeno za neki problem, ako postoji mogući (cjelobrojni) plan, ako objektivne funkcije ograničenja dopuštenog seta, ne doseže maksimalnu vrijednost u rješenju. To je zbog nedostatka cjelovitih rješenja. Bez ovog stanja, u pravilu, pogodan je vektor u obliku rješenja.

Kako bi opravdali 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 zajamčila cjelovitost funkcije, pretpostavlja se da su koeficijenti vrijednosti također cijeli brojevi. Unatoč težini takvih uvjeta, 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 rezanje bilo kojeg rješenja cijelog plana.

Algoritam za rješavanje problema uključuje pronalaženje odgovarajućih opcija jednostavna metoda, ne uzimajući u obzir cjelovite uvjete. Ako se u svim komponentama optimalnog plana nalaze 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 cjelokupni programski problem 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. Za novo ograničenje, niz svojstava je karakterističan. Prije svega, on mora biti linearan, mora odrezati ne-cijeli plan od pronađenog optimalnog skupa. Nijedna cjelovita rješenja ne smije biti izgubljena, odsječena.

Prilikom konstrukcije ograničenja potrebno je odabrati komponentu optimalnog plana s najvećim dijelom. To je ovo ograničenje koje će se dodati već 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 obračuna.

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