atividade 1

Prévia do material em texto

1/1
CENTRO UNIVERSITÁRIO DA GRANDE DOURADOS
Curso: Engenharia de Produção
Semestre: 6º 
Disciplina: Pesquisa Operacional
Professor: Bárbara Helen Rodrigues Ramires Seribeli
ATIVIDADE 1 - REFERENTE AS AULA 01 A 04
Construção de modelos
1) A empresa NYZ, fez uma recente pesquisa onde aponta que a necessidade mínima de vitaminas na alimentação é de 37 unidades por dia e a de proteínas de 31 unidades por dia. Considerando que uma pessoa tem disponível carne e ovo para se alimentar e que cada unidade de carne contém 4 unidades de vitaminas e 6 unidades de proteínas e cada unidade de ovo contém 8 unidades de vitaminas e 6 unidades de proteínas. Construa o modelo matemático que representa qual a quantidade de carne e ovo que deve ser consumida de forma a ter o “Menor custo possível”. Cada unidade de carne custa R$ 3,00 e cada unidade de ovo custa R$ 2,5. 
	Alimento
	Vitamina
	Proteína
	Custo
	Carne
	4
	6
	3
	Ovo
	8
	6
	2,5
1. Variáveis:
x1= carne por dia
x2= ovo por dia
2. Objetivo:
Minimizar z= 3x1 + 2,5x2
3. Restrições:
Minimizar z= 3x1 + 2,5x1
Sujeito a:
4x1+8x2≥37
6x1+6x2≥31
2) A Só Janelas Ltda. é uma empresa com apenas três funcionários que fazem dois tipos diferentes de janelas feitas à mão: uma com esquadria de madeira e outra com esquadria de alumínio. Eles têm um lucro de R$ 60,00 por janela com esquadria de madeira e de R$ 30,00 para janela com esquadria de alumínio. João faz as de esquadria de madeira e é capaz de construir seis delas por dia. Maria faz as janelas com esquadrias de alumínio e é capaz de construir quatro delas por dia. Roberto monta e corta os vidros e é capaz de fazer 48 m²/dia. Cada janela com esquadria de madeira usa 6 m² de vidro e cada janela com esquadria de alumínio usa 8 m² de vidro. A empresa quer determinar quantas janelas de cada tipo de esquadria podem ser fabricadas diariamente para maximizar o lucro total.
(a) Formule um modelo de programação linear para este problema.
	Produtos
	Lucro
	Disponibilidade Janelas
	Utilização de Vidros
	Janelas Esquadrilha de Madeira
	60
	6
	6
	Janelas Esquadrilha de Alumínio
	30
	4
	8
1. Variáveis:
x1= Esquadrilha de Madeira produzidas diariamente
x2= Esquadrilha de Alumínio produzidas diariamente
2. Objetivo:
Maximizar z= 60x1 + 30x2
3. Restrições:
Minimizar z= 60x1 + 60x1
Sujeito a:
6x1+ 8x2 ≤ 48
x1+ x2 ≤ 10
x1 ≤ 6
x2 ≤ 4
x1≥0
x2≥0
(b) Use o método gráfico para solucionar esse modelo. 
3) Um fazendeiro precisa decidir quantos hectares plantar de milho e arroz. Para cada hectare de milho plantado o fazendeiro recebe o lucro de R$ 5,00 e para arroz R$ 2,00. Por razões técnicas a área do milho não pode exceder 03 hectares e a de arroz não deve ser maior que 04 hectares. O milho necessita do cuidado de 01 pessoa por hectare e o arroz de 02 pessoas. O número total de pessoas disponíveis é 09. Qual deve ser a decisão do fazendeiro para obter lucro máximo? 
Observações quanto a resolução deste problema:
Resolva esta questão utilizando o método do Solver do Excel, tire print da caixa de configuração do modelo com as variáveis configuradas no solver e da planilha montada com o resultado final. Resoluções feitas por outro método não serão aceitas. 
Resolução:
Método Gráfico
4) Considere o modelo:
Maximizar Z = 2x1 + 3x2
Sujeito as restrições:
x1 + 5x2 ≤ 20
2x1 + x2 ≤ 10
x1 ≥ 0, x2 ≥ 0
a) Use o método gráfico para construir a região de soluções do modelo (construir o gráfico a mão, indicar no gráfico a região de solução factível).
Ponto de referência (0,0)
Para restrição 1: x1+5x2=20
Ponto A (0,4)
Ponto B (20,0)
Restrição2: 2x1+x2=10
Ponto D (0,10)
Ponto E (5,0)
b) Testar a função objetivo em cada uma das soluções básicas e escolher o ponto mais favorável.
Região Factível: ACE
Função objetivo: 2x1+3x2
Ponto A: 2.0+3.4=12 (valor de z)
Ponto E: 2.5+3.0=10 (valor de z)
Ponto C: Intersecção do segmentos das retas 1 e 2
(I) x1+5x2=20
(II) 2x1+x2=10
Isolamento de x1: 20-5x2
Substituir na 2 equação obtenho o valor de x2= 3,33.
Substituir o valor de x2 na equação isolada temos: x1= 3,35
Ponto C; 2.3,35+3.3,33=16,66
Max X= 2(3,35) + 3(3,33)=16,66
Método Simplex
5) Resolva o exemplo de um modelo abaixo utilizando as regras e tabelas do simplex. Apresentar as tabelas do simplex para validação da resposta (fazer a mão apresentando o passo a passo na forma de tabela).
Maximizar Z = 3x1 + 5x2
 Sujeito a:
