Pesquisa Operacional - Marcelo .Pesquisa Operacional Aula 4 – Solução Gráfica em Programação

Embed Size (px)

Text of Pesquisa Operacional - Marcelo .Pesquisa Operacional Aula 4 – Solução Gráfica em Programação

Pesquisa Operacional Aula 4 Soluo Grfica em

Programao Linear

Prof. Marcelo Musci aula@musci.info

www.musci.info

mailto:aula@musci.infohttp://www.musci.info/

Resoluo Grfica

Aplicvel para modelos com 02 variveis de deciso

til para a ilustrao de alguns conceitos bsicos.

Caso: Tintas e Tintas S.A.

A meta do problema achar a melhor

soluo vivel, ou seja, a soluo tima.

Para isso, precisamos saber quantas

solues viveis o problema possui.

Resposta: infinitas

No possvel resolver o problema por

enumerao

Propriedades do Modelo de PL

No exemplo da Tintas e Tintas S.A., o objetivo e as

restries so todos funes lineares.

Linearidade implica que a PL deve satisfazer trs

propriedades bsicas:

Proporcionalidade

Aditividade

Certeza

Propriedades do Modelo de PL

Proporcionalidade:

A contribuio de cada varivel de deciso (p.ex. x1 e x2), tanto na

funo objetivo quanto nas restries, seja diretamente proporcional

ao valor da varivel

Por exemplo, 5x1e 4x2 definem o lucro para a produo de x1e x2 toneladas de tinta para exteriores e interiores, respectivamente,

sendo que os lucros unitrios por tonelada (5 e 4) daro as

constantes de proporcionalidade;

Por outro lado, se a empresa der algum desconto por quantidade

quando as vendas ultrapassarem certas quantidades, o lucro no

ser mais proporcional s quantidades de produo, x1 e x2, e a

funo lucro se torna no linear;

Propriedades do Modelo de PL

Aditividade:

A contribuio total de todas as variveis da funo objetivo e das

restries a soma direta das contribuies individuais de cada

varivel

No exemplo, o lucro total igual soma dos dois componentes

individuais do lucro;

Por outro lado, se os dois produtos competirem por participao de

mercado, de modo que um aumento nas vendas de um deles

provoque um efeito adverso nas vendas do outro, ento a

propriedade de Aditividade no satisfeita e o modelo deixa de ser

linear;

Propriedades do Modelo de PL

Certeza:

Todos os coeficientes da funo objetivo e das restries do modelo

de PL so determinsticos, o que significa que so constantes

conhecidas

Isso raramente ocorre na vida real, sendo que o mais provvel

que os dados sejam representados por distribuies de

probabilidade;

Em essncia, os coeficientes em PL so aproximaes do valor

mdio das distribuies de probabilidade;

Se os desvios padro dessas distribuies forem suficientemente

pequenos, a aproximao ser aceitvel;

Resoluo Grfica

O procedimento grfico inclui duas etapas:

Determinar a regio de solues viveis;

Determinar a soluo tima entre todos os pontos

viveis da regio de solues;

A seguir vamos resolver o modelo de

maximizao do problema da Tintas e Tintas

S.A. usando a soluo grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Problema de mix de Produo

Fabricao de dois modelos de brinquedos: B1 e B2.

Lucros unitrios/dzia: $8 para B1 e $5 para B2

Recursos disponveis:

1000 kg de plstico especial.

40 horas para produo semanal.

Requisitos do Departamento de Marketing:

Produo total no pode exceder 700 dzias;

A quantidade de dzias de B1 no pode exceder em 350 a

quantidade de dzias de B2.

Dados tcnicos:

B1 requer 2 kg de plstico e 3 minutos por dzia.

B2 requer 1 kg de plstico e 4 minutos por dzia.

Resoluo Grfica

A Gerncia est procurando um programa de

produo que aumente o lucro da Companhia

Variveis de deciso:

X2: produo semanal de B2 (em dzias).

X1: produo semanal de B1 (em dzias).

Funo Objetivo: Maximizar o Lucro semanal

Resoluo Grfica

Max 8X1 + 5X2 (Lucro semanal)

sujeito a:

2X1 + 1X2 1000 (Plstico - Kg)

3X1 + 4X2 2400 (Tempo de produo - minutos) (40*60)

X1 + X2 700 (Produo total)

X1 - X2 350 (mix)

X1 , X2 0, (No negatividade)

Resoluo Grfica

Conceitos importantes:

Os pontos (X1, X2) que satisfazem todas as restries do

modelo formam a Regio Vivel.

Esses pontos so chamados de Solues Viveis.

Usando a resoluo grfica pode-se representar todos as

restries (semi-planos), a funo objetivo (reta) e os

trs tipos de pontos viveis.

Resoluo Grfica

1 Passo:

Traar eixos cartesianos, associando a cada um deles

uma varivel de deciso.

No exemplo de fabricao de brinquedos: X1 para o eixo

das abscissas e X2 para o eixo das ordenadas.

As restries de no-negatividade, X1 0 e X2 0,

implicam que os pares (X1, X2) viveis esto no 1

quadrante dos eixos considerados.

Resoluo Grfica 2 Passo:

Observar que a funo-objetivo, ao se fixar um valor para Z,

representa uma reta. Alteraes neste valor de Z gera uma famlia

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 traar 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 contm algum

ponto da regio vivel, no caso o ponto timo X* = (320, 360), e

est mais afastada da origem, corresponde a um valor timo da

funo objetivo Z* = 4360.

Resoluo Grfica

25

Representando as condies de no

negatividade X2

X1

Resoluo Grfica

26

Observar que no exemplo dos brinquedos, as restries 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 espao (X1, X2).

Para identificar qual destes semi-planos de interesse no caso, ou seja,

contm os pontos que satisfazem a desigualdade da restrio, basta

testar algum ponto esquerda ou direita (acima ou abaixo) da reta

suporte da desigualdade.

Um ponto que torna isto fcil a origem (0, 0), mas poderia ser qualquer

outro.

Resoluo Grfica

27

1000

500

Vivel

X2

Invivel

Tempo de

produo

3X1+4X2 2400

Restrio da produo total

X1+X2 700 (redundante) 500

700

Restrio do plstico

2X1+X2 1000

X1

700

Resoluo Grfica

28

1000

Vivel

X2

Invivel

Tempo de Produo

3X1+4X2 2400

Restrio da produo total:

X1+X2 700 (redundante) 500

Restrio do mix da produo:

X1-X2 350

Restrio do plstico

2X1+X2 1000

X1

700

Resoluo Grfica

29

1000

500

Vivel

X2

Invivel 500

700 X1

700

H trs tipos de pontos viveis. Pontos interiores. Pontos na fronteira. Pontos extremos.

Resoluo Grfica

30

A busca por uma Soluo tima:

Comear com algum valor de lucro arbitrrio,

Por exemplo $2000... Depois aumentar o lucro, se possvel...

...e continuar at que seja invivel

600

700

1000

500

X2

X1

X* = (320, 360)

com Z* = 4.360

31

Pontos extremos e Solues timas

Se o problema de Programao Linear tem uma

Soluo tima, um ponto extremo Soluo tima.

Resoluo Grfica

Resoluo Grfica

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 possvel 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). Alm disso,

o desenhista desenha 8 horas por dia antes de ir para a

feira.

Resoluo Grfica

O que o desenhista precisa decidir?

O que ele pode fazer para aumentar ou diminuir a sua

receita?

A deciso dele como usar as 8 horas dirias: 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.

Resoluo Grfica

Modelo

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

Resoluo Grfica

A soluo tima um do