Problemas de Otimização Linear e Programação Matemática - Alocação de Recursos e Maximização de Utilidade

1Um estudante utiliza em seus estudos dez livros e dois cadernos A mochila utilizada por ele não comporta todos os itens Então ele decide atribuir a cada um dos itens um valor de 1 a 10 para representar a o grau de utilidade do item formando o seguinte quadro Item 1 2 3 4 5 6 7 8 9 10 11 12 Peso kg 09 12 10 08 12 11 09 10 13 14 08 10 Utilidade 8 7 6 9 10 1 7 3 2 2 8 4 Volume litros 10 14 10 10 13 13 11 09 15 15 10 11 O quadro também traz o peso kg e volume litros de cada item As restrições de peso e volume para a mochila são 10 kg e 12 litros respectivamente Determine quais itens devem ser levados na mochila de forma que a utilidade seja maximizada Resp utilidade máxima 63 2Oito tipos diferentes de máquinas devem ser carregadas em dois caminhões do tipo furgão O quadro a seguir traz o peso o volume e retorno financeiro para cada tipo de máquina Máquina Tipo 1 Tipo 2 Tipo 3 Tipo 4 Tipo 5 Tipo 6 Tipo 7 Tipo 8 Peso toneladas 45 44 38 42 39 48 39 46 Volume m3 108 105 112 107 109 118 109 126 Retorno 1000 R 15 16 14 17 155 165 159 172 As restrições de peso e volume para o caminhão 1 são 14 toneladas e 40 m3 respectivamente Enquanto o caminhão 2 pode levar 12 toneladas e volume não superior a 35m3 Determine quais máquinas devem ser carregadas e em quais caminhões para que o retorno financeiro seja maximizado Resp Retorno máximo 9810 1Uma empresa após um processo de racionalização de produção ficou com disponibilidade de 3 recursos produtivos R1 R2 e R3 Um estudo sobre o uso desses recursos indicou a possibilidade de se fabricar 2 produtos P1 e P2 Levantando os custos e consultado o departamento de vendas sobre o preço de colocação no mercado verificouse que P1 daria um lucro de 12000 por unidade e P2 15000 por unidade O departamento de produção forneceu a seguinte tabela de uso dos recursos Produtos Recurso R1un Recurso R2un Recurso R3un P1 2 3 5 P2 4 2 3 Disponibilidade de recursos por mês 100 90 120 Que produção mensal de P1 e P2 traz o maior lucro a empresa Monte a árvore das soluções Utilize um aplicativo computacional para resolver os problemas relaxados 2 A Arte Design produz 3 tipos de estantes que necessitam de tempos diferentes na linha de montagem Para cada tipo de estante seja fabricado um custo de preparação da fábrica é incorrido Suponha que todas as estantes do mesmo tipo serão produzidas de uma só vez Tipo 1 Tipo 2 Tipo 3 Total Disponível Montagem 2 horas 5 horas 35 horas 400 horas Pintura 3 horas 2 horas 15 hora 800 horas Lucro unitário R 4000 R 3000 R 2500 Custo de preparação R 500000 R 200000 R 500000 Determine quantas estantes devem ser produzidas para maximizar o resultado Monte o modelo linear Resolva o modelo usando o solver do Excel Resp resultado máx 3000 3 Oito tipos diferentes de máquinas devem ser carregados em dois caminhões do tipo furgão O quadro a seguir traz a quantidade disponível o peso o volume e retorno financeiro para cada tipo de máquina Máquina Tipo 1 Tipo 2 Tipo 3 Tipo 4 Tipo 5 Tipo 6 Tipo 7 Tipo 8 Peso toneladas 45 44 38 42 39 48 39 46 Volume m3 108 105 112 107 109 118 109 126 Retorno 1000 R 15 16 14 17 155 165 159 172 Quantidade 2 1 3 1 2 2 3 1 As restrições de peso e volume para o caminhão 1 são 24 toneladas e 55 m3 respectivamente Enquanto o caminhão 2 pode levar 18 toneladas e volume não superior a 40m3 Determine quais máquinas devem ser carregadas e em quais caminhões para que o retorno financeiro seja maximizado 1Para um bar que funciona 24 horas por dia a seguinte quantidade de empregados é necessária Hora do dia Nº mínimo de empregados 0206 4 0610 8 1014 10 1418 7 1822 5 2202 12 Chamando de xj o número de funcionários que iniciam na hora j para j par e considerando que eles trabalham 8 horas ininterruptas minimize o número de funcionários 2Para um bar que funciona 24 horas por dia a seguinte quantidade de empregados é necessária Hora do dia Nº mínimo de empregados 0206 4 0610 8 1014 10 1416 7 1618 5 1822 12 2200 10 0002 7 Chamando de xj o número de funcionários que iniciam na hora j para j par e considerando que eles trabalham 8 horas ininterruptas minimize o número de funcionários 1 Um navio com capacidade para 4 toneladas pode ser carregado com 1 2 ou 3 itens A tabela abaixo dá o peso Wt em toneladas e a receita Rt em milhares de dólares para o item t Como o navio deve ser carregado para maximizar a receita total Item t Wt Rt 1 2 31 2 3 47 3 1 14 Obs Há mais de uma unidade para cada um dos itens 2Uma empresa que administra um parque de diversões precisa alocar seus funcionários segundo os planos de jornadas de trabalho semanal Cada funcionário trabalha 5 dias seguidos e folga 2 Os 7 planos possíveis e as demandas diárias estão no quadro abaixo Os uns do quadro abaixo colunas dos dias da semana representam os dias de trabalho Construa um modelo que decida quantos funcionários devem trabalhar em cada plano satisfazendo a demanda e minimizando o número total de funcionários Domingo Segunda Terça Quarta Quinta Sexta Sábado 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 1 4 1 1 1 1 1 5 1 1 1 1 1 6 1 1 1 1 1 7 1 1 1 1 1 1 Demanda 18 12 12 14 16 16 18 Resp número mínimo de funcionários 22 3Uma companhia de propaganda deseja planejar uma campanha em 3 diferentes meios tv rádio e revistas O gerente deve decidir sobre a quantidade de veiculações nas várias mídias e horários Um estudo de mercado resultou nos dados da tabela a seguir sendo os valores válidos para cada veiculação da propaganda TV horário normal TV horário nobre Rádio Revistas Custo 40000 75000 30000 15000 Clientes atingidos 400000 900000 500000 200000 Mulheres atingidas 300000 400000 200000 100000 A companhia definiu as seguintes metas 1 Não quer gastar mais de 80000000 2 No mínimo 2 milhões de mulheres sejam atingidas 3 Gastar no máximo 50000000 com tv 4 No mínimo 3 veiculações ocorram no horário normal na tv 5 No mínimo 2 veiculações ocorram no horário nobre na tv Formular um modelo de PLI para o problema determinando o número de veiculações a serem feitas em cada meio de comunicação de modo a atingir o máximo possível de cliente RESP clientes atingidos 11700000 2 O prefeito de uma cidade deseja determinar onde instalar postos policiais para atender a diferentes regiões metropolitanas O custo de instalação de um posto varia de acordo com a localização Os custos e cada possível localização pode atender a uma série de regiões conforme evidenciado na tabela a seguir Local 1 2 3 4 5 6 7 8 9 10 Custo R 3000 5000 1000 2000 1000 4000 3000 1000 2000 2000 Região 1 X X X X X X Região 2 X X Região 3 X X X X Região 4 X X X Região 5 X X X X X X O prefeito exige que cada região da cidade seja atendida por pelo menos um posto Formule e resolva o PPLI que determine os locais em que os postos policiais devem ser construídos de forma a minimizar os custos e atender às condições exigidas 3Uma empresa do setor alimentício está planejando abrir novas fábricas considerando 5 possibilidades Manaus Fortaleza Vitória Barueri e Curitiba A partir das novas localidades os produtos serão entregues para 5 consumidores finais São Luís Brasília Belo Horizonte Rio de Janeiro e São Paulo Cada fábrica possui um custo fixo de manutenção e uma capacidade máxima conforme a tabela a seguir Além disso a tabela também possui os custos unitários de transporte manutenção e as demandas Determinar as fábricas fornecedoras e as quantidades transportadas das destas fábricas para os locais consumidores a fim de minimizar o custo total manutenção e logístico Custos unitários de transporte São Luís Brasília Belo Rio de São Paulo Custo Capacidade Horizonte de manutenção Manaus 082 095 110 133 122 111000 35000 Fortaleza 074 112 106 113 124 124000 30000 Vitória 134 124 072 072 088 120000 25000 Barueri 148 126 098 095 070 135000 30000 Curitiba 152 145 133 122 115 140000 20000 Demanda 16000 18000 12000 17000 20000 1O banco PRINCE está abrindo novas agências bancárias e para isso precisa contratar mão de obra adicional Entretanto a escala da força de trabalho que será contratada deve ser definida Buscase escalonar os novos funcionários em turnos de trabalho de forma a satisfazer o nível de serviço desejado com o menor custo possível Em cada turno os funcionários trabalham por um período de oito horas consecutivas sendo que o período correspondente a cada turno além do custo diário por funcionário é apresentado na Tabela 1 Porém para que o nível de serviço seja atendido é necessário um número mínimo de funcionários por período conforme mostra a Tabela 2 Formule o problema de programação inteira de forma a determinar a mão de obra a ser contratada por turno com o menor custo possível respeitando a restrição de número mínimo de funcionários por período Tabela 1 Turno Período Custo diário por funcionário 1 601 1400 100 2 801 1600 80 3 1001 1800 85 4 1401 2200 130 5 2201 600 150 Tabela 2 Período Número de funcionários necessários 601 800 22 801 1000 35 1001 1200 54 1201 1400 42 1401 1600 60 1601 1700 44 1701 1800 35 1801 2000 30 2001 2200 25 2201 600 18 Determine o custo mínimo que satisfaz as restrições do problema 2 Uma fábrica de papel produz bobinas de comprimento fixo e de largura igual a 170 cm As solicitações de compra são para bobinas de largura menor o que implica uma operação de corte da bobina para obter bobinas menores Os pedidos são para 100 bobinas de 55cm 200 bobinas de 50cm e 150 bobinas de 30cm Formule e resolva o modelo linear que determina o esquema de corte que minimiza as perdas 3 A cidade do Rio de Janeiro está estudando a realocação de diversos postos de saúde de maneira a atingir o maior número possível de bairros As possíveis localizações para os postos e o conjunto de bairros a que estes poderiam atender são mostrados na tabela a seguir Localização potencial dos postos Bairros cobertos Localização 1 157 Localização 2 1278 Localização 3 135 Localização 4 2458 Localização 5 346 Localização 6 456 Localização 7 1567 Dado que os terrenos são da prefeitura e que o custo de construção dos postos é constante determine as localizações em que a prefeitura deveria construir seus postos de maneira a minimizar os custos e atender a todos os 8 bairros 4O Governo decidiu instalar em uma certa região 4 indústrias U1U2U3 e U4 Quatro localidades diferentes L1L2L3 e L4 foram selecionadas As condições geoeconômicas variam de local para local As indústrias também possuem características técnicas distintas Um estudo preliminar levou a conclusão que as eficiências relativas das diversas indústrias nas diferentes localidades são L1 L2 L3 L4 U1 15 1 2 1 U2 08 06 25 05 U3 2 07 1 2 U4 1 05 1 2 Desejase instalar uma única indústria em cada uma das 4 localidades de maneira mais eficiente Escreva o modelo linear e resolvao 1 As soluções para diversos programas lineares contidas no quadro a seguir foram obtidas durante o processo de resolução do seguinte PPLI Problema 1 Min C 5x1 2x2 3x3 sa 3x1 2x2 4x3 8 3x1 4x2 2x3 6 x1 x2 x3 0 e inteiras Construa a partir do quadro um diagrama em árvore resumindo a solução do problema Indique a solução ótima Quadro 1 Problema Última Variável Ramificada x1 x2 x3 C 1 nenhuma 209 0 13 1099 2 x1 2 13 23 383 3 x1 3 0 0 15 4 x2 inviável 5 x2 149 1 43 1249 6 x1 1 116 136 916 7 x1 2 1 1 15 2O Governo decidiu instalar em uma certa região 4 indústrias U1U2U3 e U4 Quatro localidades diferentes L1L2L3 e L4 foram selecionadas As condições geoeconômicas variam de local para local As indústrias também possuem características técnicas distintas Um estudo preliminar levou a conclusão que as eficiências relativas das diversas indústrias nas diferentes localidades são L1 L2 L3 L4 U1 15 1 2 1 U2 08 06 25 05 U3 2 07 1 2 U4 1 05 1 2 Desejase instalar uma única indústria em cada uma das 4 localidades de maneira mais eficiente Escreva o modelo linear e resolvao Resp Eficiência máxima 75