Cap Tulo 3 Algoritmo Simplex

Capítulo 3

Algoritmo Simplex

1

CAPÍTULO 3
Algoritmo Simplex

3.1

Introdução
O algoritmo Simplex é a ferramenta básica da programação linear. O objetivo do algoritmo é

transformar uma matriz dada em outra equivalente que contenha certo “desenho” ou “padrão”.
Este capítulo faz um esboço do Simplex, destacando seu parentesco com o algoritmo de
Gauss-Jordan discutido no capítulo três.

3.2

Conversão de desigualdade em uma equação
Em restrições ( ≤ ) , o lado direito pode ser considerado como a representação do limite

imposto à disponibilidade de um recurso, caso em que o lado esquerdo representaria a utilização desse recurso limitado pelas atividades (variáveis) do modelo. Assim, a diferença entre direito e o lado esquerdo da restrição ( ≤ ) resultaria na quantidade do recurso não utilizada ou folga.
Para converter uma desigualdade

(≤)

em uma equação, uma variável de folga não

negativa é adicionada ao primeiro membro da restrição.
Exemplo 1. Dada a seguinte desigualdade: 3x + 2 y ≤ 12 .
Para transformar em uma equação adicionamos a variável de folga F1 e logo temos:
3 x + 2 y + F1 = 12, com F1 ≥ 0
Pesquisa Operacional I

Jhoab Negreiros

Capítulo 3

Algoritmo Simplex

2

De forma semelhante, uma restrição ( ≥ ) estabelece um limite inferior para as atividades do modelo de programação linear, de modo que a quantidade pela qual o lado esquerdo excede o limite mínimo representa uma sobra. Consegue-se a conversão de ( ≥ ) em uma igualdade com a subtração de uma variável de sobra não negativa do lado esquerdo da desigualdade.

Exemplo 2. Dada a seguinte desigualdade: x + y ≥ 100 .
Para transformar em uma equação subtraímos a variável de folga F2 e logo temos: x + y − F2 = 100, com F2 ≥ 0

A última possibilidade restante é que o lado direito da equação resultante seja negativo. A condição sempre pode ser satisfeita multiplicando-se ambos os lados da equação resultante por

( −1) .
Exemplo 3. Dada a seguinte desigualdade: − x + 2 y ≤ −20 .
Para transformar em uma