Suponha que o dual de um problema de minimização seja dado por:
Max z=2x1 +6 x2+9 x3
s.a:
& x1+x3 <= 3 & x2+2 x3 <= 5 & x1, x2, x3 >= 0
Construa o problema primal e resolva-o graficamente ou pelo método simplex. Qual o valor ótimo da função objetivo para o problema dual? Justifique.

Passo 1

Beleza, o enunciado diz que temos um problema dual de maximização:
Maximizar
z = 2x1 + 6x2 + 9x3
sujeito a
x1 + x3 <= 3, x2 + 2x3 <= 5, x1,x2,x3 >= 0
O conteúdo aqui é Programação Linear, mais especificamente a dualidade. Para resolver a questão a gente vai:
  1. construir o problema primal (que nesse caso é de minimização) usando as regras de dualidade;
  2. resolver o primal (graficamente ou com o simplex);
  3. usar dualidade forte pra dizer o valor ótimo do dual.

Passo 2

Construindo o primal:
  • Como o dual é max com 3 variáveis e 2 restrições “≤”, o primal será min com 2 variáveis e 3 restrições “≥”.
  • Denotamos as variáveis do primal por min; w = 3y1 + 5y2 .
  • O vetor de termos independentes do dual é 1cdot y1 + 0cdot y2 ;>=;2 Longrightarrow y1 >= 2 , então a função objetivo do primal é
0cdot y1 + 1cdot y2 ;>=;6 Longrightarrow y2 >= 6
  • As restrições vêm de transpor a matriz de coeficientes do dual e impor “ 1cdot y1 + 2cdot y2 ;>=;9 ” aos coeficientes da função do dual. Assim:
    1ª variável do dual ( & min; w = 3y1 + 5y2, &sujeito a & y1 >= 2, & y2 >= 6, & y1 + 2y2 >= 9, & y1,y2>=0 , coef. na linha 1 é 1 e na linha 2 é 0) vira 2ª variável do dual ( , coef. na linha 1 é 0 e na linha 2 é 1) vira 3ª variável do dual ( , coef. na linha 1 é 1 e na linha 2 é 2) vira
Resumindo, o primal é

Passo 3

Resolver o primal:
  1. Olha as duas primeiras restrições: w = 3cdot2 + 5cdot6 = 6 + 30 = 36 e . Então o canto mais “baixo” possível no primeiro quadrante é .
  2. Verifica a 3ª: , que já é ≥9. Ou seja, satisfaz tudo.
  3. Como é minimização, quanto mais baixo o , melhor. Não dá pra diminuir ou (já estão no mínimo) e a 3ª não obriga a subir nada. Então é ótimo.
  4. Calcula :
Pela dualidade forte, o ótimo do primo = ótimo do dual.

Resposta

O valor ótimo da função objetivo do problema dual é .

Exercícios relacionados