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

(Перенаправлено з Дискретне програмування)

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

Цілочисельне програмування
Формула
Підтримується Вікіпроєктом Вікіпедія:Проєкт:Математика
Обчислювальна складність NP-повна задача

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

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

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

ред.

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

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

Джерела

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

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

ред.