aula 2 Pesquisa Operacional

Prévia do material em texto

Modelos de Programação Linear 
Fabiana Gomes dos Passos 
Roteiro da aula 
 
• Programação Linear 
 
– Modelo de Programação Linear 
– Pressupostos de um modelo de Programação Linear 
– Passos básicos de Programação Linear 
– Exemplos de Aplicação da Programação Linear 
 
 
 
Programação Linear 
• Um problema de programação linear é um problema de 
programação matemática estática onde a função objetivo e as 
restrições são funções lineares. 
• ÁREAS DE APLICAÇÃO 
– Administração da Produção 
– Análise de Investimento 
– Alocação de recursos limitados 
– Logística 
– Custo de Transporte 
– Localização da rede de distribuição 
– Alocação de recursos em marketing entre diversos meios de 
comunicação 
 
 
Programação Linear 
• MODELO DE PROGRAMAÇÃO LINEAR 
Programação Linear 
• Onde 
 
 
 
 
Para i = 1, ..., m 
• n é o número de variáveis 
• m é o número de restrições do problema 
• i é o índice de uma determinada restrição 
 
Programação Linear 
• Existem 4 características para um problema na forma padrão: 
– A função objetivo é de Maximizar; 
– As restrições têm o sinal de menor ou igual; 
– As constantes de todas as restrições são não negativas; 
– As variáveis de decisão são não negativas. 
 
 
 
Programação Linear 
• Ou na forma reduzida 
 
Maximizar: Z = 
 
Sujeito a: 
 
 
 
 x1, x2, ..., xn ≥ 0 
 


n
j
jjxc
1



n
j
ijij mibxa
1
),...,2,1(
Programação Linear 
• Ou na forma matricial 
Maximizar: 
 
Sujeito a: Ax ≤ b 
 x≥0 
onde: 
– A = matriz (mxn) dos coeficientes das variáveis de decisão nas restrições 
– x = vetor coluna (nx1) das variáveis de decisão 
– b = vetor coluna (mx1) do lado direito das restrições, 
– c = vetor linha (1xn) dos coeficientes das variáveis de decisão função 
objetivo 
 
 
 
 
cxz 
Programação Linear - Exemplos 
Problema de Minimização 
 
Min Custo = 80X1 + 10X2 
Sujeito a 
9X1 + 3X2 ≥ 30 
X1 + 8X2 ≥ 20 
X1, X2 ≥ 0 
 
Problema de Maximização 
 
Max Lucro = 110X1 + 65X2 
Sujeito a 
2X1 + X2 ≤ 7 
7X1 + 7X2 ≤ 30 
X1, X2 ≥ 0 
 
Pressupostos de um Modelo de 
Programação Linear 
 
• Proporcionalidade 
 
 O valor da função objetivo é diretamente proporcional ao 
nível de atividade de cada variável de decisão, ou seja, o valor 
da função objetivo se altera de um valor constante dada uma 
variação constante da variável de decisão. 
 
Pressupostos de um Modelo de 
Programação Linear 
 
• Aditividade 
 
 Não existe interdependência entre as variáveis de decisão do 
modelo, isto é, não permiti a existência de termos cruzados , 
tanto na função-objetivo como nas restrições. 
 
 
Pressupostos de um Modelo de 
Programação Linear 
 
• Divisibilidade 
 
 Qualquer variável de decisão pode assumir qualquer valor 
fracionário. 
 
 
 
Pressupostos de um Modelo de 
Programação Linear 
• Certeza 
 Todos os parâmetros do modelo são constantes conhecidas 
(a,b,c) provocando a análise de sensibilidade dos resultados. 
 
 
 
Modelagem em Programação Linear 
• Passos básicos na obtenção de modelos de P.L: 
 
1. Identificar as variáveis de decisão, representá-las em simbologia 
algébrica; 
2. Identificar as restrições do problema, expressá-las como equações 
ou inequações lineares em termos das variáveis de decisão; 
3. 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. 
 
 
 
Exemplo – Determinação do Mix de 
Produção 
 Uma companhia deseja programar a produção de um utensílio de cozinha 
que requer usos 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 contidos na tabela 
abaixo. O suprimento de material é de 200 quilos 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. 
Setor Produtivo 
Modelo 
A B C 
Mão de obra 
(horas por unidade) 
7 3 6 
Material 
(quilos por unidade) 
4 4 5 
Lucro Unitário 4 2 3 
• Variáveis 
X1 = produção diária do produto A; 
X2 = produção diária do produto B; 
X3 = produção diária do produto C; 
Z = lucro total da companhia. 
• Restrições 
a) Limitação da mão de obra; 
b) Limitação do material; 
c) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da companhia 
0,,
200544
150637:.
324
321
321
321
321




