Estudo Robusto de Problemas de Programação Linear

Prévia do material em texto

FACULDADE ESTÁCIO DE SÃO LUÍS
CURSO DE ENGENHARIA DE PRODUÇÃO
MARLON LIMA FEITOSA
MARLON PAULO DE MELO WOLFF 
Estudo Robusto de Problemas de Programação Linear
SÃO LUÍS - MA
2018
MARLON LIMA FEITOSA
MARLON PAULO DE MELO WOLFF 
Estudo Robusto de Problemas de Programação Linear
Projeto de pesquisa apresentado ao Curso de Bacharelado em Engenharia de Produção, da Faculdade Estácio de São Luís
Orientador: Prof.	Marlon Paulo de Melo Wolff
SÃO LUÍS - MA
2018
Sumário
Problematização;
Modelo Matemático;
Solução pelo método Gráfica;
Construindo a região viável;
Calculo dos pontos desconhecidos;
Avaliando a função objetiva;
Análise da solução pelo método Gráfica;
Determinando o preço sombra de R1, R2 e R3;
Construindo a região viável;
Calculando os pontos desconhecidos;
Avaliando a função objetivo;
Equação do preço sombra;
Determinando o custo reduzido;
Determinando os limites de aumento e de redução dos RHS;
Determinando os limites de aumento e de redução dos coeficientes da função objetivo;
Solução pelo método Simplex;
Sistema de equação do Simplex;
Construindo os tablôs;
Identificando a linha, coluna e o elemento pivô de cada tablô; 
Calculando a nova linha pivô;
Análise da solução pelo método Simplex
Determinar as variáveis básicas e não básicas;
Identificar o preço sombra de R1, R2 e R3;
Identificar o custo reduzido;
Determinar a solução ótima;
Solução pelo método Solver
Construir a planilha com os dados entrada;
Construir a planilha com os dados de saída;
Preencher a caixa de diálogo do Solver e executa;
Gera o relatório de resposta e sensibilidade;
Análise da solução pelo método Solver; 
Análise do relatório de resposta;
Análise do relatório de sensibilidade;
Qual é o efeito de uma mudança em um coeficiente da função objetivo
Qual é o efeito de uma mudança em uma constante de uma restrição
Qual é o efeito de uma mudança em um coeficiente de uma restrição
Analise de sensibilidade Ad Hoc
 Gera e analisar uma Spider Plot
 Gera e analisar uma Spider Table
Gera e analisar um Solver Table	
PROBLEMA DE PL
O grupo B. B. Mendes (Cerâmica Mendes Ltda.) foi responsável pela licitação de R$ 6,97 milhões de investimentos no ano de 2017, em Itapecuru Mirim, para produzir lajotas (7cm x31cm x19cm) e tijolos (9cm x10cm x19cm). O Engenheiro de Produção da empresa estuda como prover o melhor nível de rentabilidade na produção de lajotas e tijolos, através de planejamento, organização e controle efetivo que visam facilitar o fluxo dos produtos e maximizar o lucro. 
A empresa tem a receita de R$ 350,00 para cada milheiro de lajotas vendidos e R$ 300,00 para cada milheiro de tijolos vendidos, com disponibilidade dos elementos de composição dos produtos finais de 200H de hora/trabalho, 1.566L de água e 2.880KG de argila. Na tabela a baixo lista-se as necessidades para cada produto.
Tabela 1
	Hora/trabalho
	Água
	Argila
	1
	9
	12
	1
	6
	16
MODELO MATEMÁTICO
SOLUÇÃO PELO MÉTODO GRÁFICA
Construindo a Região Viável
	
50
50
100
100
150
150
200
200
250
250
A
B
C
D
E
	
	
		
	R3
R2
R1
Cálculo dos Pontos desconhecidos
Cálculo do Ponto C:
Cálculo do Ponto D:
Avaliando a Função Objetivo
	PONTOS
	LUCRO
	
	 
	
	
	
	
	
	
	
	
 Com 
