Considere o seguinte problema de programação linear.
min & x1-2 x2-3 x3 & -x1+3 x2+x3 <= 13 & x1+2 x2+3 x3 >= 12 & 2 x1-x2+x3=4 & x1, x2 in R & x3 <=-3
(1) Reformule o problema tal que ele esteja no formato padrão.
(2) Reformule o problema tal que ele esteja no formato canônico.
(3) Converta o problema em um problema de maximização.

Passo 1

O enunciado nos dá um PL de minimização
min;&x1-2x2-3x3 sa &-x1+3x2+x3<=13, &x1+2x2+3x3>=12, &2x1-x2+x3=4, &x1,x2in R, x3<=-3
Para levá-lo ao formato padrão precisamos (i) todas as variáveis não negativas e (ii) todas as restrições em igualdade. Para isso vamos substituir as variáveis livres e a variável com limite superior e inserir variáveis de folga/excedente.

Passo 2

Definimos
x1=x1^+-x1^-, x2=x2^+-x2^-, x1^pm,x2^pm>=0,
e, como x3<=-3, colocamos
x3=-x3'-3, x3'>=0
Em seguida introduzimos s1>=0 na primeira desigualdade e s2>=0 na segunda (como excedente), obtendo o PL em igualdades e variáveis não negativas:
Minimizar
z = x1^+-x1^--2x2^++2x2^-+3x3'
sujeito a
-,x1^++x1^-+3x2^+-3x2^--x3'+s1=16,
x1^+-x1^-+2x2^+-2x2^--3x3'-s2=21,
2x1^+-2x1^--x2^++x2^--x3'=7,
x1^+,,x1^-,,x2^+,,x2^-,,x3',,s1,,s2>=0

Passo 3

No formato canônico queremos minimizar com todas as restrições do tipo “ <=” e variáveis não negativas. Partindo do original e fazendo as mesmas substituições de variáveis do passo 2, convertemos cada igualdade em duas desigualdades “ <=” e cada “ >=” em “ <=” multiplicando por -1. O resultado é
Minimizar
z = x1^+-x1^--2x2^++2x2^-+3x3'+9
sujeito a
-,x1^++x1^-+3x2^+-3x2^--x3'<=16,
-,l(x1^+-x1^-+2x2^+-2x2^-+3x3'+9r)<=-12,
2x1^+-2x1^--x2^++x2^--x3'<=7,
-,l(2x1^+-2x1^--x2^++x2^--x3'r)<=-7,
x3'>=0,
todas as demais variáveis também >=0.

Passo 4

Para transformar em maximização basta trocar “ min z” por “ max z'=-z” mantendo as mesmas restrições e não negatividades. Assim obtemos
Maximizar
z'=-,x1^++x1^-+2x2^+-2x2^--3x3'
sujeito ao mesmo sistema de igualdades (ou de desigualdades no formato canônico) e às mesmas condições x1^pm,x2^pm,x3',s1,s2>=0.

Resposta

(1) Formato padrão:
Minimizar
z = x1^+-x1^--2x2^++2x2^-+3x3'
sujeito a
-,x1^++x1^-+3x2^+-3x2^--x3'+s1=16, x1^+-x1^-+2x2^+-2x2^--3x3'-s2=21, 2x1^+-2x1^--x2^++x2^--x3'=7,
x1^+,x1^-,x2^+,x2^-,x3',s1,s2>=0
(2) Formato canônico:
Minimizar
z = x1^+-x1^--2x2^++2x2^-+3x3'+9
sujeito a
-,x1^++x1^-+3x2^+-3x2^--x3'<=16, -,l(x1^+-x1^-+2x2^+-2x2^-+3x3'+9r)<=-12,
2x1^+-2x1^--x2^++x2^--x3'<=7, -,l(2x1^+-2x1^--x2^++x2^--x3'r)<=-7, x3'>=0,
todas as demais variáveis >=0.
(3) Problema de maximização:
Maximizar
z' = -,x1^++x1^-+2x2^+-2x2^--3x3'
sujeito ao mesmo sistema do formato padrão (ou canônico) e às mesmas não negatividades.

Exercícios relacionados