Pesquisa operacional/Método Simplex

O Método Simplex é u 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}+...+a_{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}\geq 0,x_{2}\geq 0,...,x_{n}\geq 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. O único tipo de ineqüação permitido são aquelas que atestam que todas as variáveis deveem ser não-negativas (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}\leq 3$

$x_{1}\geq 0,x_{2}\geq 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}\geq 0,x_{2}\geq 0,x_{3}\geq 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}\geq 3$

$x_{1}\geq 0,x_{2}\geq 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}\geq 0,x_{2}\geq 0,x_{3}\geq 0$