Solucione o problema de otimização linear a seguir pelo método descrito abaixo:
(i) Liste todos os pontos extremos do conjunto dos pontos factíveis.
(ii) Calcule o valor da função objetivo em cada um dos pontos factíveis.
(iii) Determine o ponto extremo que otimize a função objetivo e apresente os valores ótimos das variáveis de decisão, da função objetivo e o conjunto de índices associados à base ótima.
Além disso, diga se cada ponto extremo é ou não uma solução básica factível, apresentando os respectivos índices do conjunto de índices das variáveis básicas e do conjunto de índices das varáveis não-básicas. Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada. Caso seja múltipla ou ilimitada, mostre o formato geral da solução, tanto para as variáveis de decisão quanto para a função objetivo.
(a)
suj a
(i) Liste todos os pontos extremos do conjunto dos pontos factíveis.
(ii) Calcule o valor da função objetivo em cada um dos pontos factíveis.
(iii) Determine o ponto extremo que otimize a função objetivo e apresente os valores ótimos das variáveis de decisão, da função objetivo e o conjunto de índices associados à base ótima.
(a)
suj a
Passo 1
O que o enunciado pede e quais informações nos dá\n
- Pede que localizemos todos os pontos extremos (vértices) do conjunto factível e que calculemos o valor da função objetivo em cada um deles.\n
- Pede que determinemos qual ponto extremo otimiza a função objetivo e apresentemos os valores ótimos das variáveis de decisão, o valor ótimo da função objetivo e o conjunto de índices da base ótima.\n
- Pede, adicionalmente, para cada ponto extremo dizer se ele é uma solução básica factível, apresentando um conjunto de índices das variáveis básicas e das não-básicas, e indicar se a solução é única, múltipla ou ilimitada (se aplicável).\n
Dados do problema:\n
Passo 2
Colocando as restrições em forma mais explícita e criando variáveis de folga (slacks) para explicar a ideia de base\n
- Introduzo quatro variáveis de folga
(todas ) para transformar as desigualdades em igualdades:
- Índices que vou usar para listar variáveis:
índice , índice , índice , índice , índice , índice .\n
Breve explicação conceitual (rápida, prática):\n - Um ponto extremo do conjunto factível em
aparece quando duas restrições (ou uma restrição e um eixo) ficam ativas simultaneamente (viram igualdades) e a solução resultante é viável.\n - Uma solução básica factível (SBF) corresponde a escolher um conjunto de
variáveis (aqui restrições) que formam a base; na prática, para cada vértice escolhemos 4 variáveis como básicas (algumas podem valer zero se houver degenerescência). Vou identificar uma base possível para cada vértice.
Passo 3
Observação sobre redundância de restrições e redução do trabalho\n
- A restrição
equivale a . Como existe a restrição , esta última é mais restrita e torna a restrição redundante no conjunto factível. Portanto posso ignorá-la ao procurar vértices (ela não contribuirá para formar vértices da região factível).\n - Logo as desigualdades relevantes para formar vértices são:
Passo 4
Encontrando todos os pontos extremos (intersecções relevantes) passo a passo\n
Vou verificar interseções entre as fronteiras das restrições (incluindo os eixos e
). Cada interseção será testada quanto à factibilidade (satisfaça todas as desigualdades).\n
Vou verificar interseções entre as fronteiras das restrições (incluindo os eixos
- Interseção dos eixos:
e ponto . Verificação: todas as desigualdades são satisfeitas. Logo é factível.\n - Interseção
com (fronteira de ) . Verificação: e . Factível. Logo é vértice.\n - Interseção
com então . Verificação: (igualdade na terceira). Factível. Logo é vértice.\n - Interseção
com : inserir dá . Ponto . Verificação: (igualdade na terceira). Factível. Logo é vértice.\n - Outros candidatos de interseção (por exemplo
com dá , mas isto viola , logo não factível). Interseções com a restrição redundante geram pontos fora da região (ex.: não satisfaz ). Então já listamos todos os vértices factíveis.\n
Conclusão: os vértices factíveis são os quatro pontos
Passo 5
Calcular
em cada ponto extremo (contas mostrando passo a passo)\n
- Em
: \n - Em
: \n - Em
: \n - Em
:
Passo 6
Determinar o ponto extremo que otimiza a função objetivo e analisar unicidade/ilimitado\n
- Comparando os valores calculados, o maior valor é
no ponto . Portanto o ótimo é com .\n - A região factível é limitada (há restrições tanto em
quanto em ); não existe direção que torne indefinidamente grande sem violar restrições. Logo a solução ótima não é ilimitada.\n - Verificando se há soluções ótimas múltiplas: se houvesse múltiplas ótimas, a reta de nível
com valor máximo deveria coincidir com uma aresta inteira do polígono factível. Os outros vértices têm valores distintos de ; portanto o ótimo ocorre apenas em . Logo o ótimo é único (solução ótima única).\n - Base ótima (uma escolha de variáveis básicas) para
: calculo os folgas no ponto :
Uma base natural e não-degenerada é escolher as variáveis básicas
(índices
), com valores
. As não-básicas ficam
(índices
), com valores
.\n
- Observação sobre degenerescência e multiplicidade de base: o ponto ótimo é uma solução única do problema primal, e a base escolhida acima dá representação básica não-degenerada (todas as básicas positivas), portanto é uma base ótima única nessa representação; não há múltiplas soluções ótimas e o problema não é ilimitado.
Passo 7
Para cada ponto extremo: é SBF? quais índices básicos e não-básicos escolher (uma possível escolha), e se a representação é degenerada (múltiplas bases) ou não\n
Vou usar a indexação: ,
,
,
,
,
.\n
Vou usar a indexação:
- Ponto
: valores .\n - É solução básica factível? Sim. Uma base natural é
(as quatro folgas) e não-básicas . Todas as básicas são positivas, não há degenerescência (base única nesta representação).\n
- É solução básica factível? Sim. Uma base natural é
- Ponto
: valores .\n - É SBF? Sim. Uma base possível é
(variáveis ) com não-básicas . Todas as básicas indicadas são positivas (exceto nenhuma), portanto não-degenerada para essa escolha de base.\n
- É SBF? Sim. Uma base possível é
- Ponto
: valores .\n - É SBF? Sim. Há degenerescência porque várias folgas valem zero. Uma base possível é
(índices ) com não-básicas ; nesta escolha é básica e igual a zero (degenerescência). Portanto a representação básica é degenerada — existem múltiplas bases que representam o mesmo ponto (mas o ponto em si é único). Esta degenerescência não implica múltiplas soluções ótimas do problema (a não ser que o valor objetivo fosse o mesmo em uma aresta inteira, o que não ocorre aqui).\n
- É SBF? Sim. Há degenerescência porque várias folgas valem zero. Uma base possível é
- Ponto
: valores .\n - É SBF? Sim. Uma base conveniente e não-degenerada é
(índices ) com não-básicas . Todas as básicas têm valor estritamente positivo aqui, logo essa base não é degenerada.\n
Resumo sobre unicidade / ilimitado: nenhuma das SBFs corresponde a solução ilimitada; o ótimo global é único e ocorre em. Não há solução ótima múltipla.
- É SBF? Sim. Uma base conveniente e não-degenerada é
Resposta
Pontos extremos factíveis:
.\n
Valores da função objetivo em cada ponto, respectivamente:
.\n
Ponto que otimiza (máximo): com
.\n
Conjunto de índices associado à base ótima (uma escolha não-degenerada): (ou seja,
básicos). Não-básicas:
(ou seja,
).\n
Para cada ponto: é SBF com base
e não-básicas
(não-degenerada);\n
é SBF com base
e não-básicas
(não-degenerada);\n
é SBF com base possível
e não-básicas
(degenerada — múltiplas bases representam o mesmo ponto);\n
é SBF com base
e não-básicas
(não-degenerada).\n
A solução ótima é única (não há soluções múltiplas ótimas) e o problema não é ilimitado.
Valores da função objetivo
Ponto que otimiza (máximo):
Conjunto de índices associado à base ótima (uma escolha não-degenerada):
Para cada ponto:
A solução ótima é única (não há soluções múltiplas ótimas) e o problema não é ilimitado.