Gostaríamos de usar a técnica primal-dual para resolver o seguinte problema pelo método dos elipsoides. Qual seria o sistema correspondente que deveríamos dar ao método?
(1) max z=x1+2 x2 x1+x2 <= 5 x1-2 x2 <= 2 -x1+2 x2 <= 4 x1,2 >= 0

Passo 1

O enunciado nos dá o problema primal
max;z &= x1+2x2, x1+x2 &<= 5, x1-2x2 &<= 2, -,x1+2x2 &<= 4, x1,,x2 &>= 0,
e pede para usar a técnica primal–dual no método dos elipsoides. Para isso vamos precisar formular o dual, impor a restrição de dualidade forte e então montar um sistema de inequações na forma M w <= h que englobe primal, dual e igualdade de objetivos.

Passo 2

Formulamos o dual. Chamamos y1,y2,y3>=0 as variáveis duals ao lado dos três cortes. O dual é
min;w &= 5y1+2y2+4y3, y1+y2-y3 &>= 1, y1-2y2+2y3 &>= 2, y1,,y2,,y3 &>= 0

Passo 3

Pela dualidade forte, no ótimo vale
c^Tx ;=; b^Ty Long<=ftrightarrow x1+2x2 ;=; 5y1+2y2+4y3
Para usar o método dos elipsoides convertemos essa igualdade em duas inequações.

Passo 4

Reescrevemos todas as restrições em forma <= sobre o vetor
w = (,x1,x2,y1,y2,y3,)
Primal e não negatividades:
x1+x2<=5
x1-2x2<=2
-,x1+2x2<=4
-,x1<=0
-,x2<=0
Dual e não negatividades:
-,y1-y2+y3<=-1
-,y1+2y2-2y3<=-2
-,y1<=0
-,y2<=0
-,y3<=0
Dualidade forte (duas inequações):
x1+2x2-5y1-2y2-4y3<=0
-,x1-2x2+5y1+2y2+4y3<=0

Resposta

O sistema a ser dado ao método dos elipsoides, em variáveis (x1,x2,y1,y2,y3), é
x1+x2<=5
x1-2x2<=2
-,x1+2x2<=4
-,x1<=0
-,x2<=0
-,y1-y2+y3<=-1
-,y1+2y2-2y3<=-2
-,y1<=0
-,y2<=0
-,y3<=0
x1+2x2-5y1-2y2-4y3<=0
-,x1-2x2+5y1+2y2+4y3<=0

Exercícios relacionados