Simplex - Exercício

Prévia do material em texto

Exercício:
Um alfaiate tem, disponíveis, os seguintes tecidos: 16 metros de algodão, 11 metros de seda e 15metros de lã. Para um terno são necessários 2 metros de algodão, 1 metro de seda e 1 metro de lã. Para um vestido, são necessários 1 metro de algodão, 2 metros de seda e 3 metros de lã. Se um terno é vendido por $300,00 e um vestido por $500,00, quantas peças de cada tipo o alfaiate deve fazer, de modo a maximizar o seu lucro? 
Resolução:
Precisamos compreender qual a ideia do exercício, que neste caso, é saber quantos vestidos e quantos ternos seriam interessantes para obter o maior lucro (pois temos a diferença de preço e quanto gasta para a confecção de cada um)
	Terno: R$300
	Vestido: R$500
	X1 Ternos com X2 vestidos será a melhor opção de lucro, portanto:
n° de ternos x R$ 300 + n° de vestidos x R$ 500
Max Z = X1(300) + X2(500).
A partir daí temos nossas condições, pois temos no máximo 16 de algodão sendo que para fabricar um terno, precisamos de 2 metros e para o vestido apenas 1 metro. 11 metros de seda sendo 1 metro para terno e 2 metros para vestido e por fim 15 metros de lã onde 1 metro para terno e 3 metros para vestidos. Teremos, portanto:
	2x1 + x2 ≤ 16
	1x1 + 2x2 ≤ 11
	1x1 + 3x2 ≤ 15
Lembrando que todos valores devem ser superiores à 0 (zero), então criamos as condições a seguir:
	2x1 + x2 = 16
	se x1 for 0, x2 será 16
	se x2 for 0, x1 será 8
	1x1 + 2x2 = 11
	se x1 for 0, x2 será 5,5
	se x2 for 0, x1 será 11
	1x1 + 3x2 = 15
	se x1 for 0, x2 será 5
	se x2 for 0, x1 será 15
A partir dessas condições, podemos construir nossa tabela de referência para iniciar os cálculos. O preenchimento seguirá por etapas, onde teremos duas variáveis (x1 e x2 do nosso MAX Z) e três condições que vimos (algodão, seda e lã, que serão s1, s2 e s3). A solução que é nosso valor estabelecido como parâmetro da margem de trabalho e por fim Z que é a relação direta obtida com a combinação na produção e os lucros.
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	
	
	
	
	
	
	s2
	
	
	
	
	
	
	s3
	
	
	
	
	
	
	Z
	
	
	
	
	
	
Vamos preencher a primeira tabela apenas com as condições de quanto cada item precisa consumir de matéria prima
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	2
	1
	
	
	
	
	s2
	1
	2
	
	
	
	
	s3
	1
	3
	
	
	
	
	Z
	
	
	
	
	
	
Vamos atribuir os valores de lucro relacionado. Sendo maximização, temos então os valores negativos no final da tabela.
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	2
	1
	
	
	
	
	s2
	1
	2
	
	
	
	
	s3
	1
	3
	
	
	
	
	Z
	-300
	-500
	
	
	
	
Agora teremos de preencher a matriz onde o cruzamento retorna um, e soluções diferentes são zero
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	2
	1
	1
	0
	0
	
	s2
	1
	2
	0
	1
	0
	
	s3
	1
	3
	0
	0
	1
	
	Z
	-300
	-500
	0
	0
	0
	
Por fim, preenchemos nossa solução:
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	2
	1
	1
	0
	0
	16
	s2
	1
	2
	0
	1
	0
	11
	s3
	1
	3
	0
	0
	1
	15
	Z
	-300
	-500
	0
	0
	0
	0
Faremos nesse momento uma verificação do nosso pivô. Este cálculo se baseia na operação sobre linhas de Gauss-Jordan. Precisamos selecionar nas linhas de nossas variáveis x1 e x2 o maior valor negativo. Observamos percebemos tratar-se do -500
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	2
	1
	1
	0
	0
	16
	s2
	1
	2
	0
	1
	0
	11
	s3
	1
	3
	0
	0
	1
	15
	Z
	-300
	-500
	0
	0
	0
	0
