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.