Celočíselné programování

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

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

přičemž:

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. C ⊆ {1,…,n} je množina indexů proměnných, které mají být celočíselné.

Patří sem např.:

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. 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í.

Reference

  • Jan Pelikán: Diskrétní modely v operačním výzkumu, Professional Publishing, Praha 2001

Externí odkazy