Agora seguimos para uma operação para descobrir nosso menor valor positivo quando olhamos nas 3 soluções possíveis. Isso deverá ocorrer realizando a divisão da 7 colunas (descrição) pela terceira coluna (x2, identificada como a maior valor negativo).
	x2
	Solução
	Operação matemática
	Resultado
	1
	16
	16 / 1
	16
	2
	11
	11 / 2
	5,5
	3
	15
	15 / 3
	5
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	2
	1
	1
	0
	0
	16
	s2
	1
	2
	0
	1
	0
	11
	s3
	1
	3
	0
	0
	1
	15
	Z
	-300
	-500
	0
	0
	0
	0
O número 3 será nosso pivô, o que gerará uma nova linha 3 baseada na divisão dos números da linha pelo número pivô
	Linha 3
	s3
	1
	3
	0
	0
	1
	15
	Divisão
	s3
	1/3
	3/3
	0/3
	0/3
	1/3
	15/3
Linha pivô (Linha 3):
1 / 3 = 1 / 3
3 / 3 = 1
0 / 3 = 0
0 / 3 = 0
1 / 3 = 1 / 3
15 / 3 = 5
Nosso resultado teórico será:
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	2
	1
	1
	0
	0
	16
	s2
	1
	2
	0
	1
	0
	11
	s3
	1/3
	1
	0
	0
	1/3
	5
	Z
	-300
	-500
	0
	0
	0
	0
Mas deveremos realizarmos uma operação para zerar os valores das outras linhas, gerando novas linhas onde X2 ficará zerado com base na terceira linha.
	
	Resultado atual
	Resultado esperado
	Base
	x2
	x2
	s1
	1
	0
	s2
	2
	0
	s3
	1
	1 
	Z
	-500
	0
Para isso, deveremos analisar as opções:
Linha 1: Para eliminar o valor 1 da primeira linha, bastará subtrair a linha 1 pela linha 3
	s1
	2
	1
	1
	0
	0
	16
2 - (1 * 1 / 3) = 5 / 3
1 - (1 * 1) = 0
1 - (1 * 0) = 1
0 - (1 * 0) = 0
0 - (1 * 1 / 3) = -1 / 3
16 - (1 * 5) = 11
Linha 2: Para eliminar o valor 2 da segunda linha, a conta poderá ser a subtração do dobro da linha nova 3, por aí teremos (2 - (2*1))
	s2
	1
	2
	0
	1
	0
	11
1 - (2 * 1 / 3) = 1 / 3
2 - (2 * 1) = 0
0 - (2 * 0) = 0
1 - (2 * 0) = 1
0 - (2 * 1 / 3) = -2 / 3
11 - (2 * 5) = 1
Linha Z: Para eliminar -500 com o valor 1, podemos subtrair o valor de -500 com a multiplicação de -500 * 1, que é o valor disposto na tabela. 
	Z
	-300
	-500
	0
	0
	0
	0
-300 - (-500 * 1 / 3) = -400 / 3
-500 - (-500 * 1) = 0
0 - (-500 * 0) = 0
0 - (-500 * 0) = 0
0 - (-500 * 1 / 3) = 500 / 3
0 - (-500 * 5) = 2500
Nosso resultado final, após as operações matemáticas, será:
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	5/3
	0
	1
	0
	-1/3
	11
	s2
	1/3
	0
	0
	1
	-2/3
	1
	s3
	1/3
	1
	0
	0
	1/3
	5
	Z
	-400/3
	0
	0
	0
	500/2
	2500
Porém nosso valor de x1 ainda está negativo e nosso objetivo é torná-lo positivo, portanto, faremos o mesmo procedimento inicial de encontrarmos nosso pivô, porém nesse caso apenas temos a variável x1, então será essa coluna bastando identificar qual é a linha
	x1
	Solução
	Operação matemática
	Resultado
	5/3
	11
	11 / (5/3)
	6,6
	1/3
	1
	1 / (1/3)
	3
	1/3
	5
	5 / (1/3)
	15
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	5/3
	0
	1
	0
	-1/3
	11
	s2
	1/3
	0
	0
	1
	-2/3
	1
	s3
	1/3
	1
	0
	0
	1/3
	5
	Z
	-400/3
	0
	0
	0
	500/2
	2500
