Celočíselné programovanie

Celočíselné programovanie je odvetvie optimalizácie, prvá úloha celočíselného programovania bola riešena v roku 1958.

Úloha

Úlohou celočíselného programovania je optimalizačná úloha

$\min _{x\in M}f(x)$

navyše s podmienkou, že premenné nadobúdajú len celočíselné hodnoty. Ak niektoré z premenných môžu nadobúdať hodnoty neceločíselné, ide o úlohu zmiešanú.

Najčastejší typ: lineárneho celočíselného programovania, ktoré rieši úlohu

$\min _{x\in M}c^{T}x,$

pričom:

• $c^{T}x$ označuje skalárny súčin vektorov c, x
• množina prípustných riešení M je popísaná sústavou

$Ax=b,\quad x\geq 0,\quad x_{i}\in \mathbb {Z} {\mbox{ pro }}i\in C$

kde A je matica rozmeru m × n, b je m-rozmerný vektor a c, x sú n-rozmerné vektory. Súčin Ax označuje súčin matíc. C ⊆ {1,…,n} je množina indexov premenných, ktoré majú byť celočíselné.

Patrí sem napr.:

• problém obchodného cestujúceho
• problém batohu

Metódy riešenia

Metódy riešenia celočíselného programovania:

• metódy sečných nadrovín (metóda rezov): riešime úlohu bez podmienok celočíselnosti. Ak je získané optimálne riešenie neceločíselné, potom odrežeme kus množiny prípustných riešení M, obsahujúcu bod x, ale v ktorom neleží žiadny celočíselný bod. Postup opakujeme až nájdeme celočíselné riešenie (pre niektoré konkrétne algoritmy je konvergencia zaručená).
• metóda vetvenia a medzí (branch & bound): úlohu rozdelíme na dve podúlohy a riešime rekurzívne.

Pre lineárne celočíselné programovanie existujú ďalšie špeciálne algoritmy (Gomory,…).

Referencie

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

Externé odkazy

• http://cam.zcu.cz/~ryjacek/students/ps/TGD2.pdf Archivované 2003-07-28 na Wayback Machine (str 43 – 56)
• http://dce.felk.cvut.cz/rdu/rozvrhovani/download/rdu_c1.pdf^{[nefunkčný odkaz]} (užitočné odkazy)
• http://www1.osu.cz/studium/mopv2/celocis Archivované 2008-12-25 na Wayback Machine
• http://www.fhi.sk/files/katedry/kove/predmety/Linearne_programovanie/Fendek/LP_Int_progr_ii.pdf^{[nefunkčný odkaz]} (Gomoryho algoritmus)