Celočíselné programování

Technology

12 hours ago

Author

Albert Flores

Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958.

Úloha

Úlohou čistého (ryzího) celočíselného programování je optimalizační úloha

\min_{x \in M} f(x)

navíc s podmínkou, že proměnné nabývají pouze celočíselných hodnot. Pokud některé z proměnných mohou nabývat hodnot neceločíselných, jedná se o úlohu smíšeného celočíselného programování (na rozdíl od čistého).

Nejčastější typ: lineární celočíselné programování, které řeší úlohu

\min_{x\in M} c^Tx,

přičemž: * c^Tx označuje skalární součin vektorů c, x * množina přípustných řešení M je popsána soustavou Ax=b,\quad x\geq 0,\quad x_i\in\mathbb{Z}\mbox{ pro }i\in C : kde A je matice rozměru m × n, b je m-rozměrný vektor a c, x jsou n-rozměrné vektory. Součin Ax označuje součin matic. +more C ⊆ {1,…,n} je množina indexů proměnných, které mají být celočíselné.

Patří sem např.: * problém obchodního cestujícího (viz [2]) * problém batohu

Metody řešení

Metody řešení celočíselného programování: * metody sečných nadrovin (metoda řezů): řešíme úlohu bez podmínek celočíselnosti. Je-li získané optimální řešení neceločíselné, potom odřízneme kus množiny přípustných řešení M, obsahující bod x, ale ve kterém neleží žádný celočíselný bod. +more Postup opakujeme než nalezneme celočíselné řešení (pro některé konkrétní algoritmy je konvergence zaručena). * metoda větvení a mezí (branch & bound): úlohu rozdělíme na dvě podúlohy a řešíme rekursivně.

Pro lineární celočíselné programování existují další speciální algoritmy.

Pro úlohy kde A je totálně unimodulární matice lze s výhodou použít metody pro řešení úloh obecného lineárního programování.