Metodo Simplex

QUESTÃO 1

Maximizar Z = 4x + 5y

Sujeito a:

4x + 7y ≤ 336

6x + 3y ≤ 252

x1 , x2 ≥ 0

Solução:

1o Passo: Transformação da Função Objetivo e das Restrições:

Z – 4x – 5y = 0

4x + 7y + R1 = 336

6x + 3y + R2 = 252

2o Passo: Montagem do 1o Tableau:

Z x y R1 R2 LD Base

1 -4 -5 0 0 0 Linha Z

0 4 7 1 0 336 R1

0 6 3 0 1 252 R2

Neste primeiro tableau temos R1 e R2 na base, assumindo os valores 336 e 252, respectivamente. Como as variáveis x e y estão fora da base os seus valores são 0.

Como na Linha Z temos elementos negativos o tableau ainda não representa a solução ótima.

Portanto, alguma variável tem que entrar na base e, consequentemente, outra variável tem que sair.

3o Passo: Critério para definir a variável que entra na base:

Temos que escolher o menor valor da linha Z.

Z x y R1 R2 LD Base

1 -4 -5 0 0 0 Linha Z

0 4 7 1 0 336 R1

0 6 3 0 1 252 R2

A partir do tableau podemos perceber que esse valor é -5.

Portanto, a variável y deverá entrar na base. Logo temos que definir entre F1 e F2 quem vai sair da base. A coluna da variável que vai entrar na base é caracterizada por coluna-pivô.

4o Passo: Critério para definir a variável que sai da base:

Z x y R1 R2 LD Quociente Base

1 -4 -5 0 0 0 Linha Z

0 4 7 1 0 336 R1

0 6 3 0 1 252 R2

Para definir qual será a variável que vai sair da base (R1 ou R2) temos que calcular o quociente entre o Lado Direito (LD) e os valores que estão em destaque na coluna y, que foi a variável selecionada para entrar na base.

Logo: R1: 336/7 = 48

R2: 252/3 = 84

Portanto a variável R1 vai sair da base e a sua linha é caracterizada por linha-pivô.

5o Passo: Definição do elemento pivô:

Z x y R1 R2 LD Quociente Base

1 -4 -5 0 0 0 Linha Z

0 4 7 1 0 336 Y

0 6 3 0 1 252 R2

Esse elemento é o 7. Logo ele representa o número pivô que será utilizado para transformar os demais elementos da coluna-pivô em zero (0).

6o Passo: Alteração do elemento-pivô.

Vamos dividir toda a linha-pivô por 7, que é o elemento-pivô, transformando o elemento-pivô em 1, conforme destaque no tableau a seguir. Esse procedimento vai ser importante, pois vai facilitar o trabalho de eliminação dos demais elementos da coluna-pivô.

Z X y R1 R2 LD Base

1 -4 -5 0 0 0 Linha Z

0 4/7 1 1/7 0 48 Y

0 6 3 0 1 252 R2

7o Passo: Alteração dos elementos da coluna-pivô.

A partir de operações elementares vamos fazer o seguinte procedimento.

• Definição da nova linha y: Manter a linha y original.

• Definição da nova linha Z: Multiplicar a linha y por 5 e somar o resultado obtido com a linha Z

• Definição da nova linha R2: Multiplicar a linha y por -3 e somar o resultado obtido com a linha R2.

Z X y R1 R2 LD Base

1 -8/7 0 5/7 0 240 Linha Z

0 4/7 1 1/7 0 48 Y

0 30/7 0 -3/7 1 108 R2

Esse é o novo tableau que poderá ou não representar a solução ótima.

8o Passo: Análise da nova Linha Z

Z X y R1 R2 LD Base

1 -8/7 0 5/7 0 240 Linha Z

0 4/7 1 1/7 0 48 Y

0 30/7 0 -3/7 1 108 R2

Logo com a variável R2 saindo da base teremos como elemento-pivô o número 30/7, conforme tabela a seguir:

Z X y R1 R2 LD Base

1 -8/7 0 5/7 0 240 Linha Z

0 4/7 1 1/7 0 48 Y

0 30/7 0 -3/7 1 108 R2

O próximo passo é a transformação do elemento pivô em 1. Para tanto teremos que dividir toda a nova linha-pivô por 30/7.

Z X y R1 R2 LD Base

1 -8/7 0 5/7 0 240 Linha Z

0 4/7 1 1/7 0 48 Y

0 1 0 -1/10 7/30 126/5 X

• Transformar os demais elementos da coluna-pivô em zero.

Nova linha Z: Multiplicar a linha x por 8/7 e somar o resultado obtido com a linha z

Nova linha Y: Multiplicar a linha x por -4/7 e somar o resultado obtido com a linha y

Z X y R1 R2 LD Base

1 0 0 42/70 56/210 1344/5 Linha Z

0 0 1 14/70 -28/210 168/5 Y

0 1 0 -1/10 7/30 126/5 X

Esse é o novo tableau. Agora alcançamos a solução ótima uma vez que não temos mais