Combinando Inequações Lineares

Prévia do material em texto

1
Combinando inequações lineares
� A multiplicação por um número > 0 não altera uma 
inequação
� A soma de duas inequações (com o mesmo sentido) 
produz uma inequação válida
1 2 1 22 5 4 2 10x x x x− ≥ ⇔ − ≥
1 2
1 2
1 2
3 3
5 10
4 6 13
x x
x x
x x
+ ≤
+ ≤
+ ≤
2
Combinando inequações lineares
� A soma de duas inequações (com mesmo sentido) 
produz uma inequação válida
1 2
1 2
1 2
3 3
2
4 2 5
x x
x x
x x
+ ≤
+ ≤
+ ≤
{ } { }2 21 2 1 2 1 2: 3 3, 2 : 4 2 5x x x x x x x x∈ℜ + ≤ + ≤ ⊂ ∈ℜ + ≤
3
Combinando inequações lineares
� Geometricamente:
x1
x2
1
1
2
2
3
3
3x1 + x2 ≤ 3
x1 + x2 ≤ 2
4x1 + 2x2 ≤ 5
4
Combinando inequações lineares
� Também é possível multiplicar as inequações por 
números ≥ 0 antes de somá-las
( )
( )
1 2
1 2
1 2
2 3 3
1 2
7 3 8
x x
x x
x x
× + ≤
× + ≤
+ ≤
{ } { }2 21 2 1 2 1 2: 6 2 6, 2 : 7 3 8x x x x x x x x∈ℜ + ≤ + ≤ ⊂ ∈ℜ + ≤
5
Combinando inequações lineares
� Geometricamente:
x1
x2
1
1
2
2
3
3
6x1 + 2x2 ≤ 6
x1 + x2 ≤ 2
7x1 + 3x2 ≤ 8
6
Dualidade em Programação 
Linear
Prof.: Eduardo Uchoa
http://www.logis.uff.br/~uchoa/POI
7
Dualidade em Programação Linear
� Considere o seguinte PL:
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
max 4 5 3
s. a 3 1
5 3 8 55
2 3 5 3
, , , 0
z x x x x
x x x x
x x x x
x x x x
x x x x
= + + +
− − + ≤
+ + + ≤
− + + − ≤
≥
8
Dualidade em Programação Linear
� Sem resolver pelo Simplex, vamos estimar o valor 
ótimo z* da FO
� Para conseguir um bom limite inferior para z*, 
precisamos apenas de uma boa solução viável
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
max 4 5 3
s. a 3 1
5 3 8 55
2 3 5 3
, , , 0
z x x x x
x x x x
x x x x
x x x x
x x x x
= + + +
− − + ≤
+ + + ≤
− + + − ≤
≥
“Chutando” algumas 
soluções viáveis, temos:
(0,0,1,0) → z* ≥ 5
(2,1,1,1/3) → z* ≥ 15
(3,0,2,0) → z* ≥ 22
(0,14,0,5) → z* ≥ 29
9
Dualidade em Programação Linear
� Este método de tentativa e erro é muito inferior à
abordagem sistemática do Simplex
� Mesmo se encontrarmos por sorte a solução ótima, 
não teremos como provar que ela é mesmo ótima
� No entanto, tentaremos encontrar limites superiores 
para z* também por tentativa e erro, através de 
combinações de inequações.
10
Dualidade em Programação Linear
� Por exemplo, podemos notar que z* ≤ 275/3 = 91,66
� Multiplicando a segunda restrição por 5/3:
� Para qualquer solução viável (x1,x2,x3,x4) temos:
1 2 3 4
25 5 40 2755
3 3 3 3
x x x x+ + + ≤
1 2 3 4 1 2 3 4
25 5 40 2754 5 3 5
3 3 3 3
x x x x x x x x+ + + ≤ + + + ≤
11
Dualidade em Programação Linear
� Por exemplo, podemos notar que z* ≤ 275/3 = 91,33
� Multiplicando a segunda restrição por 5/3:
� Para qualquer solução viável (x1,x2,x3,x4) temos:
1 2 3 4
25 5 40 2755
3 3 3 3
x x x x+ + + ≤
1 2 3 4 1 2 3 4
25 5 40 2754 5 3 5
3 3 3 3
x x x x x x x x+ + + ≤ + + + ≤FO
Esta desigualdade vale para a solução ótima. Logo z* ≤ 275/3.
12
Dualidade em Programação Linear
� Um limite superior melhor pode ser obtido somando 
a segunda e a terceira restrições:
� Assim, z* ≤ 58.
1 2 3 44 3 6 3 58x x x x+ + + ≤
13
Dualidade em Programação Linear
� Um limite superior melhor pode ser obtido somando 
a segunda e a terceira restrições:
� Assim, z* ≤ 58.
� Agora, ao invés de usarmos tentativa e erro, vamos 
usar um procedimento geral pra encontrar o menor 
limite superior possível.
1 2 3 44 3 6 3 58x x x x+ + + ≤
14
Dualidade em Programação Linear
� O procedimento geral consiste em multiplicar cada 
restrição por um multiplicador ≥ 0
� y1 para a primeira restrição
� y2 para a segunda restrição
� y3 para a terceira restrição
e depois somar as desigualdades resultantes
15
Dualidade em Programação Linear
� Este procedimento gera a seguinte desigualdade:
� Na primeira tentativa, usamos y1 = 0, y2 = 5/3, y3 = 0
� No segunda tentativa, usamos y1 = 0, y2 = 1, y3 = 1
( ) ( ) ( )
( )
1 2 3 1 1 2 3 2 1 2 3 3
1 2 3 4 1 2 3
5 2 3 3
3 8 5 55 3
y y y x y y y x y y y x
y y y x y y y
+ − + − + + + − + +
+ + − ≤ + +
16
Dualidade em Programação Linear
� Queremos usar a inequação
para obter um limite superior para a FO
( ) ( ) ( )
( )
1 2 3 1 1 2 3 2 1 2 3 3
1 2 3 4 1 2 3
5 2 3 3
3 8 5 55 3
y y y x y y y x y y y x
y y y x y y y
+ − + − + + + − + +
+ + − ≤ + +
1 2 3 44 5 3 .z x x x x= + + +
17
Dualidade em Programação Linear
� Isso só é possível se o coeficiente de cada xj em 
for ≥ ao coeficiente correspondente da FO
� Logo,
( ) ( ) ( )
( )
1 2 3 1 1 2 3 2 1 2 3 3
1 2 3 4 1 2 3
5 2 3 3
3 8 5 55 3
y y y x y y y x y y y x
y y y x y y y
+ − + − + + + − + +
+ + − ≤ + +
1 2 3
1 2 3
1 2 3
1 2 3
5 4
2 1
3 3 5
3 8 5 3
y y y
y y y
y y y
y y y
+ − ≥
− + + ≥
− + + ≥
+ − ≥
1 2 3 44 5 3 .z x x x x= + + +
18
Dualidade em Programação Linear
� Se escolhermos multiplicadores yi ≥ 0 que satisfaçam 
podemos concluir que toda solução viável (x1,x2,x3,x4)
satisfaz 
1 2 3 4 1 2 34 5 3 55 3 .x x x x y y y+ + + ≤ + +
1 2 3
1 2 3
1 2 3
1 2 3
5 4
2 1
3 3 5
3 8 5 3
y y y
y y y
y y y
y y y
+ − ≥
− + + ≥
− + + ≥
+ − ≥
19
Dualidade em Programação Linear
� Em particular, a desigualdade
é satisfeita pela solução ótima. Logo,
1 2 3 4 1 2 34 5 3 55 3x x x x y y y+ + + ≤ + +
1 2 3* 55 3z y y y≤ + +
20
Dualidade em Programação Linear
� Obviamente, queremos o menor limite superior possível 
para o valor z* da FO.
� Dessa forma, chegamos ao seguinte PL:
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
min 55 3
s. a 5 4
2 1
3 3 5
3 8 5 3
, , 0
w y y y
y y y
y y y
y y y
y y y
y y y
= + +
+ − ≥
− + + ≥
− + + ≥
+ − ≥
≥
21
Dualidade em Programação Linear
� Obviamente, queremos o menor limite superior possível 
para o valor z* da FO.
� Dessa forma, chegamos ao seguinte PL:
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
min 55 3
s. a 5 4
2 1
3 3 5
3 8 5 3
, , 0
w y y y
y y y
y y y
y y y
y y y
y y y
= + +
+ − ≥
− + + ≥
− + + ≥
+ − ≥
≥
Este problema é chamado 
de dual do problema 
original.
O problema original é
chamado de primal.
22
Dualidade em Programação Linear
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
min 55 3
s. a 5 4
2 1
3 3 5
3 8 5 3
, , 0
w y y y
y y y
y y y
y y y
y y y
y y y
= + +
+ − ≥
− + + ≥
− + + ≥
+ − ≥
≥
Suponha que por tentativa e 
erro encontramos a solução 
viável (11,0,6) do dual com 
w=29.
Logo, z*≤ 29. Mas já
sabíamos que z*≥29.
Logo, z*=29 e a solução 
(0,14,0,5) do problema 
original (primal) é ótima!
23
Definição geral de PL dual
Dado um PL qualquer (o primal), existe outro PL que é o seu dual.
Suponha que esse PL é um problema de maximização na forma 
canônica:
1
1
max
S. a 1, 2,...,
 0 1,2,...,
