Metodos De Pesquisa Operacional

Professor Raymundo

de Oliveira | P.L. | Programa | Exercícios | Conceitos | Professor | Links |

Conceitos de Programação Linear

Forma Canônica

Forma Standard

Seja um modelo de PL, na forma standard, com um sistema de m equações, com m+n variáveis, além da função objetivo.

Solução Possível - é um ponto que atenda às restrições do problema, aí incluídas as restrições de não negatividade e não incluída a função a ser otimizada; isto é, as soluções possíveis não precisam otimizar a função objetivo. Tratando-se de m equações a m+n incógnitas, poderá haver, e freqüentemente há, infinitas soluções possíveis.

Solução Ilimitada (unbounded)

- é aquela em que a função objetivo pode crescer (caso da maximização) ou decrescer (caso da minimização), indefinidamente, atendendo a todas as restrições do problema.

Solução Ótima

- havendo solução possível e não havendo solução ilimitada, solução ótima é a solução possível que otimiza a função objetivo. Nesse caso, poderá haver uma ou infinitas soluções ótimas; isto é, havendo mais de uma solução ótima, haverá infinitas soluções ótimas1.

Solução Básica

- façamos n variáveis iguais a zero, sobrando m equações a m variáveis. Se esse sistema de m equações a m variáveis tiver solução, ela será chamada de Solução Básica. Haverá, assim, um máximo de Combinação de m+n , m a m, soluções básicas. {(m+n)! / ( m!n!)}.

Solução Básica Possível

- se na Solução Básica, todas as m variáveis forem não negativas, teremos uma Solução Básica Possível.

Variável Básica

- são as m variáveis que compõem a solução básica.

Variáveis Não Básicas

- são as n variáveis que não compõem a solução básica. Valem, obrigatoriamente, zero, por construção.

Solução Degenerada

- se na solução básica possível, alguma variável básica valer zero, a solução básica é dita degenerada.

Solução Impossível

- é aquela em que não há qualquer ponto que atenda ao conjunto de restrições.

O problema geral de Programação Linear, na sua forma Standard, pode ser, sempre, escrito da seguinte maneira:

Max Z = CX ,

sujeito a:

(A,I) X = P0 , P0 ³ 0 ,

X ³ 0 ,

onde:

X = (X1, X2, …Xm+n)T

C = (C1, C2, …Cm+n)

P0 = (B1, B2, …Bm)T

A11A12…A1n

A21A22…A2n

A