Análise de sensibilidade pela SOLUÇÃO GRÁFICA
Determinação do Preço Sombra:
Determinação do Preço Sombra da 1° Restrição
Construindo a Região Viável
	
50
50
100
100
150
150
200
200
250
250
A
B
C
D
E
	
	
		
	R3
R2
R1’
R1
Cálculo dos Pontos desconhecidos
Cálculo do Ponto C:
	
Cálculo do Ponto D:
Avaliando a Função Objetivo
	PONTOS
	LUCRO
	
	 
	
	
	
	
	
	
	
	
 Com 
Portanto:
Determinação do Preço Sombra da 2° Restrição
Construindo a Região Viável
	
50
50
100
100
150
150
200
200
250
250
A
B
C
D
E
	
	
		
R3
R2’
R2
	R1
Cálculo dos Pontos desconhecidos
Cálculo do Ponto C:
Cálculo do Ponto D:
Avaliando a Função Objetivo
	PONTOS
	LUCRO
	
	 
	
	
	
	
	
	
	
	
 Com 
Determinação do Preço Sombra da 3° Restrição
Construindo a Região Viável
	
50
50
100
100
150
150
200
200
250
250
A
B
C
D
E
	
	
		
	R3’
R3
R2
R1
Cálculo dos Pontos desconhecidos
Cálculo do Ponto C:
Cálculo do Ponto D:
Avaliando a Função Objetivo
	PONTOS
	LUCRO
	
	 
	
	
	
	
	
	
	
	
 Com 
Determinação do Custo Reduzido
Determinação dos limites inferiores e superiores De permissividade dos RHS 
Deslocando para cima e para baixo 
50
50
100
100
150
150
200
200
250
250
A
B
C
D
E
	
	
		
	R1
R3
R2
R1
R1 
Cálculo dos Pontos desconhecidos
Cálculo do Ponto C:
Cálculo do Ponto D:
Avaliando a Função Objetivo
	PONTOS
	LUCRO
	
	 
	
	
	
	
	
	
	
	
 Com 
Equação do aumento permitido no RHS da 
Equação da redução permitido no RHS da 
Deslocando para cima e para baixo R2 ↑↑
50
50
100
100
150
150
200
200
250
250
A
B
C
D
E
R2 
	
	
		
	R3
R2
R1
Cálculo dos Pontos desconhecidos
Cálculo do Ponto C:
Cálculo do Ponto D:
Avaliando a Função Objetivo
	PONTOS
	LUCRO
	
	 
	
	
	
	
	
	
	
	
 Com 
Equação do aumento permitido no RHS da 
Equação da redução permitido no RHS da 
Solução degenerada
Se na solução básica possível, alguma variável básica valer zero, a solução básica é dita degenerada. Geralmente a solução de um problema de PL se degenera se os valores de RHS de quaisquer restrições têm um aumento ou uma diminuição permissível igual a zero. A presença da degeneração afeta nossas interpretações dos valores no relatório de sensibilidade em diversa e relevantes maneiras.
O QUE FAZER?
Como os valores do custo reduzido também estão ligados aos coeficientes das restrições, caso o custo reduzido der um valor < 0 e uma variável de decisão ser = 0, ou seja, um Solução degenerada. Podemos analisar como a alterações de alguns coeficientes de restrições afetam a solução ótima em um problema de PL Pela formula do custo reduzido:
;
	
	
	
	
	
	
Solução pelo método simplex
Sistema de Equações do Simplex
 
1° TABELACOLUNA PIVÔ
LINHA PIVÔ
	L
	
	
	
	
	
	B
	1
	-350
	-300
	0
	0
	0
	0
	0
	1
	1
	1
	0
	0
	200
	0
	9
	6
	0
	1
	0
	1566
	0
	12
	16
	0
	0
	1
	2880
Identificando a linha pivô:
							N° da Linha pivô: 3
							Elemento pivô: 9
	