xxx
xxx
xxxas
xxxZMax
Setor Produtivo 
Modelo 
A B C 
Mão de obra 
(horas por unidade) 
7 3 6 
Material 
(quilos por unidade) 
4 4 5 
Lucro Unitário 4 2 3 
Exemplo – Fabricação de Produtos 
Exemplo – Fabricação de Produtos 
 A WINDOR GLASS Inc. dispõe de capacidade extra para produzir dois novos 
produtos. A demanda é muito maior que a capacidade disponível (toda 
produção poderá ser vendida). 
 Através dos dados contidos na tabela, logo abaixo, 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. 
Setor Produtivo 
Produto Capacidade 
Disponível Janelas Portas 
Montagem 1 hora/unid. - 4.000 horas/mês 
Laminação - 2 hora/unid. 12.000 horas/mês 
Corte 3 hora/unid. 2 hora/unid. 18.000 horas/mês 
Lucro Unitário $ 3,00 $ 5,00 
• Variáveis 
X1 = qtde. de janelas, em milhares de unidades; 
X2 = qtde. de portas, em milhares de unidades; 
Z = lucro total obtido com novos produtos. 
• Restrições 
a) disponibilidade do setor de montagem; 
b) disponibilidade do setor de laminação; 
c) disponibilidade do setor de corte; 
d) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da empresa 
0,
60023
4002
33,133:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
Setor Produtivo 
Produto Capacidade 
Disponível Janelas Portas 
Montagem 1 hora/unid. - 4.000 horas/mês 
Laminação - 2 hora/unid. 12.000 horas/mês 
Corte 3 hora/unid. 2 hora/unid. 18.000 horas/mês 
Lucro Unitário $ 3,00 $ 5,00 
Exemplo – Fabricação de Produtos 
 
Conceitos de Solução num Problema de 
Programação Linear 
 
• Solução – qualquer valor para as variáveis de decisão, 
independente de ser uma escolha desejável ou permissível; 
 
• Solução viável – uma solução em que todas as restrições são 
satisfeitas; 
 
• Solução inviável – uma solução em que ulguma das restrições ou 
as condições de não negatividade não são atendidas; 
 
• Solução ótima – uma solução viável que maximiza (ou minimiza) 
a função objetivo em toda região viável (conjunto admissível), 
podendo ser única ou não. 
 
Estrutura Algorítmica da Programação Linear 
Exercício de Fixação 
Uma fábrica pretende produzir dois produtos, o produto 1 e o produto 2. Ambos os 
produtos passam por três fases de desenvolvimento durante o processo de 
manufatura, cada uma das quais se realiza num departamento diferente. No próximo 
mês, cada um dos departamentos tem um determinado números disponível de horas 
por máquina, para ser utilizado na concepção destes dois produtos. Por sua vez, cada 
um dos produtos requer, por unidade, um dado tempo de utilização de cada máquina. 
Tempo disponível (h) 
Tempo requeridopor unidade (h) 
Produto 1 
Produto 2 
1 0 
0 2 2 
3 
4 12 18 
Departamentos 
1 2 3 
 
Para manter o problema simples, vamos assumir que os custos de produção de cada 
produto são constantes, independentemente da quantidade produzida. 
Supondo que o lucro, por unidade, de cada produto são de R$ 3 para o produto 1 e 
R$ 5 para o produto 2. 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. 
• Variáveis 
X1 = produção diária do produto 1; 
X2 = produção diária do produto 2; 
Z = lucro total obtido com os dois produtos. 
• Restrições 
a) Tempo disponível para fabricar no departamento 1; 
b) Tempo disponível para fabricar no departamento 2; 
c) Tempo disponível para fabricar no departamento 3; 
d) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da companhia 0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
Exercício de Fixação 
Tempo disponível (h) 
Tempo requerido por unidade (h) 
Produto 1 
Produto 2 
1 0 
0 2 2 
3 
4 12 18 
Departamentos 
1 2 3 
Referências 
 
 
 
 
• ANDRADE, Eduardo Leopoldino de. 
Introdução à pesquisa operacional: métodos e 
modelos para análise de decisões. 3. ed. Rio 
de Janeiro: LTC, 2004.192 p. 
 
• LACHTERMACHER, Gerson. Pesquisa 
operacional na tomada de decisões. 2. ed. 
rev. e atual. Rio de Janeiro: Elsevier, 2004. 
384 p.