Redução à Forma Padrão §

---

1. Transformações de maximização para minização §

Qualquer problema de maximização pode ser convertido num problema de minimização, pois:

2. Transformação de para §

Qualquer restrição de desigualdade de tipo ”” pode ser convertida num restrição do tipo ”” multiplicando por ambos os seus membros.

3. Transformações de igualdade em 2 de §

Qualquer restrição de igualdade pode ser convertida em duas restrições de desigualdades ”” equivalentes àquela.

O primeiro passo para a resolução de um problema de Programação Linear é a redução à Forma Padrão.

Para isto deve-se converter as restrições de desigualdade em equivalentes de igualdade.

Considerando uma desigualdade do tipo , podemos transformar em uma restrição de igualdade adicionando uma variável não negativa, chamada de variável de folga .

Por outro lado, caso haja uma restrição de desigualdade de tipo , podemos convertê-la em uma restrição de igualdade subtraindo uma variável não negativa, denominada de variável de excesso ou de folga .

Exemplos:

4. Transformação de variável negativa em não negativa §

Qualquer variável negativa , deve ser substituída por uma variável não negativa , , fazendo:

Exemplo:

5. Transformação de variável livre §

Para qualquer variável livre , que não é restringida pela condição de não negatividade, pode ser substituída por um par de variáveis não negativas e , fazendo

Desse modo, ao formularmos o problema novamente em função dessas duas variáveis, deletamos a variável do problema.

Exemplo:

Referências §

---