Universidade Federal de Itajubá – UNIFEI
Instituto de Recursos Naturais - IRN
Programação Linear
Benedito C. Silva
Vamos ver algumas questões importantes em
relação às inequações de restrição:
suponha
a inequação
A B
eu posso transforma r esta expressão
em igualdade :
A  C B
onde C é chamada
A

menor
C
slack

variável
de folga (slack variable)
B
maior
No caso de
A B
A -C B
neste caso C é variável
de excesso
em ambos os casos : C  0
(surplus
variable)
Vamos supor o seguinte problema
Max Z  X1  X2
sujeito a
X1  2 X2  10
3X1  2X2  18
X1  0
X2  0
Vamos transformá-lo na sua forma
slack (com folga)
Max Z  X1  X2
sujeito a
X1  2 X2  r  10
3X1  2X2  s  18
X1  0
X2  0
r0
s0
Graficamente, tem-se:
Observem cada vértice da área hachurada...
O que acontece em cada ponto?
Observem que em cada reta limite uma das
variáveis X1, X2, r ou s é igual a zero!!!
Como é que podemos identificar os vértices
desta figura?
Atenção este vértice
não é válido
s = -12
Simples....
Se observarmos a figura:
cada vértice é um ponto onde duas das quatro variáveis
X1, X2, r e s são zeros....
Portanto: se eu fizer duas variáveis iguais a zero, determinando
as demais (garantindo a unicidade e a não negatividade),
encontro um vértice.....mas atenção.....não esquecer da não
negatividade.
Essa regra de procura de vértices pode ser
generalizada:
Se o problema tiver seis variáveis, faço três
variáveis iguais a zero e determino as demais,
garantindo a não negatividade e a unicidade..( na
forma slack)
Se o problema tiver oito...idem......e assim por
diante
Lembrete importante: sabemos que o máximo ou o
mínimo é um desses vértices.......portanto.....temos
um caminho para chegar ao ótimo.....
Vamos ver agora o Método Simplex
Os problemas que serão resolvidos possuem a seguinte
forma:
maximizar
ou minimizar
uma função do tipo :
u  c1 x1  c 2 x 2  .......... .. c n x n  d
restrições
do tipo :
a i1 x1  a i 2 x 2 .......... .......... .....  a in x n  bi ou
a i1 x1  a i 2 x 2 .......... .......... .....  a in x n  bi ou
a i1 x1  a i 2 x 2 .......... .......... .....  a in x n  bi
e, finalmente , a não negativida de das variáveis
envolvidas
Atenção (problema padrão):
•em geral vamos max u e as restrições são do tipo
menor igual;
•a não negatividade pode não ser necessária, mas
isso é um caso especial...
Vamos supor o seguinte problema:
min u  3 x  4 y
min u  3 x  4 y
s .a
Não está na forma padrão
s .a
x  2 y  12
x  2 y  12
2 x  3 y  18
2 x  3 y  18
x, y  0
x, y  0
o mesmo problema na forma padrão :
o mesmo problema na forma padrão :
max[  u ]   3 x  4 y
max[  u ]   3 x  4 y
 x  2 y   12
 x  2 y   12
