Programação Linear - Slide

Prévia do material em texto

PESQUISA 
OPERACIONAL
Programação Linear - PL
Profa. Fátima Martins - UFCG
Programação Linear - PL
• É uma das principais ferramentas da PO.
• A função objetivo e todas as restrições são representadas por funções
lineares.
• Variáveis são contínuas.
• Objetivo – maximização (ou minimização) de uma função objetivo linear
com relação as variáveis de decisão do modelo.
• Respeitando-se as limitações (restrições) do problema expressas por um
sistema de equações e inequações associadas com as variáveis de
decisão do modelo. Incluindo as de não negatividade.
Programação Linear - PL
• Modelagem do problema: variáveis de decisão, função objetivo e
restrições
• A partir da construção do modelo matemático que representa o problema
real de PL, o próximo passo consiste em terminar a SOLUÇÃO ÓTIMA.
• A solução ótima é aquela com maior valor (se o problema for de
maximização) ou menor valor (se o problema for de minimização) na
função objetivo e que satisfaz as restrições lineares impostas.
Como encontrar a solução de problemas através da PL?
MAXIMIZAÇÃO MINIMIZAÇÃO
Programação Linear - PL
Formulação Matemática de um modelo geral de Programação Linear
Os problemas de programação linear buscam determinar valores ótimos para as 
variáveis de decisão X1, X2, ..... Xn, que devem ser contínuas..
que está sujeita a um conjunto de restrições lineares de igualdade (equações com sinal 
do tipo =) e/ou de desigualdade ( inequações com sinal do tipo ≤ ou ≥ ).
a fim de maximizar ou minimizar a função linear Z, 
As soluções que satisfazem todas 
as restrições, inclusive as de não 
negatividade, são chamadas 
soluções factíveis. A solução factível que apresenta 
melhor valor da função objetivo é 
chamada de solução ótima.
Programação Linear - PL
RESUMINDO: Passos básicos na obtenção de modelos de PL
1. Identificar as variáveis de decisão, representá-las em simbologia
algébrica.
2. Identificar o objetivo de interesse no problema, representá-lo como função
linear em termos das variáveis de decisão, que deverá ser maximizada ou
minimizada.
3. Identificar as restrições do problema, expressá-las como equações ou
inequações lineares em termos das variáveis de decisão.
Programação Linear - PL
Representação matemática do modelo: 
max ou mim Z = f (x1, x2, ..... xn ) = c1 x1 + c2 x2, ..... cnxn
Sujeito a: 
ɑ11x1 + ɑ12x2 +......... +ɑ1nxn ) {≤ = ≥} b1
ɑ21x1 + ɑ22x2 +......... +ɑ2nxn ) {≤ = ≥} b2
.
.
ɑm1x1 + ɑm2x2 +......... +ɑmnxn ) {≤ = ≥} bm
x1, x2, ..... xn ≥ 0 (restrição de não negatividade)
Onde: 
Z é a função objetivo
x1 são as variáveis de decisão
ɑij é a constante das restrições
b1 é o termo independente ou quantidade de 
recursos disponíveis 
ci é a constante da variável da função objetivo.
Exemplo de problema de PL 
Formulando o modelo: variáveis de decisão, função objetivo e restrições 
Exemplo 1 
Uma companhia deseja programar a produção de um utensílio de cozinha que requer o uso
de dois tipos de recursos – mão-de-obra e material. A companhia está considerando a
fabricação de três modelos e o seu departamento de engenharia forneceu os dados a
seguir:
Modelo
A B C
Mão-de-obra
(horas por unidade)
7 3 6
Material
(kg por unidade)
4 4 5
Lucro
($ por unidade)
4 2 3
O suprimento de material é de 200 kg
por dia. A disponibilidade diária de mão-
de-obra é 150 horas. Formule um
modelo de Programação Linear para
determinar a produção diária de cada um
dos modelos de modo a maximizar o
lucro total da companhia.
1. Quais as variáveis de decisão?
XA – produção diária do modelo A
XB – produção diária do modelo B
XC – produção diária do modelo C
2. Quais as restrições?
(Limitação de mão-de-obra) 7XA + 3XB + 6XC  150
(Limitação de material) 4XA + 4XB +5XC  200
(Não-negatividade) XA  0, XB 0, XC  0.
2 . Qual a função objetivo? maximização do lucro total
Max Z = 4XA + 2XB +3XC
Formulando o modelo
Exemplo de problema de PL 
Exemplo 2
Uma empresa fabrica dois produtos P1 e P2.
O lucro unitário de P1 é de R$ 1.000,00 e o lucro unitário de P2 é de R$ 1.800,00.
A empresa precisa de 20 horas para fabricar uma unidade de P1 e de 30 horas para
fabricar uma unidade e P2. O tempo anual de produção disponível é de 1.200 horas.
Alem disso, a demanda esperada para cada produto é de 40 unidades anuais para P1 e
30 unidades anuais de P2.
Qual o plano de produção para que a empresa maximize seu lucro nesses itens? 
Construa o modelo de programação linear:
1. Quais as variáveis de decisão?
X1 – Quantidade de P1 
X2 – Quantidade de P2
2. Quais as restrições? Relacionada ao tempo e demanda
(Tempo de produção ) 20X1 + 30X2  1200
(Demanda esperada de P1) X1  40
(Não-negatividade) X1  0, X2 0 
2 . Qual a função objetivo? maximização do lucro
Max L = 1000X1 + 1800X2
(Demanda esperada de P2) X2  30
Formulando o modelo
Encontrar quantidade para X1, X2 tais que: 
Max Z = 1000X1 + 1800X2
Sujeito as restrições: 
20X1 + 30X2  1200
X1  40
X2  30
X1  0, X2 0
modelo
Exemplo 3
Um sapateiro fabrica 6 sapatos por hora, se fizer somente sapatos; e 5 cintos por hora,
se fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 sapato e 1
unidade de couro para fabricar um cinto. O total disponível de couto é de 6 unidades. O
lucro unitário para sapatos é de $ 5,00 e o do cinto é de $ 2. Defina o plano de produção
do sapateiro, visando maximizar o lucro por hora.
Construa o modelo de programação linear:
Exemplo de problema de PL 
1. Quais as variáveis de decisão?
X1 – Quantidade de Sapatos 
X2 – Quantidade de cintos
2. Quais as restrições? Relacionada ao tempo e couro
(Tempo de produção ) 10X1 + 12X2  60
(Disponibilidade de couro) 2X1 + 1X2  6
(Não-negatividade) X1  0, X2 0 
2 . Qual a função objetivo? maximização do lucro
Max Z = 5X1 + 2X2
6 sap = 1 hora
1 sap = 10 min
5 cint = 1 hora
1 cint = 12 min
Formulando o modelo
Encontrar quantidade para X1, X2 tais que: 
Max Z= 5X1 + 2X2
Sujeito as restrições: 
10X1 + 12X2  60 
2X1 + 1X2  6
X1  0, X2 0 
Modelo
Modelo de Programação linear na forma 
Padrão e Canônica: 
max ou mim z = f (x1, x2, ..... xn ) = c1 x1 + c2 x2, ..... cnxn
sujeito a: 
ɑ11x1 + ɑ12x2 +......... +ɑ1nxn = b1
ɑ21x1 + ɑ22x2 +......... +ɑ2nxn = b2
.
.
ɑm1x1 + ɑm2x2 +......... +ɑmnxn ) = bm
xJ ≥ 0, j = 1,2,...n (restrição de não negatividade)
PADRÃO
• Os termos independentes devem ser 
não negativos
• Todas as restrições devem ser 
equações lineares na forma de 
igualdade
• As variáveis de decisão devem ser 
não negativas.
max z = f (x1, x2, ..... xn ) = c1 x1 + c2 x2, ..... cnxn
Sujeito a: 
ɑ11x1 + ɑ12x2 +......... +ɑ1nxn ≤ b1
ɑ21x1 + ɑ22x2 +......... +ɑ2nxn ≤ b2
.
.
ɑm1x1 + ɑm2x2 +......... +ɑmnxn ≤ bm
x1, x2, ..... xn ≥ 0 (restrição de não negatividade)
Modelo de Programação linear na forma 
Padrão e Canônica: 
CANÔNICA (de maximização)
Se a função objetivo for de 
maximização, todas as restrições 
devem ser representadas com sinal 
do tipo ≤
Modelo de Programação linear na forma 
Padrão e Canônica: 
CANÔNICA (de minimização)
min z = f (x1, x2, ..... xn ) = c1 x1 + c2 x2, ..... cnxn
sujeito a: 
ɑ11x1 + ɑ12x2 +......... +ɑ1nxn ≥ b1
ɑ21x1 + ɑ22x2 +......... +ɑ2nxn ≥ b2
.
.
ɑm1x1 + ɑm2x2 +......... +ɑmnxn ≥ bm
x1, x2, ..... xn ≥ 0 (restrição de não negatividade)
Se a função objetivo for de 
minimização, todas as restrições 
devem ser representadas com 
sinal do tipo ≥
Transformações para a forma padrão ou 
canônica
• Problema padrão de maximização pode ser transformado em um de minimização
• Problema padrãode minimização pode ser transformado em um de maximização
Transformando a função objetivo
Multiplica toda a função por -1 
e troca o objetivo para Min
Multiplica toda a função por -1 
e troca o objetivo para Max
EXEMPLO: Max Z= 5X1 + 2X2 Min - Z= - 5X1 - 2X2
EXEMPLO: Min Z = 80X1 + 100X2 Max - Z = - 80X1 - 100X2
Transformações para a forma padrão ou 
canônica
• Restrição de desigualdade do tipo ≤ pode ser transformada em outra do tipo ≥ 
• Restrição de desigualdade do tipo ≥ pode ser transformada em outra do tipo ≤
Transformando as restrições ≥ e ≤ 
Exemplo: 10X1 + 12X2  60 -10X1 - 12X2 ≥ - 60 
Multiplica toda a função por -1 
e vira o sinal
Multiplica toda a função por -1 
e vira o sinal
Exemplo: 20X1 + 30X2 ≥ 120 - 20X1 - 30X2 ≤ - 120 
• Restrição de igualdade pode ser transformada em duas de desigualdade
Transformando as restrições de = em ≥ e ≤ 
Transformações para a forma padrão ou 
canônica
EXEMPLO: 40X1 + 60X2 = 150
40X1 + 60X2 ≥ 150
40X1 + 60X2 ≤ 150
• Restrição de desigualdade do tipo ≤ pode ser reescrita por meio de uma equação de 
igualdade com a adição de uma variável não negativa no lado esquerdo – variável de 
folga
Transformando as restrições de ≤ em =
Transformações para a forma padrão ou 
canônica
Explicando: Se em tenho: 5x1 + 2x2 ≤ 40. Eu posso alterar para 5x1 + 2x2 = 40 ???
Agora, se atribuir um valor para X1 e para X2, o que acontece? 
Vamos atribuir 0 para as duas variáveis. 0 + 0 = 40 Está correto? NÃO
5x1 + 2x2 + X3 = 40. 0 + 0 + X3 = 40 Está correto!!
X3 = 40
Transformando as restrições de ≥ em =
Transformações para a forma padrão ou 
canônica
Explicando: Se em tenho: 5x1 + 2x2 ≥ 40. Se altero para 5x1 + 2x2 = 40. Posso fazer isso?
Agora, se atribuir um valor para X1 e para X2, o que acontece? 
Vamos atribuir 0 para as duas variáveis. 0 + 0 = 40 Está correto? NÃO
5x1 + 2x2 - X3 = 40. 0 + 0 - X3 = 40 Está correto!!
• Restrição de desigualdade do tipo ≥ pode ser transformada em uma equação de 
igualdade com a subtração de uma variável não negativa no lado esquerdo – variável de 
excesso
- X3 = 40 ou X3 = - 40
Transformações para a forma padrão ou 
canônica
• Uma variável Xj que não tem restrição de sinal, chamada variável livre, pode ser expressa 
com a diferença de duas variáveis não negativas.
Explicando: uma variável X1, pode ser representada por + X1 – X1 ou + X1 – X1 = 0 
Variável livre
Transformações para a forma padrão ou 
canônica
Transforme o problema a seguir na forma canônica
Multiplicar por -1
Transformo em duas expressões uma com sinal ≥ e outra com 
sinal ≤, depois multiplico a que está com o sinal ≥ por -1
3x1 + 4x2 + 5x3 ≥ 580 Multiplico essa por -1 e 
vira o sinal 
3x1 + 4x2 + 5x3 ≤ 580
Para um problema de PL a seguir, reescreva-o na forma padrão, a partir de uma 
função objetivo de minimização
Transformações para a forma padrão ou 
canônica
Max = 5x1 - 5x1 + 2x2 - 4x3 - x4
Ajustei a variável livre
Colocando na forma padrão
Variável de folga e ajusta a variável livre
Variável de excesso e ajusta a variável livre
Hipóteses do modelo de Programação Linerar
Um problema de programação linear, a função objetivo e as restrições devem
ser lineares, as variáveis de decisão devem ser contínuas e não negativas, e os
parâmetros do modelo determinísticos, de forma a satisfazer as seguintes
hipóteses:
Proporcionalidade: para cada variável de decisão do modelo, a sua
contribuição em relação a função objetivo e as restrições seja diretamente
proporcional ao valor da variável de decisão.
Hipóteses do modelo de Programação Linerar
Hipóteses do modelo de Programação Linerar
Hipóteses do modelo de Programação Linerar
Aditividade: O valor da função objetivo ou de cada função de restrição é 
expresso pela soma das contribuições individuais de cada variável de decisão.
Divisibilidade e não negatividade: cada uma variável de decisão pode assumir
quaisquer valores não negativos dentro de um intervalo, podendo ser fracionário desde
que atenda as restrições do modelo.
Certeza: os coeficientes da função objetivo, das restrições e os termos independentes
são determinísticos (constantes e conhecidos).
•Transforme os problemas de maximização em minimização
Multiplica toda a função por -1 
e troca o objetivo para Min
1)Transforme os problemas na forma padrão
Variável de folga
Variável de Excesso
Variável de Excesso
1) Transforme os mesmos problemas para a forma canônica
Multiplica toda a função por -1 e troca o sinal