Programação Linear (2D)

PL com 2 variáveis: região viável, otimização por vértices

Exemplo resolvido — Programação Linear (2D)

Maximizar	3x + 2y

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Uma região viável não é promessa de resposta 🖖

A regra dos vértices tem um pré-requisito fácil de ignorar: um ótimo precisa existir. Carregue o exemplo não limitado — maximizar 2x + y sujeito a x ≥ 0, y ≥ 0, x + y ≥ 2 — e a região viável é perfeitamente não vazia, mas nenhum vértice é o melhor, porque você pode caminhar para nordeste indefinidamente e continuar melhorando. Por isso esta ferramenta devolve um de três veredictos, não apenas um: ótimo, inviável ou não limitado. Ela chega ao terceiro testando se existe uma direção de recessão que melhora, e não por falhar em achar um vértice. Troque esse mesmo exemplo para minimizar e uma resposta finita aparece de imediato em (0, 2). Viabilidade e solubilidade são perguntas separadas.

As melhores respostas se escondem nos vértices 🖖

Em termos simples, você está equilibrando recursos limitados sob várias regras ao mesmo tempo, e cada desigualdade recorta uma parte do plano. Onde todas as regras se sobrepõem fica a região viável, e cada ponto dentro dela é um plano válido. Como uma função objetivo linear sempre melhora numa direção, a melhor solução cai num vértice onde as restrições se encontram. A lição: para otimizar você nunca testa todos os pontos, apenas o punhado de vértices.

Como um problema de dieta anteviu o simplex 🖖

Em 1945, o economista George Stigler estudou a dieta mais barata que cobrisse todas as necessidades nutricionais, um problema linear com 77 alimentos. Sem um algoritmo, fez uma estimativa astuta e chegou a cerca de $39.93 por ano (preços de 1939). Quando o método simplex de Dantzig o resolveu com exatidão em 1947, o mínimo real era $39.69 — a estimativa manual de Stigler errou por apenas cerca de 24 centavos ao ano. Assim, a economia árida virou um dos casos fundadores da programação linear.

PROGRAMAÇÃO LINEAR — POR QUE SÓ SE OLHAM OS CANTOS

Em que caso de programação linear você está?

Todo programa linear faz a mesma pergunta: até onde dá para empurrar um objetivo retilíneo por uma região cercada por restrições retilíneas? Como ambos são retos, o melhor ponto só pode ser um canto — e é por isso que o método consiste em listar os cantos e comparar. Em que caso você está depende de a região prender ou não o objetivo, e de o canto entregue ser um número realmente utilizável.

Região limitada — o ótimo fica num canto z = 10 → (2, 2)

O melhor canto é fracionário, e isso é outro problema z = 24 → (8/3, 8/3)

Região ilimitada com resposta limitada min z = 13

Sem ótimo finito — e olhar os cantos não vai avisar z → ∞

Região limitada — o ótimo fica num canto

O que você sabe: Um objetivo a maximizar e restrições ≤ suficientes para fechar a região. O conjunto viável é um polígono.

O que verificar: z = 10 → (2, 2)

Exemplo resolvido: Maximizar 3x + 2y sujeito a x + y ≤ 4, x ≤ 2, y ≤ 3. Os cantos são (0,0), (2,0), (2,2), (1,3), (0,3), e z = 10 em (2,2) supera todos.

Abrir este caso: Problema da dieta

Região limitada — o ótimo fica num canto. A reta objetivo desliza para cima e para a direita até tocar o polígono num único canto. Um objetivo a maximizar e restrições ≤ suficientes para fechar a região. O conjunto viável é um polígono. — A reta objetivo desliza para cima e para a direita até tocar o polígono num único canto.

O melhor canto é fracionário, e isso é outro problema

O que você sabe: De novo uma região limitada, mas o canto que o objetivo escolhe não cai em números inteiros.

O que verificar: z = 24 → (8/3, 8/3)

Exemplo resolvido: Maximizar 5x + 4y sujeito a 2x + y ≤ 8, x + 2y ≤ 8, x ≤ 4, y ≤ 4. O ótimo é z = 24 em (8/3, 8/3), cerca de (2,67, 2,67).

Abrir este caso: Produção da fábrica

O melhor canto é fracionário, e isso é outro problema. As duas restrições ativas se cruzam longe das linhas da grade, então o melhor canto tem coordenadas fracionárias. De novo uma região limitada, mas o canto que o objetivo escolhe não cai em números inteiros. — As duas restrições ativas se cruzam longe das linhas da grade, então o melhor canto tem coordenadas fracionárias.

Região ilimitada com resposta limitada

O que você sabe: Minimizar com restrições ≥. A região viável vai ao infinito, mas o objetivo ainda tem um piso.

O que verificar: min z = 13

Exemplo resolvido: Minimizar 2x + 3y sujeito a x + y ≥ 6, x ≥ 2, y ≥ 1. A região é infinita e mesmo assim o mínimo é z = 13 em (5,1).

Abrir este caso: Custo mínimo

Região ilimitada com resposta limitada. A região se afasta da origem sem limite, mas o objetivo é minimizado num canto perto dela. Minimizar com restrições ≥. A região viável vai ao infinito, mas o objetivo ainda tem um piso. — A região se afasta da origem sem limite, mas o objetivo é minimizado num canto perto dela.

Sem ótimo finito — e olhar os cantos não vai avisar

O que você sabe: O objetivo melhora ao longo de uma direção que as restrições nunca bloqueiam. Não existe melhor ponto.

