Programação linear

Programação Linear - Introdução
• Todo problema de Programação Linear (PPL) consiste dos seguintes elementos: Variáveis de decisão: variáveis consideradas relevantes ao problema, passíveis de quantificação e disponíveis. Função objetivo: é uma função, produto dos coeficientes pelas variáveis de decisão, que se deseja otimizar no problema. Restrições: elementos restritivos que todo problema possui.

Pesquisa Operacional I

1

Programação Linear - Introdução
• É um problema de programação matemática em que as funçõesobjetivo e de restrições são lineares. • Constituem um tipo especial de modelos de otimização, devendo possuir as seguintes características: Não se considera economias de proporcionalidade; não negatividade; aditividade; separabilidade; escala nem custos iniciais para implantação de alternativa j (função objetivo); Não existe interatividade entre as alternativas de atividades. Por exemplo, um preço de determinado produto não pode variar condicionado à compra de outro produto. As variáveis de decisão podem ser fracionadas, ou seja, qualquer variável de decisão pode assumir qualquer valor positivo fracionário.
Pesquisa Operacional I 2

Programação Linear - Formulações
• FORMA PADRÃO (Standard)
Restrições do modelo são apresentadas na forma de EQUAÇÕES.

Otimizar Z = Sujeito a:

c1 x1 + c 2 x 2 + ... + c nx n a 11 x1 + a 12 x 2 + ... + a1nx n = b1 a 21 x1 + a 22 x 2 + ... + a 2 nx n = b 2 M a m1 x1 + a m 2 x 2 + ... + a mn x n = b m x1, x 2,..., x n ≥ 0
Pesquisa Operacional I 3

Onde:

Programação Linear - Formulações
• FORMA CANÔNICA
Restrições do modelo são apresentadas na forma de INEQUAÇÕES.

Otimizar Z =

c1 x1 + c 2 x 2 + ... + c nx n

Sujeito a: a 11 x1 +

a 12 x 2 + ... + a 1nx n ≥ b1 ( OU ≤ ) a 21 x1 + a 22 x 2 + ... + a 2 nx n ≥ b 2 ( OU ≤ )

Onde:

M a m1 x1 + a m 2 x 2 + ... + a mn x n ≥ b m ( OU ≤ ) x1, x 2,..., x n ≥ 0
Pesquisa Operacional I 4

Programação Linear - Formulações
• FORMA REDUZIDA
n