Цілочисельне програмування

Цілочисельне програмування — різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами.

Цілочисельне програмування
Формула	${\displaystyle \sigma _{g}=\exp \left({\sqrt {\sum _{i=1}^{n}(\ln {A_{i} \over \mu _{g}})^{2} \over n}}\right).\qquad \qquad (1)}$
Підтримується Вікіпроєктом
Обчислювальна складність	NP-повна задача

Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами.

Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність.

Булівське програмування

До часткового випадку задачі цілочисельного лінійного програмування відносяться задачі, де змінні X можуть приймати всього лише два значення — 0 і 1. Відповідні задачі часто називають задачами булівського програмування. Найвідоміші із цих задач — задачі про призначення (якого працівника на яку роботу поставити), задачі вибору маршруту (задача комівояжера, задача листоноші) тощо.

Для розв'язання задач цього типу розробляються специфічні алгоритми, засновані на комбінаториці, графах тощо.

Джерела

• Пономаренко В. С. Цілочисельне програмування в економіці [Текст] / Пономаренко В. С., Голубничий Д Ю., Третяк В. Ф.. — X. : Вид. ХНЕУ, 2005. — 204 с.

Інтернет-ресурси

• A Tutorial on Integer Programming
• Conference Integer Programming and Combinatorial Optimization, IPCO
• The Aussois Combinatorial Optimization Workshop