O que verificar: z → ∞

Exemplo resolvido: Maximizar 2x + y sujeito a x + y ≥ 2, x ≥ 0, y ≥ 0. Siga por x crescente para sempre e o objetivo cresce para sempre; a resposta é ilimitada.

Abrir este caso: Ilimitado

Sem ótimo finito — e olhar os cantos não vai avisar. A região sombreada é aberta para cima e para a direita, e o objetivo continua melhorando por ali sem fim. O objetivo melhora ao longo de uma direção que as restrições nunca bloqueiam. Não existe melhor ponto. — A região sombreada é aberta para cima e para a direita, e o objetivo continua melhorando por ali sem fim.

Referências (3)

The diet problem in the history block: Stigler, G. J. (1945). "The Cost of Subsistence." Journal of Farm Economics 27(2), 303.
Simplex, and the vertex theorem it relies on: Dantzig, G. B. Linear Programming and Extensions. Princeton University Press, 1963.
Unboundedness and recession directions, the tool’s third verdict: Boyd, S. & Vandenberghe, L. Convex Optimization. Cambridge University Press, 2004, §2.5. ISBN 978-0-521-83378-3.

Problema resolvido na íntegra

O problema da Dieta para maximizar Z = 3x + 2y 5 passos
Qual é o vértice vencedor e quanto vale o vértice adjacente? Este é o Problema da dieta: maximizar Z = 3x + 2y sujeito a x + y ≤ 4, x ≤ 2 e y ≤ 3, com x e y ambos maiores ou iguais a 0.
1. Considere dois pontos admissíveis quaisquer e percorra o segmento de reta entre eles. Uma função objetivo linear ao longo desse percurso é uma média ponderada dos seus dois valores extremos, e uma média ponderada nunca excede o maior extremo. Assim, nenhum ponto situado estritamente entre outros dois pode ser a solução ótima única, e aplicar esse princípio a cada direção por sua vez confina o ótimo a um vértice.
  
  $Z (λ A + (1 - λ) B) = λ Z (A) + (1 - λ) Z (B) \leq max {Z (A), Z (B)}, 0 \leq λ \leq 1$
2. Um vértice é o ponto onde duas retas de fronteira se cruzam, pelo que os candidatos resultam de combinar as cinco retas duas a duas. Há dez pares, dois dos quais paralelos, e apenas cinco dos restantes oito satisfazem as restrições que não lhes deram origem — x + y = 4 cruza-se com x = 0 em (0, 4), o que viola y ≤ 3.
  
  ${x + y = 4, x = 2} \Rightarrow (2, 2); {x + y = 4, y = 3} \Rightarrow (1, 3); (0, 0), (2, 0), (0, 3)$
3. Cinco avaliações aritméticas e uma comparação, e a pesquisa está concluída. Não resta interior por testar nem aresta por percorrer.
  
  $Z = 3 x + 2 y : 0, 6, 10, 9, 6 ⟹ (x^{*}, y^{*}) = (2, 2), Z^{*} = 10$
4. No vértice vencedor, x + y = 4 e x = 2 são ambas restrições ativas, enquanto y = 2 se encontra uma unidade inteira abaixo do seu teto de 3. Uma restrição com folga não está a limitar nada, pelo que relaxá-la não altera nada; vale a pena resolver novamente as outras duas com mais uma unidade cada.
  
  $b_{1} : 4 \to 5 \Rightarrow (2, 3), Z = 12, y_{1} = 2; b_{2} : 2 \to 3 \Rightarrow (3, 1), Z = 11, y_{2} = 1; y^{*} = 2 < 3 \Rightarrow y_{3} = 0$
5. Pondere cada um desses três preços pela quantidade desse recurso atribuída ao problema.
  
  $b_{1} y_{1} + b_{2} y_{2} + b_{3} y_{3} = 4 (2) + 2 (1) + 3 (0) = 10 = Z^{*}$
Resposta

A ferramenta apresenta x* = 2, y* = 2 e Z* = 10, o terceiro dos cinco valores nos vértices. Os números do passo 4 — 2, 1 e 0 — são os preços sombra, e respondem a uma questão a que o gráfico não consegue responder: mais uma unidade do orçamento de x + y vale o dobro de mais uma unidade de x, e mais uma unidade de y não vale absolutamente nada. O passo 5 é a dualidade forte, e tal não é um acaso destes números; os preços ponderados pelas disponibilidades reproduzem sempre o ótimo, que é precisamente o que os torna preços. Um preço sombra também tem uma data de validade. O orçamento de x + y paga 2 por unidade apenas até 5, onde o vértice atinge (2, 3), as outras duas restrições passam a estar ativas e Z se fixa em 12 — além desse ponto, o preço é 0 e cada unidade extra adquirida é desperdiçada.

$max {c^{⊤} x : A x \leq b, x \geq 0} = min {b^{⊤} y : A^{⊤} y \geq c, y \geq 0} = 10$

Pela equipa 42Math · Atualizado 2026-08-17

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Estatística e Finanças →

Problemas de exemplo

Problema da dieta - Maximização clássica limitada: o ótimo ocorre em um vértice factível.
Produção da fábrica - Restrições de capacidade que se cruzam criam uma região factível poligonal.
Custo mínimo - A minimização com restrições de limite inferior escolhe o vértice factível mais próximo da origem na direção do objetivo.
Ilimitado - A região factível pode ser ilimitada, portanto o objetivo pode não ter um ótimo finito.