Metoda Homori. Reševanje problemov celotnega programiranja

Veliko problemov gospodarske narave, problemov načrtovanja in celo reševanja vprašanj iz drugih področij človeške dejavnosti so povezane s spremenljivkami, ki se nanašajo na celo število. Kot rezultat njihove analize in iskanja optimalnih metod rešitve se je pojavil problem ekstremnih problemov. Njegove funkcije so zgornja značilnost, da se upošteva celoštevilčna vrednost, in problem se obravnava v matematiki kot celovito programiranje.

Kot glavna usmeritev uporabe nalog s spremenljivkami, ki imajo celostne vrednosti, je optimizacija. Metoda, ki uporablja celo število linearno programiranje, še vedno imenovan način izrezovanja.

Metoda Homory je dobila ime z matematikom, ki je najprej razvil leta 1957-1958 algoritem, ki se še vedno pogosto uporablja za reševanje celovitih problemov linearnega programiranja. Kanonska oblika celovitega programskega problema omogoča popolno odkrivanje prednosti te metode.

Metoda Gomori za linearno programiranje bistveno otežuje problem iskanja optimalnih vrednosti. Navsezadnje je poleg vseh parametrov problema glavni pogoj. Ni težko za težave, če imajo izvedljiv načrt (celo število), če objektivne funkcije omejitve dopustnega nabora, v raztopini ne dosežejo največ. To je posledica odsotnosti celovitih rešitev. Brez tega pogoja je praviloma ustrezen vektor v obliki raztopine.

Za utemeljitev numeričnih algoritmov pri reševanju problemov postane potrebno določiti različne dodatne pogoje.

S pomočjo metode Gomori se množica problemskih načrtov običajno obravnava kot omejen tako imenovani polytope rešitev. Iz tega sledi, da ima niz vseh integralnih načrtov zadevne težave končna vrednost.

Tudi, da se zagotovi celovitost funkcije, se domneva, da so koeficienti vrednosti tudi celo število. Kljub resnosti takih pogojev jih je mogoče poslati malo.

Metoda Homori dejansko vključuje gradnjo omejitev, ki odrečejo odločitve, ki niso neločljive. V tem primeru ni nobene rešitve za celovit načrt.

Algoritem za reševanje problema vključuje iskanje ustreznih možnosti simpleksna metoda, ne upoštevajo celih pogojev. Če v vseh komponentah optimalnega načrta obstajajo rešitve, povezane s celi števili, lahko sklepamo, da je cilj celovitega programiranja dosežen. Možno je, da se bo razkrila neodločljivost problema, zato dobimo dokaz, da problem integernega programiranja nima rešitve.

Možna je varianta, če so v komponentah optimalne rešitve neločene številke. V tem primeru se vsem omejitvam naloga doda nova omejitev. Za novo omejitev je značilno več lastnosti. Najprej mora biti linearna, mora odrezati ne celovit načrt iz najdenega optimalnega nabora. Ne sme biti izgubljena ena celovita rešitev.

Pri konstruiranju omejitve je treba izbrati komponento optimalnega načrta z največjim delnim delom. Ta omejitev bo dodana že obstoječi tabeli simplexa.

Rešitev pridobljene težave najdemo z uporabo navadnih preprostih transformacij. Preverimo rešitev problema za prisotnost celostnega optimalnega načrta, če je pogoj izpolnjen, potem je problem rešen. Če spet rezultat dobimo s prisotnostjo neločenih rešitev, potem uvajamo dodatno omejitev in ponovimo postopek izračuna.

Po izvedbi končnega števila iteracij dobimo optimalen načrt za problem, ki smo ga postavili pred celovitim programiranjem, ali dokazati nerešljivost problema.