Co je celočíselné lineární programování?
Problémy s celočíselným lineárním programováním vznikají při pokusu o řešení lineárních systémů a zároveň stanoví, že všechny neznámé proměnné musí být celá čísla nebo celá čísla. Lineární systémy jsou množiny rovnic, které popisují situaci, pro kterou se programátor snaží najít řešení. Obvykle se skládají z jedné rovnice, která musí být maximalizována nebo minimalizována a jedné nebo více omezující rovnice, která omezuje neznámé proměnné. Aby byl systém lineární, musí být každé omezení lineární rovnicí; to znamená, že nesmí obsahovat žádné instance neznámé proměnné s exponenty většími než jedna.
Pravidelné lineární systémy lze snadno řešit pomocí počítače. Program může identifikovat řešení tak, že najde derivát a nastaví ho na nulu. Poté může ověřit, že bod je maximum nebo minimum, kontrolou jeho bezprostředního okolí funkce. Pokud je derivát definován v každém bodě funkce, počítač má pouze omezený počet možných řešení ke kontrole.
Lineární programování se stává celočíselným lineárním programováním s přidáním celočíselného omezení. To znamená, že problém zůstává stejný, ale odpověď musí sestávat z celočíselných hodnot pro neznámé hodnoty: musí to být celá čísla. Někdy to znamená, že řešení bude suboptimální ve srovnání s případem, ve kterém jsou frakce povoleny; odráží však skutečný svět, ve kterém položky často přicházejí v diskrétních, nedělitelných jednotkách. Díky tomu je pro podnikové aplikace důležité celočíselné lineární programování, protože firmy chtějí maximalizovat zisky v maximální možné míře, ale nemohou se rozhodnout prodat zlomek produktu.
Jakmile jsou zavedena celočíselná omezení, problém řešení lineárního systému je NP-kompletní. To znamená, že čas, který počítač potřebuje k vyřešení systému, je neurčitý. S celočíselnými omezeními nemohou počítače použít nástroj derivace, protože neexistuje žádná záruka, že nulový bod derivace bude klesat na celé číslo. Řešením bude celé číslo s nejvyšší nebo nejnižší hodnotou ze všech celých čísel, takže počítač by je musel zkontrolovat všechny - proces, který by mohl trvat nekonečné množství času.
Programátoři vyvinuli heuristiku nebo metody řešení problémů, aby se vypořádali se složitostí těchto problémů. Jednou z metod řešení celočíselných úloh lineárního programování je algoritmus větvení a vázání, ve kterém počítač řeší řadu problémů souvisejících s původním, aby se zúžil dostupný rozsah hodnot na jedno řešení. U složitých problémů to však může trvat dlouho.