MSL 4 TAREFA 9

Prévia do material em texto

�PAGE �1�
�
Modelagem de Sistemas Logísticos 
Tarefa 9 – QUESTÕES
Nome_____________________________________________
QUESTÃO ÚNICA: resolver o problema de PL abaixo pelo método SIMPLEX. 
MIN Z = 3x1 + 4x2 + 2x3 + 5x4
s.a.
4x1 + 2x2 + x3 + 2x4 ≥ 100
x1 + 3x2 + 4x3 + 7x4 ≥ 150
x1, x2, x3, x4 ≥ 0
SOLUÇÃO
1º passo: transformar a função-objetivo de MIN em MAX
MAX (-Z) = - 3x1 – 4x2 – 2x3 – 5x4
2º passo: determinar a função-objetivo artificial transformada
W = - Z
MAX W = - 3x1 – 4x2 -2 x3 – 5x4
s.a.
4x1 + 2x2 + x3 + 2x4 – xF1 + A1 = 100
x1 + 3x2 + 4x3 + 7x4 – xF2 + A2 = 150
W = A1 + A2
3º passo: minimizar o valor de W em função de que queremos que W e A1 + A2 devem ser zerados e determinar a função-objetivo artificial transformada
MIN (-W) = -A1 – A2
-W + A1 + A2 = 0
4º passo: construir o quadro SIMPLEX
	-W
	X1
	X2
	X3
	X4
	xF1
	xF2
	A1
	A2
	b
	1
	0
	0
	0
	0
	0
	0
	1
	1
	0
	0
	4
	2
	1
	2
	-1
	0
	1
	0
	100
	0
	1
	3
	4
	7
	0
	-1
	0
	1
	150
5º passo: corrigir inconsistências
Nova linha 1 = Antiga linha 1 – (coeficiente da coluna A1 na linha 1) x Linha da variável A1 – (coeficiente da coluna A2 na linha 1) x Linha da variável A2 
Nova linha 1 = [1 0 0 0 0 0 0 1 1 0] + [0 -4 -2 -1 -2 1 0 -1 0 -100] + [0 -1 -3 -4 -7 0 1 0 -1 -150] = [1 -5 -5 -5 -9 1 1 0 0 -250]
6º passo: colocar a nova linha 1 no quadro SIMPLEX
	-W
	X1
	X2
	X3
	X4
	xF1
	xF2
	A1
	A2
	b
	1
	-5
	-5
	-5
	-9
	1
	1
	0
	0
	-250
	0
	4
	2
	1
	2
	-1
	0
	1
	0
	100
	0
	1
	3
	4
	7
	0
	-1
	0
	1
	150
7º passo: solucionar o quadro SIMPLEX
Variável que entra na base = x4
Variável que sai da base = A2
Elemento pivô = 7
Linha pivô:
	0
	1
	3
	4
	7
	0
	-1
	0
	1
	150
	÷ 7
	
	
	
	
	
	
	
	
	
	0
	1/7
	3/7
	4/7
	1
	0
	-1/7
	0
	1/7
	150/7
Nova linha 1:
	0
	1/7
	3/7
	4/7
	1
	0
	-1/7
	0
	1/7
	150/7
	x coeficiente da coluna de x4 com sinal invertido (9)
	0
	9/7
	27/7
	36/7
	9
	0
	-9/7
	0
	9/7
	1350/7
	1
	-5
	-5
	-5
	-9
	1
	1
	0
	0
	-250
	1
	-26/7
	-8/7
	1/7
	0
	1
	-2/7
	0
	9/7
	-400/7
Nova linha 2:
	0
	1/7
	3/7
	4/7
	1
	0
	-1/7
	0
	1/7
	150/7
	x coeficiente da coluna de x4 com sinal invertido (-2)
	0
	-2/7
	-6/7
	-8/7
	-2
	0
	2/7
	0
	-2/7
	-300/7
	0
	4
	2
	1
	2
	-1
	0
	1
	0
	100
	0
	26/7
	8/7
	-1/7
	0
	-1
	2/7
	1
	-2/7
	400/7
	-W
	X1
	X2
	X3
	X4
	xF1
	xF2
	A1
	A2
	b
	1
	-26/7
	-8/7
	1/7
	0
	1
	-2/7
	0
	9/7
	-400/7
	0
	26/7
	8/7
	-1/7
	0
	-1
	2/7
	1
	-2/7
	400/7
	0
	1/7
	3/7
	4/7
	1
	0
	-1/7
	0
	1/7
	150/7
Variável que entra na base: x1
Variável que sai da base: A1
Elemento pivô: 26/7
Linha pivô
	0
	26/7
	8/7
	-1/7
	0
	-1
	2/7
	1
	-2/7
	400/7
	÷ 26/7
	
	
	
	
	
	
	
	
	
	0
	1
	4/13
	-1/26
	0
	-7/26
	1/13
	7/26
	-1/13
	200/13
