Avaliação 1 - 2023-1

Questão 1. (V) Verdadeiro (F) Falso (1,5 pts) ( F ) Se x1 e x2 são variáveis binárias, então x1 + x2  1 é equivalente à restrição “Se x1 = 1, então x2 = 1” ( F ) Se Y é uma variável binária, então (5 - MY)  (X1 + X2)  (10 + M(1 - Y)) é equivalente à restrição “ Se Y=1, então X1 + X2  10; se não, 10X1 + X2  5.” (M é um número real positivo muito grande – big-M) ( F ) Um problema de localização P-medianas é a escolha de uma localização que minimize a distância até o “cliente” mais distante. ( F ) O valor ótimo da função objetivo para o problema de P-medianas em uma rede é maior que o valor ótimo da função objetivo para o problema de P-centros nesta mesma rede. ( V ) Se x1, x2 e x3 são variáveis binárias, então x1  x2 + x3 é equivalente à restrição “Se x1, então x2 ou x3” Questão 2 - Uma empresa recebe um pedido de quatro produtos, que devem ser fabricados durante as próximas duas semanas, para entrega no final da segunda semana. Devido as configurações/setup, no máximo três produtos podem ser fabricados durante uma semana. A capacidade de produção é de 400 unidades por semana. Durante qualquer semana em que um produto é fabricado, há um custo de configuração/setup e um tamanho mínimo de lote. Além disso, os produtos A e B não podem ser fabricados durante a mesma semana, enquanto o produto D não pode ser fabricado na semana anterior à fabricação do produto C. Os dados relevantes são: Produto Custo de Setup Produção Tamanho Estoque Quantidade Semana 1 Semana 2 Custo/unidade mínimo do lote Custo/unidade necessária A 100 80 1 50 1 100 B 90 100 2 50 2 200 C 50 75 1 25 1 100 D 100 120 2 50 1 300 Formule um modelo de pli para encontrar o plano de produção de menor custo para atender a esse pedido. Quantas inteiras são necessárias? Quantas variáveis contínuas são necessárias? (3,0 pts) Sij: Custo de setup do produto i na semana j; Ci: Custo unitário de produção do produto i; i  {A,B,C,D} e j  {1,2} Variáveis: Yij ϵ {0,1}; (Se Yij = 1 então o produto i será produzido na semana j) Xij ϵ Z+; (Quantidade do produto i a produzir na semana j) Função Objetivo e restrições: Min Z = s.a (big-M) Xij  Z+ Yij  {0,1}, i  {A,B,C,D} e j  {1,2} Questão 3 - Considere a rede de cinco cidades abaixo, onde os números entre parênteses representam as demandas totais de um produto nessas cidades e os números nos arcos de conexão representam as distâncias. Observe que não há conexões diretas entre algumas cidades. B C E D A 6 3 4 7 8 5 5 (3) (1) (4) (1) (2) a. Defina o que é o problema da p-mediana numa rede. Como a p-mediana difere de um problema p-centro de uma rede? (0,5 pts) Um problema de p-mediana busca designar clientes a p facilidades minimizando a SOMA TOTAL DAS DISTÂNCIAS, enquanto que um problema de P-centros busca minimiza a MAIOR DISTÂNCIA. b. Dê uma interpretação para 1-mediana da rede. (0,5 pts) Decidir a localização de uma única facildiade que minimize a soma das distâncias até todos os clientes. c. Deseja-se construir 2 quartéis de bombeiros em duas cidades diferentes (1 quartel em cada cidade). Em quais das cinco cidades devem ser construídos os quartéis de modo a minimizar a maior distância de qualquer quartel às cidades que irá atender. Apenas formule o pli. (Desconsidere as demandas indicadas na rede.) (1,5 pts) Variável: r  0 – (r é maior distância possível das cidades aos quartéis de bombeiros) Min Z = r s.a , para todo j , distância de i até todo j (Yi = 1 se a cidade i vai receber a construção do quartel) (Xij = 1 se o quartel i for designada á cidade j) i,j  {A,B,C,D,E} Questão 4 - Uma "mochila" deve ser preenchida para maximizar o valor do conteúdo, sujeito a uma restrição de peso: Item Valor($) Peso(kg) Volume(cm3) 1 10 6 30 2 8 5 20 3 6 3 20 4 3 2 10 5 2 1 20 No máximo uma unidade de um item deve ser incluída. O peso total da mochila não pode exceder 14 kg. a. Formule esse problema como um problema de programação inteira. (0,5 pts) Ci = Valor do item i; Pi = Peso do item i; Vi = Volume do item i, i  {1,2,3,4,5} Variáveis: Yi ϵ {0,1}; (Se Yi = 0 então o item i NÃO será incluído; Se Yi = 1 então o item i será incluído na mochila) Max Z = s.a b. Em seguida, uma restrição de volume também é imposta: o volume total da mochila não pode exceder 60 cm3. Qual restrição deve ser adicionada ao PLI do item a.? (0,5 pts) c. Se colocar item 1 então o item 2 deve estar porém o item 4 não. Qual(is) restrição(ões) adicionar? (0,5 pts) Y1  Y2 Y1 + Y4 1 ou Y1  Y2 Y1 + Y2 + Y4 2 Questão 5 - A seção de I&D de uma empresa desenvolveu 4 possíveis novas linhas de produtos. A direção da empresa deve agora pronunciar-se sobre quais dos produtos fabricar e em que quantidades, com base num modelo matemático para determinar a combinação mais lucrativa de produtos. A criação de uma nova linha de produção tem um elevado custo inicial, de acordo com a seguinte tabela, em que a terceira linha mostra a receita unitária de cada produto: Produto  1 2 3 4 Custo inicial (x106) 50 40 70 60 Lucro unitário 70 60 90 80 O único recurso que limita a produção é a disponibilidade de horas máquina (6000 horas), e deve-se escolher uma das máquinas para utilizar, ou máquina A ou máquina B. As horas máquina requeridas em cada uma são as seguintes: Produto  1 2 3 4 Horas na máquina A 5 3 6 4 Horas na máquina B 4 4 3 5 A direção impôs também as seguintes restrições relativas aos níveis de produção de cada produto: i. No máximo 2 novos produtos podem ser fabricados. ii. O produto 3 pode ser produzido apenas se os produtos 1 ou 2 o forem. Formule um único programa linear inteiro misto que ajuda a decidir: a) quais e quanto de cada produto fabricar e; b) qual máquina utilizar (A ou B). (2,5 pts) Variáveis: Yi ϵ {0,1} (Se Yi=1 então produz o produto i) i ϵ {1,2,3,4} Xi ϵ Z+ (Quanto produzir do produto i) W ϵ {0,1} (Se W=1 então ativa a restrição 5x1 + 3x2 + 6x3 + 4x4 6000, senão ativa 4x1 + 4x2 + 3x3 + 5x4 6000) Função Objetivo: Max Z = (7*X1 + 6*X2 + 9*X3 + 8*X4 )– (5000000*Y1 + 40000000*Y2 + 70.000*Y3 + 60000000*Y4) s.a Xi M*Yi Y1 + Y2  Y3 5X1 + 3X2 + 6X3 + 4X + M*W (big-M) 4X1 + 6X2 + 3X3 + 5X + M*(1-W) (big-M) Yi, W ϵ {0,1} Xi ϵ Z+ i ϵ {1,2,3,4}