Lista de Exercicios Pesquisa Operacional UFABC - Modelo Matematico e Solver

Universidade Federal do ABC ESTG01317 Pesquisa Operacional Prof Eder Oliveira Abensur 2º Quad 2023 LISTA DE EXERCÍCIOS Modelo Matemático Manuscrito Planilha eletrônica com os resultados do Solver anexos Os problemas de PL devem apresentar manuscrito i a pergunta ii a definição das variáveis objetivo e restrições Incluir documento com foto 1 Três refinarias 1 2 3 enviam um produto à base de gasolina a dois terminais de distribuição 7 8 por meio de uma rede de tubulações Qualquer demanda que não puder ser satisfeita pela rede é adquirida de outras fontes A rede de tubulações é atendida por três estações de bombeamento 4 5 6 como apresentado na figura abaixo O produto flui pela rede na direção mostrada pelas setas A capacidade de cada ramo é dada em milhões de barris por dia Determinar o fluxo máximo diário de combustível que pode ser enviada aos terminais 2 Uma empresa fabricante de sapatos previu as seguintes demandas em unidades para os próximos 6 meses mês 1 200 mês 2 260 mês 3 240 mês 4 340 mês 5 190 mês 6 150 Custa R7 para produzir um par de sapatos no turno de trabalho regular e R11 fora do turno regular Em cada mês a capacidade de produção trabalhandose apenas no turno regular é de 200 pares de sapato e trabalhandose fora do turno regular a empresa consegue fabricar mais 100 pares de sapato Sabendose que o custo mensal para estocar um par de sapatos é R1 e a capacidade mensal máxima de armazenamento é de 200 pares determine a o programa de produção que minimiza o custo total de produção atendendo a demanda dos 6 meses 3 Entre muitas medidas de risco disponíveis para a alocação de investimentos há uma denominada de desvio médio absoluto A intenção desta e das demais medidas de risco é auxiliar na formação de portfólios de investimentos Para os propósitos deste exercício uma maneira de expressar esta medida de risco é mostrada a seguir 1 1 n T jt j j j t r r DA x T Onde jt j r r é o desvio do rendimento do título j no momento t face ao rendimento médio do título j durante o período 𝑡 com 𝑡 1 T Os preços de fechamento diários de 20 ações n durante 21 pregões são apresentados a seguir Com base nestes dados e assumindose uma meta de rentabilidade de 050 desenvolver um modelo matemático de PL que determine a melhor alocação que um investidor com aversão ao risco pode fazer para um capital inicial de R 1000000 expressar os resultados em R por ação e desprezar outros custos de transação da seguinte forma Universidade Federal do ABC ESTG01317 Pesquisa Operacional Prof Eder Oliveira Abensur 2º Quad 2023 a Assumir rj como a média b Assumir rj como a mediana A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 1 272 23 204 1015 623 3163 418 495 2279 4 2 276 239 097 1001 635 3102 413 50 2182 4 3 276 231 076 1015 64 315 415 4939 2211 4 4 277 231 1 1049 629 32 397 498 2198 4 5 28 223 05 1023 631 3259 388 497 2188 399 6 275 222 014 1054 644 3308 378 4917 2119 35 7 284 198 025 1071 663 3336 37 4726 2085 3 8 281 171 052 1112 669 3336 377 4475 202 398 9 27 168 053 1092 671 3339 365 4547 209 35 10 273 165 049 1099 645 332 368 4614 2105 399 11 272 156 067 111 66 333 368 4581 2054 394 12 267 146 065 1122 668 3399 37 4489 2055 385 13 27 155 067 1091 669 3302 357 4456 206 37 14 26 135 062 11 693 325 352 45 2101 37 15 261 14 042 1104 71 3178 351 4501 2092 35 16 261 125 036 11 717 3198 355 4392 2095 36 17 269 126 029 108 709 325 355 413 2092 378 18 269 136 048 108 746 33 367 4146 2085 398 19 273 161 051 108 73 33 367 432 2066 4 20 278 154 046 1076 72 337 371 4425 2087 479 21 278 151 054 1075 708 3299 361 4449 2046 49 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 1 19 1166 172 1397 857 1554 6644 1435 246 256 2 19 114 17 1298 846 1567 6925 1414 2425 253 3 1899 1149 168 1298 825 156 6696 1411 244 2475 4 1894 1165 169 131 801 1635 6512 1392 243 253 5 1897 1165 174 131 783 1677 6378 1371 2465 251 6 199 1162 215 1252 735 1646 634 1344 2459 2515 7 2095 1122 193 125 74 1665 6205 1335 2438 2509 8 2188 1135 197 1335 743 17 6239 1353 2481 2532 9 2185 1143 197 1324 749 172 625 1368 25 256 10 2173 1151 205 1321 727 1718 6101 1346 2525 2537 11 2199 1155 205 1329 73 1735 6306 1349 259 2542 12 2195 1163 207 1329 723 1751 63 136 2579 2627 13 2284 1174 217 123 705 1737 6315 1341 261 2674 14 229 1178 205 1152 69 17 638 131 259 2635 15 2285 1103 203 1151 716 1694 6397 1329 2568 2741 16 2289 1154 201 1149 712 1705 643 1355 2569 2781 17 2315 1165 197 1149 7 1717 645 1335 2532 2753 18 223 116 19 1378 7 1688 6123 1306 2534 2645 19 2213 1177 194 1486 725 1709 625 1311 2566 2695 20 2212 1176 187 125 696 1698 613 1297 2641 2611 21 2168 116 18 125 709 1663 6011 1308 2631 2596 Universidade Federal do ABC ESTG01317 Pesquisa Operacional Prof Eder Oliveira Abensur 2º Quad 2023 4 Uma empresa testa uma nova tecnologia de câmeras de vigilância de 360 para monitorar as dependências de um andar com arquivos confidenciais O layout do andar é mostrado a seguir com as salas ligadas por portas abertas Uma câmera localizada em uma porta pode monitorar duas salas adjacentes A empresa quer que todas as salas sejam monitoradas com o menor número possível de câmeras Formule um modelo de PLI para esta situação e encontre a quantidade e a localização das câmeras 5 Uma empresa produz televisão em 3 fábricas São Paulo João Pessoa e Manaus Os pontos principais de revenda com as respectivas encomendas mensais são Rio de Janeiro 6000 unidades Salvador 5000 unidades Aracajú 2000 unidades Maceió 1000 unidades Recife 3000 unidades A produção máxima mensal em cada fábrica é São Paulo 10000 unidades João Pessoa 5000 unidades Manaus 6000 unidades O custo de transportes das fábricas até as revendas é dado pelo quadro abaixo R por 1000 unidades de TV Para De Rio de Janeiro 1 Salvador 2 Aracaju 3 Maceió 4 Recife 5 1 São Paulo 1000 2000 3000 3500 4000 2 João Pessoa 4000 2000 1500 1200 1000 3 Manaus 6000 4000 3500 3000 2000 Determinar a o número de unidades produzidas em cada fábrica e entregues a cada revenda a fim de minimizar o custo de transporte na forma tabular b o número de unidades produzidas em cada fábrica e entregues a cada revenda a fim de minimizar o custo de transporte na forma de rede Universidade Federal do ABC ESTG01317 Pesquisa Operacional Prof Eder Oliveira Abensur 2º Quad 2023 6 A central de computadores da universidade A é equipada com quatro computadores centrais de grande porte mainframes O número de usuários a qualquer instante é 25 Cada usuário pode apresentar um trabalho de um terminal a cada 15 minutos em média mas o tempo real entre apresentações é exponencial Trabalhos que chegam são dirigidos automaticamente ao primeiro computador disponível O tempo de execução por apresentação segue uma exponencial com média de 2 minutos Calcule o seguinte a A probabilidade de um trabalho ser executado imediatamente após a apresentação b O tempo médio até o resultado de um trabalho ser desenvolvido ao usuário c O número médio de trabalhos que esperam execução d A porcentagem de tempo em que a central de computadores inteira está ociosa e O número médio de computadores ociosos Questão 1 Queremos maximizar o fluxo que chega nos terminais 7 e 8 Para isso criaremos as seguintes variáveis 𝑋𝑖𝑗 Fluxo que passa pelo arco 𝑖 𝑗 Como queremos maximizar o fluxo que chega nos terminais 7 e 8 logo desejamos maximizar 𝑋47 𝑋67 𝑋68 𝑋58 Considere como a capacidade máxima do arco Naturalmente o fluxo que 𝑐𝑖𝑗 𝑖 𝑗 passa pelos arcos precisa ser menor que sua capacidade logo temos as seguintes restrições 𝑋𝑖𝑗 𝑐𝑖𝑗 𝑖 𝑗 𝐴𝐺 Além disso as estações de bombeamento 4 5 e 6 não produzem e nem consomem o fluxo logo o fluxo que entra é igual ao fluxo que sai Logo temos as seguintes restrições 𝑋14 𝑋24 𝑋45 𝑋46 𝑋47 0 𝑋25 𝑋35 𝑋45 𝑋56 𝑋58 0 𝑋26 𝑋46 𝑋56 𝑋67 𝑋68 0 Portanto temos o seguinte modelo max 𝑋47 𝑋67 𝑋68 𝑋58 sa 𝑋𝑖𝑗 𝑐𝑖𝑗 𝑖 𝑗 𝐴𝐺 𝑋14 𝑋24 𝑋45 𝑋46 𝑋47 0 𝑋25 𝑋35 𝑋45 𝑋56 𝑋58 0 𝑋26 𝑋46 𝑋56 𝑋67 𝑋68 0 𝑋𝑖𝑗 0 𝑖 𝑗 𝐴𝐺 Utilizando o Solver Excel obtemos que o fluxo máximo é de 110 milhões de barris Os valores das variáveis X estão descritas abaixo X 1 2 3 4 5 6 7 8 1 0 0 0 20 0 0 0 0 2 0 0 0 5 20 50 0 0 3 0 0 0 0 15 0 0 0 4 0 0 0 0 5 10 10 0 5 0 0 0 0 0 10 0 30 6 0 0 0 0 0 0 50 20 7 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 Questão 2 Queremos determinar um plano de produção ótimo para a empresa fabricante de sapato Considere as seguintes variáveis 𝑥𝑖 Quantidade produzida no turno regular no mês 𝑖 1 6 𝑦𝑖 Quantidade produzida fora do turno regular no mês 𝑖 1 6 𝑒𝑖 Quantidade estocada no mês 𝑖 1 6 Queremos minimizar o custo de produção ou seja minimizar 7 𝑖1 6 𝑥𝑖 11 𝑖1 6 𝑦𝑖 1 𝑖1 6 𝑒𝑖 Temos uma limitação no número de sapatos produzidos no turno regular e fora dele além da limitação de armazenamento 𝑥𝑖 200 𝑖 1 6 𝑦𝑖 100 𝑖 1 6 𝑒𝑖 200 𝑖 1 6 Considere a demanda do mês Além disso precisamos atender a 𝑑𝑖 𝑖 1 6 demanda logo temos as seguintes restrições 𝑥1 𝑦1 𝑒1 𝑑1 𝑥𝑖 𝑦𝑖 𝑒𝑖1 𝑒𝑖 𝑑𝑖 𝑖 2 6 Portanto temos o seguinte modelo min 7 𝑖1 6 𝑥𝑖 11 𝑖1 6 𝑦𝑖 1 𝑖1 6 𝑒𝑖 sa 𝑥𝑖 200 𝑖 1 6 𝑦𝑖 100 𝑖 1 6 𝑒𝑖 200 𝑖 1 6 𝑥1 𝑦1 𝑒1 𝑑1 𝑥𝑖 𝑦𝑖 𝑒𝑖1 𝑒𝑖 𝑑𝑖 𝑖 2 6 𝑥𝑖 0 𝑖 1 6 𝑦𝑖 0 𝑖 1 6 𝑒𝑖 0 𝑖 1 6 Utilizando o solver excel temos que o custo mínimo total é de R 1066000 Abaixo é apresentado os valores das variáveis do modelo x 1 2 3 4 5 6 200 200 200 200 190 150 y 1 2 3 4 5 6 0 60 80 100 0 0 e 1 2 3 4 5 6 0 0 40 0 0 0 Questão 3 Questão 4 Desejamos instalar o menor quantidade de câmeras de forma a vigiar todas as salas Considere as seguintes variáveis 𝑥𝑖 Se a câmera foi ou não instalada no local 𝑖 1 9 Os locais de instalação estão ilustrados abaixo Desejamos minimizar o número de câmeras instaladas ou seja queremos minimizar Precisamos satisfazer que toda sala é vigiada por pelo menos uma 𝑖1 9 𝑥𝑖 câmera logo temos as seguintes restrições 𝑥1 𝑥2 1 𝑥2 𝑥3 1 𝑥3 𝑥4 1 𝑥1 𝑥5 1 𝑥4 𝑥5 𝑥6 𝑥7 1 𝑥7 𝑥9 1 𝑥8 𝑥9 1 𝑥8 1 Portanto temos o seguinte modelo min 𝑖1 9 𝑥𝑖 sa 𝑥1 𝑥2 1 𝑥2 𝑥3 1 𝑥1 𝑥5 1 𝑥4 𝑥5 𝑥6 𝑥7 1 𝑥7 𝑥9 1 𝑥8 𝑥9 1 𝑥8 1 𝑥𝑖 0 1 𝑖 1 9 Utilizando o solver Excel é possível determinar que com apenas 4 câmeras é possível cobrir todas as salas instalando as mesmas nos locais 1 3 7 e 8 Questão 5 Inicialmente considere que 1 São Paulo 2 João Pessoa 3 Manaus 1 Rio de Janeiro 2 Salvador 3 Aracaju 4 Maceió 5 Recife Considere as seguintes variáveis Quantidade de 1000 unidades produzida da fábrica para a revenda 𝑋𝑖𝑗 𝑖 1 2 3 𝑗 1 5 Considere também as seguintes constantes Custo de transporte de 1000 unidades produzida da fábrica para a 𝑐𝑖𝑗 𝑖 1 2 3 revenda 𝑗 1 5 Desejamos minimizar o custo total de transporte logo temos que minimizar 𝑖1 3 𝑗1 5 𝑐𝑖𝑗 𝑋𝑖𝑗 Considere as seguintes constantes 𝑂𝑖 Produção máxima da fábrica 𝑖 1 2 3 𝐷𝑗 Demanda da revenda 𝑗 1 9 Temos que atender toda a demanda respeitando a produção máxima de cada fábrica Temos então as seguintes restrições 𝑖1 3 𝑥𝑖𝑗 𝐷𝑗 𝑗 1 9 𝑗1 9 𝑥𝑖𝑗 𝑂𝑖 𝑖 1 2 3 Portanto temos o seguinte modelo min 𝑖1 3 𝑗1 5 𝑐𝑖𝑗 𝑋𝑖𝑗 sa 𝑖1 3 𝑥𝑖𝑗 𝐷𝑗 𝑗 1 5 𝑗1 9 𝑥𝑖𝑗 𝑂𝑖 𝑖 1 2 3 𝑋𝑖𝑗 0 𝑖 1 2 3 𝑗 1 5 Utilizando o solver Excel obtemos que o menor custo total é de R 2520000 O resultado da alocação de transporte é dada na tabela abaixo X 1 2 3 4 5 1 6 4 0 0 0 2 0 1 2 1 1 3 0 0 0 0 2 Questão 6 e λ 5 3 µ 1 2 a 𝑃 1 µ λ 1 1 2 5 3 1 1 2 3 5 1 3 10 0 7 b Tempo médio de espera 1 λµ 1 5 3 1 2 1 102 6 1 8 6 6 8 3 4 c Número médio de trabalhos na fila µ λµ 1 2 3 4 1 2 4 3 4 6 2 3 d Utilização do sistema µ λ 0 3 e Número médio de computadores ociosos λ µ 10 3 3 333 Questão 1 Queremos maximizar o fluxo que chega nos terminais 7 e 8 Para isso criaremos as seguintes variáveis Xij Fluxo que passa pelo arco i j Como queremos maximizar o fluxo que chega nos terminais 7 e 8 logo desejamos maximizar X 47 X67X68X58 Considere cij como a capacidade máxima do arco i j Naturalmente o fluxo que passa pelos arcos precisa ser menor que sua capacidade logo temos as seguintes restrições Xij cij i j AG Além disso as estações de bombeamento 4 5 e 6 não produzem e nem consomem o fluxo logo o fluxo que entra é igual ao fluxo que sai Logo temos as seguintes restrições X14 X24X 45X 46X470 X25X 35 X45X56X580 X26 X46X56X67X680 Portanto temos o seguinte modelo max X 47 X67X68X58 sa Xij cij i j AG X14 X24X 45X 46X470 X25X 35 X45X56X580 X26 X46X56X67X680 Xij 0 i j AG Utilizando o Solver Excel obtemos que o fluxo máximo é de 110 milhões de barris Os valores das variáveis X estão descritas abaixo X 1 2 3 4 5 6 7 8 1 0 0 0 20 0 0 0 0 2 0 0 0 5 20 50 0 0 3 0 0 0 0 15 0 0 0 4 0 0 0 0 5 10 10 0 5 0 0 0 0 0 10 0 30 6 0 0 0 0 0 0 50 20 7 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 Questão 2 Queremos determinar um plano de produção ótimo para a empresa fabricante de sapato Considere as seguintes variáveis xi Quantidade produzida no turno regular no mês i16 yi Quantidade produzida fora do turno regular no mês i16 ei Quantidade estocada no mês i16 Queremos minimizar o custo de produção ou seja minimizar 7 i1 6 xi11 i1 6 yi1 i1 6 ei Temos uma limitação no número de sapatos produzidos no turno regular e fora dele além da limitação de armazenamento xi200 i16 yi100 i16 ei200i16 Considere di a demanda do mês i16 Além disso precisamos atender a demanda logo temos as seguintes restrições x1 y1e1d1 xi yiei1eidi i26 Portanto temos o seguinte modelo min 7 i1 6 xi11 i1 6 yi1 i1 6 ei sa xi200 i16 yi100 i16 ei200i16 x1 y1e1d1 xi yiei1eidi i26 xi0 i16 yi0 i16 ei0 i16 Utilizando o solver excel temos que o custo mínimo total é de R 1066000 Abaixo é apresentado os valores das variáveis do modelo x 1 2 3 4 5 6 200 200 200 200 190 150 y 1 2 3 4 5 6 0 60 80 100 0 0 e 1 2 3 4 5 6 0 0 40 0 0 0 Questão 3 Questão 4 Desejamos instalar o menor quantidade de câmeras de forma a vigiar todas as salas Considere as seguintes variáveis xi Se a câmera foi ou não instalada no local i19 Os locais de instalação estão ilustrados abaixo Desejamos minimizar o número de câmeras instaladas ou seja queremos minimizar i1 9 xi Precisamos satisfazer que toda sala é vigiada por pelo menos uma câmera logo temos as seguintes restrições x1 x21 x2 x31 x3x41 x1 x51 x4x5x6 x71 x7x91 x8x91 x81 Portanto temos o seguinte modelo min i1 9 xi sa x1 x21 x2 x31 x1 x51 x4x5x6 x71 x7x91 x8x91 x81 xi01 i19 Utilizando o solver Excel é possível determinar que com apenas 4 câmeras é possível cobrir todas as salas instalando as mesmas nos locais 1 3 7 e 8 Questão 5 Inicialmente considere que 1 São Paulo 2 João Pessoa 3 Manaus 1 Rio de Janeiro 2 Salvador 3 Aracaju 4 Maceió 5 Recife Considere as seguintes variáveis Xij Quantidade de 1000 unidades produzida da fábrica i123 para a revenda j 15 Considere também as seguintes constantes cij Custo de transporte de 1000 unidades produzida da fábrica i123 para a revenda j 15 Desejamos minimizar o custo total de transporte logo temos que minimizar i1 3 j1 5 cij Xij Considere as seguintes constantes Oi Produção máxima da fábrica i123 D j Demanda da revenda j 19 Temos que atender toda a demanda respeitando a produção máxima de cada fábrica Temos então as seguintes restrições i1 3 xij D j j 19 j1 9 xijOi i123 Portanto temos o seguinte modelo min i1 3 j1 5 cij Xij sa i1 3 xij D j j 15 j1 9 xijOi i123 Xij 0 i123 j 15 Utilizando o solver Excel obtemos que o menor custo total é de R 2520000 O resultado da alocação de transporte é dada na tabela abaixo X 1 2 3 4 5 1 6 4 0 0 0 2 0 1 2 1 1 3 0 0 0 0 2 Questão 6 λ5 3 e μ1 2 a P1μ λ1 1 2 5 3 11 2 3 51 3 1007 b Tempo médio de espera 1 λμ 1 5 31 2 1 102 6 1 8 6 6 8 3 4 c Número médio de trabalhos na fila μ λμ 1 2 3 4 1 2 4 3 4 62 3 d Utilização do sistema μ λ 03 e Número médio de computadores ociosos λ μ 10 3 3333