n
j j
j
n
ij j i
j
j
z c x
a x b i m
x j n
=
=
=
≤ =
≥ =
∑
∑
24
Definição geral de PL dual
Primal: Dual:
1
1
max
S. a 1, 2,...,
 0 1,2,...,
n
j j
j
n
ij j i
j
j
z c x
a x b i m
x j n
=
=
=
≤ =
≥ =
∑
∑
1
1
min
S. a 1, 2,...,
 y 0 1,2,...,
m
i i
i
m
ij i j
i
i
w b y
a y c j n
i m
=
=
=
≥ =
≥ =
∑
∑
25
Dualidade em Programação Linear
� O dual de um problema de maximização é um 
problema de minimização
� As m restriçõesprimais estão em correspondência 
um-para-um com as m variáveis duais yi
� As n restrições duais estão em correspondência 
um-para-um com as n variáveis primais xj
� O coeficiente de cada variável na FO, primal ou 
dual, aparece no outro problema como lado direito 
da restrição correspondente
� A matriz A de coeficientes do primal aparece 
transposta no dual.
26
Propriedades do PL dual
� Teorema 1 – O dual do dual é o primal.
27
Prova do Teorema 1
1 1
1 1
max min
S. a 1, 2,..., ( ) S. a 1,2,...,
 y 0 1,2,...,
 0 1,2,...,