Nova linha 1
	0
	1
	4/13
	-1/26
	0
	-7/26
	1/13
	7/26
	-1/13
	200/13
	x coeficiente da coluna de x1 com sinal invertido (26/7)
	0
	26/7
	8/7
	-1/7
	0
	-1
	2/7
	1
	-2/7
	400/7
	1
	-26/7
	-8/7
	1/7
	0
	1
	-2/7
	0
	9/7
	-400/7
	1
	0
	0
	0
	0
	0
	0
	1
	1
	0
Nova linha 3
	0
	1
	4/13
	-1/26
	0
	-7/26
	1/13
	7/26
	-1/13
	200/13
	x coeficiente da coluna de x1 com sinal invertido (-1/7)
	0
	-1/7
	-4/91
	1/182
	0
	1/26
	-1/91
	-1/26
	1/91
	-200/91
	0
	1/7
	3/7
	4/7
	1
	0
	-1/7
	0
	1/7
	150/7
	0
	0
	40/91
	105/182
	1
	1/26
	-14/91
	-1/26
	14/91
	1750/91
	-W
	X1
	X2
	X3
	X4
	xF1
	xF2
	A1
	A2
	b
	1
	0
	0
	0
	0
	0
	0
	1
	1
	0
	0
	1
	4/13
	-1/26
	0
	-7/26
	1/13
	7/26
	-1/13
	200/13
	0
	0
	40/91
	105/182
	1
	1/26
	-14/91
	-1/26
	14/91
	250/13
Solução ótima: W = A1 = A2 = 0
8º passo: substituir a linha de (-W) pela linha de Z (original) e eliminar as colunas A1 e A2
	Z
	X1
	X2
	X3
	X4
	xF1
	xF2
	b
	1
	-3
	-4
	-2
	-5
	0
	0
	0
	0
	1
	4/13
	-1/26
	0
	-7/26
	1/13
	200/13
	0
	0
	40/91
	105/182
	1
	1/26
	-14/91
	250/13
Corrigir inconsistências (colunas x1 e x4):
Nova linha 1 = Velha linha 1 – (coeficiente da coluna x1 na linha 1) x (linha x1) – (coeficiente da coluna x4 na linha 1) x (linha x4) = 
Nova linha 1 = [1 -3 -4 -2 -5 0 0 0] + 3 x [0 1 4/13 -1/26 0 -7/26 1/13 200/13] + 5 x [0 0 40/91 105/182 1 1/26 -14/91 250/13] = 
[1 0 -80/91 10/13 0 -8/13 -7/13 1850/13]
	Z
	X1
	X2
	X3
	X4
	xF1
	xF2
	b
	1
	0
	-15/13
	10/13
	0
	-8/13
	-7/13
	1850/13
	0
	1
	4/13
	-1/26
	0
	-7/26
	1/13
	200/13
	0
	0
	5/13
	15/26
	1
	1/26
	-2/13
	250/13
Variável que entra na base: x3 (maior coeficiente positivo)
Variável que sai da base: x4
Elemento pivô: 15/26
Linha pivô:
	0
	0
	5/13
	15/26
	1
	1/26
	-2/13
	250/13
	÷ 15/26
	
	
	
	
	
	
	
	0
	0
	2/3
	1
	26/15
	1/15
	-4/15
	100/3
Nova linha 1
	
	0
	0
	2/13
	1
	26/15
	1/15
	-4/15
	100/3
	X (-10/13)
	
	
	
	
	
	
	
	
	
	0
	0
	-20/169
	-10/13
	-4/3
	-2/39
	-8/39
	-1000/39
	+
	
	
	
	
	
	
	
	
	
	1
	0
	-15/13
	10/13
	0
	-8/13
	-7/13
	1.850/13
	
	1
	0
	-215/169
	0
	-4/3
	-2/3
	-1/3
	350/3
Nova linha 2
	
	0
	0
	2/13
	1
	26/15
	1/15
	-4/15
	100/3
	x
	
	
	
	
	
	
	
	
	1/26
	0
	0
	2/338
	1/26
	1/15
	1/390
	-2/195
	50/39
	+
	
	
	
	
	
	
	
	
	
	0
	1
	4/13
	-1/26
	0
	-7/26
	1/13
	200/13
	
	0
	1
	53/169
	0
	1/15
	-52/195
	1/15
	50/3
	Z
	X1
	X2
	X3
	X4
	xF1
	xF2
	b
	1
	0
	-215/169
	0
	-4/3
	-2/3
	-1/3
	350/3
	0
	1
	53/169
	0
	1/15
	-52/195
	1/15
	50/3
	0
	0
	80/15
	1
	26/15
	1/15
	-4/15
	100/3
Essa é a solução ótima, pois não há nenhuma variável não básica com coeficiente positivo na 1ª linha do quadro SIMPLEX:
Z = 350/3
Variáveis básicas: 
x1 = 50/3 
x3 = 100/3
Variáveis não básicas: 
x2 = x4 = xF1 = xF2 = 0
�PAGE \* MERGEFORMAT�2