Curso de Programação Linear

Professor Raymundo
de Oliveira

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 = ……………………

Am1Am2…Amn

I … matriz identidade

Teoremas

1- Todas as Soluções Possíveis num Problema de Programação Linear formam um Conjunto Convexo (Q). 2- A condição necessária e suficiente para que um ponto X ³ 0, em Q, seja um ponto extremo, é que X seja uma solução básica possível satisfazendo o sistema (A,I) X = P0 , P0 ³ 0 , X ³ 0 3- A solução ótima do problema de Programação Linear Max Z = CX , sujeito a: (A,I) X = P0 , P0 ³ 0 , X ³ 0 , quando é finita, ocorre num ponto extremo do espaço de soluções possíveis (Q). Se a solução ótima ocorre em mais de um ponto extremo, o valor da função objetivo será o mesmo para todas as combinações convexas desses pontos extremos. Definições Seja um conjunto de m equações lineares a r incógnitas (m