O número 1/3 será nosso pivô na segunda etapa, o que gerará uma nova linha 2 baseada na divisão dos números da linha pelo número pivô
Linha pivô (Linha 2):
	Linha 2
	s2
	1/3
	0
	0
	1
	-2/3
	1
	Divisão
	s2
	1/3 / (1/3)
	0/(1/3)
	0/(1/3)
	1/(1/3)
	-2/3 / (1/3)
	1/ (1/3)
1 / 3 / (1 / 3) = 1
0 / (1 / 3) = 0
0 / (1 / 3) = 0
1 / (1 / 3) = 3
-2 / 3 / (1 / 3) = -2
1 / (1 / 3) = 3
Nosso resultado teórico será:
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	5/3
	0
	1
	0
	-1/3
	11
	s2
	1
	0
	0
	3
	-2
	3
	s3
	1/3
	1
	0
	0
	1/3
	5
	Z
	-400/3
	0
	0
	0
	500/2
	2500
Linha 1: Para eliminação da primeira linha, vamos subtrair a linha 2 que estará multiplicada por 5/3.
A dica fica em pensar que a linha 2 tem o valor 1, por isso fica fácil
5 / 3 - (5 / 3 * 1) = 0
0 - (5 / 3 * 0) = 0
1 - (5 / 3 * 0) = 1
0 - (5 / 3 * 3) = -5
-1 / 3 - (5 / 3 * -2) = 3
11 - (5 / 3 * 3) = 6
Linha 3: Para eliminar, o princípio é quase o mesmo uma vez que ambas tem o valor de 1/3
1 / 3 - (1 / 3 * 1) = 0
1 - (1 / 3 * 0) = 1
0 - (1 / 3 * 0) = 0
0 - (1 / 3 * 3) = -1
1 / 3 - (1 / 3 * -2) = 1
5 - (1 / 3 * 3) = 4
Linha Z: Como anteriormente disposto, pegaremos a linha pivô e observaremos o método de eliminação dos valores da coluna x1. 
-400 / 3 - (-400 / 3 * 1) = 0
0 - (-400 / 3 * 0) = 0
0 - (-400 / 3 * 0) = 0
0 - (-400 / 3 * 3) = 400
500 / 3 - (-400 / 3 * -2) = -100
2500 - (-400 / 3 * 3) = 2900
No final dessa etapa teremos:
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	0
	0
	1
	-5
	3
	6
	s2
	1
	0
	0
	3
	-2
	3
	s3
	0
	1
	0
	-1
	1
	4
	Z
	0
	0
	0
	400
	-100
	2900
Perceba que na coluna S3 ainda temos o valor -100 (negativo) porém as variáveis x1 e x2 estão de forma binária ( ou zero ou 1 ).
Nesse momento, definiremos novamente a coluna pivô. Pela lógica, o menor negativo será -100
	s3
	Solução
	Operação matemática
	Resultado
	3
	6
	6/3
	2
	-2
	33/-2
	-1,5
	1
	4
	4/1
	4
Perceba que mesmo sendo -1,5, sempre olharemos o menos valor positivo, portanto, linha 1.
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	0
	0
	1
	-5
	3
	6
	s2
	1
	0
	0
	3
	-2
	3
	s3
	0
	1
	0
	-1
	1
	4
	Z
	0
	0
	0
	400
	-100
	2900
Linha pivô (Linha 1):
	Linha 1
	s1
	0
	0
	1
	-5
	3
	6
	Divisão
	s1
	0/3
	0/3
	1/3
	-5/3
	3/3
	6/3
6 / 3 = 2
0 / 3 = 0
0 / 3 = 0
1 / 3 = 1 / 3
-5 / 3 = -5 / 3
3 / 3 = 1
Nosso resultado teórico será:
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	0
	0
	1/3
	-5/3
	1
	2
	s2
	1
	0
	0
	3
	-2
	3
	s3
	0
	1
	0
	-1
	1
	4
	Z
	0
	0
	0
	400
	-100
	2900
