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?
Passo 1
O enunciado nos dá o problema primal
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
que englobe primal, dual e igualdade de objetivos.
Passo 2
Formulamos o dual. Chamamos
as variáveis duals ao lado dos três cortes. O dual é
Passo 3
Pela dualidade forte, no ótimo vale
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
Primal e não negatividades:
Dual e não negatividades:
Dualidade forte (duas inequações):
Resposta
O sistema a ser dado ao método dos elipsoides, em variáveis
, é