2 x  3 y  18
2 x  3 y  18
x, y  0
x, y  0
Suponhamos agora o problema
max u  3 x  4 y
s .a
x  2 y  12
2 x  3 y  18
x, y  0
este problema
na forma slack padrão pode ser escrito como :
max u  3 x  4 y
s .a
x  2 y  r  12
2 x  3 y  s  18
x, y, r , s  0
ou ainda :
max u  3 x  4 y
x  2 y  12   r
2 x  3 y  18   s
x, y, r , s  0
Este formato, como será visto, é muito prático para aplicação do
método Simplex, além de servir para a análise da dualidade e
análise de sensibilidade
Este formato nos diz que as variáveis do lado esquerdo podem
tomar qualquer valor, definindo as variáveis do lado direito
variáveis do lado esquerdo são chamadas de independentes
variáveis do lado direito de dependentes
se as variáveis do lado esquerdo forem iguais a zero:
x=0 e y=0 implica que r=12 e s=18
Vamos supor uma PL com m restrições e n variáveis,
onde:
mn
A PL está na forma canônica (padrão, regra..) se todas
as restrições forem equações e se cada restrição possuir
uma variável que ocorre somente nela, com coeficiente
igual a 1
•essas variáveis com coeficiente 1 são chamadas de
básicas (variáveis dependentes)
•as demais variáveis são chamadas de não básicas
No exemplo anterior:
max u  3 x  4 y
s .a
x  2 y  r  12
2 x  3 y  s  18
x, y, r , s  0
as variáveis
slack (de folga) são básicas
Entretanto, podem existir variáveis que não são slack’s e que
podem ser básicas, imaginem o problema:
max u  3 x  4 y  3 z
s .a
x  2 y  12
2 x  y  z  19
x, y, z  0
na forma slack :
max u  3 x  4 y  3 z
s .a
x  2 y  s  12
2 x  y  z  19
x, y, z, s  0
este sistema
é canônico
e z é básica (e não é slack! )
Considera-se em geral que:
•variável básica = variável dependente = variável
slack
•variável independente é sinônimo de não básica
A forma canônica facilita a solução da PL:
Qualquer problema de PL possui uma forma canônica!
Definição: qualquer ponto que satisfaça as restrições e a não
negatividade de uma PL é um ponto viável (feasible point)
Vamos ver um CONCEITO MUITO IMPORTANTE
Um ponto viável básico é obtido quando fazemos as variáveis
não básicas iguais a zero e calculamos as demais variáveis e
obtém-se valores não negativos;
Teorema Importante:
O máximo ou um mínimo de uma PL na forma canônica, se
existir, é um ponto viável básico
Vamos ver mais alguns conceitos importantes....
Uma PL está no formato canônico perfeito se:
•a Função Objetivo é do tipo maximizar U
•os valores dos b’s (lado direito das restrições) são todos
positivos
•a função objetivo é expressa somente em função de
variáveis não básicas
Vamos sempre procurar esta forma canônica perfeita!
Vamos supor o seguinte problema:
max u  x  y
s .a
x  2 y  s  12
Forma canônica perfeita
2 x  y  t  19
x, y, s, t  0
s e t são variáveis
Outro fato importante: este sistema pode ser transformado
numa outra forma canônica perfeita
básicas
Pontos básicos vinculados a formas canônicas perfeitas
são viáveis e portanto candidatos para o ÓTIMO...
Vamos ver agora o que se chama de pivoteamento
(pivoting):
é o procedimento usado para ir de uma forma canônica
para outra, mudando uma variável não básica para
variável básica
Para isso, vamos ver o “tableau” Simplex:
Considere:
Maximizar
c1 x1  c 2 x 2 .......... .......... .  d  u
sujeito
a
a1,1 x1  a1, 2 x 2 .......... .......  a1, n x n  s1  b1
a 2 ,1 x1  a 2 , 2 x 2 .......... .......  a 2 , n x n  s 2  b 2
.
.
a m ,1 x1  a m , 2 x 2 .......... .......  a m , n x n  s m  b m
x1 , x 2 ......, x n , s1 , s 2 ........ s m  0
Vamos passar as variáveis básicas s para o lado
direito e as variáveis b’s para a esquerda...
Maximizar
c1 x1  c 2 x 2 .......... .......... .  d  u
sujeito
a
a1,1 x1  a1, 2 x 2 .......... .........  a1, n x n  b1   s1
a 2 ,1 x1  a 2 , 2 x 2 .......... .......  a 2 , n x n  b 2   s 2
.
.
a m ,1 x1  a m , 2 x 2 .......... ....  a m , n x n  b m   s m
x1 , x 2 ......, x n , s1 , s 2 ........ s m  0
Em forma de tableau temos.......
tableau
AS RESTRIÇÕES DE NÃO NEGATIVIDADE NÃO
ESTÃO NO tableau PORQUE SE CONSIDERA QUE
ELAS ESTÃO ATENDIDAS
Como fazer o pivoteamento...xj por si
xj
a
i, j
*
ak , j
a i .l
  si
a k ,l
si
1 / ai, j
( a i .l ) / a i , j
a k , j /(  a i , j )
a k , l  ( a k , j )( a i , l ) /( a i , j )
 x j
O método Simplex para PL na forma canônica
perfeita (estágio 2)
Vamos considerar o seguinte exemplo:
Max U
4x  3y  2z  u
s .a
2 x  y  z  12   r
 x  2 y  3z  9  s
3x  4 y  z  6  t
não
negativida de
Variáveis não básicas
x
y
z
1
2
1
1
- 12

-r
-1
2
3
-9

-s
3
4
-1
-6

