Pesquisa operacional/Método Simplex

O Método Simplex é um algoritmo bastante popular para resolver problemas numéricos de Programação Linear. O jornal Computing in Science and Engineering o considerou um dos 10 mais importantes algoritmos descobertos no século.

Através dele, podemos obter a solução ótima de um problema de Programação Linear de forma eficiente.

A Forma Padrão da Programação Linear

O primeiro passo para se resolver um problema de acordo com o algoritmo Simplex é escrevendo o problema na forma padrão:

Máx/Mín $Z=c_1{x}_1+c_2{x}_2+...+c_n{x}_n$ sujeito à:

$a_{11}{x}_1+a_{12}{x}_2+...+a_{1n}{x}_n=b_1$

$a_{21}{x}_1+a_{22}{x}_2+...+a_{2n}{x}_n=b_2$

.

.

.

$a_{m1}{x}_1+a_{m2}{x}_2+...+a_{mn}{x}_n=b_m$

$x_1\ge 0,x_2\ge 0,...,x_n\ge 0$

Perceba que a forma padrão que estamos mostrando agora é diferente dos modelos de programação linear vistos no capítulo anterior. Na forma padrão, temos um conjunto de equações, e não apenas uma. A única inequação permitida é aquela que atesta a não negatividade das variáveis de decisão (ou seja, podem ser positivas ou nulas).

Transformando um Modelo de Programação Linear na Forma Padrão

Normalmente, os modelos que criamos não estão na forma padrão. Temos que fazer algumas manipulações algébricas para resolver este problema. Veja os exemplos abaixo:

Exemplo 1: O Modelo tem Desigualdade do Tipo Menor ou Igual

Tome o seguinte modelo:

Máx $Z=x_1+x_2$

$x_1\le 3$

$x_1\ge 0,x_2\ge 0$

Como deixar este modelo na forma padrão? É muito simples! Basta adicionar uma variável de folga chamada $x_3$ e transformar o modelo acima em:

Máx $Z=x_1+x_2$

$x_1+x_3=3$

$x_1\ge 0,x_2\ge 0,x_3\ge 0$

Exemplo 2: O Modelo tem Desigualdade do Tipo Maior ou Igual

Vamos agora tomar um modelo semelhante ao anterior:

Máx $Z=x_1+x_2$

$x_1\ge 3$

$x_1\ge 0,x_2\ge 0$

Para deixar este exemplo na forma padrão, fazemos algo parecido com o que fizemos no Exemplo 1. Inserimos variáveis de excesso:

Máx $Z=x_1+x_2$

$x_1-x_3=3$

$x_1\ge 0,x_2\ge 0,x_3\ge 0$

Exemplo 3: O Modelo possui Variáveis sem Restrição de Sinal

Mais um exemplo semelhante:

Máx $Z=x_1+x_2$

$x_1\le 3$

$x_2\ge 0$

Perceba que desta vez, a variável $x_1$ não possui restrição de sinal. Ela pode ser tanto positiva como negativa. Para resolver isso, precisamos eliminar a variável incômoda. Podemos simplesmente substituí-la por uma operação de subtração entre duas variáveis não negativas:

Máx $Z=(x_a-x_b)+x_2$

$(x_a-x_b)\le 3$

$x_a\ge 0,x_b\ge 0,x_2\ge 0$

Agora é só colocar uma variável de excesso da mesma forma que fizemos no Exemplo 2 e este modelo estará na forma padrão.

Exemplo 4: Uma Equação ou Inequação possui o Lado Direito Negativo

Para que um modelo esteja na forma padrão, o valor à direita de uma equação ou inequação deve ser sempre não-negativo. Então, caso haja equações do tipo:

$x+y=-7$

$x+2y\le -7$

A primeira coisa que devemos fazer é multiplicar os dois lados da equação e inequação por (-1):

$-x-y=7$

$-x-2y\ge 7$

Exemplo 5: Um Modelo mais Complexo

Tome o seguinte modelo de Programação Linear:

MÁX $Z=5x_1+10x_2-x_3$ sujeito às restrições:

$x_1-3x_2-x_3\le 1$

$x_1+x_2+x_3\ge -4$

$20x_1-12x_2+16x_3=-7$

$x_1,x_3\ge 0$

A primeira coisa que deve-se notar é que a variável $x_2$ não possui nenhuma restrição de sinal. Ela pode ser tanto negativa como positiva ou nula. Teremos que nos livrar desta variável incômoda assim como no Exemplo 3:

MÁX $Z=5x_1+10(x_a-x_b)-x_3$ sujeito às restrições:

$x_1-3(x_a-x_b)-x_3\le 1$

$x_1+(x_a-x_b)+x_3\ge -4$

$20x_1-12(x_a-x_b)+16x_3=-7$

$x_1,x_a,x_b,x_3\ge 0$

Agora vamos inserir uma variável de folga chamada $x_4$ na primeira inequação e uma variável de excesso chamada $x_5$ na segunda inequação:

MÁX $Z=5x_1+10(x_a-x_b)-x_3$ sujeito às restrições:

$x_1-3(x_a-x_b)-x_3+x_4=1$

$x_1+x_a-x_b+x_3-x_5=-4$

$20x_1-12x_a+12x_b+16x_3=-7$

$x_1,x_a,x_b,x_3\ge 0$

Agora o único inconveniente são a inequação 2 e a equação 3 que possuem o lado direito negativo. Vamos multiplicá-los por (-1);

MÁX $Z=5x_1+10(x_a-x_b)-x_3$ sujeito às restrições:

$x_1-3(x_a-x_b)-x_3+x_4=1$

$-x_1-x_a+x_b-x_3+x_5=4$

$-20x_1+12(x_a+x_b)-16x_3=7$

$x_1,x_a,x_b,x_3\ge 0$

Voilá! O modelo já está na forma padrão!

Algumas Definições Úteis

Antes de prosseguirmos, é importante que você se acostume com algumas definições que serão usadas nos futuros exemplos e explicações:

• Função Objetivo: A função inicial que deve ser otimizada em um problema de Programação Linear.
• Região factível: Conjunto de todas as soluções possíveis para um problema de Programação Linear. Se for um conjunto vazio, o programa linear é dito impossível ou inviável.
• Solução Básica: Uma solução obtida quando assumimos que um número igual à diferença entre o número de variáveis e o número de equações corresponde à quantidade de variáveis iguais a 0.
• Solução Factível: É qualquer solução encontrada que satisfaça as equações e inequações do modelo padrão de um problema de Programação Linear.
• Solução ilimitada: Solução na qual a Solução Ótima tende à infinito.
• Solução Ótima: Solução para as equações que otimiza o valor da função objetivo.