--- title: "Celočíselné programování" source: "https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD" wiki: "systems-analysis.info/int" article: "Celočíselné_programování" language: "cs" categories: - "Category:Czech" - "Category:Operations research" revision_id: 839 wiki_created_at: 2026-09-06T22:39:33Z wiki_modified_at: 2026-09-06T22:39:33Z downloaded_at: 2026-09-07T22:42:37Z --- # Celočíselné programování **Celočíselné programování** (**CP**; angl. *integer programming, IP*) — je odvětví matematické optimalizace, které se zabývá úlohami, kde některé nebo všechny proměnné musí nabývat pouze celočíselných hodnot[\[1\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-ru-wiki-ip-1). Nejprozkoumanějším speciálním případem je **celočíselné lineární programování** (**CLP**; angl. *integer linear programming, ILP*), kde účelová funkce i omezení jsou lineární. Na rozdíl od lineárního programování, kde proměnné mohou nabývat libovolných reálných hodnot, požadavek celočíselnosti činí úlohy CP výrazně obtížněji řešitelnými[\[2\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-wolsey-book-2). Celočíselné programování nachází široké uplatnění v ekonomice, logistice, plánování výroby a dalších oblastech, kde jsou proměnné ze své podstaty diskrétní (například počet vyrobených jednotek produkce nebo počet pracovníků)[\[3\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-pisaruk-book-3). ## Definice a terminologie Obecná úloha celočíselného lineárního programování může být zapsána následovně: Najít vektor $x$, který: maximalizuje (nebo minimalizuje) $c^{T}x$ při podmínkách: $Ax \leq b$ $x \geq 0$ $x \in {\mathbb{Z}}^{n}$ (všechny složky vektoru $x$ jsou celá čísla) kde $x$ — vektor proměnných, $c$ a $b$ — vektory a $A$ — matice koeficientů[\[4\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-conforti-book-4). V závislosti na požadavcích na proměnné se rozlišují následující typy úloh: - **Čistě celočíselné programování**: všechny proměnné musí být celé. - **Smíšeně celočíselné programování** (angl. *mixed-integer programming, MIP*): pouze část proměnných musí být celočíselná. - **Booleovské (0-1) programování**: proměnné nabývají pouze hodnot 0 nebo 1, což umožňuje modelovat logická rozhodnutí typu „ano/ne". ## Klíčové vlastnosti a složitost ### Výpočetní složitost Úloha celočíselného lineárního programování je v obecném případě NP-těžká[\[5\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-karp-1972-5). To znamená, že neexistuje žádný známý algoritmus schopný nalézt přesné optimální řešení pro libovolnou úlohu CP v polynomiálním čase. Složitost je dána kombinatorickou povahou úlohy, neboť počet možných celočíselných řešení může s rostoucím počtem proměnných růst exponenciálně. ### Vztah k lineárnímu programování (LP-relaxace) Pro každou úlohu CP lze formulovat její **lineární relaxaci** — úlohu lineárního programování (LP), v níž je vypuštěn požadavek celočíselnosti proměnných. Řešení LP-relaxace má dvě důležité vlastnosti: 1. Lze jej nalézt výrazně rychleji (v polynomiálním čase). 2. Optimální hodnota účelové funkce LP-relaxace poskytuje odhad (horní hranici pro úlohu maximalizace a dolní pro minimalizaci) optimální hodnoty původní celočíselné úlohy[\[2\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-wolsey-book-2). Jednoduché zaokrouhlení zlomkového řešení LP-relaxace na nejbližší celá čísla však zpravidla nevede k optimálnímu ani přípustnému řešení celočíselné úlohy[\[1\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-ru-wiki-ip-1). ### Vlastnost totální unimodularity Existuje důležitá třída úloh CLP, které se řeší stejně snadno jako jejich LP-relaxace. Jsou to úlohy, v nichž je matice omezení $A$ **totálně unimodulární** (tj. determinant každé její čtvercové podmatice se rovná 0, +1 nebo −1). Je-li matice $A$ totálně unimodulární a vektor $b$ celočíselný, pak jsou všechny vrcholy mnohostěnu přípustných řešení LP-relaxace automaticky celočíselné. Řešení nalezené simplexovou metodou tedy bude celočíselné[\[4\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-conforti-book-4). Příklady takových úloh jsou dopravní úloha a přiřazovací úloha. ## Metody řešení Pro řešení obecných úloh CP, které nevykazují vlastnost totální unimodularity, byly vyvinuty přesné metody založené na myšlence implicitního prohledávání. - **Metoda větví a mezí** (angl. *Branch and Bound*) — hlavní přesná metoda, založená na systematickém rozkladu množiny přípustných řešení na podmnožiny (větvení) a odřezávání těch podmnožin, které zjevně neobsahují optimální řešení. K hodnocení perspektivnosti podmnožin se využívá LP-relaxace[\[6\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-en-wiki-ip-6). - **Metoda řezných rovinek** (Gomoryho metoda; angl. *Cutting Plane Method*) — iterativní přístup, který postupně přidává k úloze nová lineární omezení („řezy"). Tyto řezy „odřezávají" zlomková řešení LP-relaxace, aniž by se dotkla jediného přípustného celočíselného řešení, a postupně přibližují oblast přípustných řešení LP-relaxace ke konvexnímu obalu celočíselných řešení[\[6\]](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_note-en-wiki-ip-6). Moderní řešiče zpravidla využívají hybridní algoritmy, jako je **metoda větví a řezů** (angl. *Branch and Cut*), která spojuje výhody obou přístupů. ## Příklady a oblasti použití Celočíselné programování umožňuje modelovat řadu klasických úloh kombinatorické optimalizace. - *Úloha o batohu*: klasická úloha 0-1 programování, v níž je třeba vybrat sadu předmětů s maximální celkovou hodnotou při nepřekročení omezení na celkovou hmotnost. - *Úloha obchodního cestujícího*: úloha hledání nejkratší trasy procházející zadanou množinou měst. Může být formulována jako úloha celočíselného programování, kde proměnné rozhodují o zařazení hran grafu do výsledné trasy. Díky své flexibilitě je CP jedním z nejžádanějších nástrojů v operačním výzkumu a nachází uplatnění v oblastech, jako jsou: - **Logistika a řízení dodavatelských řetězců**: optimalizace tras dopravy, rozmístění skladů, řízení zásob. - **Plánování výroby**: sestavování výrobních harmonogramů, alokace zdrojů, vytížení zařízení. - **Finance a ekonomika**: tvorba investičního portfolia, kapitálové rozpočtování. - **Telekomunikace a energetika**: projektování komunikačních sítí, plánování provozu energetických bloků. ## Viz také - Lineární programování - Metoda větví a mezí ## Poznámky 1. ↑ [1.0](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-ru-wiki-ip_1-0) [1.1](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-ru-wiki-ip_1-1) "Целочисленное программирование". *Википедия*. [1] 2. ↑ [2.0](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-wolsey-book_2-0) [2.1](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-wolsey-book_2-1) Wolsey, Laurence A. (2020). *Integer Programming* (2nd ed.). John Wiley & Sons. 3. [↑](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-pisaruk-book_3-0) Писарук Н.Н. (2010). *Модели и методы смешанного целочисленного программирования*. Минск: БГУ. 4. ↑ [4.0](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-conforti-book_4-0) [4.1](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-conforti-book_4-1) Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). *Integer Programming*. Springer. 5. [↑](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-karp-1972_5-0) Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: *Complexity of Computer Computations*. Springer. 6. ↑ [6.0](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-en-wiki-ip_6-0) [6.1](https://systems-analysis.info/int/Celo%C4%8D%C3%ADseln%C3%A9_programov%C3%A1n%C3%AD#cite_ref-en-wiki-ip_6-1) "Integer programming". *Wikipedia*. [2]