n m
j j i i
j i
n m
ij j i ij i j
j i
ij
c x b y
P a x b i m D P a y c j n
i mx j n
= =
= =
 
 
 
 
= ≤ = → = ≥ = 
 
  ≥ =≥ =
 
 
∑ ∑
∑ ∑
28
Prova do Teorema 1
1 1
1 1
min max ( )
( ) S. a 1, 2,..., S. a ( ) 1,2,...,
 y 0 1,2,..., y 0 1,2,...,
m m
i i i i
i i
m m
ij i j ij i j
i i
i i
b y b y
D P a y c j n a y c j n
i m i m
= =
= =
 
− 
 
 
= ≥ = = − ≤ − = 
 
 ≥ = ≥ =
 
 
∑ ∑
∑ ∑
29
Prova do Teorema 1
11
1 1
min ( )max ( )
( ) S. a ( ) 1, 2,..., ( ( )) S. a ( ) 1, 2,...,
 y 0 1,2,...,
 0 1, 2,...,
nm
j ji i
ji
m n
ij i j ij j i
i j
i j
c xb y
D P a y c j n D D P a x b i m
i m x j n
==
= =

−
− 

 
= − ≤ − = → = − ≥ − = 
 
 ≥ = ≥ =
 
 
∑∑
∑ ∑
30
Prova do Teorema 1
1 1
1 1
min ( ) max
( ( )) S. a ( ) 1, 2,..., S. a 1, 2,..., 
 0 1, 2,..., 0 1, 2,...,
n n
j j j j
j j
n n
ij j i ij j i
j j
j j
c x c x
D D P a x b i m P a x b i m
x j n x j n
= =
= =
 
− 
 
  
= − ≥ − = = = ≤ = 
 
 ≥ = ≥ =
 
  
∑ ∑
∑ ∑ �
31
É igualmente válido definir o primal como 
sendo um problema de minimização
Dual:Primal:
1
1
max
S. a 1, 2,...,
 0 1,2,...,
