aula 3 Pesquisa Operacional

Prévia do material em texto

Programação Linear com o uso 
do Método Gráfico 
Fabiana Gomes dos Passos 
Roteiro da aula 
 
• Método Gráfico 
 
– Quando se deve utilizar o Método Gráfico 
– Exemplo de Aplicação 
– Passos para Solução Gráfica 
 
 
 
 
Método Gráfico 
 
• Quando o problema envolve apenas duas variáveis de 
decisão, a solução ótima de um problema de programação 
linear pode ser encontrada graficamente; 
 
• Com poucas variáveis, métodos exatos ou enumerativos 
produzem soluções ótimas em tempo computacional 
razoável; 
 
• Com muitas variáveis, métodos aproximativos são indicados. 
 
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 alguma das restrições ou 
as condições de não negatividade não são atendidas; 
 
 
 
• Supondo que existem soluções viáveis 
– Encontrar a melhor solução admissível, em termos do valor da função 
objetivo do modelo 
• Solução ótima 
– Uma solução admissível com o melhor valor da função objetivo 
 
 Num problema de maximização – é uma solução admissível 
o mix de produção (ponto ótimo) com o maior valor de Z. 
 
 Num problema de minimização – é uma solução admissível 
o mix de produção com o menor valor de Z. 
Objetivo da Programação Linear 
Exemplo 1 
o A Companhia MAXIMÓVEIS fabrica 2 tipos de produtos: 
o Cadeiras e Mesas 
o Margem de Contribuição Unitária: 
o Cadeira = $ 8,00 
o Mesa = $ 6,00 
o As cadeiras e mesas são processadas em 2 departamentos: 
o Montagem 
o Acabamento 
 
 Através dos dados contidos na tabela , 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. 
Exemplo 1 
o Cada unidade dos produtos consome as seguintes horas na fabricação: 
Departamento 
Montagem 
Acabamento 
 Cadeiras 
4 
2 
Mesas 
2 
4 
Horas totais 
disponíveis 
60 
48 
Horas por unidade 
 
 
• Variáveis 
X1 = Quantidade de cadeiras; 
X2 = Quantidade de mesas; 
Z = lucro total da companhia. 
• Restrições 
a) Limitação de montagem ; 
b) Limitação de acabamento; 
c) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da companhia 
0,
4842
6024:.
68
21
21
21
21




xx
xx
xxas
xxZMax
 
1. Qual o mix de produção entre mesas e cadeiras que 
maximiza o lucro da firma? 
 
1. Ou seja, Quanto produzir de cadeiras (x1) e mesas 
(x2) para maximizar a função objetivo? 
 
2. Qual será o lucro máximo da companhia? 
Problema 
Passos para resolução gráfica de 
problemas de programação linear 
o Passo 1 – estabelecer os dois eixos que irão representar as 
quantidades x1 e x2; 
 
o Passo 2 – encontrar o conjunto de soluções viáveis do 
problema (representação gráfica de cada uma das restrições); 
 
o Passo 3 – traça-se a reta da função objetivo na origem 
 
 
o Passo 4 – desloca-se esta reta paralelamente até encontrar o 
máximo da função no conjunto definido pelas restrições. 
 
02211  nnxcxcxcz 
 
Solução Gráfica 
Eixo X – CADEIRA (x1) 
Eixo Y – MESA (x2) 
 
 
1 – Estabelecer os dois eixos que irão representar 
as quantidades x1 e x2 
CADEIRA (x1) 
MESA (x2) 
 
Solução Gráfica 
Restrição 1: MONTAGEM 
4x1 + 2x2  60 
x1 = 0  x2  30 (0,30) 
x2 = 0  x1  15 (15,0) 
2 – Colocar as restrições no gráfico 
15 
30 
MONTAGEM 
CADEIRA (x1) 
MESA (x2) 
4x1 + 2x2  60 
 
Solução Gráfica 
Restrição 2: ACABAMENTO 
2x1 + 4x2  48 
x1 = 0  x2  12 (0,12) 
x2 = 0  x1  24 (24,0) 
12 
24 
MESA (x2) 
CADEIRA (x1) 
ACABAMENTO 
2x1 + 4x2  48 
 
Solução Gráfica 
15 24 
ACABAMENTO 
30 
MONTAGEM 
CADEIRA 
MESA 
2 – Determinar a área de soluções viáveis 
Cada ponto dessa região, 
definido pelas coordenadas 
(x1, x2) é uma solução viável 
12 
SOLUÇÕES VIÁVEIS 
 
Solução Gráfica 
3 – Encontrar a solução a partir das curvas de nível 
 (retas paralelas definidas pela função-objetivo) 
Para saber os valores de x1 e x2 para um dado 
nível de MCT, por exemplo de $ 48,00: 
Tem-se que: 8x1+ 6x2 = 48 
Para x1 = 0; x2 = 8 (0, 8) 
Para x2 = 0, x1 = 6 (6, 0) 
CADEIRA 
MESA 
15 
8 
6 
12 
Função Objetivo 
8x1 + 6x2 = 48 
 
Solução Gráfica 
Supondo uma maior MCT, 
por exemplo de $ 72,00: 
Tem-se que: 8x1+ 6x2 = 72 
Para x1 = 0; x2 = 12 (0,12) 
Para x2 = 0, x1 = 9 (9, 0) 
CADEIRA 
MESA 
15 
12 
Função Objetivo 
8x1 + 6x2 = 48 
8 
6 9 
Função Objetivo 
8x1 + 6x2 = 72 
 
