Pesquisa Operacional

2.3 - Solução pelo algoritmo simplex

Perceba que O processo gráfico tem muitas limitações, a começar pelo fato que só pode ser usado para duas variáveis de entrada. Foi necessário o desenvolvimento de método mais completo para realizar esses cálculos. Esse método é conhecido como SIMPLEX.

O método simplex, ao contrário do método gráfico, trabalha com equações e não com inequações. Deste modo as inequações devem ser transformadas em equações e isso é feito com a adição de variáveis. Vamos, portanto determinar as variáveis que podem ser aparecer em um problema deste tipo. Utilizaremos as definições estabelecidas por Contador:

Variável de entrada é a variável que deve ser otimizada e surge naturalmente do enunciado do problema. No caso do exercício das CPUs, que continuaremos usar como exemplo, as variáveis de entrada são o número de CPUs grandes (x1) e o número de CPUs pequenas (x2).

Termo independente é o valor numérico de uma restrição e, por convenção, é colocado à direita do sinal da inequação. No nosso exemplo, são as quantidade limitantes produzidas para cada componente.

Variável de folga ou residual, utilizada quando a desigualdade for do tipo ≤, é uma variável não negativa, somado ao lado esquerdo da desigualdade, e numericamente igual à diferença entre o termo independente e os valores à esquerda da desigualdade. Corresponde numa determinada solução à parcela não aproveitada de recursos. No nosso exemplo são as eventuais sobras de componentes (gabinetes ou placas)

Variável de excesso, utilizada quando a desigualdade for do tipo ≥, é uma variável negativa, subtraída do lado esquerdo da desigualdade, e numericamente igual à diferença entre o valor do termo independente e o valor das variáveis que estão à esquerda da desigualdade. No nosso não existirão valores deste tipo, pois é um problema de maximização.

Variável artificial é uma variável adicionada à esquerda em todas as restrições que não contenham uma variável de folga, sendo utilizada, portanto nas restrições que são originalmente com sinal ≥ ou =. A variável artificial é necessária porque a solução inicial do Simplex é obtida igualando a zero todas as variáveis de entrada e todas as de excesso, o que corresponde a fazer cada variável de folga e cada variável artificial igual ao valor do termo independente da equação da qual a variável em questão aparece. No nosso exemplo não existem variáveis deste tipo, visto serem inequações do tipo ≤.

Desta forma, no nosso exemplo as inequações seriam transformadas em equações, da seguinte forma:

Inequações:

...