n
j j
j
n
ij j i
j
j
w c x
a x b i m
x j n
=
=
=
≤ =
≥ =
∑
∑
1
1
min
S. a 1,2,...,
 y 0 1,2,...,
m
i i
i
m
ij i j
i
i
z b y
a y c j n
i m
=
=
=
≥ =
≥ =
∑
∑
32
Simetria da Dualidade
Na verdade, temos um par de PLs na forma canônica, um de 
minimização, outro de maximização. Escolhendo um deles para ser 
o primal, o outro fica sendo o dual.
1
1
max
S. a 1, 2,...,
 0 1,2,...,
n
j j
j
n
ij j i
j
j
w c x
a x b i m
x j n
=
=
=
≤ =
≥ =
∑
∑
1
1
min
S. a 1,2,...,
 y 0 1,2,...,
m
i i
i
m
ij i j
i
i
z b y
a y c j n
i m
=
=
=
≥ =
≥ =
∑
∑
33
Propriedades do PL dual
� Teorema da dualidade fraca – Se o primal
for um PL de maximização que tem uma 
solução viável x com valor z e o seu dual tem 
solução viável y com valor w, então z≤w.
34
Prova do Teorema da dualidade fraca
1 1 1 1 1 1
*
Para qualquer viável para o primal e qualquer viável para o dual:
( ) ( ) . 
Em particular, se o primal e o dual tiverem soluções ótimas e 
n n m m n m
j j ij i j ij j i i i
j j i i j i
x y
z c x a y x a x y b y w
x y
= = = = = =
= ≤ = ≤ =∑ ∑ ∑ ∑ ∑ ∑ �
*
* *
,
 w . z ≤
35
Versão minimização do Teorema
� Teorema da dualidade fraca – Se o primal
for um PL de minimização que tem uma 
solução viável x com valor z e o dual tem 
solução viável y com valor w, então z≥w.
36
Propriedades do PL dual
� Teorema da dualidade forte – Se o primal
tem solução ótima x* com valor z*, então o 
dual tem solução ótima y* com valor w* e 
z*=w*.
� Consequência: sempre é possível usar uma 
solução do dual para provar a que uma 
solução ótima do primal realmente é ótima. 
37
Relações entre os PLs primal e Dual
Pelo Teorema da dualidade fraca:
� Se o Primal for ilimitado, o dual é inviável.
� Se o dual for ilimitado, o primal é inviável.
38
É possível que tanto o primal quanto o 
dual sejam inviáveis
� Exemplo:
1 2 1 2
1 2 1 2
1 2 1 2
1 2 1 2
max 2 min 2
S. a 1 S. a 2
2 1
, 0 , 0
z x x w y y
x x y y
x x y y
x x y y
= − = −
− ≤ − ≥
− + ≤ − − + ≥ −
≥ ≥
39
Relações entre o primal e o dual
Ilimitado
Inviável
Ótimo
PRIMAL
IlimitadoInviávelÓtimo
DUAL
Possível
Impossível
40
Exemplo de aplicação de dualidade: 
“prova dos 9” do Simplex
� Imagine que resolvemos o seguinte PL pelo 
Simplex
maximizar z = 4,0 x1 + 6,0 x2
Sujeito a
1,5 x1 + 4,0 x2 ≤ 24
3,0 x1 + 1,5 x2 ≤ 21
1,0 x1 + 1,0 x2 ≤ 8
x1 , x2 ≥ 0
41
O dicionário final é:
A solução associada:
x1 =3,2
x2 = 4,8
z = 41,6
Queremos verificar se não houve 
nenhum erro, ou seja, que essa 
solução é realmente viável e ótima.
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208 4 14
5 5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
42
Dualidade em Programação Linear
� Verificar se a solução é viável é fácil
� Como verificar se a solução é ótima?
4/5 × (1,5 x1 + 4,0 x2 ≤ 24)
0 × (3,0 x1 + 1,5 x2 ≤ 21)
14/5 × (1,0 x1 + 1,0 x2 ≤ 8)
4 x1 + 6 x2 ≤ 41,6
Não é possível existir solução 
viável com z > 41,6.
Logo, x1 = 3,2, x2 = 4,8 é ótima!
43
Dualidade em Programação Linear
� Geometricamente
1,2x1 + 3,2x2 ≤ 19,2
2,8x1 + 2,8x2 ≤ 22,4
4x1 + 6x2 ≤ 41,6
xmad
5
x
a
l
44
A solução dual ótima (4/5,0,14/5) que 
permite provar a otimalidade está
escondida no dicionário final!
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208
5
4 14
5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
45
A solução dual ótima (4/5,0,14/5) que 
permite provar a otimalidade está
escondida no dicionário final!
2 3 5
4 3 5
1 3 5
3 5
24 2 3
5 5 5
21 3 39
5 5 10
16 2 8
5 5 5
208
5
4 14
5 5
x x x
x x x
x x x
z x x
= − +
= − +
= + −
= − −
A mágica será explicada nas 
próximas aulas.
O importante agora é saber 
que quando se resolve um PL 
pelo Simplex, seu dual também 
está sendo resolvido.
46
Teorema das folgas complementares
* *
* *
1
* *
1
Seja viável para o primal e viável para o dual. Ambas as
soluções serão ótimas se e somente se:
 ( ) 0 1, ,