4x1 ≤ 12
5x1 + 5x2 ≤ 21
2x1 + x2 ≤ 8
x1 , x2 ≥ 0
Resolução:
Z-3x1-5x2=0
4x1+xf1≤12
5x1 + 5x2 + xf2≤ 21
2x1 + x2+ xf3 ≤ 8
	z
	x1
	x2
	xf1
	xf2
	xf3
	b
	1
	-3
	-5
	0
	0
	0
	0
	0
	4
	0
	1
	0
	0
	12
	0
	5
	5
	0
	1
	0
	21
	0
	2
	1
	0
	0
	1
	8
NPL: 0 5 5 0 1 0 21
÷ (5) 0 1 1 0 0,2 0 4,2
Nova Tabela:
	z
	x1
	x2
	xf1
	xf2
	xf3
	b
	1
	2
	0
	0
	1
	0
	21
	0
	4
	0
	1
	0
	0
	12
	0
	10
	10
	0
	6
	0
	42
	0
	3
	2
	0
	0,2
	0
	12,2
Solução: 
	VB
	VnB
	Valor de Z
	Xf1=12
	X1=0
	Z= 21
	xf2=21
	X2=0
	
Análise de Sensibilidade e Dualidade
6) A ElectraPlus produz dois tipos de motores elétricos em duas máquinas. Uma unidade do motor 1 requer duas horas na máquina 1 e uma hora na máquina 2. Para o motor 2, uma unidade requer uma hora da máquina 1 e três horas da máquina 2. As receitas por unidade dos produtos 1 e 2 são $30 e $20, respectivamente. O tempo de processamento diário disponível para cada máquina é oito horas.
Desta forma, representando o número diário de unidade dos motores 1 e 2 por x1 e x2, respectivamente, o modelo de programação linear é dado como:
Max z = 30x1 + 20x2 
Sujeito a 
2x1 + x2 ≤ 8 (máquina 1)
x1 + 3x2 ≤ 8 (máquina 2) 
x1, x2 ≥ 0 ( não-negatividade)
Logo, pede-se: 
(a) Determine o mix ótimo de produção diária.
Determinação dos pontos utilizando como referência os valores (0,0)
1. 2x1+x2=8
A (0,8)
B (4,0)
2. x1+3x2=8
D (0,2,67)
E (8,0)
Teste da Região Factível
Ponto de teste (1,1)
2.1+1≤8=3≤8 – Verdadeiro
1+3≤8=4≤8 - Verdadeiro
Teste os valores de Z:
Ponto D (0, 2,67)
10x1+10x2=30.0+20.(2,67)= 53,4 (valor de z)
Ponto C (3,2; 1,6)
30.(3,2)+20.(1,6)= 128 (valor de Z)
Ponto B (4,0)
30.4+20.0=120 (Valor de Z)
Solução Ótima: Z= 128 ; x1=3,2 e x2=1,6
(b) A Electraplus decidiu realizar alterações na máquina 1 em relação a capacidade de horas de 8 horas para 9 horas diária. Use análise de sensibilidade para determinar se a solução ótima permanecerá inalterada e determine o seu preço dual. 
Determinação dos pontos utilizando como referência os valores (0,0)
Reta 3 2x1+x2=9
Reta 2 x1+3x2=8
Pontos F (Intersecção das retas 2 e 3
Conclusão: Se a capacidade diária da máquina 1 for aumentada de 8 para 9 horas, a solução antes que era em C ocorrerá agora em F.
Análise de Sensibilidade Gráfica
Determinação do ponto F das retas 2 e 3
(I) 2x1+x2=9
(II) x1+3x2=8
Isolar x1 para encontrar o calor de x2
Reta 2: x1=(8-3x2)
Substituir na equação I
2.(8-3x2)+x=9
X2= 1,4
P/ x1= 8-(3.1,4)= 3,8
Ponto F (3,8; 1,4)
Conclusão:
Ponto F (3,8; 1,4)
Substituir na função objetivo:
Z= 30.3,8 + 20.1,4= 142
Determinação do preço Dual
Conclusão:
O preço dual pode ser determinado através da taxa de variação na ceita resultante do aumento de uma hora na capacidade da máquina do Ponto C para o Ponto F, logo temos, $ 14/h. Isso significa que uma unidade de aumento na capacidade da máquina 1 aumentará a receita em $14.
7) Escreva o dual dos problemas primais abaixo:
a) Min Z = 10x1 + 20x2
Sujeito a:
x1 + 2x2 ≥ 3
2x1+ 5x2 ≥ 60
x1, x2 ≥ 0
Resolução:
Max. Z: 3y1+60y2
y1+2y2≤10
2y1+5y2≤20
y1+y2≤0
b) Max Z = 5x1 + 6x2
Sujeito a: 
x1 + 2x2 ≤ 5
x1 + 5x2 ≤ 3
4x1 + 7x2 ≤ 8
x1, x2 ≥ 0
Resolução:
Min. Z: 5y1+3y2+8y3
1y1+2y2+4y3≤5
2y1+5y2+7y3≤6
y1+y2+y3≤0
Problemas com transporte
8) A prefeitura de Dourados está fazendo obras em três bairros. O material para essas obras é transportado de três depósitos O1, O2 e O3 de onde são retiradas 57, 84 e 95 toneladas de material, respectivamente. As obras são destinadas para os bairros D1, D2 e D3, que necessitam diariamentede 49, 83 e 106 toneladas, respectivamente. Os custos unitários para o transporte desse material estão na tabela a seguir.
Tabela 01 - Custos Unitários dos Transportes (R$/unidade)
	
	Destino 01
	Destino 02
	Destino 03
	
	Depósito 01
	7
	9
	6
	0
	Depósito 02
	5
	7
	5
	47
	Depósito 03
	8
	5
	12
	0
	
	0
	0
	49
	
 
 Pede-se para determinar:
