Programação linear

Exemplo Numérico Seja o seguinte problema de Programação Linear:

1- Transformação do modelo para o formato padrão:

Exemplo Numérico 2- Quadro inicial de cálculo, Passo 1 do algoritmo:

x1 x2 x3 x4 x5 x6 X7

Z
0
4
5
9
11
0
0
0

X5
15
1
1
1
1
1
0
0

X6
120
7
5
3
2
0
1
0

X7
100
3
5
10
15
0
0
1

(*) observar que no primeiro quadro as variáveis de folga constituem uma base canônica, sendo desnecessária a determinação de sua inversa.

3- Passo 2 do algoritmo: Regra de Parada. Como existe >0 uma variável deve entrar na base. A escolhida é x4 pois é o maior valor entre os .

x1 x2 x3
X4
x5 x6 X7

Z
0
4
5
9
11
0
0
0

X5
15
1
1
1
1
1
0
0

x6
120
7
5
3
2
0
1
0

x7
100
3
5
10
15
0
0
1

Exemplo Numérico

4- Passo 3 do algoritmo: Determinação da variável que sai da base (determinação do pivô).

A variável x7 sai da base uma vez que 100/15 é o menor valor para o crescimento de x4 .

x1 x2 x3 x4 x5 x6 x7

z
0
4
5
9
11
0
0
0

x5
15
1
1
1
1
1
0
0
15/1
x6
120
7
5
3
2
0
1
0
120/2
x7
100
3
5
10
15
0
0
1
100/15
Pivô

5- Passo 4 do algoritmo: Operação de cálculo dos valores de solução associados à nova base. No caso do uso do quadro Simplex essa fase corresponde ao denominado pivoteamento, que permite o cálculo das matrizes do problema através do método das operações elementares. A linha do pivô é dividida por 15, o valor do pivô.
Exemplo Numérico

Etapa 1: Construção do Pivô:

x1 x2 x3 x4 x5 x6 x7

z
0
4
5
9
11
0
0
0

x5
15
1
1
1
1
1
0
0

x6
120
7
5
3
2
0
1
0

x7
20/3
1/5
1/3
2/3
1
0
0
1/15

Etapa 2: Construção da Coluna do Pivô:

x1 x2 x3 x4 X5 x6 x7

z
-220/3
9/5
4/3
5/3
0
0
0
-11/15

x5
25/3
4/5
2/3
1/3
0
1
0