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

813 palavras 4 páginas
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

Relacionados

  • Pesquisa operacional
    3556 palavras | 15 páginas
  • Método Gráfico
    726 palavras | 3 páginas
  • jhvjb jgnbnvnv
    2002 palavras | 9 páginas
  • 149716650361
    1454 palavras | 6 páginas
  • Pesquisa operacional
    8352 palavras | 34 páginas
  • INVESTIGACAO OPERACIONAL
    2866 palavras | 12 páginas
  • graduacao
    2525 palavras | 11 páginas
  • Apresentacao PO 4
    507 palavras | 3 páginas
  • Programação linear
    1226 palavras | 5 páginas
  • trabalho
    492 palavras | 2 páginas