Originais do Prof. Fernando Deeke Sasse

Consideremos novamente o problema de produção de brinquedos apresentado em Solução Gráfica. Vamos transformar as desigualdades que determinam as restrições em um sistema de equações lineares. Para isso vamos introduzir as chamadas "variáveis de folga" (slack). Na formulação original temos

max

,

,

,

, .

Agora

max

,

, .

onde introduzimos as variáveis de folga .

Podemos dar uma interpretação para essas variáveis de folga : representa o excesso de carros produzidos, o excesso de trens produzidos, o número de peças especiais não utilizadas a partir do número máximo disponível.

A solução do problema de otimização deve ser uma solução para este sistema. Temos um sistema de equações em variáveis. Como teremos em geral infinitas soluções. O método simplex toma somente um número finito destas soluções, chamado conjunto básico de soluções .

Dado um sistema linear A x = b podemos selecionar qualquer submatriz m x m não-singular de A (chamada matriz base ) , fazer as restantes variáveis não básicas iguais a zero, e resolver o sistema resultante para as variáveis básicas. Isso resulta numa solução básica que denotaremos por .

Denotando a matriz base por B , o sistema resultante, após fazermos n-m variáveis iguais a zero, pode ser escrito como B = b ou b . A inversão de matrizes pode ser facilmente realizada pelo Maple. Como as variáveis de decisão devem ser não-negativas, o método seleciona somente as soluções onde todas as componentes de são não-negativas. O número de soluções básicas é limitado por binomial (n,m) = n! / [m!(n-m)!], sendo possivelmente menor. No nosso problemas temos um número máximo possível de soluções dado por binomial (5,3) = 10. Vamos mostrar que para este problema temos 8 soluções básicas.

Suponhamos inicialmente que = = 0 (trens e partes especiais na medida exata), . As variáveis básicas são então . Vamos obter utilizando Maple :

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> Sistema:= [ x[1]+x[3]=90, x[2]+x[4]=60, 5*x[1]+6*x[2]+x[5]=600];

> A:=genmatrix(Sistema, [x[1],x[2],x[3],x[4],x[5]],ladodireito);

> b:=evalm(ladodireito);

>

> B:=augment(col(A,1),col(A,2),col(A,3));

> xb:=linsolve(B,b);

Esta solução factível corresponde à produção de 48 carros e 60 trens, com um surplus de 42 carros (e 0 trens).

Vamos supor agora que = = 0 . Temos então

> B:=augment(col(A,1),col(A,2),col(A,5));

> xb:=linsolve(B,b);

Esta solução é não-factível, pois corresponderia a um consumo de 810 partes especiais/dia, o que é impossível. O processo então se repete através da formação e solução de todos os possíveis sistemas. A solução ótima é aquela onde z atinge o máximo valor. Na próxima seção veremos como o método simplex seleciona somente uma pequena fração do número de sistemas possíveis

A cada solução factível básica está associada uma solução factível do problema de programação linear. A princípio temos um método algorítmico que nos permitiria encontrar todas as soluções básicas associadas a um problema de programação linear. Computando a função objetivo para cada solução poderíamos chegar à solução do problema. Tal método é, entretanto, muito ineficiente. Por exemplo, para um problema modesto, envolvendo 7 variáveis de decisão e 4 restrições teríamos que resolver binomial(9+4,4) =715 sistemas de 4 equações e 4 incógnitas. No próximo documento (Soluções Básicas e Factíveis), vamos introduzir, através de um exemplo, o método simplex, que iterativamente obtém uma solução básica factível após a outra sempre melhorando a função objetivo. Veremos que o número de passos é pequeno.