Cap tulo II

Capítulo 2 - O algoritmo do Simplex
2.1 Introdução
O algoritmo do Simplex é um procedimento algébrico iterativo para resolver modelos de Programação Linear. Qualquer que seja o tipo de problema, o número de variáveis e o número ou tipo de restrições, este algoritmo pode ser-lhe aplicado, desde que verifique as cinco propriedades que assistem aos problemas de programação linear
– proporcionalidade, divisibilidade, não negatividade, aditividade e linearidade da função objectivo.
Este algoritmo traduz um conjunto de passos bem definidos e baseia-se no seguinte princípio: partindo de uma solução possível inicial, o algoritmo vai sistematicamente alterando a solução de modo a que, em cada iteração, o valor da função objectivo melhore ou, quando muito, fique na mesma. Assim, passo a passo, as sucessivas soluções possíveis, que vão sendo criadas, aproximam-se cada vez mais da solução que será óptima – aquela solução que não pode ser mais melhorada. Desta forma, num problema de maximização, de iteração para iteração, deparamo-nos com soluções que apresentam um valor da função objectivo cada vez maior, até atingir o máximo valor possível. Em problemas de minimização, por sua vez, as sucessivas soluções conferem um valor cada vez menor ao objectivo até que seja mínimo.

2.2 O Algoritmo
A resolução de um problema, utilizando o algoritmo do Simplex, constitui a base de trabalho para uma boa interpretação económica do problema. Vejamos como se resolve um problema de programação linear pelo algoritmo mencionado.
Consideremos o problema de maximização enunciado e formulado no capítulo anterior, que contém apenas duas variáveis de decisão:

12

Maximizar Z= 10x1 + 9 x2 sujeito a:
5 x1  4 x 2  200 ( Material )

4 x1  6 x 2  240 (Tempo  máquina)
2 x1  x 2  70 (Tempo  hom em) x1 , x2  0
Teremos que proceder a uma série de transformações para se poder aplicar o algoritmo.


Forma canónica

A aplicação do algoritmo do Simplex pressupõe que o problema esteja apresentado
num