Região viável - Feasible region

Um problema com cinco restrições lineares (em azul, incluindo as restrições de não negatividade). Na ausência de restrições de número inteiro, o conjunto viável é toda a região delimitada por azul, mas com restrições de número inteiro é o conjunto de pontos vermelhos.

Uma região fechada viável de um problema de programação linear com três variáveis ​​é um poliedro convexo .

Na otimização matemática , uma região viável , conjunto viável , espaço de busca ou espaço de solução é o conjunto de todos os pontos possíveis (conjuntos de valores das variáveis ​​de escolha) de um problema de otimização que satisfaz as restrições do problema , potencialmente incluindo desigualdades , igualdades e restrições de inteiros . Este é o conjunto inicial de soluções candidatas para o problema, antes que o conjunto de candidatas seja reduzido.

Por exemplo, considere o problema

Minimizar ${\ displaystyle x ^ {2} + y ^ {4}}$

no que diz respeito às variáveis e${\ displaystyle x}$${\ displaystyle y,}$

sujeito a

${\ displaystyle 1 \ leq x \ leq 10}$

e

${\ displaystyle 5 \ leq y \ leq 12. \,}$

Aqui, o conjunto viável é o conjunto de pares ( x , y ) em que o valor de x é no mínimo 1 e no máximo 10 e o valor de y é no mínimo 5 e no máximo 12. Observe que o conjunto viável do problema é separado da função objetivo , que estabelece o critério a ser otimizado e que no exemplo acima é${\ displaystyle x ^ {2} + y ^ {4}.}$

Em muitos problemas, o conjunto viável reflete uma restrição de que uma ou mais variáveis ​​devem ser não negativas. Em problemas de programação de inteiros puros , o conjunto viável é o conjunto de inteiros (ou algum subconjunto dele). Em problemas de programação linear , o conjunto viável é um politopo convexo : uma região no espaço multidimensional cujos limites são formados por hiperplanos e cujos cantos são vértices .

A satisfação da restrição é o processo de encontrar um ponto na região viável.

Conjunto convexo viável

Em um problema de programação linear, uma série de restrições lineares produzem uma região convexa viável de valores possíveis para essas variáveis. No caso de duas variáveis, essa região tem a forma de um polígono simples convexo .

Um conjunto convexo viável é aquele em que um segmento de linha conectando quaisquer dois pontos viáveis ​​passa apenas por outros pontos viáveis, e não por quaisquer pontos fora do conjunto viável. Conjuntos convexos viáveis ​​surgem em muitos tipos de problemas, incluindo problemas de programação linear, e são de particular interesse porque, se o problema tem uma função objetivo convexa que deve ser maximizada, geralmente será mais fácil resolvê-los na presença de um convexo conjunto viável e qualquer ótimo local também será um ótimo global .

Nenhum conjunto viável

Se as restrições de um problema de otimização forem mutuamente contraditórias, não há pontos que satisfaçam todas as restrições e, portanto, a região viável é o conjunto nulo . Nesse caso, o problema não tem solução e é considerado inviável .

Conjuntos viáveis ​​limitados e ilimitados

Um conjunto viável limitado (parte superior) e um conjunto viável ilimitado (parte inferior). O conjunto na parte inferior continua para sempre para a direita.

Os conjuntos viáveis ​​podem ser limitados ou ilimitados . Por exemplo, o conjunto viável definido pelo conjunto de restrições { x ≥ 0, y ≥ 0} é ilimitado porque em algumas direções não há limite de quão longe alguém pode ir e ainda estar na região viável. Em contraste, o conjunto viável formado pelo conjunto de restrições { x ≥ 0, y ≥ 0, x + 2 y ≤ 4} é limitado porque a extensão do movimento em qualquer direção é limitada pelas restrições.

Em problemas de programação linear com n variáveis, uma condição necessária, mas insuficiente para que o conjunto viável seja limitado, é que o número de restrições seja pelo menos n + 1 (conforme ilustrado pelo exemplo acima).

Se o conjunto viável for ilimitado, pode haver ou não um ótimo, dependendo das especificações da função objetivo. Por exemplo, se a região viável é definida pelo conjunto de restrições { x ≥ 0, y ≥ 0}, então o problema de maximizar x + y não tem ótimo, pois qualquer solução candidata pode ser melhorada aumentando x ou y ; no entanto, se o problema é minimizar x + y , então há um ótimo (especificamente em ( x , y ) = (0, 0)).

Solução candidata

Em otimização e outros ramos da matemática , e em algoritmos de busca (um tópico da ciência da computação ), uma solução candidata é um membro do conjunto de soluções possíveis na região viável de um determinado problema. Uma solução candidata não precisa ser uma solução provável ou razoável para o problema - ela está simplesmente no conjunto que satisfaz todas as restrições ; ou seja, está no conjunto de soluções viáveis . Algoritmos para resolver vários tipos de problemas de otimização muitas vezes restringem o conjunto de soluções candidatas a um subconjunto das soluções viáveis, cujos pontos permanecem como soluções candidatas, enquanto as outras soluções viáveis ​​são doravante excluídas como candidatas.

O espaço de todas as soluções candidatas, antes que quaisquer pontos viáveis ​​tenham sido excluídos, é chamado de região viável, conjunto viável, espaço de busca ou espaço de solução. Este é o conjunto de todas as soluções possíveis que satisfazem as restrições do problema. A satisfação da restrição é o processo de encontrar um ponto no conjunto viável.

Algoritmo genético

No caso do algoritmo genético , as soluções candidatas são os indivíduos da população que estão sendo evoluídos pelo algoritmo.

Cálculo

No cálculo, uma solução ótima é buscada usando o primeiro teste de derivada : a primeira derivada da função sendo otimizada é igualada a zero, e quaisquer valores das variáveis ​​de escolha que satisfaçam esta equação são vistos como soluções candidatas (enquanto aqueles que não estão excluídos como candidatos). Existem várias maneiras pelas quais uma solução candidata pode não ser uma solução real. Em primeiro lugar, pode fornecer um mínimo quando um máximo está sendo procurado (ou vice-versa) e, em segundo lugar, pode fornecer nem um mínimo nem um máximo, mas sim um ponto de sela ou um ponto de inflexão , no qual uma pausa temporária na elevação local ou ocorre queda da função. Essas soluções candidatas podem ser descartadas pelo uso do teste da segunda derivada , cuja satisfação é suficiente para que a solução candidata seja pelo menos localmente ideal. Terceiro, uma solução candidata pode ser um ótimo local, mas não um ótimo global .

Ao tomar antiderivadas de monômios da forma, a solução candidata usando a fórmula da quadratura de Cavalieri seria esta solução candidata de fato correta, exceto quando${\ displaystyle x ^ {n},}$${\ displaystyle {\ tfrac {1} {n + 1}} x ^ {n + 1} + C.}$${\ displaystyle n = -1.}$

Programação linear

Uma série de restrições de programação linear em duas variáveis ​​produzem uma região de valores possíveis para essas variáveis. Problemas solucionáveis ​​de duas variáveis ​​terão uma região viável na forma de um polígono simples convexo se for limitada. Em um algoritmo que testa pontos viáveis ​​sequencialmente, cada ponto testado é, por sua vez, uma solução candidata.

No método simplex para resolver problemas de programação linear , um vértice do politopo viável é selecionado como a solução candidata inicial e é testado quanto à otimização; se for rejeitado como ótimo, um vértice adjacente é considerado a próxima solução candidata. Esse processo é continuado até que uma solução candidata seja considerada a ideal.

Referências