Cálculo da nova linha pivô:
	0
	9
	6
	0
	1
	0
	1566
Linha pivô: 
 ÷9:	
	0
	1
	0,6667
	0
	0,111
	0
	174
Nova linha pivô: 
COLUNA PIVÔ
2° TABELA
	L
	
	
	
	
	
	B
	
	1
	0
	-66.67
	0
	38,88
	0
	60900
	
	0
	0
	0,33
	1
	-0,111
	0
	26
	
	0
	1
	0,6667
	0
	0,111
	0
	174
	
	0
	0
	8
	0
	-1,32
	1
	792
	
LINHA PIVÔ
Identificando a linha pivô:
						N° da Linha pivô: 2
					Elemento pivô: 0,33
	
Cálculo da nova linha pivô:
	0
	0
	0,33
	1
	-0,111
	0
	26
Linha pivô: 
		÷0,33
	0
	0
	1
	3,03
	-0,33
	0
	78,78
Nova linha pivô: 
3° TABELA
	L
	
	
	
	
	
	B
	
	1
	0
	0
	200
	16.667
	0
	66.100
	
	0
	0
	1
	3
	-0,33
	0
	78
	
	0
	1
	0
	-2,03
	0,132
	0
	122
	
	0
	0
	0
	-24,118
	-1,057
	1
	168
	
ANÁLISE pelo método simplex
Variáveis básicas 					Variáveis não básicas 
						
							
	
	
 Com 
Solução pelo método SOLVER
Dados de Entrada
	Decisão de produtos
	 
	 
	 
	 
	Produtos
	Lajotas
	TijolosVariáveis de decisão
	0
	0
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 Parte de requisitos por produtos 
	 
	Restrições
	S.A.
	Lajotas
	Tijolos
	 
	Utilizado
	Sinal
	Disponibilidade
	Horas/trabalho
	1
	1
	 
	0
	≤
	200
	Água
	9
	6
	 
	0
	≤
	1566
	Argila
	12
	16
	 
	0
	≤
	2880
	 
	 
	 
	 
	 
	 
	Função objetivo
	 R$ 350,00 
	 R$ 300,00 
	 
	 R$ - 
	 
	 
Dados de Saída
	Decisão de produtos
	 
	 
	 
	 
	Produtos
	Lajotas
	Tijolos
	 
	 
	 
	 
	Variáveis de decisão
	122
	78
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 Parte de requisitos por produtos 
	 
	Restrições
	S.A.
	Lajotas
	Tijolos
	 
	Utilizado
	Sinal
	Disponibilidade
	Horas/trabalho
	1
	1
	 
	200
	≤
	200
	Água
	9
	6
	 
	1566
	≤
	1566
	Argila
	12
	16
	 
	2712
	≤
	2880
	 
	 
	 
	 
	 
	 
	Função objetivo
	 R$ 350,00 
	 R$ 300,00 
	 
	 R$ 66.100,00 
	 
	 
Análise de sensibilidade
Relatório de Resposta
	
	Célula do Objetivo (Máx.)
	
	
	
	
	Célula
	Nome
	Valor Original
	Valor Final
	
	
	$E$13
	Função objetivo utilizado
	 R$ - 
	 R$ 66.100,00 
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	Células Variáveis
	
	
	
	
	Célula
	Nome
	Valor Original
	Valor Final
	Número Inteiro
	
	$B$5
	Variáveis de decisão lajotas
	0
	122
	Conting.
	
	$C$5
	Variáveis de decisão tijolos
	0
	78
	Conting.
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	Restrições
	
	
	
	
	Célula
	Nome
	Valor da Célula
	Fórmula
	Status
	Margem de Atraso
	$E$9
	Horas/trabalho utilizado
	200
	$E$9<=$G$9
	Associação
	0
	$E$10
	Água utilizado
	1566
	$E$10<=$G$10
	Associação
	0
	$E$11
	Argila utilizado
	2712
	$E$11<=$G$11
	Não-associação
	168
	$B$5
	Variáveis de decisão lajotas
	122
	$B$5>=0
	Não-associação
	122
	$C$5
	Variáveis de decisão tijolos
	78
	$C$5>=0
	Não-associação
	78