Linha 2: Para eliminar a segunda linha e sua segunda coluna, podemos multiplicar por -2
1 - (-2 * 0) = 1
0 - (-2 * 0) = 0
0 - (-2 * 1 / 3) = 2 / 3
3 - (-2 * -5 / 3) = -1 / 3
-2 - (-2 * 1) = 0
3 - (-2 * 2) = 7
Linha 3: Subtração da linha 1 multiplicada por 1.
0 - (1 * 0) = 0
1 - (1 * 0) = 1
0 - (1 * 1 / 3) = -1 / 3
-1 - (1 * -5 / 3) = 2 / 3
1 - (1 * 1) = 0
4 - (1 * 2) = 2
Linha Z: 
0 - (-100 * 0) = 0
0 - (-100 * 0) = 0
0 - (-100 * 1 / 3) = 100 / 3
400 - (-100 * -5 / 3) = 700 / 3
-100 - (-100 * 1) = 0
2900 - (-100 * 2) = 3100
Nesse momento temos os valores positivos na linha do Z
	Base
	x1
	x2
	s1
	s2
	s3
	Solução
	s1
	0
	0
	1/3
	-5/3
	1
	2
	s2
	1
	0
	2/3
	3
	0
	7
	s3
	0
	1
	-1/3
	2/3
	0
	2
	Z
	0
	0
	100/3
	700/3
	0
	3100
A solução ótima é Z = 3100. Agora retomaremos a situação inicial e verificaremos como ficará com os valores da coluna “Solução”.
n° de ternos x R$ 300 + n° de vestidos x R$ 500
Max Z = 7(300) + 2(500)
Max Z = (2100) + (1000) = 3100
MÉTODO GRÁFICO
Pelo método gráfico, podemos seguir da seguinte maneira:
	2x1 + x2 ≤ 16
	1x1 + 2x2 ≤ 11
	1x1 + 3x2 ≤ 15
2x1 + x2 ≤ 16:
1x1 + 2x2 ≤ 11
1x1 + 3x2 ≤ 15
	se x1 for 0, x2 será 16
	se x2 for 0, x1 será 8
	se x1 for 0, x2 será 5,5
	se x2 for 0, x1 será 11
	se x1 for 0, x2 será 5
	se x2 for 0, x1 será 15
Teremos portanto:
Separando todos os pontos, teremos:
A) x1 = 0, x2 = 16
B) x2 = 0, x1 = 8
E) x1= 0, x2 = 5,5
F) x2 = 0, x1 = 11
H) x1 = 0, x2 = 5
I) x2 = 0, x1 = 15
Notamos então, que os pontos que nos faltam são o C e G dentro da perspectiva de ótima.
C) Como esse ponto é intersecção da linha de ‘1x1 + 2x2 ≤ 11’ e ‘2x1 + x2 ≤ 16’, utilizaremos ambas fórmulas para encontrarmos os valores referentes.
1x1 + 2x2 = 11 x(2) e (-)
2x1 + x2 = 16
0x1 + 3x2 = 6
x2 = 2
x1 = 7
G) Como esse ponto é intersecção da linha de ‘1x1 + 2x2 ≤ 11’ e ‘1x1 + 3x2 ≤ 15’, utilizaremos ambas fórmulas para encontrarmos os valores referentes.
1x1 + 2x2 =11 (-)
1x1 + 3x2 = 15 
0x1 -1x2 = 4
x2 = 4
x1 = 3
Em resumo, vamos obter a seguinte tabela:
	Ponto
	Coordenada X (X1)
	Coordenada Y (X2)
	Valor da função (Z)
	O
	0
	0
	0
	A
	0
	16
	8000
	B
	8
	0
	2400
	C
	7
	2
	3100
	D
	33 / 5
	14 / 5
	3380
	E
	0
	11 / 2
	2750
	F
	11
	0
	3300
	G
	3
	4
	2900
	H
	0
	5
	2500
	I
	15
	0
	4500
O valor da função(Z) é obtido com a substituição das variáveis