Celočíselné lineární programování

Abstract

Práce je věnována metodám řešení standardních úloh lineárního programování. V teoretické části jsou popsány základní algoritmy pro řešení neceločíselných úloh. Všechny algoritmy jsou popsány nejdříve zcela obecně, nicméně pro jejich lepší pochopení neformálně. Následně jsou demonstrovány na příkladech, které jsou vypracovány dostatečně podrobně na to, aby byl případný čtenář schopen řešit obdobné úlohy samostatně. Ve zcela stejném duchu jsou pak popsány dvě základní metody pro řešení celočíselných úloh metoda Gomoryho řezů a metoda větví a mezí , které jsou založeny na znalosti jejich neceločíselných řešení. Praktická část nabízí jednoduchý program s přívětivým uživatelským prostředí pro řešení úloh popsaných v teoretické části. Je určen jednak k řešení obdobných úloh, ale především ke kontrole samostatně řešených úloh, ať již neceločíselných, tak celočíselných.