Relatório de Sensibilidade
	
	Células Variáveis
	
	
	
	
	
	 
	 
	Final
	Reduzido
	Objetivo
	Permitido
	Permitido
	Célula
	Nome
	Valor
	Custo
	Coeficiente
	Aumentar
	Reduzir
	$B$5
	Variáveis de decisão lajotas
	122
	0
	350
	100
	50
	$C$5
	Variáveis de decisão tijolos
	78
	0
	300
	50
	66,66666667
	
	
	
	
	
	
	
	
	Restrições
	
	
	
	
	
	 
	 
	Final
	Sombra
	Restrição
	Permitido
	Permitido
	Célula
	Nome
	Valor
	Preço
	Lateral R.H.
	Aumentar
	Reduzir
	$E$9
	Horas/trabalho utilizado
	200
	200
	200
	7
	26
	$E$10
	Água utilizado
	1566
	16,66666667
	1566
	234
	126
	$E$11
	Argila utilizado
	2712
	0
	2880
	1E+30
	168
Análise de sensibilidade ad hoc
Spider Plot
Spider Table
	Lucro
	Horas/trabalho
	Água
	Argila
	$E$13
	$E$9
	$E$10
	$E$11
	 R$ 66.100,00 
	200
	1566
	2880
	90%
	 R$ 62.100,00 
	 R$ 63.150,00 
	 R$ 65.100,00 
	92%
	 R$ 62.900,00 
	 R$ 64.012,00 
	 R$ 65.580,00 
	94%
	 R$ 63.700,00 
	 R$ 64.534,00 
	 R$ 66.060,00 
	96%
	 R$ 64.500,00 
	 R$ 65.056,00 
	 R$ 66.100,00 
	98%
	 R$ 65.300,00 
	 R$ 65.578,00 
	 R$ 66.100,00 
	100%
	 R$ 66.100,00 
	 R$ 66.100,00 
	 R$ 66.100,00 
	102%
	 R$ 66.900,00 
	 R$ 66.622,00 
	 R$ 66.100,00 
	104%
	 R$ 67.500,00 
	 R$ 67.144,00 
	 R$ 66.100,00 
	106%
	 R$ 67.500,00 
	 R$ 67.666,00 
	 R$ 66.100,00 
	108%
	 R$ 67.500,00 
	 R$ 68.188,00 
	 R$ 66.100,00 
	110%
	 R$ 67.500,00 
	 R$ 68.710,00 
	 R$ 66.100,00 
Table solver
	Horas/trabalho
	Lajotas
	Tijolos
	Horas/trabalho
	Água
	Argila
	Lucro
	$G$9
	$B$5
	$C$5
	$E$9
	$E$10
	$E$11
	$E$13
	200
	122
	78
	 R$ 66.100,00 
	200
	1566
	2712
	170
	170
	0
	170
	1530
	2040
	 R$ 59.500,00 
	175
	172
	3
	175
	1566
	2112
	 R$ 61.100,00 
	180
	162
	18
	180
	1566
	2232
	 R$ 62.100,00 
	185
	152
	33
	185
	1566
	2352
	 R$ 63.100,00 
	190
	142
	48
	190
	1566
	2472
	 R$ 64.100,00 
	195
	132
	63
	195
	1566
	2592
	 R$ 65.100,00 
	200
	122
	78
	200
	1566
	2712
	 R$ 66.100,00 
	205
	112
	93
	205
	1566
	2832
	 R$ 67.100,00 
	210
	108
	99
	207
	1566
	2880
	 R$ 67.500,00 
	215
	108
	99
	207
	1566
	2880
	 R$ 67.500,00 
	220
	108
	99
	207
	1566
	2880
	 R$ 67.500,00