A1resumida

Departamento de Engenharia de Produção
Universidade Federal do Rio Grande do Norte

Pesquisa Operacional II
Aula 1 - Revisão de Programação Linear

Principais ingredientes


Variáveis
◦ Seus valores não são conhecidos a priori.
◦ Deseja-se encontrar valores de variáveis que resultem no melhor conjunto de decisões a fim de se otimizar o problema. 

Função objetivo
◦ Expressão matemática que combina as variáveis para representar um objetivo almejado (max ou min).



Restrições
◦ Expressões matemáticas que combinam as variáveis a fim de expressar limites para as possíveis soluções.

2

Programação Linear


Em programação linear (PL), todas as expressões matemáticas são lineares.



Um número surpreendente de problemas de PO podem ser modelados usando PL.
◦ Escalonamento de vôos aéreos.
◦ Processamento e distribuição de petróleo.



A IBM estimava que em 1970, 25% de todo o processamento computacional no mundo era dedicado a resolução de PL.
3

Os pontos extremos são importantes! 

A solução ótima de um PL está sempre em um ponto extremo!



Esta observação simplifica drasticamente a busca pela solução ótima, pois podemos concentrar a busca nos pontos extremos da região viável.

4

Região viável

13 mar 200
9.
17:
48

Curvas de nível

13 mar 200
9.
17:
48

Região inviável

13 mar 200
9.
17:
48

Múltiplos ótimos

Região factível ilimitada

Forma padrão


Consideramos sempre o problema na forma padrão:
Dimensões:
A (m x n) b (m x 1)

Forma padrão


Considere a seguinte região viável no
R2

Forma padrão

Pontos Extremos
Sempre que existe uma solução ótima, existe um ponto extremo ótimo.
 Também intuímos que uma maneira de achar a solução ótima seria visitar os pontos extremos sucessivamente
 Como determinar pontos extremos sem o auxílio do gráfico?


PL: propriedades básicas


O ponto ótimo é sempre um ponto extremo.



Se um ponto extremo viável apresenta um valor de função objetivo melhor ou igual a todos os seus pontos extremos adjacentes,