Aula 05 MÉTODO GRÁFICO PARTE 2

Prévia do material em texto

PESQUISA OPERACIONAL I –
CEP/CT 025
CURSO DE ENGENHARIA DE PRODUÇÃO – UFPIAULA MÉTODO 
GRAFICO
Prof. Airton CarneiroProf. Francisco Pinheiro
EX2: Encontre a solução ótima do seguinte problema
de PL.
0, 
2045 
1553 
6 
5 
2 ..
97 
21
21
21
2
1
21
21







xx
xx
xx
x
x
xxts
xxMin
Exercício
PROGRAMAÇÃO LINEAR – SOLUÇÃO GRÁFICA
Prof. Airton CarneiroProf. Francisco Pinheiro
3 / 55
X11086
51 x
42
62 x
221  xx
10
14
12
X2
8
6
4
-2
2
-2
1553 21  xx
2045 21  xx
02 x
01 x
PROGRAMAÇÃO LINEAR – SOLUÇÃO GRÁFICA
Exercício
Prof. Airton CarneiroProf. Francisco Pinheiro
4 / 55
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
PROGRAMAÇÃO LINEAR – SOLUÇÃO GRÁFICA
Exercício
Prof. Airton CarneiroProf. Francisco Pinheiro
 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;
PROGRAMAÇÃO LINEAR
Restrições Redundantes
Prof. Airton CarneiroProf. Francisco Pinheiro
 Considere o problema:
0, 
2045 
1553 
6 
5 
12 
2 ..
106 
21
21
21
2
1
21
21
21








xx
xx
xx
x
x
xx
xxts
xxMin
PROGRAMAÇÃO LINEAR
Restrições Redundantes
Prof. Airton CarneiroProf. Francisco Pinheiro
7 / 55
X11086
51 x
42
62 x
221  xx
10
14
12
X2
8
6
4
-2
2
-2
2045 21  xx
02 x
01 x
12 21  xx
1553 21  xx
Restrição Redundante
PROGRAMAÇÃO LINEAR
Restrições Redundantes
Prof. Airton CarneiroProf. Francisco Pinheiro
 Um Problema de Programação com solução
múltipla é aquele que possui mais de uma solução
ótima, ou seja, existe na região viável mais de um
ponto que dá o Z ótimo;
 Isto acontece somente quando a função objetivo
tem coeficientes proporcionais ao de alguma
restrição no entorno da região de otimalidade;
PROGRAMAÇÃO LINEAR
Solução Múltipla
Prof. Airton CarneiroProf. Francisco Pinheiro
 Considere o seguinte o problema de PL
 Encontre a solução ótima.
0, 
2045 
1553 
6 
5 
2 ..
106 
21
21
21
2
1
21
21







xx
xx
xx
x
x
xxts
xxMin
PROGRAMAÇÃO LINEAR
Solução Múltipla
Prof. Airton CarneiroProf. Francisco Pinheiro
10 / 55
X11086
51 x
42
62 x
221  xx
10
14
12
X2
8
6
4
-2
2
-2
1553 21  xx
2045 21  xx
Soluções Ótimas Múltiplas
02 x
01 x
PROGRAMAÇÃO LINEAR
Solução Múltipla
Prof. Airton CarneiroProf. Francisco Pinheiro
 Considere o seguinte problema de LP
Encontre a solução ótima.
0, 
2045 
1553 
6 
2 ..
106 
21
21
21
2
21
21






xx
xx
xx
x
xxts
xxMax
PROGRAMAÇÃO LINEAR
Solução Ilimitada
Prof. Airton CarneiroProf. Francisco Pinheiro
12 / 55
X1108642
62 x
221  xx
10
14
12
X2
8
6
4
-2
2
-2
1553 21  xx
2045 21  xx
02 x
01 x
PROGRAMAÇÃO LINEAR
Solução Ilimitada
Prof. Airton CarneiroProf. Francisco Pinheiro
 Um problema de programação linear é dito
inviável quando o conjunto de soluções viáveis é
vazio.
 Considere o problema
0, 
20 
12 ..
 
21
21
21
21




xx
xx
xxts
xxMax
PROGRAMAÇÃO LINEAR
Solução Inviável
Prof. Airton CarneiroProf. Francisco Pinheiro
14 / 55
2021  xx
-2
-2
2
4
6
8
10
12
14
2 4 6 8 10
12 21  xx
2021  xx
X2
X1
Conjunto não convexo
PROGRAMAÇÃO LINEAR
Solução Inviável