Область допустимых решений
Материал из Википедии — свободной encyclopedia
В теории оптимизации допустимая область, допустимое множество, пространство поиска или пространство решений — это множество всех возможных точек (значений переменных) задачи оптимизации, которые удовлетворяют ограничениям[англ.] задачи. Эти ограничения могут включать неравенства, равенства и требование целочисленности решения [1][2]. Область допустимых решений является начальной областью поиска кандидатов в решение задачи, и эта область во время поиска может сужаться.
Например, возьмём задачу
- Минимизировать
с ограничениями на переменные и
и
В этом случае область допустимых решений представляет собой множество пар (x1, x2), для которых значение x1 не меньше 1 и не больше 10, а значение x2 не меньше 5 и не больше 12. Заметим, что множество допустимых решений рассматривается отдельно от целевой функции, которая определяет критерий оптимизации и которая в вышеприведённом примере равна
Во многих задачах допустимая область решений включает ограничение, по которому одна и более переменных должны быть неотрицательными. В задачах чисто целочисленного программирования множество допустимых решений состоит из целых чисел (или некоторого подмножества). В задачах линейного программирования область допустимых решений является выпуклым политопом — областью в многомерном пространстве, границы которого образованы гиперплоскостями[1].
Удовлетворение ограничений — это процесс поиска точки в области допустимых решений.