Gömöry metoda. Řešení celočíselných úloh programování

váhové problémy ekonomické, plánování a dokonce i problémy z jiných sférách lidské životními problémy spojené s proměnnými v souvislosti s celými čísly. Jako výsledek své analýzy a hledání nejlepších způsobů, jak řešit pojem extrémním výzvám. Jeho funkce je výše uvedená funkce trvá celočíselnou hodnotu, a úkol sám o sobě je považována matematiku jako celočíselného programování.

Hlavní využití problémy s proměnnou, celé číslo, je optimalizace. Metoda, která využívá celé číslo lineárního programování, také nazýván cut-off metody.

Gömöry metoda byla pojmenovaná po matematikovi, který byl vyvinut v letech 1957-1958 algoritmu je stále široce používá k řešení problémů celočíselné lineární programování. Kanonická forma číslo programovací problém umožňuje přístup a plně popisují výhody tohoto způsobu.

Způsob Gömöri aplikovat na lineární programování značně komplikuje úkol najít optimální hodnoty. Po celistvosti je základním požadavkem, dále všechny parametry daného problému. Existují případy, kdy tento problém tím, že má platné (integer) plány, přítomnost v objektivní funkce omezení přípustného setu rozhodnutí přijde k dosažení maxima. To je vzhledem k její nedostatek je integrální řešení. Aniž by za stejných podmínek, zpravidla v podobě rozhodnutí je vhodný vektor.

Ospravedlnit numerické algoritmy pro řešení problémů je třeba provést další překrývání různých podmínek.

Použitím metody z Gomory, obvykle zvažují mnoho plánů tzv problém omezených polyhedron řešení. Na tomto základě je množina všech integrálního plánu má konečnou hodnotu pro daný úkol.

Také pro záruční integrovanou funkci předpokládat, že hodnoty koeficientů jsou také celá čísla. Navzdory závažnosti těchto podmínek, slabší jim podaří alespoň některé.

Metoda Gömöry v podstatě zahrnuje omezení budov, které se prolínají řešení, která nejsou nonintegral. V tomto případě neexistuje žádný cut-off ne celočíselné řešení plán.

Algoritmus pro řešení tohoto problému zahrnuje hledání vhodných možností simplex metody, aniž by s přihlédnutím k podmínkám celistvosti. Jsou-li všechny komponenty optimální plán obsahuje rozhodnutí související s celými čísly, lze předpokládat, že celočíselné programování cíle je dosaženo. Možná, že je nalezen nerozpustnost problému, takže máme důkaz, že celočíselné programování problém nemá řešení.

Varianta, kdy jsou součásti optimální řešení obsahuje množství non-celé číslo. V tomto případě se nová omezení se přidá do všech omezení tohoto problému. Nové omezení se vyznačují řadou vlastností. Především by mělo být lineární, by měla být odříznut od nalezeno sady neceločíselný optimální plán. Ani celé číslo řešení by neměl být ztracen, odříznut.

Při vytváření omezení by měla být zvolena složka optimální plán s nejvyšší frakce. Je toto omezení bude přidána do stávající simplex tabulky.

Najdeme řešení vzniklého problému za použití běžných transformaci simplex. Ověříme řešení problému o existenci celočíselné optimálního plánu, je-li podmínka splněna, pak je problém vyřešen. Pokud se výsledek opět získá za přítomnosti non-celočíselné řešení, pak zavést další omezení, a opakujte postup výpočtu.

Poté, co provedl konečný počet iterací, abychom dosáhli optimálního programu problému způsobeného před celočíselné programování, nebo prokázat nerozpustnost problému.