Solução Gráfica 
Repete o processo até encontrar a linha 
de máxima MCT que esteja dentro da 
área de soluções possíveis 
Este ponto de intercessão representa a 
solução possível ótima 
CADEIRA 
MESA 
15 
12 
Função Objetivo 
8x1 + 6x2 = 48 
8 
6 9 
Função Objetivo 
8x1 + 6x2 = 72 
Solução ótima 
Solução Gráfica 
CADEIRA 
MESA 
12 
Solução ótima 
Neste exemplo, a solução ótima está 
na interseção entre: 
a função-objetivo e qualquer uma 
das restrições, ou 
as 2 restrições 
Acabamento 
Montagem 
15 
Calculando o Ponto ótimo 
• Pelo gráfico, na intercessão entre as 2 restrições 
 Montagem 4C + 2M = 60 (1) 
Acabamento 2C + 4M = 48 (2) 
 
Calculando C pela 2ª equação: 
2C + 4M = 48  C = 24 – 2M (3) 
Substituindo em 1: 
4(24 – 2M) + 2M = 60 
96 –8M + 2M = 60  - 6M= - 36  M = 6 
Substituindo em 3: 
C = 24- 2(6) 
C = 12 
Solução ótima: 6 mesas e 12 cadeiras 
 
Solução Gráfica 
4 – Encontrar a solução pela comparação dos pontos 
extremos 
 Através de todos os pontos extremos da área de soluções viáveis 
e escolhemos aquele com maior MCT 
CADEIRA 
MESA 
(0,12) 
Solução ótima 
(15,0) (0,0) 
(12,6) 
MCT = 8x1 + 6x2 
(0,0) MCT = 0 
(0,12) MCT = 72 
(15,0) MCT = 120 
(12,6) MCT = 132 
Exemplo 2 
 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 horas/dia 
Laminação - 2 hora/unid. 12 horas/dia 
Corte 3 hora/unid. 2 hora/unid. 18 horas/dia 
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,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
Setor Produtivo 
Produto Capacidade 
Disponível Janelas Portas 
Montagem 1 hora/unid. - 4 horas/dia 
Laminação - 2 hora/unid. 12 horas/dia 
Corte 3 hora/unid. 2 hora/unid. 18 horas/dia 
Lucro Unitário $ 3,00 $ 5,00 
Exemplo 2 
 
1. Quanto produzir de janelas (x1) e portas (x2) para 
maximizar a funçãoobjetivo? 
 
2. Qual será o lucro máximo da companhia? 
 
Problema 
Solução Gráfica 
0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
2 x 
9 
8 
7 
6 
5 
4 
3 
2 
1 
0 
0 1 2 3 4 5 6 7 8 9 
1 x 
12 2 2  x 
4 1  x 
18 2 3 2 1   x x 
0 2  x 
0 1  x Neste exemplo, a solução 
ótima está na interseção 
entre: 
a função-objetivo e 
qualquer uma das 
restrições, ou 
as 2 restrições 
Calculando o Ponto ótimo 
• Pelo gráfico, na intercessão entre as 2 restrições 
 Laminação 2x2 = 12 (1) 
Corte 3x1 + 2x2 = 18 (2) 
 
Calculando x2 pela 1ª equação: 
2x2 = 12  x2 = 6 (3) 
Substituindo em 2: 
3x1 + 2(6) = 18 
3x1 + 12 = 18  3x1 = 6 x1 = 2 
 
Solução ótima: 2 janelas e 6 portas 
Calculando o Lucro Máximo 
• Substitua o ponto ótimo, encontrado anteriormente, 
na equação da função objetivo Z 
 
 Z = 
 
 
 
 
Solução ótima: 2 janelas e 6 portas 
 
Como X1 = 2 e X2 = 6 
 
Substituindo esses valores na função objetivo: 
 
3(2) + 5(6) = 6 + 30 = 36 
 
O lucro máximo da companhia é R$ 36,00 
 
5 3 2 1  x x 
Solução Gráfica 
• O que fazer se além de portas e janelas a WINDOR puder fabricar, também, 
mesas e armários? 
Resolver graficamente o problema torna-se inviável ... É necessário usar 
métodos numéricos mais eficazes e eficientes. 
 
• Quantos produtos diferentes uma fábrica pode produzir? 
5, 10, 100, 1000, ... 
 
• Quantos setores de produção uma fábrica possui? 
5, 10, 100, 1000, ... 
 
• E se existem restrições adicionais em relação ao uso de matéria-prima, 
energia, estoques, mão de obra, cadeia de suprimento e distribuição? 
Outros modelos, mais complexos, poderão ser formulados ... 
A solução gráfica não se aplica a estas outras situações !!! 
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 requerido por 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 os lucros, 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 
Representação gráfica do problema 
 
x1 
x2 
2 4 
6 
8 
2 
4 
6 8 
x1 = 4 
2x2 = 12 
3x1 + 2x2 = 18 
0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
x1 
x2 
2 4 
6 
8 
2 
4 
6 8 
Z = 10 = 3x1 + 5x2 
Z = 20 = 3x1 + 5x2 
Z = 36 = 3x1 + 5x2 
(2, 6) 
Solução ótima: 2 produtos 1 e 
6 produtos 2 
 
Como X1 = 2 e X2 = 6 
3(2) + 5(6) = 6 + 30 = 36 
Lucro máximo é R$ 36,00 
 
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.