Questões - Pesquisa Operacional 2 2022 2

4. Sobre o problema do Caixeiro Viajante, considere um exemplo de um veículo de coleta de materiais recicláveis. Suponha que exista uma determinada quantidade de material disponível em cada cidade (d_i) e que o veículo tem um limite de capacidade de transporte (G). Considere que a distância entre cada cidade representa um custo proporcional de transporte (c_{ij}) e que existe um valor do material a ser coletado em cada cidade (p_i). O objetivo do veículo é coletar os materiais nas cidades que resultem em um maior valor final, descontando os custos de transporte. Observe que nesse caso não é necessário visitar todas as cidades. Escolha uma das formulações apresentadas para o problema do caixeiro viajante e reformule o modelo para adaptar as condições para aplicação no exemplo acima. 5. Considere as seguintes equações como possível função objetivo para o problema de p-mediana, onde os índices i e j correspondem aos clientes e locais candidatos, respectivamente; ‘w’ é a demanda por cliente; ‘d’ a distância entre os nós; e ‘x’ a variável de decisão. Escreva qual a diferença entre elas, comparando os possíveis resultados ao se usar cada uma. \text{minimizar } z = \sum_{i \in I}\sum_{j \in M}w_id_{ij}x_{ij} \quad (1) \text{minimizar } z = \sum_{i \in I}\sum_{j \in M}d_{ij}x_{ij} \quad (2) UNIVERSIDADE FEDERAL DE SÃO CARLOS Campus Sorocaba Rod. João Leme dos Santos (SP-264), Km 110 Bairro Itinga CEP 18052-780 – Sorocaba SP Fone: (55) 15 3229-7426 6. Uma empresa quer planejar a produção de quatro produtos: A, B, C D, para os próximos quatro meses. A tabela abaixo apresenta a demanda por produto em cada mês, a capacidade de produção mensal de cada produto, os custos de preparação e estocagem por unidade do produto. Demanda mensal (unidades) Produto jan fev mar abr Capacidade Custos de Custo de produção Preparação Estocagem ($) A 5000 6000 3000 10000 8000 12000 35 B 900 1000 4000 5000 5000 28000 39 C 6000 9000 4000 8000 8000 13800 45 D 10000 11000 14000 16000 15000 19500 85 Além da capacidade de produção por produto, como alguns recursos produtivos são compartilhados, existe um limite de capacidade global de 28000 unidades por mês. Em cada mês, o produto D só pode ser produzido se forem produzidos A ou B. Formule um modelo de programação inteira que represente o problema acima. 7. Considere uma empresa que fabrique 5 produtos. As informações sobre custos, demandas, tempos de produção e setup, capacidade e disponibilidade de horas extras estão disponíveis na tabela abaixo: Demanda Custo Tempo Tempo sem.1 sem.2 sem.3 sem.4 setup produção estocagem prod. 1 23 24 63 95 600 2,5 11 prod. 2 100 53 65 71 380 0,6 13 prod. 3 18 27 30 25 300 1,5 0,1 prod. 4 50 12 36 10 750 3 3 prod. 5 58 58 87 92 400 0,5 2 Capacidade (horas) 120 100 120 130 Hora extra disponível 30 30 40 40 Custo de hora extra 550 550 550 550 Formule um modelo de programação matemática para representar o problema de planejamento da produção envolvido. Lista de Exercícios Pesquisa Operacional Problema 1 Resposta As cidades são d_i com i = 1,…,m e assim as variáveis X_ij binária podem representar se escolhemos levar os materiais da cidade i para a cidade j. Assim a função custo é dada por C = \sum_{i=1}^{m}\sum_{j=1}^{m} c_{ij}X_{ij} Já o valor recolhido pelo transporte é dador por V = \sum_{i=1}^{m} v_i(\sum_{j =1, j \neq i}^{m}Y_{ij}) once Y_ij é a fração do material de valor v_i coletada. Assim a função objetivo é Z = V - C As restrições dão dadas por R1. As coletas da cidade i vão para apenas uma cidade fim: \sum_{j=1, j \neq i}^{m} X_{ij} = 1, i = 1,…,m R2. Já o limite de cada caminhão é dado por G e apenas uma fração do d_i encaixa nesta capacidade d_i Y_{ki} \leq G, i, k = 1,…,m Problema 2 Resposta Cada vez que escolhemos ir de i para j, x_ij = 1, assim acrescentamos um deslocamento igual a d_ij. Assim a equação (2) busca minimizar a distância percorrida cumpridas algumas restrições que não nos foram apresentadas. Por outro lado, w_i é a demanda por clientes na cidade i. Como queremos minimizar, supõe-se que seja a demanda de clientes que justifica transportar todos das cidades j’s para a cidade i, supõe-se que se a necessidade de demanda para compensar for menor, a possibilidade de sucesso na empreitada aumenta. Problema 3 Resposta Supomos que o estoque comece zerado, pois não há informações de que existam alguns prontos. Vamos denotar os meses por i ∈ {1, 2, 3, 4}. Temos o que é produzido no mês i dado por X_i e o que vai para estoque do mês i para o mês seguinte que representaremos por E_i. Para diferenciar entre os produtos, usamos X_i^A, X_i^B, X_i^C, X_i^D, i= 1, 2, 3, 4, E_i^A, E_i^B, E_i^C, E_i^D, i= 1, 2, 3. Note que não é necessário estocagem para o mês 4, pois supomos que não é interessante ter estoque para o mês sem demanda conhecida a seguir. P_i = 12000X_i^A + 28000X_i^B + 13800X_i^C + 19500X_i^D, i = 1, 2, 3, 4, C_i = 35E_i^A + 39E_i^B + 45E_i^C + 85E_i^D, i = 1, 2, 3. A função objetivo é dada por Z = \sum_{i=1}^{4} P_i + \sum_{j=1}^{3} G_j As restrições são: R1. As restrições de demanda: X_1^A \geq 5000, X_4^A + E_1^A \geq 6000, X_3^A + E_4^A \geq 10000, X_4^A + E_3^A = 10000 X_1^B \geq 900, X_2^B + E_1^B \geq 1000, X_3^B + E_2^B \geq 4000, X_4^B + E_3^B = 5000 X_1^C \geq 6000, X_2^C + E_1^C \geq 9000, X_3^C + E_2^C \geq 4000, X_4^C + E_3^C = 2000 X_1^D \geq 10000, X_2^D + E_1^D \geq 11000, X_3^D + E_2^D \geq 14000, X_4^D + E_3^D = 16000 R2. Limitação nas capacidades de produção: X_i^A \leq 8000, X_i^B \leq 5000, X_i^C \leq 8000, X_i^D \leq 15000 R3. Condição de estocagem: X_1^A - 5000 = E_1^A, X_2^A + E_1^A - 6000 = E_2^A, X_3^A + E_2^A - 3000 = E_3^A, X_4^A + E_1^A - 6000 = 0, X_1^B - 900 = E_1^B, X_2^B + E_1^B - 1000 = E_2^B, X_3^B + E_2^B - 4000 = E_3^B, X_4^B + E_1^B - 5000 = 0, X_1^C - 6000 = E_1^C, X_2^C + E_1^C - 9000 = E_2^C, X_3^C + E_2^C - 4000 = E_3^C, X_4^C + E_1^C - 2000 = 0, X_1^D - 10000 = E_1^D, X_2^D + E_1^D - 11000 = E_2^D, X_3^D + E_2^D - 14000 = E_3^D, X_4^D + E_1^D - 16000 = 0, Lembrando que as variáveis são inteiras positivas.