e ( - ) 0 1, , .
n
i i ij j
j
m
ij i j j
i
x y
y b a x i m
a y c x j n
=
=
− = = …
= = …
∑
∑
47
Teorema das folgas complementares
* *
* *
1
* *
1
Seja viável para o primal e viável para o dual. Ambas as
soluções serão ótimas se e somente se:
 ( ) 0 1, ,
e ( - ) 0 1, , .
n
i i ij j
j
m
ij i j j
i
x y
y b a x i m
a y c x j n
=
=
− = = …
= = …
∑
∑
Folga da restrição i do primal
Se a folga de uma restrição primal for > 0 => a variável dual correspondente = 0
Se uma variável dual >0 => a folga da restrição primal correspondente = 0
48
Teorema das folgas complementares
* *
* *
1
* *
1
Seja viável para o primal e viável para o dual. Ambas as
soluções serão ótimas se e somente se:
 ( ) 0 1, ,
e ( - ) 0 1, , .
n
i i ij j
j
m
ij i j j
i
x y
y b a x i m
a y c x j n
=
=
− = = …
= = …
∑
∑
Excesso da restrição j do dual
Se o excesso de uma restrição dual for > 0 => a variável primal correspondente = 0
Se uma variável primal >0 => o excesso da restrição dual correspondente= 0
49
Implicação do Teorema das folgas 
complementares
� Uma solução primal viável x1*, x2*, ..., xn* é ótima se e 
somente se existem números y1*, y2*, ..., ym* tais que:
* *
1
* *
1
*
1
*
sempre que 0
0 sempre que
e que sejam dual viáveis, i.e.:
1, 2,...,
0 1,2,..., .
m
ij i j j
i
n
i ij j i
j
m
ij i j
i
i
a y c x
y a x b
a y c j n
y i m
=
=
=
= >
= <
≥ ∀ =
≥ ∀ =
∑
∑
∑
(1)
(2)
50
Exemplo de aplicação de dualidade: teste de 
otimalidade de solução obtida por chute
é uma solução ótima para o PL?
* * * * * *
1 2 3 4 5 62, 4, 0, 0, 7, 0x x x x x x= = = = = =
1 2 3 4 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 6
1 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
max 18 7 12 5 8
s. a 2 6 2 7 3 8 1
3 4 3 2 2
8 3 5 2 2 4
4 8 7 3 1
5 2 3 6 2 5
, , , , , 0
z x x x x x
x x x x x x
x x x x x x
x x x x x
x x x x x
x x x x x x
x x x x x x
= − + + +
− + + + + ≤
− − + − + + ≤ −
− + − + ≤
+ + − + ≤
+ − + − − ≤
≥
51
Teorema das folgas complementares
� Nesse caso, em (1) teremos:
* * * * *
1 2 3 4 5
* * * *
1 2 3 5
* * * *
1 2 4 5
*
2
*
5
2 3 8 4 5 18
6 3 2 7
3 2 0
0
0
y y y y y
y y y y
y y y y
y
y
− + + + =
− − − + = −
+ − − =
=
=
52
Teorema das folgas complementares
� Resolver um sistema 3 x 3:
* * *
1 3 4
* *
1 3
* *
1 4
2 8 4 18
6 3 7
3 0
y y y
y y
y y
+ + =
− − = −
− =
53
Teorema das folgas complementares
Dado que a solução (1/3, 0, 5/3, 1, 0) satisfaz (2), ela é
dual viável (e ótima) e a solução primal x1*, x2*, ..., x6* é
ótima.
* * * * *
1 2 3 4 5
* * * *
1 2 3 5
* * * *
1 2 4 5
*
2
*
5
2 3 8 4 5 18
6 3 2 7
3 2 0
0
0
y y y y y
y y y y
y y y y
y
y
− + + + =
− − − + = −
+ − − =
=
=
54
Teorema das folgas complementares
é uma solução ótima para o PL?
* * * * *
1 2 3 4 50, 2, 0, 7, 0x x x x x= = = = =
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
max 8 9 12 4 11
s. a 2 3 4 3 1
7 3 2 1
5 4 6 2 3 22
, , , , 0
z x x x x x
x x x x x
x x x x x
x x x x x
x x x x x
= − + + +
− + + + ≤
+ + − + ≤
+ − + + ≤
≥
55
Teorema das folgas complementares
� Em (1) teremos:
* * *
1 2 3
* * *
1 2 3
*
2
3 7 4 9
2 2 4
0
y y y
y y y
y
− + + = −
− + =
=
56
Teorema das folgas complementares
� Resolver um sistema 2 x 2:
* *
1 3
* *
1 3
3 4 9
2 4
y y
y y
− + = −
+ =
57
Teorema das folgas complementares
Dado que a solução única desse sistema (17/5,0,3/10) 
não é dual viável, a solução proposta não é ótima.
* * *
1 2 3
* * *
1 2 3
*
2
3 7 4 9
2 2 4
0
y y y
y y y
y
− + + = −
− + =
=
58
Como encontrar o dual de um PL que não 
está na forma canônica?
1 2 1 2
1 2 1 2
1 2 1 2
1 2 1 2
1 2
max 2 max 2
S. a 1 S. a 1
4 4
, 0 4
, 0
z x x z x x
x x x x
x x x x
x x x x
x x
= − = −
− ≥ ⇔ − + ≤
+ = + ≤
≥ − − ≤ −
≥
Uma possibilidade é converter para a forma canônica
59
Como encontrar o dual de um PL que não 
está na forma canônica?
1 2 3
1 2 3
1 2 3
1 2 3
min 4 4
S. a 2
1
, , 0
w y y y
y y y
y y y
y y y
= + −
− + − ≥
+ − ≥ −
≥
O dual então fica:
60
Como encontrar o dual de um PL que não 
está na forma canônica?
1 2 3
1 2 3
1 2 3
1 2 3
min 4 4
S. a 2
1
, , 0
w y y y
y y y
y y y
y y y
= + −
− + − ≥
+ − ≥ −
≥
As variáveis y2 e y3 podem ser substituídas por uma única variável irrestrita
61
Como encontrar o dual de um PL que não 
está na forma canônica?
1 2
1 2
1 2
1
2
min 4
S. a 2
1
0
irrestrito
w y y
y y
y y
y
y
= +
− + ≥
+ ≥ −
≥
O dual então é equivalente a:
62
É possível encontrar o dual de um PL que 
não está na forma canônica diretamente
= cjirrestrita
≤ cj≤ 0 Restrições
≥ cj≥ 0
Variáveis
irrestrita= bi
≤ 0≥ bi Variáveis
≥ 0≤ bi
Restrições
DUALminimizarmaximizarPRIMAL
63
É possível encontrar o dual de um PL que 
não está na forma canônica diretamente
= cjirrestrita
≥ cj≤ 0 Restrições
≤ cj≥ 0
Variáveis
irrestrita= bi
≤ 0≤ bi Variáveis
≥ 0≥ bi
Restrições
DUALmaximizarminimizarPRIMAL
64
OBSERVAÇÃO
Este material refere-se às notas de aula do curso 
TEP117 (Pesquisa Operacional I) da Universidade 
Federal Fluminense (UFF) e não pode ser 
reproduzido sem autorização prévia do autor. 
Quando autorizado, seu uso é exclusivo para 
atividades de ensino e pesquisa em instituições 
sem fins lucrativos.