ExercícioUm fabricante de fantasias tem em estoque 32m de brim, 22 m de seda e 30m de cetime pretende fabricar dois modelos de fantasias. O primeiro modelo (m1) consome 4m de brim, 2m de seda e 2m de cetim. O segundo modelo (m2) consome 2m de brim, 4m de seda e 6m de cetim. Se m1 é vendido a 6000 u.m. e m2 a 10000 u.m., quantas peças de cada tipo ofabricante deve fazer para obter receita máxima?

Modelo

x1 modelo de fantasia 1x2 modelo de fantasia 2

Função-objetivo Max Z=6000 x1 + 10000 x2

4x1+2x2<=32 32 metros de brim2x1+4x2<=22 22 metros de seda2x1+6x2<=30 30 metros de cetim

1) Inserir variáveis de folga

x3 = 32 - 4x1 - 2x2 4x1+2x2+x3 = 32

Z -6000x1 - 10000x2 = 04x1+2x2+x3 = 32 x32x1+4x2+x4 = 22 x42x1+ 6x2+x5 = 30 x5

2) Elaborar quadro simplex inicial

Z x1 x2Z 1 -6000 -10000x3 0 4 2x4 0 2 4x5 0 2 6

x1 0x2 0x3 32x4 22x5 30Z 0

elemento pivô = 6

3) Variável que entra, variável que sai (primeira iteração)

entra (maior negatividade)sai (maior restrição ao crescimento de x2)

4) Alteração do quadro simplex e cálculo da nova linha pivô (primeira iteração)

dividir antiga linha pivô pelo elemento pivô

Z x1 x2Zx3x4x2 0 0.33333333333 1

5) Cálculo das novas linhas e nova solução viável (primeira iteração)

QUADRO ANTIGOZ x1 x2

Z 1 -6000 -10000x3 0 4 2x4 0 2 4x5 0 2 6

Cálculo nova linha ZAntiga Z 1 -6000 -10000Pivô Z -10000 -10000 -10000Nova pivô 0 0.33333333333 1Nova Z 1 -2666.6666667 0

Cálculo nova linha x3Antiga x3 0 4 2Pivô x3 2 2 2Nova L pivô 0 0.33333333333 1Nova x3 0 3.33333333333 0

Cálculo nova linha x4Antiga x4 0 2 4Pivô x4 4 4 4Nova L pivô 0 0.33333333333 1Nova x4 0 0.66666666667 0

NOVO QUADROZ x1 x2

Z 1 -2666.6666667 0x3 0 3.33333333333 0x4 0 0.66666666667 0x2 0 0.33333333333 1

x1 0x2 5x3 22x4 2x5 0Z 50000

não é a solução ótima porque ainda há coeficientes negativos na linha ZSe há coeficientes negativos na linha Z, há espaço para crescimento da variável

6) Variável que entra, variável que sai (segunda iteração)

Z x1 x2Z 1 -2666.6666667 0x3 0 3.33333333333 0x4 0 0.66666666667 0x2 0 0.33333333333 1

entra x1 maior negatividadesai x4 maior restrição ao crescimento de x1

7) Alteração do quadro simplex e cálculo da nova linha pivô (segunda iteração)

dividir linha x4 por 0.66666666667

Z x1 x2Zx3x1 0 1 0x2

8) Cálculo das novas linhas e nova solução (segunda iteração)

ANTIGO QUADROZ x1 x2

Z 1 -2666.6666667 0x3 0 3.33333333333 0x4 0 0.66666666667 0x2 0 0.33333333333 1

Cálculo nova linha ZAntiga Linha Z 1 -2666.6666667 0pivo linha Z -2666.66666666667 -2666.6666667 -2666.666666667nova linha pivô 0 1 0nova linha Z 1 0 0

Cálculo nova linha x3Antiga Linha x3 0 3.33333333333 0pivo linha x3 3.33333333333333 3.33333333333 3.3333333333333nova linha pivô 0 1 0nova linha x3 0 - 0

Cálculo nova linha x2Antiga Linha x2 0 0.33333333333 1pivo linha x2 0.333333 0.333333 0.333333nova linha pivô 0 1 0nova linha x2 0 0.00000 1

