Metoda Homori. Řešení celočíselných programovacích problémů

Mnoho problémů ekonomické povahy, problémy s plánováním a dokonce i řešení otázek z jiných sfér lidské činnosti jsou spojeny s proměnnými, které se vztahují k celému číslu. V důsledku jejich analýzy a hledání optimálních metod řešení se objevila koncepce extrémního problému. Jeho vlastnosti jsou výše uvedeným prvkem, aby získaly celočíselnou hodnotu a samotný problém je v matematice zpracován jako celé programování.

Jako hlavní směr použití úkolů s proměnnými, které berou celočíselné hodnoty, je optimalizace. Metoda, která používá celé číslo lineární programování, stále nazýváme metodou ořezávání.

Metoda Homory získala své jméno jménem matematika, který nejprve vyvinul v letech 1957-1958 algoritmus, který je stále široce používán pro řešení celočíselných lineárních programovacích problémů. Kanonická forma celočíselného programovacího problému umožňuje plně odhalit výhody této metody.

Metoda Gomori pro lineární programování podstatně komplikuje problém nalezení optimálních hodnot. Koneckonců, celé číslo je hlavní podmínkou, kromě všech parametrů problému. Není neobvyklé, že má nějaký problém, pokud má nějaký plán (celočíselný) objektivní funkce omezení přípustné sady, nedosahuje maximální hodnoty v řešení. To je způsobeno absencí celočíselných řešení. Bez této podmínky je zpravidla vhodný vektor ve formě řešení.

Pro ospravedlnění číselných algoritmů při řešení problémů je nutné překrýt různé dodatečné podmínky.

Pomocí metody Gomori je soubor plánů problémů obvykle považován za ohraničený tzv. Polytope řešení. Z toho plyne, že soubor všech integrovaných plánů pro daný problém má konečnou hodnotu.

Také, aby byla zaručena celočíselnost funkce, předpokládá se, že koeficienty hodnot jsou také celá čísla. Navzdory závažnosti těchto podmínek mohou být posláni kousek.

Metoda Homori ve skutečnosti zahrnuje konstrukci omezení, které oddělují rozhodnutí, která nejsou integrální. V tomto případě neexistuje žádné oříznutí jakéhokoli řešení pro celočíselný plán.

Algoritmus pro řešení problému zahrnuje nalezení vhodných možností simplexní metoda, neberouc v úvahu celočíselné podmínky. Pokud ve všech složkách optimálního plánu existují řešení týkající se celých čísel, můžeme předpokládat, že je dosaženo cíle celočíselného programování. Je možné, že se odhalí nerozhodnutelnost problému, takže dostaneme důkaz, že problém s celočíselným programováním nemá řešení.

Varianta je možná, pokud v součástech optimálního řešení existují nečíselná čísla. V tomto případě je nové omezení přidáno ke všem omezením úkolu. Pro nové omezení je charakteristické několik vlastností. Nejprve musí být lineární, musí odříznout neurčitý plán z nalezené optimální množiny. Žádné jednotné řešení by nemělo být ztraceno, odříznuto.

Při konstrukci omezení je nutné vybrat součást optimálního plánu s největší částí. Toto omezení bude přidáno do již existující simplexní tabulky.

Řešení získaného problému nalezneme pomocí obyčejných simplexních transformací. Kontrolujeme řešení problému přítomnosti celočíselného optimálního plánu, pokud je podmínka splněna, problém je vyřešen. Jestliže výsledek byl opět získán za přítomnosti necelových řešení, zavádíme další omezení a opakujeme proces výpočtu.

Po provedení konečného počtu iterací získáme optimální plán problému před celočíselným programováním nebo dokážeme nerozpoznatelnost problému.