Diskrétní programování

Diskrétní programování ( diskrétní optimalizace ) je odvětví matematického programování .

Na rozdíl od optimalizačních problémů se spojitými proměnnými nabývají proměnné v problémech diskrétního programování pouze diskrétní hodnoty, jako jsou celá čísla.

Problémy kombinatorické optimalizace lze řešit pomocí metod diskrétního programování. Jednou z hlavních metod řešení problémů diskrétního programování jsou metoda cut-off [1] , metoda větvení a vazby [2] a dynamické programování [3] .

Příklady problémů

• Problém s přiřazením
• Problém s batohem
• Problém cestujícího prodejce
• Úkoly teorie plánování
• Přepravní úkol
• Problémy s pokrytím grafu

Poznámky

1. ↑ Korbut, 1969 , s. 98.
2. ↑ Korbut, 1969 , s. 213.
3. ↑ Korbut, 1969 , s. 251.

Literatura

• Korbut A.A. , Finkelstein Yu.Yu. Diskrétní programování. - M. : Nauka, 1969. - 368 s.
• Khokhlyuk V. I. Diskrétní optimalizační metody. Tutorial. NSU , ​​2013. 154 s.
• Kombinatorické metody a algoritmy pro řešení vysokorozměrných diskrétních optimalizačních problémů: [monografie] / V. R. Chačaturov , Veselovskij V. E., Zlotov A. V., Kaldybaev S. U., Kaliev E. Zh., Kovalenko A. G., Montlevich R. M., Sigal I. Khachaturov. V .; [Resp. vyd. V.V. Shkurba ]; Ros. akad. vědy. Calc. centrum. - M.: Nauka, 2000. - 353, [1] str. : ill., tab.; 22 cm; ISBN 5-02-008311-9