В математической оптимизации и информатике допустимая область , допустимое множество или пространство решений — это набор всех возможных точек (наборов значений переменных выбора) задачи оптимизации , которые удовлетворяют ограничениям задачи , потенциально включая неравенства , равенства и целочисленные ограничения. [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]
В исчислении оптимальное решение ищется с использованием теста первой производной : первая производная оптимизируемой функции приравнивается к нулю, и любые значения переменных выбора, которые удовлетворяют этому уравнению, рассматриваются как возможные решения (в то время как те, которые не исключаются из числа кандидатов). Существует несколько причин, по которым возможное решение может не оказаться реальным решением. Во-первых, он может дать минимум, когда ищут максимум (или наоборот), а во-вторых, он может дать не минимум и не максимум, а, скорее, седловую точку или точку перегиба , в которой происходит временная пауза в локальном подъеме. или происходит падение функции. Такие возможные решения можно исключить с помощью теста второй производной , удовлетворение которого достаточно для того, чтобы возможное решение было, по крайней мере, локально оптимальным. В-третьих, возможное решение может быть локальным , но не глобальным оптимумом .
При выборе первообразных мономов вида возможное решение с использованием квадратурной формулы Кавальери будет: Это возможное решение фактически правильно, за исключением случаев, когда
В симплексном методе решения задач линейного программирования вершина допустимого многогранника выбирается в качестве исходного кандидата на решение и проверяется на оптимальность; если оно отклонено как оптимальное, соседняя вершина считается следующим кандидатом на решение. Этот процесс продолжается до тех пор, пока не будет найдено оптимальное возможное решение.
