Universidade Federal de Ouro Preto Departamento de Engenharia de Produo- DEENP

Pesquisa Operacional 1 Aula 6- Soluo grfica de PPLProfa. Milena Estanislau Diniz 2 Semestre/2011

Tema da aula de hoje-> Soluo grfica de PPLs

Soluo grfica de PPL->Identificao da regio vivel. Plotar restries no grfico, identificando a regio factvel de cada restrio. A regio admissvel do problema formada pela interseo entre as regies admissveis de cada restrio.

Soluo grfica de PPLIdentificao da soluo vivel Soluo grfica com duas variveis-> utilizao do plano cartesiano com os dois eixos (abcissa e ordenada) representadas pelas duas variveis do problema. -> variveis x1 e x2: eixos do plano cartesiano -> regio vivel (contm todas as restries do problema): regio onde est situada a soluo tima.-> restries de no-negatividade: soluo deve estar apenas na regio onde as variveis assumem valores no negativos.

Exemplo Soluo grficaI. Identificar os valores de (x1, x2) que satisfaam todas as restries (regio de admissibilidade)

x28

1 x1 0, x2 0 (x1 , x2) esto no 1 Quadrante

6

4

2

2

4

6

x1

Exemplo Soluo grficaI. Identificar os valores de (x1, x2) que satisfaam todas as restries (regio de admissibilidade)

x28 x1 = 4

1 x1 0, x2 0 (x1 , x2) esto no 1 Quadrante2 x 1 4 (x1 , x2) esto situados esquerda ou sobre a reta x 1 = 4

6

4

2

2

4

6

x1

Exemplo Metalrgica: Soluo grficaI. Identificar os valores de (x1, x2) que satisfaam todas as restries (regio de admissibilidade regio vivel)

x28 x1 = 4

1 x1 0, x2 0 (x1 , x2) esto no 1 Quadrante2 x 1 4 (x1 , x2) esto situados esquerda ou sobre a reta x 1 = 4 3 x 2 6 (x1 , x2) esto situados abaixo ou sobre a reta x 2 = 6

6

x2 = 6

4

2

2

4

6

x1

7

Exemplo Soluo grficaI. Identificar os valores de (x1, x2) que satisfaam todas as restries (regio de admissibilidade regio vivel)

x28 x1 = 4

1 x1 0, x2 0 (x1 , x2) esto no 1 Quadrante2 x 1 4 (x1 , x2) esto situados esquerda ou sobre a reta x 1 = 4 3 x 2 6 (x1 , x2) esto situados abaixo ou sobre a reta x 2 = 6

6

x2 = 6

4

4 3 x 1 + 2 x 2 18 (x1 , x2) esto situados abaixo ou sobre a reta 3x1 + 2x2 =18

2

2

4

6

x1

Exemplo Soluo grficaI. Identificar os valores de (x1, x2) que satisfaam todas as restries (regio de admissibilidade regio vivel)

x28 x1 = 4

1 x1 0, x2 0 (x1 , x2) esto no 1 Quadrante2 x 1 4 (x1 , x2) esto situados esquerda ou sobre a reta x 1 = 4 3 x 2 6 (x1 , x2) esto situados abaixo ou sobre a reta x 2 = 6

6

x2 = 6

4 Regio de admissibilidade

4 3 x 1 + 2 x 2 18 (x1 , x2) esto situados abaixo ou sobre a reta 3x1 + 2x2 =18

2

2

4

6

x1

Soluo grfica de PPL Determinar a regio de soluo vivel deste PPL:maximizar 3 x1 2 x2 sujeito a : x1 x2 9 3 x1 x2 18 x1 7 x2 6 x1 , x2 0restrio (1)

restrio (2)restrio (3) restrio (4)

Soluo grfica de PPL No-negatividade e restries (1) a (4): regio vivelmaximizar 3 x1 2 x2 sujeito a : x1 x2 9 3 x1 x2 18 x1 7 x2 6 x1 , x2 0A restrio (3) desnecessria ou redundante.restrio (1)

restrio (2)restrio (3) restrio (4)

Soluo grfica de PPL

Passos para resolver graficamente um PPL:a) Traar o hiperplano definido pelas restries do PPL. b) Determinar o gradiente da funo objetivo no ponto x d) Caminhar no sentido e direo do gradiente da funo objetivo at tangenciar a regio vivel e) O ponto de tangncia representa a soluo tima x*

Exemplo Metalrgica: Soluo grficaII. Representar a funo objetivox2

A funo objetivo Z = 3x1 + 5x2 define uma reta que pode ser deslocada paralelamente no sentido do seu gradiente (em amarelo) (garantindo o crescimento de Z), at se tornar tangente regio admissvel.

8E (0,6) D (2,6)

6

Regio das 5 admissveis solues 4C (4,3)

2

A (0,0)

2

3

4B (4,0)

6

x1

Exemplo Metalrgica: Soluo grficaII. Representar a funo objetivoZ = 3x1 + 5x2x2H (0; 7,2)

5x2 = z - 3x1 x2 = z/5 - 3x1 /5

8

6G (0;5,4)

D (0,6)

C (2,6)

Regio das 5 admissveis solues 4B (4,3)

F (0;2,4)

2

0 (0,0)

2

3

4A (4,0)

6

x1

Exemplo Metalrgica: Soluo grficaIII. Determinar a soluox28

Curva de nvel

Neste caso o ponto de tangncia (2,6) que otimiza a funo objetivo x1 = 2, x2 = 6. valor timo: 36.

6

D

(2,6) a soluoC

Regio das 5 admissveis solues 4B E (2,3) F (3,2)

2

0

2

3

A

4

6

x1

Soluo grficaPara cada valor de z diferente, obtemos uma linha diferente. importante notar que todas as linhas que correspondem a diferentes valores de z so paralelas. Isto acontece porque a inclinao de qualquer linha de z c1x1 c 2 x2 o coeficiente angular de z.

Exemplo 2- Resoluo grfica de PPLsUma empresa fabrica dois perfumes diferentes, P1 e P2.Devido s restries de estoque, a empresa s consegue produzir 2 litros do perfume 1, e dois litros do perfume 2. Devido s restries do processo produtivo, ela dispe de trs horas para a produo dos dois perfumes, sendo que cada perfume requer uma hora para ser fabricado.

Os lucros dos perfumes so, respectivamente, $1 e $2. Qual o esquema timo de produo?

Exemplo 2- Resoluo grfica de PPLs

Modelo de Programao Linear:

max

x1 x1 x1 x1

2 x2 x2 x2 x2 2 2 3 0

,

Exemplo 2- Resoluo grfica de PPLsx2 x1 2

max

x1 x1 x1 x1

2 x2 x2 x2 x2 2 2 3 0

,x2 2

x1

Exemplo 2- Resoluo grfica de PPLsx2 x1 2

max

x1 x1 x1 x1

2 x2 x2 x2 x2 2 2 3 0

,x2 2

C

x1

Exemplo 2- Resoluo grfica de PPLsx2x1 >= 0

maxx1 2

x1 x1 x1 x1

2 x2 x2 x2 x2 2 2 3 0

,x2 2

C

x2 >= 0x1

Exemplo 2- Resoluo grfica de PPLsx2 x1 2

max

x1 x1 x1 x1

2 x2 x2 x2 x2 2 2 3 0

,x2 2

3/2 (1,1)

x1

Exemplo 2- Resoluo grfica de PPLsx2 x1 2A = (0,0) B = (2,0) C = (2,1) D = (1,2) E = (0,2) F = (0,3) G = (2,2) H = (3,0)

max

x1 x1 x1 x1

2 x2 x2 x2 x2 2 2 3 0

F

,x2 2

x* = (1,2), z* = 5E

D

G

C

A

B

H

x1

Soluo grfica de PPL Maximizao: soluo tima representada pelo vrtice da regio admissvel apontada pelo gradiente Minimizao: considera-se o sentido contrrio do gradiente Em caso de dvida entre vrtices candidatos a timo, calcula-se o valor da funo objetivo para cada um deles