-t
4
-3
2
0

u
Coeficientes
da FO
Variáveis básicas
Primeiro passo: escolher qualquer coeficiente
positivo cj da função objetivo....p.e. o valor 4
x
y
z
1
2
1
1
- 12

-r
-1
2
3
-9

-s
4
-1
-6

-t
-3
2
0

u
3*
4
Segundo passo: procurar na coluna do 4 todos
valores positivos de ai,j..no caso 2 e 3....calculo
para cada um o valor de bi/ai,j
para 2 temos 12/2 = 6
para 3 temos 6/3 = 2 (menor valor...escolho
este...por isso o *....).....
Próximo passo....pivotar a3,1...ou seja vou x por t....
Obtenho:
Observem que o valor da FO é igual a 8
Mas este valor é o ótimo?...
NÃO.....ainda existe um coeficiente positivo na
FO...10/3....vamos fazer um novo pivoting.......
O novo tableau é:
Solução: t=0, y=0 e s=0
FO=87/4 e r=9/8 z=33/8 e x=27/8
Como transformar problemas de PL na sua forma canônica
perfeita......
por exemplo :
Max u  4x  3y  2z
s.a
x  2y - z
2x
-y

3
 -5
4x  2y  3z  7
x, y e z  0
Primeiro passo é colocar o sistema na sua forma slack...
por exemplo :
Max u  4x  3y  2z
Max
s.a
u  4x  3y  2z
x  2y - z
2x
-y

3
 -5
4x  2y  3z  7
x, y e z  0
s.a
x  2y - z  r
2x
-y
s
4x  2y  3z
x, y e z  0
Vamos multiplicar a segunda restrição por -1

3
 -5
 7
Estas duas restrições
não possuem
variáveis básicas
Max
u  4x  3y  2z
s.a
x  2y - z  r
- 2x  y
s
4x  2y  3z

3
 5
 7
x, y e z  0
Max
u  4x  3y  2z
s.a
x  2y - z  r
solução
- 2x
 y
4x  2y  3z
x, y e z  0
A1 e A2 são variáveis
artificiais.....

3
- s  A1  5
 A2  7
Duas questões importantes:
•as variáveis artificiais precisam ser iguais a zero para
validade das inequações
•caso apareçam variáveis básicas (VB’s) na FO o
Método Simplex não se aplica, neste caso deve-se
resolver um problema equivalente, sem VB na FO
por
exemplo :
Max U  x  r  s
Vamos
resolver?
solução
s.a
x  y  r  9
2x  y  s  10
4x - 2y  t  11
Max u  - 2x - 2y  19
s.a
xyr 9
2x  y  s  10
4x - 2y  t  11
x, y, r, s, t  0
x, y, r, s, t  0
As variáveis artificiais precisam ser iguais a zero, isso
pode ser feito de duas maneiras:
O Método do Grande M (Big M): quando for necessário o
emprego de variáveis artificiais, elas entram na FO com
coeficientes grandes para induzir o valor zero das
mesmas..exemplo...
Min U  3x  2y
Min UU 3x
3x2y2y
Min
s.a
s.a
s.a
x  2y  2
xx  22yy2 2
3x - y  4
3x
- yy 44
3x
x, y- 
0
x, y  0
x,vamos
y  0 colocar o problema na forma slack :
vamos colocar o problema na forma slack :
Max - U colocar
 -3x - 2yo problema na forma slack :
vamos
Max - U  -3x - 2y
x  2y- U
- r  -3x
2 - 2y
Max
x  2y - r  2
3x - y - s  4 com x, y, r, s  0
x  2y - r  2
3x - y - s  4 com x, y, r, s  0
r e s não são básicas, portanto é necessário :
3x - y - s  4 com x, y, r, s  0
r e s não são básicas, portanto é necessário :
Max - U  -3x - 2y
rMax
e s -não
são- 2y
básicas, portanto é necessário :
U

-3x
x  2y - r  A  2
Max
- U  -3x
- 2y
x3x 2y
- y -- rs  A
B
 24...neste caso como queremos A e B
x - 2y
B A
 2
3x
y - s-a rzero,
 4...neste
caso como
queremos
A e Bpara :
iguais
vamos modificar
o nosso
problema
iguais
a szero,
vamos
o nosso problema para :
3x
4 - MAmodificar
Max- y- -U
B
3x 
- 2y
- MB
Max
  3xcomo
