Teoria da Pesquisa Operacional

Pesquisa Operacional I
Fundamentos
Marcone Jamilson Freitas Souza
Alexandre Xavier Martins
Tatiana Alves Costa
José Maria do Carmo Bento Alves
Frederico Augusto Coimbra Guimarães
Departamento de Computação
Programa de Pós-Graduação em Engenharia Mineral
Universidade Federal de Ouro Preto http://www.iceb.ufop.br/prof/marcone Roteiro
Solução gráfica de um PPL
 Teorema Fundamental da Programação Linear
 Caracterização de vértice
 Fundamentação do Método SIMPLEX
 Método das duas fases
 Dualidade
 Análise de sensibilidade


Resolução gráfica de PPL’s
Passos para resolver graficamente um PPL:


a)
b)

c)
d)

e)

Escolher uma solução x viável qualquer
Traçar o hiperplano definido pela função objetivo passando pelo ponto x
Determinar o gradiente da função objetivo no ponto x
Caminhar no sentido e direção do gradiente da função objetivo até tangenciar a região viável
O ponto de tangência representa a solução ótima x*

Fundamentação do Método
SIMPLEX
Seja resolver o seguinte PPL:

max

x1 x1 x1 x1  2 x2
 2

,

x2

 2

x2 x2  3
 0

x2

Fundamentação do Método
SIMPLEX
max

A = (0,0)
B = (2,0)
C = (2,1)
D = (1,2)
E = (0,2)
F = (0,3)
G = (2,2)
H = (3,0)

x1  2

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

G

D z= x1 x1 x1


,

x2

 2
 2

x2 x2  3
 0

x2  2

C
+

+2

x2

B

3

x1



z=

x2

A

 2 x2

x1

ma x 4

x1

H

x1

Teorema Fundamental da
Programação Linear
O ótimo de um PPL, se existir, ocorre em pelo menos um vértice do conjunto de soluções viáveis. Situações que podem ocorrer com relação ao conjunto M de soluções viáveis:





1)

M = {}
Neste caso não há solução viável => Não há solução ótima Teorema Fundamental da
Programação Linear
2)

M é não vazio
a)

M é limitado

x*

Única solução ótima, a qual é vértice x*

y*

Infinidade de soluções ótimas, sendo duas vértices