Considere os problemas de otimização linear a seguir:
(i) Solucione-os graficamente, caso possível. Caso não, explique as razões;
(ii) Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada;
(i) Solucione-os graficamente, caso possível. Caso não, explique as razões;
(ii) Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada;
Passo 1
O enunciado pede duas coisas:
(i) “Solucione-os graficamente, caso possível.” (ou explique por que não é possível).
(ii) “Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada.”
(i) “Solucione-os graficamente, caso possível.” (ou explique por que não é possível).
(ii) “Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada.”
As informações fornecidas (copiadas do enunciado) são as restrições:
Observação importante: o enunciado mostra apenas a palavra “max” sem especificar a função objetivo (ou seja, falta a expressão a ser maximizada). Não há outra informação sobre a função objetivo nos dados fornecidos.
Passo 2
Vou primeiro explicar por que a ausência da função objetivo impede uma “solução ótima” numérica e o que ainda é possível fazer:
- Para resolver graficamente um problema de otimização linear precisa-se da função objetivo, típica forma
(ou ). Sem os coeficientes não dá para dizer qual ponto da região factível é ótimo. - Mesmo assim, podemos analisar completa e explicitamente a região factível (conjunto de pontos que satisfazem todas as restrições). Isso é útil porque, com a região em mãos, eu mostro exatamente como se procederia graficamente quando a função objetivo for dada.
Passo 3
Simplifico a primeira desigualdade (faça devagar para não se perder):
A desigualdade é
A desigualdade é
Os termos
e
se cancelam:
. Logo sobra
Multiplicando ambos os lados por
(lembre que ao multiplicar por
a desigualdade inverte):
Portanto, a primeira restrição é simplesmente
.
Passo 4
Agora escrevo todas as restrições de forma simples:
Mas note que
já implica
, então a restrição
é redundante aqui. O que resta efetivamente é:
Passo 5
Determino os vértices (pontos extremos) da região factível — passo essencial para a solução gráfica de qualquer problema linear (teorema dos vértices: máximo/mínimo linear ocorre em vértice ou aresta):
- Interseção entre
e dá o ponto . - Interseção entre
e . Substituo em e obtenho então . Logo o ponto é . - Interseção entre
e dá , então o ponto é .
Assim a região factível é o triângulo convexo com vértices
Esse triângulo é compacto (fechado e limitado), logo qualquer função linear objetivo terá valor máximo e mínimo atingidos nesse triângulo.
Passo 6
Explico didaticamente como resolver graficamente quando a função objetivo for dada (passo a passo que você pode usar no exame):
- Suponha a função objetivo
que queremos maximizar. Para um valor fixo a equação é uma reta (linha de nível) no plano. Varia-se e desloca-se essa reta paralelamente até o último ponto em que ela ainda intersecta a região factível; esse último contato é o ótimo. - Pelo teorema dos vértices, o ótimo será sempre um dos vértices
ou possivelmente toda uma aresta inteira se a reta de nível ficar exatamente alinhada (paralela) com uma aresta que contém pontos factíveis ótimos. - Para decidir qual vértice é ótimo basta calcular
nesses três vértices e pegar o maior (ou menor, se fosse minimização). Isto dá cálculo rápido sem desenhar muito: calcule , e .
Exemplos rápidos para fixar:
- Se
(isto é, ) então valores nos vértices: . O máximo é em — solução única. - Se
(isto é, ) então valores: . O máximo é em — solução única. - Situação de múltiplas soluções: ocorre quando a reta de nível é paralela a uma aresta e o deslocamento máximo alcança toda essa aresta. Ex.: se a reta de nível for paralela à aresta entre
e (essa aresta é horizontal, direção ), então a função objetivo deve ter coeficiente (ou seja, depender só de ). Nesse caso, se o máximo ocorrer nessa aresta, todos os pontos da aresta teriam o mesmo valor — daí múltiplas soluções. (Note: se o valor nos vértices e são diferentes a menos que ; logo para concretizar múltiplas soluções na aresta horizontal precisa de condições específicas nos coeficientes que façam a mesma avaliação em todos os pontos da aresta e maior que em . Em termos gerais, múltiplas soluções ocorrem exatamente quando a direção do gradiente da função objetivo é perpendicular ao vetor normal da aresta, i.e., quando as isolinhas são paralelas à aresta.)
Passo 7
Concluo as consequências relevantes (resumo prático que você usa na prova):
- A região factível está completamente determinada e é o triângulo com vértices
. - Como a região é limitada, para qualquer função linear objetivo existe máximo e mínimo finitos atingidos na região.
- A unicidade ou multiplicidade da solução depende dos coeficientes da função objetivo: tipicamente a solução é única (ocorre em um vértice); é múltipla somente se a reta de nível da função objetivo for paralela a uma aresta factível que seja a fronteira do ótimo; não há caso de solução ilimitada (unbounded) porque a região factível é limitada.
Resposta
(i) Não é possível determinar numericamente a solução ótima porque a função objetivo não foi fornecida; entretanto a região factível é o triângulo com vértices
e, uma vez dada a função objetivo
, resolve‑se graficamente deslocando a reta
até o último contato — o ótimo será um dos vértices (ou uma aresta inteira se houver degenerescência).
(ii) Para qualquer função linear objetivo existe solução e ela é finita (a região é limitada); a solução é normalmente única (ocorre em um vértice) e será múltipla somente se os coeficientes da função objetivo fizerem as isolinhas paralelas a uma aresta que contenha o ótimo; a solução não é ilimitada.
(ii) Para qualquer função linear objetivo existe solução e ela é finita (a região é limitada); a solução é normalmente única (ocorre em um vértice) e será múltipla somente se os coeficientes da função objetivo fizerem as isolinhas paralelas a uma aresta que contenha o ótimo; a solução não é ilimitada.