NOVO QUADROZ x1 x2

Z 1 0 0x3 0 0 0x1 0 1 0x2 0 0 1

x1 3x2 4x3 12x4 0x5 0Z 58000

não é a solução ótima porque ainda há coeficientes negativos na linha ZSe há coeficientes negativos na linha Z, há espaço para crescimento da variável

9) Variável que entra, variável que sai (terceira iteração)

Z x1 x2Z 1 0 0x3 0 0 0x1 0 1 0x2 0 0 1

entra x5 maior negatividadesai x3 maior restrição

10) Ateração quadro simplex e cálculo nova linha pivô (terceira iteração)

dividir linha x3 por 3

Z x1 x2Zx5 0 0 0

x1x2

11) Cálculo das novas linhas e nova solução (terceira iteração)

antigo quadroZ x1 x2

Z 1 0 0x3 0 0 0x1 0 1 0x2 0 0 1

Cálculo nova linha ZAntiga linha Z 1 0 0Pivô Z -1000 -1000 -1000nova linha pivô 0 0 0Nova Linha Z 1 0 0

Cálculo nova linha x1Antiga linha x1 0 1 0pivô x1 -1 -1 -1nova linha pivô 0 0 0Nova Linha x1 0 1 0

Cálculo Nova linha x2Antiga linha x2 0 0 1pivô x2 0.5 0.5 0.5nova linha pivô 0 0 0Nova Linha x1 0 0 1

NOVO QUADROZ x1 x2

Z 1 0 0x5 0 0 0x1 0 1 0x2 0 0 1

x1 7x2 2x3 0x4 0x5 4Z 62000

solução ótima

pergunta: quantos metros sobraram de cada tecido?sobraram 4 metros de cetim

2x1+6x2<=3014 + 12 = 26mestoque = 30

x3 x4 x5 VALOR divisão0 0 0 01 0 0 32 160 1 0 22 5.50 0 1 30 5

x2x5

x3 x4 x5 constante

0 0 0.16666666667 5

x3 x4 x5 constante0 0 0 01 0 0 320 1 0 220 0 1 30

0 0 0 0 a a-(bxc)-10000 -10000 -10000 -10000 b

0 0 0.16666666667 5 c0 0 1666.66666667 50000

1 0 0 322 2 2 20 0 0.16666666667 51 0 -0.3333333333 22

0 1 0 224 4 4 40 0 0.16666666667 50 1 -0.6666666667 2

x3 x4 x5 constante0 0 1666.66666667 500001 0 -0.3333333333 220 1 -0.6666666667 20 0 0.16666666667 5

x3 x4 x5 constante divisão0 0 1666.66666667 500001 0 -0.3333333333 22 6.60 1 -0.6666666667 2 30 0 0.16666666667 5 15

x3 x4 x5 constante

0 1.5 -1 3

x3 x4 x5 constante0 0 1666.66666667 500001 0 -0.3333333333 220 1 -0.6666666667 20 0 0.16666666667 5

0 0 1666.66666667 50000 A A-(BXC)-2666.6666667 -2666.6666667 -2666.6666667 -2666.6666667 B

0 1.5 -1 3 C0 4000 -1000 58000

1 0 -0.3333333333 223.33333333333 3.33333333333 3.33333333333 3.33333333333

0 1.5 -1 31 -5 3 12

0 0 0.16666666667 50.333333 0.333333 0.333333 0.333333

0 1.5 -1 30 -0.4999995 0.49999966667 4.000001

x3 x4 x5 constante0 4000 -1000 580001 -4.9999995 2.99999966667 12.0000010 1.5 -1 30 -0.4999995 0.49999966667 4

x3 x4 x5 constante divisão0 4000 -1000 580001 -4.9999995 2.99999966667 12.000001 4.00000077780 1.5 -1 3 -3 desconsiderar0 -0.4999995 0.49999966667 4 8.0000053333

x3 x4 x5 constante

0.33333333333 -1.6666665 0.99999988889 4.00000033333

x3 x4 x5 constante0 4000 -1000 580001 -4.9999995 2.99999966667 12.0000010 1.5 -1 30 -0.4999995 0.49999966667 4

