Solução Gráfica de Problemas de Programação Linear

Solução Gráfica de Problemas de Programação Linear

Marcelo Lisboa Rocha
PO - ADM
Objetivo

Definições:
- Solução e Região Factível: x é solução factível se satisfizer todas as restrições e condições de não negatividade. O conjunto de todas as soluções factíveis é chamado de região factível.
- Solução Ótima: é uma solução factível que fornece o melhor valor para função objetivo. Denota-se x* f(x* ) ≤ f(x), para qualquer x factível.

Definições:
- Poliedro do problema: é a figura delimitada pela região factível.
- o teorema fundamental da programação linear diz que, uma vez que todas as equações e/ou inequações envolvidas são lineares, o valor ótimo da função objetivo só pode ocorrer em um dos vértices da região factível. 3

Solução Gráfica de PPL’s
•

Passos para resolver graficamente um PPL:
a) Escolher uma solução x viável qualquer
b) Traçar o hiperplano definido pela função objetivo passando pelo ponto x
c) Determinar o gradiente da função objetivo no ponto x
d) Caminhar no sentido e direção do gradiente da função objetivo até tangenciar a região viável (maximização).
Caminhar no sentido contrário ao gradiente em problemas de minimização.
e) O ponto de tangência representa a solução ótima x*

Solução Gráfica de PPL’s
•

Quando o problema envolve apenas duas variáveis de decisão, a solução ótima de um PPL pode ser encontrada graficamente.

•

Isto será visto nos exemplos a seguir.

Solução Gráfica
Resolver o seguinte PPL:

max

x1 x1 x1 x1  2 x2


,

x2 x2 x2






2
2
3
0

Solução Gráfica max x2
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

D

x1  2 x2 x1 x2 x1  x2 x1 , x2






x2  2

G

C

A

B

H

x1

2
2
3
0

Teorema Fundamental da Programação
Linear
•

•

O ótimo de um PPL, se existir, ocorre em pelo menos um vértice do conjunto