Cap tulo III

Capítulo 3 – Resolução de problemas com variáveis artificiais
3.1. Introdução
Vimos no capítulo anterior que, a quarta regra da forma canónica sugere que qualquer restrição sob a forma de igualdade ou do tipo “maior ou igual”, terá que eventualmente incluir uma variável artificial, de forma a garantir a existência de uma solução básica inicial. Assim,
 Sabemos que qualquer inequação do tipo “maior ou igual” passará a definir-

se por uma equação equivalente, através da subtracção de uma variável excesso, à qual em seguida se adiciona uma variável artificial, que representará a variável básica inicial associada a essa restrição.
 Se as restrições forem de igualdade, como já são equações não exigem a

introdução de qualquer variável auxiliar. Contudo, estas restrições requerem a introdução de uma variável artificial sempre que não exista uma variável que possa assumir o carácter de variável básica na solução inicial.
Tal como o próprio nome indica, a variável artificial é uma variável “auxiliar”, introduzida apenas para permitir a formação de uma base artificial, necessária para a resolução de qualquer problema de programação linear.
As variáveis artificiais não têm qualquer significado prático real, pelo que não existe forma de as interpretar quando apresentam um valor positivo. Daí que, após a construção da base inicial, é necessário fazer sair da base tais variáveis, para que a solução óptima encontrada para o problema seja constituída apenas pelas variáveis que apresentam significado prático real – as variáveis de decisão e as variáveis auxiliares.
Existem dois métodos de resolução de problemas com variáveis artificiais, ambos baseados no algoritmo do simplex, que vão permitir introduzir uma regra adicional que traduz a necessidade de anular esse tipo de variáveis. Os dois métodos são seguidamente apresentados.

28

3.2 O método do grande M ou método das penalidades

O método do grande M utiliza uma forma de penalização das variáveis artificiais que as