- 2y - MA
- MB
neste
queremos
A eB
s.a - Ucaso
s.a
iguais
x  2y -ar zero,
 A  2vamos modificar o nosso problema
x3x 2y
- y -- rs  A
B
 24 com x, y, r, s, A, B  0
Max - U   3x - 2y - MA - MB
para :
r e s não são básicas, portanto
é necessário
r e s não são básicas, portanto
Max - U  -3x - 2y
:
é necessário
:
Max
- U  -3x - 2y
x  2y - r  A  2
x3x -2y
y - -s r B A
 4 2
neste
3x
- y caso
- s  como
B  4 queremos
A eB
iguais acaso
zero, como
vamos queremos
modificar o nosso
neste
A e B problema para :
Max - U   3x - 2y - MA - MB
iguais a zero, vamos modificar
o nosso problema
para :
s.a
Max - U   3x - 2y - MA - MB
x  2y - r  A  2
s.a
3x - y - s  B  4 com x, y, r, s, A, B  0
x  2y - r  A  2
3x - y - s  B  4 com x, y, r, s, A, B  0
Dois casos podem ocorrer:
•A e B são variáveis não básicas iguais a zero ou
•A, ou B ou ambas são básicas com valores iguais a zero
•se A ou B ou ambas forem diferente de zero o problema não tem
solução (infeasible)
Solução:
primeiro devemos retirar da FO as variáveis básicas A e B
Primeiro tableau:
x
y
r
s
1

1
2
-1
0
-2
3
-1
0
-1
-4

-B
- 6M

-U
- 3  4M
-2M
Maior coeficiente
-M
-M
-A
O tableau final será:
B
A
r
s
1
- 1/7
3/7
- 3/7
1/7
- 2/7

-y
2/7
1/7
- 1/7
- 2/7
- 10/7

-x
4/7 - M
9/7 - M
- 9/7
- 4/7
- 34/7
 -U
Portanto, A=0, B=0, r=0, s=0 e y=2/7 e x=10/7
valor de U = 34/7
Vejam que curioso: sem saber o valor de M resolvemos o
problema!!!
Segunda forma de tratar o problema das variáveis
artificais: O Método de Duas Fases
Mini U  3x  2y
Max - U  -3x - 2y
s.a
s.a
x  2y  2
Chega-se a:
x  2y - r  A  2
3x - y  4
3x - y - s  B  4
x, y  0
x, y, r, s, A, B  0
Fase I: Resolver o seguinte problema Minmizar
w  A B
s.a.
x  2y - r  A  2
3x - y - s  B  4
x, y, r, s, A, B  0
W só será zero se A e B forem zero,
portanto se existe o ponto P (x,y,r,s)
para o problema original, o ponto Q
(x,y,r,s,0,0) será solução do
problema com A e B
Fase II Dado que A e B são zeros, posso eliminá-los do Tableau final e
obtenho com as demais variáveis um novo problema de PL que
resolvido fornece os valores procurados!! Vamos continuar com
o nosso exemplo:
Minmizar
w  A B
s.a.
x  2y - r  A  2
3x - y - s  B  4
x, y, r, s, A, B  0
Primeiro vamos retirar as
variáveis básicas da FO e escrever
o tableau com as duas funções
objetivo U e W, obtemos:
x
y
r
s
1
1
2
-1
0
-2

-A
3
-1
0
-1
-4

-B
-3
-2
0
0
0

-U
4
1
-1
-1
-6

-w
Primeiro
pivô
B
y
r
s
- 1/3
7/3
-1
1/3
- 2/3

-A
1/3
- 1/3
0
- 1/3
- 4/3

-x
1
-3
0
-1
-4

-U
- 4/3
Segundo
pivô
7/3
-1
1/3
1
- 2/3

-w
Resultando em:
B
A
r
s
1
- 1/7
3/7
- 3/7
1/7
- 2/7

-y
2/7
1/7
- 1/7
- 2/7
- 10/7

-x
4/7
9/7
- 9/7
- 4/7
-1
-1
0
0
- 34/7
0
 -U
 -w
Observem w=0 e A=B=0; as duas colunas de A e B podem
ser eliminadas;
O tableau restante já apresenta o resultado final com
U=34/7 y= 2/7 e x= 10/7...o mesmo resultado do método
Big M
Bom, existem outros métodos (truques) para tratar
as variáveis fictícias, mas para nosso propósito
vamos ficar com esses dois!!!