0 4000 -1000 58000-1000 -1000 -1000 -1000

0.33333333333 -1.6666665 0.99999988889 4.00000033333333.333333333 2333.3335 -0.0001111111 62000.0003333

0 1.5 -1 3-1 -1 -1 -1

0.33333333333 -1.6666665 0.99999988889 4.000000333330.33333333333 -0.1666665 0 7.00000033333

0 -0.4999995 0.49999966667 40.5 0.5 0.5 0.5

0.33333333333 -1.6666665 0.99999988889 4.00000033333-0.1666666667 0.33333375 0 1.99999983333

x3 x4 x5 constante333.333333333 2333.3335 0 62000.00033330.33333333333 -1.6666665 0.99999988889 4.000000333330.33333333333 -0.1666665 0 7.00000033333-0.1666666667 0.33333375 0 1.99999983333

Microsoft Excel 11.0 Relatório de respostaPlanilha: [simplex2.xls]Plan2Relatório criado: 31/3/2008 15:25:47

Célula de destino (Máx)Célula Nome Valor original Valor final$C$17 qtde 62000 62000

Células ajustáveisCélula Nome Valor original Valor final$C$15 modelo 1 qtde 7 7$C$16 modelo 2 qtde 2 2

RestriçõesCélula Nome Valor da célula Fórmula Status Transigência$E$17 brim 32 $E$17<=$E$18 Agrupar 0$F$17 seda 22 $F$17<=$F$18 Agrupar 0$G$17 cetim 26 $G$17<=$G$18 Sem agrupar 4

Microsoft Excel 11.0 Relatório de limitesPlanilha: [simplex2.xls]Relatório de limites 1Relatório criado: 31/3/2008 15:29:48

DestinoCélula Nome Valor$C$17 qtde 62000

Ajustável Inferior Destino Superior DestinoCélula Nome Valor Limite Resultado Limite Resultado$C$15 modelo 1 qtde 7 0 20000 7 62000$C$16 modelo 2 qtde 2 0 42000 2 62000

Modelo

x1 modelo 1x2 modelo 2

Função-objetivo Max Z=6000 x1 + 10000 x2

4x1+2x2<=322x1+4x2<=222x1+6x2<=30

qtde lucro brim seda cetimmodelo 1 7 6000 4 2 2modelo 2 2 10000 2 4 6

62000 32 22 2632 22 30

x3 x4 x50 0 4

PASSOS INICIAIS

Modelar o problema de PLInserir variáveis de folgaConstruir quadro simplex inicial

A CADA ITERAÇÃO

Determinar quem entra e quem sai da baseAlterar quadro simplex e calcular nova linha pivôCalcular novas linhasVerificar se atingiu solução ótima

Z x1 x2 x3 x4 x5 VALOR divisãoZ 1 -6000 -10000 0 0 0 0

entra x2 x3 0 4 2 1 0 0 32 16sai x5 x4 0 2 4 0 1 0 22 5.5

x5 0 2 6 0 0 1 30 5

Z x1 x2 x3 x4 x5 VALOR divisãoZ 1 -2666.667 0 0 0 1666.667 50000

entra x1 x3 0 3.3333333 0 1 0 -0.333333 22 6.6sai x4 x4 0 0.6666667 0 0 1 -0.666667 2 3

x2 0 0.3333333 1 0 0 0.166667 5 15

Z x1 x2 x3 x4 x5 VALORZ 1.0 0.0 0.0 0.0 4000.0 -1000.0 58000.0

entra x5 x3 0.0 0.0 0.0 1.0 -5.0 3.0 12.0 3.999999sai x3 x1 0.0 1.0 0.0 0.0 1.5 -1.0 3.0 -3

x2 0.0 0.0 1.0 0.0 -0.50 0.5 4.0 7.999999

Z x1 x2 x3 x4 x5 VALORZ 1.0 0.0 0.0 333.3 2333.3 0.0 62000.0x3 0.0 0.0 0.0 0.3 -1.7 1.0 4.0x1 0.0 1.0 0.0 0.3 -0.2 0.0 7.0x2 0.0 0.0 1.0 -0.2 0.3 0.0 2.0