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

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)