Modulo 3 - Formas Geral, Padrão e Canônica

Prévia do material em texto

Módulo 3
Programação Linear
Formas Geral, Padrão e Canônica
27
Formas Geral, Padrão e Canônica
Prof. Ms. Antonio dos Santos
O objetivo da PL é determinar entre as soluções
factíveis de um problema de otimização, uma que
seja a “melhor”, medida pelo valor da função
Objetivo da PL 28
seja a “melhor”, medida pelo valor da função
objetivo do modelo. Por "melhor" entende-se o
maior ou menor valor, dependendo se o objetivo é
maximizar ou minimizar.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
A função a maximizar(minimizar),
Z= c1 x1+ c2 x2+ …+ cN xN ,
denomina-se função objetivo (FO)
Relembrando alguns conceitos fundamentais
29
As equações (inequações)
denominam-se restrições.
As desigualdades x1 ≥≥≥≥ 0, x2 ≥≥≥≥ 0 ,…, xN ≥≥≥≥ 0
denominam-se condições de não negatividade.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
As variáveis x1 , x2 , ... , xN ,
denominam-se variáveis de decisão.
As constantes aij ,
Relembrando alguns conceitos fundamentais
30
ij
denominam-se coeficientes tecnológicos.
As constantes bi ,
denominam-se termos independentes.
As constantes cj ,
denominam-se coeficientes da função objetivo
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Qualquer especificação de valores para as variáveis
de decisão (x1, x2,…, xN ) que satisfaça as restrições
do modelo e as condições de não negatividade
denomina-se solução factível.
Relembrando alguns conceitos fundamentais
31
denomina-se solução factível.
O conjunto de todas as soluções factíveis
denomina-se região de factibilidade.
Uma solução ótima maximiza (minimiza) a função
objetivo sobre toda a região de factibilidade.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Soluções do Problema de PL
� Um problema de PL pode ter:
� uma única solução ótima
� ou
32
� ou
� múltiplas soluções ótimas (uma infinidade)
� ou 
� não ter ótimo finito
� ou
� não ter nenhuma solução (neste caso o problema é infactível)
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Maximizar(minimizar) Z= c1 x1 + c2 x2 + …+ cN xN
sujeito a
a11 x1 + a12 x2 + … + a1 j xj + …+ a1N xN { ≤≤≤≤, =, ≥≥≥≥} b1
a21 x1 + a22 x2 + … + a2 j xj + …+ a2N xN {≤≤≤≤, =, ≥≥≥≥} b2
colunacoluna jj
FunçãoFunção objetivoobjetivo
restriçõesrestrições
Programação Linear
Problema na Forma Geral
33
a21 x1 + a22 x2 + … + a2 j xj + …+ a2N xN {≤≤≤≤, =, ≥≥≥≥} b2
…
ai 1 x1 + ai 2 x2+ … + ai j xj + …+ ai N xN {≤≤≤≤, =, ≥≥≥≥} bi
…
aM 1 x1+ aM 2 x2+ … + aM j xj + …+ aM N xN {≤≤≤≤, =, ≥≥≥≥} bM
x1, x2,…, xj ,…, xN ≥≥≥≥0 
onde ai j , bi e cj ( i=1,2,…,M, j=1,2,…,N ) são constantes e em cada 
restrição apenas se verifica uma e só uma das relações {≤, =, ≥}.
linha ilinha i
Condições de nãoCondições de não
negatividadenegatividade
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Problema na Forma Canônica
Maximizar Z= c x + c x + …+ c x
Quando as restrições de um modelo de Programação
Linear são apresentadas na forma de inequações do tipo
menor ou igual, diz-se que esse modelo está na forma
canônica.
34
Maximizar Z= c1 x1+ c2 x2+ …+ cN xN
sujeito a
a11 x1 + a12 x2 + …+ a1N xN ≤≤≤≤ b1
a21 x1 + a22 x2 + …+ a2N xN ≤≤≤≤ b2
.. … 
aM 1 x1 + aM 2 x2 + …+ aM N xN ≤≤≤≤ bM
x1, x2 ,…, xj,…,xN ≥≥≥≥0 
canônica.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Maximizar Z= c x + c x + …+ c xMaximizar Z= c x + c x + …+ c x
Quando as restrições de um modelo de Programação
Linear são apresentadas na forma de equações diz-se
que esse modelo está na forma padrão (ou “standard”).
Programação Linear
Problema na Forma Padrão
35
Maximizar Z= c1 x1+ c2 x2+ …+ cN xN
(Minimizar)
sujeito a
a11 x1 + a12 x2 + …+ a1N xN = b1
a21 x1 + a22 x2 + …+ a2N xN = b2
… 
aM 1 x1 + aM 2 x2 + …+ aM N xN = bM
x1, x2 ,…, xj,…,xN ≥≥≥≥0 
Maximizar Z= c1 x1+ c2 x2+ …+ cN xN
(Minimizar)
sujeito a
a11 x1 + a12 x2 + …+ a1N xN = b1
a21 x1 + a22 x2 + …+ a2N xN = b2
… 
aM 1 x1 + aM 2 x2 + …+ aM N xN = bM
x1, x2 ,…, xj,…,xN ≥≥≥≥0 
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Operações de Reformulação
Qualquer problema de maximização pode converter-se
num problema de minimização, pois:
36
máximo Z = mínimo (-Z)
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Operações de Reformulação
Qualquer restrição de desigualdade de tipo “≤” pode ser
convertida numa restrição do tipo “≥” multiplicando por
(-1) ambos os seus membros.
37
ai 1 x1 + ai 2 x2 + …+ ai N xN ≤≤≤≤ bi 
- ai 1 x1 - ai 2 x2 - …- ai N xN ≥≥≥≥ - bi
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
ai 1 x1 + …+ ai N xN ≤≤≤≤ bi 
Operações de Reformulação
Qualquer restrição de desigualdade pode ser convertida
numa restrição de igualdade, através da introdução de uma
nova variável (variável de excesso ou folga) F de valor não
negativo.
38
ai 1 x1 + …+ ai N xN ≤≤≤≤ bi 
ai 1 x1 + …+ ai N xN + F= biF ≥≥≥≥ 0
negativo.
ai 1 x1 + …+ ai N xN ≥ bi 
ai 1 x1 + …+ ai N xN - F= biF ≥≥≥≥ 0
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos