Programação Linear Solução Gráfica - musci.eng.br · •Um problema de Programação Linear com solução múltipla é aquele que possui mais de uma solução ótima, ou seja,

Programação Linear – Solução Gráfica

• Não é simples obter a solução ótima de um problema deProgramação Linear;

• Existem diversas maneiras de obter esta soluçãoótima;

• Quando o problema envolver apenas duas variáveis dedecisão, a solução ótima pode ser encontradagraficamente.

• Um desenhista faz quadros artesanais para vendernuma feira que acontece todo dia, à noite;

• Ele faz desenhos grandes e desenhos pequenos, evende-os por R$5,00 e R$2,00, respectivamente;

• Só é possível vender 4 desenhos grandes e 3 desenhospequenos por noite;

• O desenho grande é feito em uma hora (grosseiro) e opequeno é feito em duas horas (detalhado). Alémdisso, o desenhista desenha 8 horas por dia antes deir para a feira.

O Problema do Desenhista

• O que o desenhista precisa decidir?

• O que ele pode fazer para aumentar ou diminuir a suareceita?

• A decisão dele é como usar as 8 horas diárias: quantosdesenhos pequenos e grandes ele deve fazer!

• Chamemos de x1 e x2 as quantidades de desenhosgrandes e pequenos que ele faz, por dia,respectivamente.

A Decisão do Desenhista

Max Z x x 5 21 2faturamento

1s a x (a) 4. . Máximo de desenhos grandes

x (b) 32Máximo de desenhos pequenos

x x (c) 2 81 2Restrição de tempo

Não negatividadex (d) 01 , x 02

Determine o Modelo!

x2

x1

1

2

3

4

1 2 43


x1 ocupa o eixo dasabcissas e x2 o eixodas ordenadas

Todos os valorespara x1 e x2 sãoconsideradosinicialmente


x2

x1

x2 é não negativa

2 0x

Logo:


A região viávelé reduzida!

O mesmo raciocíniopara x1 resulta:

x2

x1

2 0x

A região viávelé reduzida mais ainda!


x2

x1

2 0x

1 0x


Agora pensemosna restrição (a):

1 4x

x2

x1

1

2

3

4

1 2 43


x2

x1

1

2

3

4

1 2 43

1 4x


x1

1

2

3

4

1 2 43

x2

E a restrição (b):

2 3x


x2

x1

1

2

3

4

1 2 43

2 3x

Agora precisamoscolocar a restrição (c):

Solução Gráfica – Região Viável Parcial

x1

1

2

3

4

1 2 43

2 3x

1 4x

1 0x

2 0x 1 22 8x x

Região Viável Parcial é Compreendida entre as retas

x1

1

2

3

4

1 2 43

É importante veraonde a nova retavai passar. Vamos

ver sua interseção com oseixos principais

2 3x

1 4x

1 0x

2 0x

• Toda Interseção é determinada resolvendo umsistema de equações

1 22 8x x

1 0x

1 22 8x x

2 0x

2 4x

(0,4)

1 8x

(8,0)

Intersecção com os Eixos Principais

1

2

3

4

1 2 43

x2

x1

(0,4)

(8,0)

Um Esboço da Nova Reta

Para uma maiorprecisão é importantedefinir os pontosvermelhos

1 2

1

2 8

4

x x

x

2 2x

(4,2)

1 2x

(2,3)

Definindo os Pontos de Intersecção

1 2

2

2 8

3

x x

x

A Nova Reta

(2,3)

(4,2)

1

2

3

4

1 2 43

x2

x1

Como toda restrição,uma parte da antiga região viável será desprezada. Qual?

Esta pergunta é a mesma:

Para onde a restrição aponta? Para baixo ou

para cima?

Como a restrição é <, as pessoas costumam dizerque aponta para baixo.Está errado raciocinar

assim!

Devemos investigar algum ponto que esteja

na região acima ou abaixo da reta

Decidindo sobre a Restrição

(2,3)

(4,2)

1

2

3

4

1 2 43

x2

x1

Vamos escolher, por facilidade o ponto (0,0):

1 22 8x x

0 2 0 0 Aplicando:

Logo, (0,0) está dentro da restrição. Portanto, a reta aponta para baixo.

0 8

Decidindo sobre a rRestrição

E, portanto,

Decidindo sobre a Restrição

1

2

3

4

1 2 43

x2

x1

(2,3)

(4,2)

(2,3)

(4,2)

RegiãoViável

A região viável é o conjunto de todas assoluções viáveis do

problema

Região Viável

1

2

3

4

1 2 43

x2

x1

São pontos especiais, nos vértices da região

viável

Pontos Extremos

D=(2,3)

C=(4,2)

A=(0,0)

B=(4,0)

E=(0,3)

1

2

3

4

1 2 43

x2

x1

Em todos estespontos, temos

Z = 10

A

Como obter estes

pontos?

O Conjunto de Pontos para Z=10

