Aula4 PL grafico

Prévia do material em texto

Pesquisa Operacional 
Aula 4 – Solução Gráfica em 
Programação Linear 
 
Prof. Marcelo Musci 
aula@musci.info 
www.musci.info 
 
 
Resolução Gráfica 
Aplicável para modelos com 02 variáveis de decisão 
Útil para a ilustração de alguns conceitos básicos. 
 
 
 
 
 Caso: Tintas e Tintas S.A. 
 A meta do problema é achar a melhor 
solução viável, ou seja, a solução ótima. 
 Para isso, precisamos saber quantas 
soluções viáveis o problema possui. 
 Resposta: infinitas 
 Não é possível resolver o problema por 
enumeração 
 
Propriedades do Modelo de PL 
 No exemplo da Tintas e Tintas S.A., o objetivo e as 
restrições são todos funções lineares. 
 Linearidade implica que a PL deve satisfazer três 
propriedades básicas: 
 Proporcionalidade 
 Aditividade 
 Certeza 
Propriedades do Modelo de PL 
 Proporcionalidade: 
 A contribuição de cada variável de decisão (p.ex. x1 e x2), tanto na 
função objetivo quanto nas restrições, seja diretamente proporcional 
ao valor da variável 
 Por exemplo, 5x1e 4x2 definem o lucro para a produção de x1e x2 
toneladas de tinta para exteriores e interiores, respectivamente, 
sendo que os lucros unitários por tonelada (5 e 4) darão as 
constantes de proporcionalidade; 
 Por outro lado, se a empresa der algum desconto por quantidade 
quando as vendas ultrapassarem certas quantidades, o lucro não 
será mais proporcional às quantidades de produção, x1 e x2, e a 
função lucro se torna não linear; 
Propriedades do Modelo de PL 
 Aditividade: 
 A contribuição total de todas as variáveis da função objetivo e das 
restrições é a soma direta das contribuições individuais de cada 
variável 
 No exemplo, o lucro total é igual à soma dos dois componentes 
individuais do lucro; 
 Por outro lado, se os dois produtos competirem por participação de 
mercado, de modo que um aumento nas vendas de um deles 
provoque um efeito adverso nas vendas do outro, então a 
propriedade de Aditividade não é satisfeita e o modelo deixa de ser 
linear; 
Propriedades do Modelo de PL 
 Certeza: 
 Todos os coeficientes da função objetivo e das restrições do modelo 
de PL são determinísticos, o que significa que são constantes 
conhecidas 
 Isso raramente ocorre na vida real, sendo que o mais provável é 
que os dados sejam representados por distribuições de 
probabilidade; 
 Em essência, os coeficientes em PL são aproximações do valor 
médio das distribuições de probabilidade; 
 Se os desvios padrão dessas distribuições forem suficientemente 
pequenos, a aproximação será aceitável; 
Resolução Gráfica 
 O procedimento gráfico inclui duas etapas: 
 Determinar a região de soluções viáveis; 
 Determinar a solução ótima entre todos os pontos 
viáveis da região de soluções; 
 
 A seguir vamos resolver o modelo de 
maximização do problema da Tintas e Tintas 
S.A. usando a solução gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
 Problema de mix de Produção 
 Fabricação de dois modelos de brinquedos: B1 e B2. 
 Lucros unitários/dúzia: $8 para B1 e $5 para B2 
 Recursos disponíveis: 
 1000 kg de plástico especial. 
 40 horas para produção semanal. 
 
 Requisitos do Departamento de Marketing: 
 Produção total não pode exceder 700 dúzias; 
 A quantidade de dúzias de B1 não pode exceder em 350 a 
quantidade de dúzias de B2. 
 
Dados técnicos: 
 B1 requer 2 kg de plástico e 3 minutos por dúzia. 
 B2 requer 1 kg de plástico e 4 minutos por dúzia. 
 
Resolução Gráfica 
 A Gerência está procurando um programa de 
produção que aumente o lucro da Companhia 
 Variáveis de decisão: 
X2: produção semanal de B2 (em dúzias). 
X1: produção semanal de B1 (em dúzias). 
Função Objetivo: Maximizar o Lucro semanal 
Resolução Gráfica 
 Max 8X1 + 5X2 (Lucro semanal) 
 
 sujeito a: 
 2X1 + 1X2 ≤ 1000 (Plástico - Kg) 
 3X1 + 4X2 ≤ 2400 (Tempo de produção - minutos) (40*60) 
 X1 + X2 ≤ 700 (Produção total) 
 X1 - X2 ≤ 350 (mix) 
 X1 , X2  0, (Não negatividade) 
Resolução Gráfica 
Conceitos importantes: 
Os pontos (X1, X2) que satisfazem todas as restrições do 
modelo formam a Região Viável. 
Esses pontos são chamados de Soluções Viáveis. 
 
Usando a resolução gráfica pode-se representar todos as 
restrições (semi-planos), a função objetivo (reta) e os 
três tipos de pontos viáveis. 
 
Resolução Gráfica 
1º Passo: 
 
 Traçar eixos cartesianos, associando a cada um deles 
uma variável de decisão. 
 
 No exemplo de fabricação de brinquedos: X1 para o eixo 
das abscissas e X2 para o eixo das ordenadas. 
 
 As restrições de não-negatividade, X1  0 e X2  0, 
implicam que os pares (X1, X2) viáveis estão no 1º 
quadrante dos eixos considerados. 
 
