Considere o seguinte conjunto de restrições:
X1+2 X2+2 X3+4 X4 <= 40
2 X1-X2+X3+2 X4 <= 8
4 X1-2 X2+X3-X4 <= 10
X1 ; X2 ; X3 ; X4 >= 0
Max z=5 X1-4 X2+6 X3-8 X4

Passo 1

Beleza, olha só o que a gente tem: é um problema de Programação Linear (PL) em que queremos maximizar
z = 5x1 - 4x2 + 6x3 - 8x4
sujeito às restrições
x1 + 2x2 + 2x3 + 4x4 <= 40, 2x1 - x2 + x3 + 2x4 <= 8, 4x1 - 2x2 + x3 - x4 <= 10, x1,x2,x3,x4>=0
Conteúdo: Método simplex / análise de coeficientes.
O que vamos usar:
1) Observação rápida sobre coeficientes negativos no objetivo.
2) Reduzir o problema aos dois variáveis “boas” e testar vértices.

Passo 2

Repara que no objetivo as variáveis x2 e x4 têm coeficientes negativos (–4 e –8).
Em PL maximização, sempre que um cj<0 é melhor pôr aquela variável = 0 (porque ela só diminui z).
Então, já vamos “zerar”
x2 = 0, x4 = 0

Passo 3

Substituindo x2=0 e x4=0 nas restrições, sobra um PL em (x1,x3):
x1 + 2x3 <= 40, 2x1 + x3 <= 8, 4x1 + x3 <= 10, x1>=0,;x3>=0,
e o objetivo vira
z = 5x1 + 6x3

Passo 4

Esse problema 2D a gente resolve testando os vértices da região factível.
As interseções “naturais” são:
  • (0,0)
  • interseção com eixo x3: ponha x1=0 em cada linha
    • 2x3=40implies x3=20 (mas esbarra em 2x1+x3<=8implies x3<=8, e em 4x1+x3<=10implies x3<=10)
    • o mais restritivo é x3<=8, logo ponto (0,8).
  • interseção com eixo x1: ponha x3=0
    • x1<=40;
    • 2x1<=8implies x1<=4;
    • 4x1<=10implies x1<=2,5.
    • o mais restritivo é x1<=2,5, ponto (2,5,0).
  • interseção entre as duas retas ativas: 2x1 + x3 = 8, 4x1 + x3 =10 Subtraindo a primeira da segunda dá 2x1=2implies x1=1, daí x3=8-2cdot1=6. Ponto (1,6).

Passo 5

Agora avalia z=5x1+6x3 em cada vértice:
  • Em (0,0): z=0.
  • Em (0,8): z=5cdot0 +6cdot8 = 48.
  • Em (2,5,0): z=5cdot2,5 +6cdot0=12,5.
  • Em (1,6): z=5cdot1 +6cdot6 = 5+36=41.
O maior valor é 48, no ponto (0,8).

Resposta

x1=0,;x2=0,;x3=8,;x4=0 e max z = 48

Exercícios relacionados