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

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Дискретне програмування)
Перейти до навігації Перейти до пошуку
Цілочисельне програмування
Формула
Підтримується Вікіпроєктом Вікіпедія:Проєкт:Математика
Обчислювальна складність NP-повна задача

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

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

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

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

[ред. | ред. код]

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

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

Джерела

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

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

[ред. | ред. код]