Suponha que o dual de um problema de minimização seja dado por:
Max z=2x1
s.a:
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
sujeito a
O conteúdo aqui é Programação Linear, mais especificamente a dualidade. Para resolver a questão a gente vai:
construir o problema primal (que nesse caso é de minimização) usando as regras de dualidade;
resolver o primal (graficamente ou com o simplex);
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) vira2ª variável do dual (, coef. na linha 1 é 0 e na linha 2 é 1) vira3ª variável do dual (, coef. na linha 1 é 1 e na linha 2 é 2) vira
Resumindo, o primal é
Passo 3
Resolver o primal:
Olha as duas primeiras restrições: w = 3cdot2 + 5cdot6 = 6 + 30 = 36 e . Então o canto mais “baixo” possível no primeiro quadrante é .
Verifica a 3ª: , que já é ≥9. Ou seja, satisfaz tudo.
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.
Calcula :
Pela dualidade forte, o ótimo do primo = ótimo do dual.
Resposta
O valor ótimo da função objetivo do problema dual é .