Resolução Gráfica 
2º Passo: 
 
 Observar que a função-objetivo, ao se fixar um valor para Z, 
representa uma reta. Alterações neste valor de Z gera uma família 
de retas paralelas. 
 
 No exemplo dos brinquedos: considere a reta obtida fazendo Z= 
2000, isto é , a reta dada por 8X1 + 5X2 = 2000. Percebe-se que ao 
se traçar retas paralelas no sentido de ficar mais afastado da 
origem (0, 0), o valor de Z aumenta. 
 
 De fato pode-se verificar que a reta paralela, que contém algum 
ponto da região viável, no caso o ponto ótimo X* = (320, 360), e 
está mais afastada da origem, corresponde a um valor ótimo da 
função objetivo Z* = 4360. 
Resolução Gráfica 
25 
Representando as condições de não 
negatividade 
X2 
X1 
Resolução Gráfica 
26 
Observar que no exemplo dos brinquedos, as restrições correspondem a 
semi-planos associados, respectivamente, às retas suportes dadas por: 
 
 2X1 + 1X2 = 1000 
 3X1 + 4X2 = 2400 
 X1 + X2 = 700 
 X1 - X2 = 350 
 X1 , X2  0 
 
Notar que cada reta suporte define dois semi-planos no espaço (X1, X2). 
Para identificar qual destes semi-planos é de interesse no caso, ou seja, 
contém os pontos que satisfazem a desigualdade da restrição, basta 
testar algum ponto à esquerda ou à direita (acima ou abaixo) da reta 
suporte da desigualdade. 
Um ponto que torna isto fácil é a origem (0, 0), mas poderia ser qualquer 
outro. 
Resolução Gráfica 
27 
1000 
500 
Viável 
X2 
Inviável 
Tempo de 
produção 
3X1+4X2  2400 
Restrição da produção total 
 X1+X2  700 (redundante) 
500 
700 
Restrição do plástico 
2X1+X2  1000 
X1 
700 
Resolução Gráfica 
28 
1000 
Viável 
X2 
Inviável 
Tempo de Produção 
3X1+4X2  2400 
 Restrição da produção total: 
 X1+X2 700 (redundante) 
500 
Restrição do mix da produção: 
X1-X2  350 
Restrição do plástico 
2X1+X2 1000 
X1 
700 
Resolução Gráfica 
29 
1000 
500 
Viável 
X2 
Inviável 
500 
700 
X1 
700 
Há três tipos de pontos viáveis. 
Pontos interiores. Pontos na fronteira. Pontos extremos. 
Resolução Gráfica 
30 
A busca por uma Solução Ótima: 
Começar com algum valor de lucro arbitrário, 
Por exemplo $2000... 
Depois aumentar o lucro, se possível... 
...e continuar até que seja inviável 
600 
700 
1000 
500 
X2 
X1 
X* = (320, 360) 
com Z* = 4.360 
31 
Pontos extremos e Soluções Ótimas 
Se o problema de Programação Lineartem uma 
Solução Ótima, um ponto extremo é Solução Ótima. 
 
Resolução Gráfica 
Resolução Gráfica 
 O Problema do Desenhista 
 Um desenhista faz quadros artesanais para vender 
numa feira que acontece todo dia, à noite; 
 Ele faz desenhos grandes e desenhos pequenos, e 
vende-os por R$5,00 e R$2,00, respectivamente; 
 Só é possível vender 4 desenhos grandes e 3 desenhos 
pequenos por noite; 
 O desenho grande é feito em uma hora (grosseiro) e o 
pequeno é feito em duas horas (detalhado). Além disso, 
o desenhista desenha 8 horas por dia antes de ir para a 
feira. 
Resolução Gráfica 
O que o desenhista precisa decidir? 
O que ele pode fazer para aumentar ou diminuir a sua 
receita? 
A decisão dele é como usar as 8 horas diárias: quantos 
desenhos pequenos e grandes ele deve fazer! 
 
Chamemos de x1 e x2 as quantidades de desenhos 
grandes e pequenos que ele faz, por dia,respectivamente. 
Resolução Gráfica 
Modelo 
 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
 A solução ótima é um dos pontos da região 
viável; 
 Basta procurar dentro da região viável o ponto 
que dará o maior valor para Z. 
 Investiguemos o valor de Z em alguns pontos da 
região viável: 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
 Exemplo 3 
Resolução Gráfica 
Resolução Gráfica 
Resolução Gráfica 
 Exemplo 4 
Resolução Gráfica 
Resolução Gráfica 
Restrições Redundantes 
 Uma restrição é dita redundante quando a sua exclusão 
do conjunto de restrições, de um problema, não altera o 
conjunto de soluções viáveis deste; 
 
 É uma restrição que não participa da determinação do 
conjunto de soluções viáveis; 
 
 Existe um outro problema sem esta restrição com a 
mesma solução ótima. 
Restrições Redundantes 
 Considere o problema: 
Restrições Redundantes 
Solução Múltipla 
Solução Múltipla 
 Considere o seguinte o problema de PL 
Solução Múltipla 
Solução Ilimitada 
 Considere o seguinte o problema de PL 
 
Solução Ilimitada 
Solução Inviável 
 Um problema de programação linear é dito 
inviável quando o conjunto de soluções viáveis 
é vazio. 
 Considere o problema de PL 
Solução Inviável 
Resolução Gráfica 
 Resolva os exemplos dessa aula em papel 
milimetrado.