·
Marketing e Comunicação ·
Outros
Send your question to AI and receive an answer instantly
Preview text
Pesquisa Operacional Graduação em Administração Prof Ludwig Miguel FGV Ebape Atividades 24mar Exercício 03 Lista 10mar23 2 Programação Linear 4 Mix de produção Produção multiperiodo Escala de funcionários Combinação de insumos Modelo de investimento aplicações da PL Programação Linear Inteira PL e PI Quando falamos de Programação Linear ex mix de produção produção multiperiodo etc ALOCACAO DE RECURSOS Quando falamos de Programação Inteira ex onde localizar novas instalações para atender a demanda etc SELECAO ou ATRIBUICAO 6 Optimização com variáveis inteiras Exemplos Setup costs custos fixos Localização de instalações ex centros de distribuição hospitais etc Programação de maquinário ex como alocar a maquina para diferentes trabalhos dependendo da capacidade e rapidez da maquina Rotas de veículos em entrega Basicamente este tipo de problemas trata de SELECAO ou ATRIBUICAO estabelecer o que uma pessoamaquina deve fazerselecionar 7 Optimização com variáveis inteiras Problemas de PI são aqueles de programação matemática em que uma ou variáveis de decisão são representadas apenas por valores inteiros Em LP tudo é fraccionado contínuo em IP alguns valores são discretos Programação inteira total todas as variáveis de decisão são do tipo inteiro Programação inteira mista apenas uma parte das variáveis é do tipo inteiro enquanto as outras são do tipo real Nosso escopo em PI falaremos de Programação Linear Inteira 8 Alguns exemplos de PI 9 Escala de pessoal Determinar a quantidade de staff em cada um das suas localidades Mais de 6500 restaurantes nos EUA Quantos funcionários devem estar em cada restaurante por turno Equipes muito pequenas por restaurante arredondamentos pode ser muito impreciso Taco Bell desenvolveu um PI ie um PL com variáveis inteiras para resolver o problema de alocação da força de trabalho 13 milhões de economia por ano Fonte Jackie Hueter William Swart 1998 An Integrated LaborManagement System for Taco Bell Interfaces 2817591 httpsdoiorg101287inte28175 Alguns exemplos de PI 10 Seleção da melhor rota A WM Waste Management opera uma rede de reciclagem com 293 aterros 16 plantas de energia a partir de resíduos 72 instalações de energia a partir de gás 146 plantas de reciclagem 346 estacoes de transferência e 435 pontos de coleta Seus veículos precisam percorrer 2000 rotas diariamente Como determinar a melhor rota Uso de variáveis binárias PI de grande porte economizando 498 milhões em custos operacionais em um período de 5 anos Fonte Sahoo S Kim S Kim BI Kraas B Popov A 2005 Routing Optimization for Waste Management Interfaces 351 2436 httpwwwjstororgstable27651734 Formulação de PI Usando o problema clássico da mochila de trilha Quatro itens para selecionar Capacidade da mochila de 10 kg Precisamos maximizar o valor total sem ultrapassar a capacidade da mochila A formulação completa é max 16𝑥 22𝑥 12𝑥 8𝑥 sa 5𝑥 7𝑥 4𝑥 3𝑥 10 𝑥 01 1 4 11 Programa inteiro ou programa binário variáveis binárias da PI nos permitem Implementar regras de seleção de variáveis Regra do tipo pelo menosno máximo alguns itens Supondo que seja obrigatório selecionar pelo menos um dos itens 23 ou 4 pode ser um dois ou os três itens 𝑥 𝑥 𝑥 1 Supondo que seja obrigatório selecionar no máximo dois itens entre o 1 3 e 4 pode ser um dois o nenhum 𝑥 𝑥 𝑥 2 12 O uso de variáveis binárias da PI nos permite Incluir condicional OU na seleção de variáveis Selecionar OU o item 2 OU item 3 Foco na situação item 2 selecionado o que acontece com item 3 e viceversa 𝑥 𝑥 1 Selecionar item 2 caso contrário os itens 3 e 4 juntos Foco na situação não seleção do item 2 o que acontece com item 3 e item 4 2𝑥 𝑥 𝑥 2 13 O uso de variáveis binárias da PI nos permite Incluir condicionantes se então na seleção de variáveis Se o item 2 é selecionado selecione também o item 3 foco é a situação seleção do item 2 o que acontece com o item 3 𝑥 𝑥 Se o item 1 é selecionado não selecione item 3 e 4 foco é na situação seleção do item 1 o que acontece com item 3 e 4 21 𝑥 𝑥 𝑥 14 O uso de variáveis binárias da PI nos permite Incluir regras pelo menosno máximo para selecionar algumas restrições flexibilidade Precisamos satisfazer uma de duas restrições pelo menos uma 𝑔𝑥 𝑏 e 𝑔𝑥 𝑏 Definindo uma variável binária 𝑧 9 0 𝑠𝑒 𝑔 𝑥 𝑏 𝑓𝑜𝑟 𝑠𝑎𝑡𝑖𝑓𝑒𝑖𝑡𝑎 1 𝑠𝑒 𝑔 𝑥 𝑏 𝑓𝑜𝑟 𝑠𝑎𝑡𝑖𝑠𝑓𝑒𝑖𝑡𝑎 Com 𝑀 número muito grande sendo o limite superior de cada LHS as seguintes restrições implementam o que precisamos 𝑔 𝑥 𝑏 𝑀𝑧 𝑔 𝑥 𝑏 𝑀1 𝑧 15 16 Selecionando investimentos Custos de setup fixed charges Problemas de atribuição de cobertura aplicações da PI Seleção de investimento modelo binário simples 17 A TAT Co avalia sete oportunidades de investimento O cash necessário para cada investimento e o valor presente líquido NPV que cada investimento adiciona estão na tabela abaixo Cada NPV está baseado em um fluxo de receita futura e inclui uma necessidade de caixa inicial A tabela lista também o retorno sobre o investimento ROI para cada investimento definido como a relação de NPV sobre o cash necessário Seleção de investimento modelo binário simples 18 O orçamento disponível é 15 milhões TAT quer encontrar uma política de investimento que maximize o total de NPV O pressuposto principal aqui é que se a TAT quiser fazer parte de qualquer investimento ela tem que adquirir o total da oferta não podendo fracionar caso fosse permitida a participação parcial poderíamos usar LP Não pode por exemplo optar pelo investimento 1 investindo 25 milhões que demanda 50 milhões obtendo um NPV de 28 milhões Selecionar investimentos modelo binário simples 19 A solução ótima da TAT inca que o NPV máximo de 167 milhões pode ser obtido selecionando os investimentos 3 5 e 6 Estes três investimentos consomem somente 149 milhões ficando sem aplicação 100 mil Esta sobra não pode ser aplicada em função da restrição Porque esta solução é superior a escolher o investimento com base no ranking ROI apresentado Selecionar investimentos modelo binário simples 20 Modifique o modelo conforme estes três cenários e encontre a solução ótima a Suponha que no máximo apenas dois projetos possam ser escolhidos b Suponha que por uma decisão de negócio caso o inv 5 seja escolhido o inv 1 também deva ser escolhido c Suponha que pelo menos o inv 2 ou o inv 3 ou ambos devam ser selecionados Atividade em grupo para entrega em 3103 eclass Custos de setup fixed charge 21 Custo que incorre quando determinada atividade é realizada a qualquer nível positivo Nenhum custo fixo é apurado se nenhuma atividade é realizada Exemplos A construção de armazémdepósito incorre em determinado custo fixo independente se o depósito é construído com baixa ou alta capacidade de armazenamento A maquina que é usada para produzir diversos produtos deve ser configurada e preparada para a produção de cada produto Isto independente do tamanho do lote a ser produzido Custos de setup fixed charge 22 Variáveis binárias são usadas para transformar problemas não lineares eg setup costs problems em modelos lineares inteiros Ajudam a modelar a logica do problema Neste caso existe um custo fixo se uma atividade é realizada a qualquer nível positivo Não há esse custo se nenhuma atividade é realizada Custos de setup para a fábrica i Custos de setup fixed charge 23 A GraT Textil produz camisetas shorts calças saias e jaquetas Cada tipo de vestimenta demanda um maquinário específico a disposição As máquinas necessárias para cada tipo de roupa são alugadas a taxas semanais como mostrado na tabela abaixo Custos de setup fixed charge 24 Esta tabela lista as quantidades de tecido e mão de obra horas necessária por unidade de vestimenta bem como o preço de venda e o custo unitário variável Custos de setup fixed charge 25 Em uma dada semana 4000 horas de mão de obra e 4500 metros quadrados m2 de tecido estão disponíveis A companhia gostaria de encontrar uma solução que maximize o resultado semanal Note por exemplo que o custo de produzir x camisetas durante uma semana é 0 zero se x 0 mas é 1500 20x se x 0 Custos de setup fixed charge 26 Importante para o problema é preciso relacionar a quantidade x e o custo de setup s aluguel de forma que quando tenhamos x positivo incorra em s max 𝑃𝑥 𝐶𝑥 𝑆𝑦 𝑥 𝐾𝑦 Onde 𝐾 é a capacidade de produção do item i 𝑦 é 1 se o produto é produzido A produção do item i deve ser inferior a capacidade da maquina Se 𝑥 0 então 𝑦 não pode ser zero Se 𝑥 0 𝑦 poderá ser 0 ou 1 Tanto x como y são variáveis de decisão Restrição fixedcharge Custos de setup fixed charge 27 Iniciar modelo simplificado e depois montar o final A solução ótima para a GraT indica que a empresa deve produzir 966 shorts e 379 jaquetas e nenhum outro dos produtos O lucro total é de 54614 É uma solução em dois estágios interrelacionados No primeiro o Solver determina que produtos produzir No segundo o Solver determina quantos desses produtos shorts e jaquetas produzir Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 28 A Wt Aerolíneas quer desenhar um sistema de hubs nos EUA Cada hub é usado para conectar voos de e para cidades distantes até 1000 km do hub A Wt opera voos entre 12 cidades ver tabela A companhia quer determinar o menor numero de hubs necessário para cobrir todas as cidades considerando que toda cidade deve ser atendida por pelo menos um hub Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 29 A tabela lista quais cidades estão a uma distancia de 1000km das outras cidades Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 30 Primeiro passo como informar o modelo com o input de distancias Iniciar modelo simplificado e depois montar o final Solução ótima três cidades Resposta objetivo mínimo 3 hubs Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 31 A UC vende e oferece serviços de manutenção pra impressoras 3d aos seus clientes em 11 cidades nos EUA ver tabela A companhia quer estabelecer Centros de Serviços em 3 dessas cidades Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 32 Escolhida a localização dos Centros de Serviço é preciso direcionar os clientes em cada cidade para um do três CS É desses centros que partirão os técnicos para visitas Por exemplo se optar por ter um centro em New York e direcionar os clientes de Boston para o CS de New York um representante da empresa viajará de New York para Boston quando os serviços forem demandados Problemas de atribuição de cobertura 33 As distancias em kms entre as cidades estão listadas na tabela A quantidade anual estimada de visitas viagens ida e volta para os vários clientes estão também listadas na tabela O que á UC deve fazer para minimizar a distancia anual total viajada pelos seus representantes de serviços Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 34 Começar pela versão simplificada e depois ampliar para o modelo final Solução ótima Dallas NY e SF Distancia em km mil 5145 Atividades 1404
Send your question to AI and receive an answer instantly
Preview text
Pesquisa Operacional Graduação em Administração Prof Ludwig Miguel FGV Ebape Atividades 24mar Exercício 03 Lista 10mar23 2 Programação Linear 4 Mix de produção Produção multiperiodo Escala de funcionários Combinação de insumos Modelo de investimento aplicações da PL Programação Linear Inteira PL e PI Quando falamos de Programação Linear ex mix de produção produção multiperiodo etc ALOCACAO DE RECURSOS Quando falamos de Programação Inteira ex onde localizar novas instalações para atender a demanda etc SELECAO ou ATRIBUICAO 6 Optimização com variáveis inteiras Exemplos Setup costs custos fixos Localização de instalações ex centros de distribuição hospitais etc Programação de maquinário ex como alocar a maquina para diferentes trabalhos dependendo da capacidade e rapidez da maquina Rotas de veículos em entrega Basicamente este tipo de problemas trata de SELECAO ou ATRIBUICAO estabelecer o que uma pessoamaquina deve fazerselecionar 7 Optimização com variáveis inteiras Problemas de PI são aqueles de programação matemática em que uma ou variáveis de decisão são representadas apenas por valores inteiros Em LP tudo é fraccionado contínuo em IP alguns valores são discretos Programação inteira total todas as variáveis de decisão são do tipo inteiro Programação inteira mista apenas uma parte das variáveis é do tipo inteiro enquanto as outras são do tipo real Nosso escopo em PI falaremos de Programação Linear Inteira 8 Alguns exemplos de PI 9 Escala de pessoal Determinar a quantidade de staff em cada um das suas localidades Mais de 6500 restaurantes nos EUA Quantos funcionários devem estar em cada restaurante por turno Equipes muito pequenas por restaurante arredondamentos pode ser muito impreciso Taco Bell desenvolveu um PI ie um PL com variáveis inteiras para resolver o problema de alocação da força de trabalho 13 milhões de economia por ano Fonte Jackie Hueter William Swart 1998 An Integrated LaborManagement System for Taco Bell Interfaces 2817591 httpsdoiorg101287inte28175 Alguns exemplos de PI 10 Seleção da melhor rota A WM Waste Management opera uma rede de reciclagem com 293 aterros 16 plantas de energia a partir de resíduos 72 instalações de energia a partir de gás 146 plantas de reciclagem 346 estacoes de transferência e 435 pontos de coleta Seus veículos precisam percorrer 2000 rotas diariamente Como determinar a melhor rota Uso de variáveis binárias PI de grande porte economizando 498 milhões em custos operacionais em um período de 5 anos Fonte Sahoo S Kim S Kim BI Kraas B Popov A 2005 Routing Optimization for Waste Management Interfaces 351 2436 httpwwwjstororgstable27651734 Formulação de PI Usando o problema clássico da mochila de trilha Quatro itens para selecionar Capacidade da mochila de 10 kg Precisamos maximizar o valor total sem ultrapassar a capacidade da mochila A formulação completa é max 16𝑥 22𝑥 12𝑥 8𝑥 sa 5𝑥 7𝑥 4𝑥 3𝑥 10 𝑥 01 1 4 11 Programa inteiro ou programa binário variáveis binárias da PI nos permitem Implementar regras de seleção de variáveis Regra do tipo pelo menosno máximo alguns itens Supondo que seja obrigatório selecionar pelo menos um dos itens 23 ou 4 pode ser um dois ou os três itens 𝑥 𝑥 𝑥 1 Supondo que seja obrigatório selecionar no máximo dois itens entre o 1 3 e 4 pode ser um dois o nenhum 𝑥 𝑥 𝑥 2 12 O uso de variáveis binárias da PI nos permite Incluir condicional OU na seleção de variáveis Selecionar OU o item 2 OU item 3 Foco na situação item 2 selecionado o que acontece com item 3 e viceversa 𝑥 𝑥 1 Selecionar item 2 caso contrário os itens 3 e 4 juntos Foco na situação não seleção do item 2 o que acontece com item 3 e item 4 2𝑥 𝑥 𝑥 2 13 O uso de variáveis binárias da PI nos permite Incluir condicionantes se então na seleção de variáveis Se o item 2 é selecionado selecione também o item 3 foco é a situação seleção do item 2 o que acontece com o item 3 𝑥 𝑥 Se o item 1 é selecionado não selecione item 3 e 4 foco é na situação seleção do item 1 o que acontece com item 3 e 4 21 𝑥 𝑥 𝑥 14 O uso de variáveis binárias da PI nos permite Incluir regras pelo menosno máximo para selecionar algumas restrições flexibilidade Precisamos satisfazer uma de duas restrições pelo menos uma 𝑔𝑥 𝑏 e 𝑔𝑥 𝑏 Definindo uma variável binária 𝑧 9 0 𝑠𝑒 𝑔 𝑥 𝑏 𝑓𝑜𝑟 𝑠𝑎𝑡𝑖𝑓𝑒𝑖𝑡𝑎 1 𝑠𝑒 𝑔 𝑥 𝑏 𝑓𝑜𝑟 𝑠𝑎𝑡𝑖𝑠𝑓𝑒𝑖𝑡𝑎 Com 𝑀 número muito grande sendo o limite superior de cada LHS as seguintes restrições implementam o que precisamos 𝑔 𝑥 𝑏 𝑀𝑧 𝑔 𝑥 𝑏 𝑀1 𝑧 15 16 Selecionando investimentos Custos de setup fixed charges Problemas de atribuição de cobertura aplicações da PI Seleção de investimento modelo binário simples 17 A TAT Co avalia sete oportunidades de investimento O cash necessário para cada investimento e o valor presente líquido NPV que cada investimento adiciona estão na tabela abaixo Cada NPV está baseado em um fluxo de receita futura e inclui uma necessidade de caixa inicial A tabela lista também o retorno sobre o investimento ROI para cada investimento definido como a relação de NPV sobre o cash necessário Seleção de investimento modelo binário simples 18 O orçamento disponível é 15 milhões TAT quer encontrar uma política de investimento que maximize o total de NPV O pressuposto principal aqui é que se a TAT quiser fazer parte de qualquer investimento ela tem que adquirir o total da oferta não podendo fracionar caso fosse permitida a participação parcial poderíamos usar LP Não pode por exemplo optar pelo investimento 1 investindo 25 milhões que demanda 50 milhões obtendo um NPV de 28 milhões Selecionar investimentos modelo binário simples 19 A solução ótima da TAT inca que o NPV máximo de 167 milhões pode ser obtido selecionando os investimentos 3 5 e 6 Estes três investimentos consomem somente 149 milhões ficando sem aplicação 100 mil Esta sobra não pode ser aplicada em função da restrição Porque esta solução é superior a escolher o investimento com base no ranking ROI apresentado Selecionar investimentos modelo binário simples 20 Modifique o modelo conforme estes três cenários e encontre a solução ótima a Suponha que no máximo apenas dois projetos possam ser escolhidos b Suponha que por uma decisão de negócio caso o inv 5 seja escolhido o inv 1 também deva ser escolhido c Suponha que pelo menos o inv 2 ou o inv 3 ou ambos devam ser selecionados Atividade em grupo para entrega em 3103 eclass Custos de setup fixed charge 21 Custo que incorre quando determinada atividade é realizada a qualquer nível positivo Nenhum custo fixo é apurado se nenhuma atividade é realizada Exemplos A construção de armazémdepósito incorre em determinado custo fixo independente se o depósito é construído com baixa ou alta capacidade de armazenamento A maquina que é usada para produzir diversos produtos deve ser configurada e preparada para a produção de cada produto Isto independente do tamanho do lote a ser produzido Custos de setup fixed charge 22 Variáveis binárias são usadas para transformar problemas não lineares eg setup costs problems em modelos lineares inteiros Ajudam a modelar a logica do problema Neste caso existe um custo fixo se uma atividade é realizada a qualquer nível positivo Não há esse custo se nenhuma atividade é realizada Custos de setup para a fábrica i Custos de setup fixed charge 23 A GraT Textil produz camisetas shorts calças saias e jaquetas Cada tipo de vestimenta demanda um maquinário específico a disposição As máquinas necessárias para cada tipo de roupa são alugadas a taxas semanais como mostrado na tabela abaixo Custos de setup fixed charge 24 Esta tabela lista as quantidades de tecido e mão de obra horas necessária por unidade de vestimenta bem como o preço de venda e o custo unitário variável Custos de setup fixed charge 25 Em uma dada semana 4000 horas de mão de obra e 4500 metros quadrados m2 de tecido estão disponíveis A companhia gostaria de encontrar uma solução que maximize o resultado semanal Note por exemplo que o custo de produzir x camisetas durante uma semana é 0 zero se x 0 mas é 1500 20x se x 0 Custos de setup fixed charge 26 Importante para o problema é preciso relacionar a quantidade x e o custo de setup s aluguel de forma que quando tenhamos x positivo incorra em s max 𝑃𝑥 𝐶𝑥 𝑆𝑦 𝑥 𝐾𝑦 Onde 𝐾 é a capacidade de produção do item i 𝑦 é 1 se o produto é produzido A produção do item i deve ser inferior a capacidade da maquina Se 𝑥 0 então 𝑦 não pode ser zero Se 𝑥 0 𝑦 poderá ser 0 ou 1 Tanto x como y são variáveis de decisão Restrição fixedcharge Custos de setup fixed charge 27 Iniciar modelo simplificado e depois montar o final A solução ótima para a GraT indica que a empresa deve produzir 966 shorts e 379 jaquetas e nenhum outro dos produtos O lucro total é de 54614 É uma solução em dois estágios interrelacionados No primeiro o Solver determina que produtos produzir No segundo o Solver determina quantos desses produtos shorts e jaquetas produzir Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 28 A Wt Aerolíneas quer desenhar um sistema de hubs nos EUA Cada hub é usado para conectar voos de e para cidades distantes até 1000 km do hub A Wt opera voos entre 12 cidades ver tabela A companhia quer determinar o menor numero de hubs necessário para cobrir todas as cidades considerando que toda cidade deve ser atendida por pelo menos um hub Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 29 A tabela lista quais cidades estão a uma distancia de 1000km das outras cidades Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 30 Primeiro passo como informar o modelo com o input de distancias Iniciar modelo simplificado e depois montar o final Solução ótima três cidades Resposta objetivo mínimo 3 hubs Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 31 A UC vende e oferece serviços de manutenção pra impressoras 3d aos seus clientes em 11 cidades nos EUA ver tabela A companhia quer estabelecer Centros de Serviços em 3 dessas cidades Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 32 Escolhida a localização dos Centros de Serviço é preciso direcionar os clientes em cada cidade para um do três CS É desses centros que partirão os técnicos para visitas Por exemplo se optar por ter um centro em New York e direcionar os clientes de Boston para o CS de New York um representante da empresa viajará de New York para Boston quando os serviços forem demandados Problemas de atribuição de cobertura 33 As distancias em kms entre as cidades estão listadas na tabela A quantidade anual estimada de visitas viagens ida e volta para os vários clientes estão também listadas na tabela O que á UC deve fazer para minimizar a distancia anual total viajada pelos seus representantes de serviços Problemas de atribuição de cobertura minimizar o numero de elementos de um conjunto necessários para oferecer cobertura a um outro conjunto predeterminado 34 Começar pela versão simplificada e depois ampliar para o modelo final Solução ótima Dallas NY e SF Distancia em km mil 5145 Atividades 1404