Loading AI tools
З Вікіпедії, вільної енциклопедії
Цілочисельне програмування — різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами.
Цілочисельне програмування | |
Формула | |
---|---|
Підтримується Вікіпроєктом | Вікіпедія:Проєкт:Математика |
Обчислювальна складність | NP-повна задача |
Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами.
Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність.
До часткового випадку задачі цілочисельного лінійного програмування відносяться задачі, де змінні X можуть приймати всього лише два значення — 0 і 1. Відповідні задачі часто називають задачами булівського програмування. Найвідоміші із цих задач — задачі про призначення (якого працівника на яку роботу поставити), задачі вибору маршруту (задача комівояжера, задача листоноші) тощо.
Для розв'язання задач цього типу розробляються специфічні алгоритми, засновані на комбінаториці, графах тощо.
![]() |
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.