a) O modelo de transporte que minimiza o custo de transporte.
	
	D1
	D2
	D3
	O1
	
	
	57
	O2
	37
	
	47
	O3
	12
	83
	
b) O custo de transporte mínimo.
Min Z: XO1D1*7 + XO1D2*9 + XO1D3*6 + XO2D1*5 + XO2D2*7 + XO2D3*5 + XO3D1*8 + XO3D2*5 + XO3D3*12
Min Z: 0*7 + 0*9 + 57*6 + 37*5 + 0*7 + 47*5 + 12*8 + 83*5 + 0*12
Min Z: 1273
9) O problema da designação é um tipo especial de problema de programação linear em que os “designados” estão sendo indicados para a realização de tarefas. Diante da frase afirmada, cite pelo menos 02 exemplos reais onde utilizou-se problemas de designação, e explique a maneira como estes foram formulados.
Exemplo 1:
O coordenador de um curso selecionou aletoriamente quatro alunos da turma do último semestre. Ele tem a média final de cada aluno em quatro disciplinas. Para cada disciplina uma prova será aplicada e cada aluno será submetido a apenas uma delas. Sendo assim o coordenador pertente distribuir as provas de forma que alcance maior chance possível dos alunos obterem o melhor desempenho geral.
Nesse caso foi utilizado o Método Hungaro de Designação: Primeiro cobrindo os zeros da tabela com o menor números de linhas possíveis. Segundo Encontrando o menor valor dentre os números não cobertos, de todos os elementos.
Exemplo 2:
Para usinar um item, que passa por três máquinas de uma oficina, três funcionários foram treinados em cada uma delas, porém, descobriu-se que o tempo gasto por cada um deles é diferente em todas as máquinas. Deseja-se a atribuição Funcionário/Máquina que alcançará maior produtividade.
Nesse caso como temos o equilíbrio, desta forma foi fácil a resolução realizando a Redução de Linhas, Redução de Colunas e identificado a designação viável.
10) Construa e coloque em gráfico um problema primal de sua escolha com duas variáveis de decisão e duas restrições funcionais que tenham soluções viáveis, após construa o problema dual e demonstre graficamente se ele também apresenta soluções viáveis ou não.
Max. Z= 2x1 + 3x2
Sujeito a:
4x1 + 6x2≤60
x1+x2≥12
x1≥0, x2≥0
4x1 + 6x2≤60
A (0,10)
B (15,0)
x1+x2≥12
C (0,12)
D (12,0)
Problema Dual:
Min. Z= 60y1 + 12y2
Sujeito a:
4y1+y2≥2
6y1+y2≤3
y1≥0, y2≥0
oleObject2.bin
image3.emf
Milho X1Arroz X2Total (z)
Objetivo 5211,7
X1X2Resultado Limite
Hectares Total 347<=7
Pessoas 122,3<=9
Limite Milho -11-2,3<=3
Limite Arroz 010<=4
X1X2Z
Dados Calculados 2,302,3
Função objetivo - a ser maximizada pelo solver
valores ótimos encontrados pelo solver
Tabela cintendo as restrições do problema
image4.png
image5.png
image6.png
image7.emf
oleObject3.bin
image1.emf
oleObject1.bin
image2.emf