В математической оптимизации и информатике допустимая область, допустимое множество или пространство решений — это множество всех возможных точек (наборов значений переменных выбора) задачи оптимизации , которые удовлетворяют ограничениям задачи , потенциально включая неравенства , равенства и целочисленные ограничения. [1] Это начальный набор возможных решений задачи до того, как набор кандидатов был сужен.
Например, рассмотрим задачу минимизации функции относительно переменных и при условии и Здесь допустимый набор — это набор пар ( x , y ), в которых значение x не менее 1 и не более 10, а значение y не менее 5 и не более 12. Допустимый набор задачи отделен от целевой функции , которая устанавливает критерий оптимизации и которая в приведенном выше примере равна
Во многих задачах допустимое множество отражает ограничение, что одна или несколько переменных должны быть неотрицательными. В задачах чистого целочисленного программирования допустимое множество — это множество целых чисел (или некоторое его подмножество). В задачах линейного программирования допустимое множество — это выпуклый многогранник : область в многомерном пространстве, границы которой образованы гиперплоскостями , а углы — вершинами .
Удовлетворение ограничений — это процесс нахождения точки в допустимой области.
Выпуклое допустимое множество — это множество , в котором отрезок прямой, соединяющий любые две допустимые точки, проходит только через другие допустимые точки и не проходит через какие-либо точки за пределами допустимого множества. Выпуклые допустимые множества возникают во многих типах задач, включая задачи линейного программирования, и они представляют особый интерес, поскольку, если задача имеет выпуклую целевую функцию , которая должна быть максимизирована, ее, как правило, будет легче решить при наличии выпуклого допустимого множества, и любой локальный оптимум также будет глобальным оптимумом .
Если ограничения задачи оптимизации взаимно противоречивы, то нет точек, которые удовлетворяют всем ограничениям, и, таким образом, допустимая область является пустым множеством . В этом случае задача не имеет решения и называется недопустимой .
Допустимые множества могут быть ограниченными или неограниченными . Например, допустимое множество, определенное набором ограничений { x ≥ 0, y ≥ 0}, неограничено, поскольку в некоторых направлениях нет предела тому, как далеко можно зайти и все еще оставаться в допустимой области. Напротив, допустимое множество, образованное набором ограничений { x ≥ 0, y ≥ 0, x + 2 y ≤ 4}, ограничено, поскольку степень движения в любом направлении ограничена ограничениями.
В задачах линейного программирования с n переменными необходимым, но недостаточным условием для того, чтобы допустимое множество было ограничено, является то, чтобы число ограничений было не менее n + 1 (как показано в приведенном выше примере).
Если допустимое множество не ограничено, то может быть или не быть оптимума, в зависимости от специфики целевой функции. Например, если допустимая область определяется набором ограничений { x ≥ 0, y ≥ 0}, то задача максимизации x + y не имеет оптимума, поскольку любое возможное решение может быть улучшено путем увеличения x или y ; однако если задача состоит в минимизации x + y , то оптимум существует (в частности, при ( x , y ) = (0, 0)).
В оптимизации и других разделах математики , а также в алгоритмах поиска (тема в информатике ) возможное решение является членом множества возможных решений в допустимой области заданной задачи. [2] Возможное решение не обязательно должно быть вероятным или разумным решением задачи — оно просто находится в наборе, который удовлетворяет всем ограничениям ; то есть оно находится в наборе допустимых решений . Алгоритмы для решения различных типов задач оптимизации часто сужают множество возможных решений до подмножества допустимых решений, точки которого остаются в качестве возможных решений, в то время как другие допустимые решения в дальнейшем исключаются из числа кандидатов.
Пространство всех возможных решений, до того как были исключены все возможные точки, называется допустимой областью, допустимым множеством, пространством поиска или пространством решений. [2] Это множество всех возможных решений, которые удовлетворяют ограничениям задачи. Удовлетворение ограничений — это процесс нахождения точки в допустимом множестве.
В случае генетического алгоритма кандидатами на решения являются особи в популяции, эволюционирующие с помощью алгоритма. [3]
В исчислении оптимальное решение ищется с помощью теста первой производной : первая производная оптимизируемой функции приравнивается к нулю, и любые значения переменной(ых) выбора, которые удовлетворяют этому уравнению, рассматриваются как возможные решения (в то время как те, которые не удовлетворяют, исключаются как возможные решения). Существует несколько способов, при которых возможное решение может не быть фактическим решением. Во-первых, оно может давать минимум, когда ищется максимум (или наоборот), и, во-вторых, оно может не давать ни минимума, ни максимума, а скорее седловую точку или точку перегиба , в которой происходит временная пауза в локальном росте или падении функции. Такие возможные решения могут быть исключены с помощью теста второй производной , удовлетворение которого достаточно для того, чтобы возможное решение было по крайней мере локально оптимальным. В-третьих, возможное решение может быть локальным оптимумом , но не глобальным оптимумом .
При взятии первообразных мономов вида возможное решение с использованием квадратурной формулы Кавальери будет Это возможное решение на самом деле верно, за исключением случаев, когда
В симплексном методе решения задач линейного программирования вершина допустимого многогранника выбирается в качестве начального возможного решения и проверяется на оптимальность; если она отвергается как оптимальное, соседняя вершина рассматривается как следующее возможное решение. Этот процесс продолжается до тех пор, пока не будет найдено возможное решение, являющееся оптимальным.