1

2

3

4

1 2 43

x2

x1

(2;0)

D

C

E

B

(0,8;3)

(2;0)

• Quando Z assume um valor fixo, temos uma reta!

• Entretanto, é possível que vários pontos da regiãoviável possuam um mesmo valor para Z, como foi ocaso anterior;

• Também é possível que nenhum ponto assuma umdeterminado valor de Z.

– Por exemplo, que pontos viáveis dariam Z = 30?

O Valor Fixo de Z

6,0

0,15

4 ; 5

5,5 ; 1,25

O Conjunto de Soluções para Z=30

O Conjunto deSoluções Viáveis para Z = 30 é vazio

Neste caso, sempre que aumentarmos o valor de Z areta irá para a direita!

Z = 10 Z = 30

A reta se deslocou para a direita

Variando o Valor de Z

O que aconteceu, do ponto de vista da reta, quandomudamos o valor de Z?

• Como é um problema de maximizar, a solução ótimaserá o ponto da região viável que esteja mais à direita.

C=(4,2)

Também é importantesaber o valor da funçãoobjetivo no ponto ótimo

A Solução Ótima

• Calcula-se então:

5 4 2 2 24Z

Podemos então concluir que, desenhando 4 quadrosgrandes e 2 quadros pequenos por dia, o Desenhistaterá seu faturamento máximo, de R$24,00 na feira.

O Valor da Função Objetivo na Solução Ótima

• Para obter a solução de forma gráfica, siga os passos:

– Desenhe a região viável, que dependeexclusivamente das restrições;

– Descubra a inclinação da função objetivo (desenheem algum ponto interno à região viável,aleatoriamente)

– Descubra para que lado a função objetivo melhora;

– Projete a função nesta direção; em caso dedúvidas, você sempre pode aplicar a funçãoobjetivo em mais de um ponto, escolhendo o pontomais adequado.

Solução Gráfica - Resumo

Considere o seguinte o problema de LP

a) Encontre a solução ótima.

b) Se a função objetivo fosse alterada para 2x1+6x2, qual seria a solução ótima?

c) Quantos pontos extremos existem?

1 2

1 2

1 2

1 2

3 3

. . 2 4 12

6 4 24

, 0

Max x x

s a x x

x x

x x

Solução Gráfica de um PL - Exercício


(0,0)

1

2

0 1 2 3 4 5 6

3

x2

2 0x

1 0x x1

(0,3)

(6,0)

1 22 4 12x x

(4,0)

(0,6)

1 26 4 24x x 5

4

6

7


(0,0)

1

2

0 1 2 3 4 5 6X1

(0,3)

(6,0)

(4,0)

(0,6)

3

4

5

6

x2 7

(3,3/2)

x1

21 330 xxZ

21 336 xxZ

21 330 xxZ

21 336 xxZ

21 330 xxZ

21 339 xxZ

1 26 3 3Z x x

1 20 3 3Z x x

1 29 3 3Z x x

1 213,5 3 3Z x x

Encontre a solução ótima do seguinte o problema de PL

0,

2045

1553

6

5

2 ..

97 Min

21

21

21

2

1

21

21

xx

xx

xx

x

x

xxas

xx


x11086

1 5x

42

2 6x

1 2 2x x

10

14

12

x2

8

6

4

-2

2

-2

1 23 5 15x x

1 25 4 20x x

2 0x

1 0x


x1108642

10

14

12

x2

8

6

4

-2

2

-2

51 x

62 x

221 xx

2045 21 xx

02 x

01 x

1553 21 xx


• Uma restrição é dita redundante quando a suaexclusã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 doconjunto de soluções viáveis;

• Existe um outro problema sem esta restrição com amesma solução ótima.

Programação Linear – Restrições Redundantes

Considere o problema:

0,

2045

1553

6

5

12

2 ..

106 Min

21

21

21

2

1

21

21

21

xx

xx

xx

x

x

xx

xxas

xx


x11086

1 5x

42

2 6x

1 2 2x x

10

14

12

x2

8

6

4

-2

2

-2

1 25 4 20x x

2 0x

1 0x

1 22 1x x

1 23 5 15x x

Restrição Redundante


• Um problema de Programação Linear com soluçãomúltipla é aquele que possui mais de uma soluçãoótima, ou seja, existe na região viável mais de umponto que dá o Z ótimo.

• Isto acontece somente quando a função objetivo temcoeficientes proporcionais ao de alguma restrição.

Programação Linear – Solução Múltipla

Considere o seguinte o problema de PL

Encontre a solução ótima.

0,

2045

1553

6

5

2 ..

106 Min

21

21

21

2

1

21

21

xx

xx

xx

x

x

xxas

xx

Programação Linear – Solução Múltipla

Documents

Programação Linear Solução Gráfica - musci.eng.br · •Um problema de Programação Linear com solução múltipla é aquele que possui mais de uma solução ótima, ou seja,