Programação Linear - Apresentação nas formas Geral, Canónica e Standard

Como foi visto no anterior artigo de Programação Matemática, um Problema de Programação Linear (PPL) após a sua formulação apresenta-se na forma:

Max (ou Min) z = F(x1, x2, ..., xn) = c1 x1 + c2 x2 + ... + cn xn
s.a.
    g1(x1, x2, ..., xn) = a11 x1 + a12 x2 + ... + a1n xn, =,b1
    g2(x1, x2, ..., xn) = a21 x1 + a22 x2 + ... + a2n xn, =,b2
 ...
    gm(x1, x2, ..., xn) = am1 x1 + am2 x2 + ... + amn xn, =,bm

Mas esta forma na maior parte das vezes não é adequada como ponto de partida para uma resolução. Existem muitos métodos para resolver problemas de programação linear, e a maior parte deles requer uma simplificação que se traduz na adaptação à notação matricial, e que esta facilmente pode ser introduzida em qualquer aplicação ou folha de cálculo que possua algoritmos de resoluções deste tipo de problemas. Assim, dever-se-á determinar todos os coeficientes efectivos necessários ao uso de qualquer método e algoritmo.


Forma Geral

Aos coeficientes ci dá-se geralmente o nome de custos.
Este PPL diz-se estar na forma geral porque a função objectivo (f.o.) pode ser maximizada ou minimizada e as restrições podem apresentar qualquer das três formas {,=,}.
Nesta forma admite-se que um PPL possa apresentar variáveis,

não negativas:
não positivas:
livres ou independentes:


Um PPL diz-se estar na forma canónica quando:

- pretende-se maximizar a função objectivo;
- as restrições forem do tipo;
- todas as variáveis forem não negativas:


Ainda, diz-se que um PPL encontra-se na forma standard quando:

- pretende-se maximizar a função objectivo;
- as restrições forem do tipo  = ;
- todas as variáveis forem não negativas:


Para resolver um PPL, é geralmente necessário que se encontre na sua forma mais amigável - a forma standard.


Forma Canónica

Em ordem a transformar um problema na forma geral para a forma canónica, deve tornar-se o problema numa maximização com restrições de sinale variáveis não negativas.

1. No caso de o problema ser uma minimização pode dizer-se que minimizar uma função é equivalente a maximizar a sua simétrica, isto é,

    Min F = Max G (em que G = -F).

2. Para esta forma, pretende-se que todas as restrições figurem com o sinal. Quando as restrições tiverem sinalou  = , deveremos rescrevê-las:

- Se se tiver uma restrição com sinaldevemos multiplicar toda a restrição por -1 (Esta operação nem sempre será útil, pois afectará também o termo independente que poderá ficar negativo).

- Se se tiver uma restrição com sinal  =  é possível rescrevê-la,

ai1 x1 + ai2 x2 +...+ ain xn = bi <=>
ai1 x1 + ai2 x2 +...+ ain xn <= bi  e  ai1 x1 + ai2 x2 +...+ ain xn >= bi


3. Quanto à imposição de não negatividade das variáveis:

- Quando se tem uma variável não positiva xi <= 0, deve considerar-se yi = - xi >= 0, e assim substituir todos os  xi  por  -yi  tanto na f.o. como em todas as restrições.
- Quando se tem uma variável livre, deve tomar-se em conta que pode escrever-se xi como diferença de duas variáveis artificiais não negativas: xi = yi - zi , com  yi , zi >= 0  (observe-se que  xi  permanece livre).


Forma Standard

A passagem à forma standard é mais simples por não envolver mais alterações na f.o. nem nas variáveis, ficando apenas por transformar todas as restrições em igualdades. Este procedimento é conseguido com a introdução de novas variáveis designadas por folgas ou desvios ( fi >= 0).


Com efeito, verifica-se facilmente que para a restrição i existe um real  fi >= 0, tal que,
ai1 x1 + ai2 x2 + ... + ain xnbi  <=>  ai1 x1 + ai2 x2 + ... + ain xn + fi = bi     (*)

Em notação matricial, pode escrever-se um PPL na forma standard:


    s.a.
      
      

onde X é vector-coluna das variáveis incluindo as folgas e outras variáveis artificiais que mais tarde poderão figurar no sistema; CT é o vector-linha dos custos correspondentes; A é matriz de coeficientes das restrições; B é o vector-coluna dos termos independentes (t.i.) das equações das restrições.

Usualmente a resolução por qualquer método de programação linear parte de uma solução inicial ou de arranque, que no caso da Origem do referencial ser uma solução admissível, será poderá ser essa a solução inicial; fazendo x1, x2, ..., xn = 0  então tem-se X = 0 e em (*) fi = bi o que significa que se Xf  for o vector-coluna apenas das variáveis de folga e artificiais então Xf = B.


Exemplo 2: Colocar o seguinte programa na forma standard:



       

Pode observar-se que de facto o problema encontra-se na forma geral de acordo com o que se dispôs anteriormente. Mas devem ser feitas algumas alterações para reformulá-lo, primeiro para a forma canónica e depois para a forma standard: 


Na função objectivo: uma vez que Min F = Max G (com G = -F),

    Min  F =  8 x1 + 4 x2 - 5 x3     <=>    Max  G =  - 8 x1 - 4 x2 + 5 x3     

Quando for determinado o valor óptimo G*, então ter-se-á também F* = -G*


Nas restrições

A primeira restrição já está com o tipo que se pretende para a forma canónica.
A segunda restrição será multiplicada por -1, e obter-se-á,
     -3 x1 + 2 x2 - 5 x3-12

A terceira restrição poderá ser rescrita como o sistema,
    - x1 + 2 x2 + 2 x3   = 10  <=>  - x1 + 2 x2 + 2 x310    e   - x1 + 2 x2 + 2 x310

e portanto
    - x1 + 2 x2 + 2 x3   = 10  <=>  - x1 + 2 x2 + 2 x310    e     x1 - 2 x2 - 2 x3-10

Nas variáveis

A variável x1 é não negativa e não precisa de ser alterada.
A variável x2 é não positiva, logo devemos considerar y2 = - x20    que é não negativa.
A variável x3 é livre, mas podemos rescrevê-la como diferença entre duas outras variáveis não negativas: x3 = y3 - z3 , y30 , z30.
Em resumo, apresenta-se o problema na forma canónica,


Finalmente para concretizar o problema na forma standard, quanto à função objectivo e quanto às variáveis não há nada a alterar; bastará portanto transformar as restrições de  para  = , bastando introduzir as variáveis folga respectivas em cada equação:

Em resumo, apresenta-se o problema na forma standard,
    

Sem comentários:

Enviar um comentário