Problema da Mochila: Formulação e Exercício

Facens Problema da Mochila Um viajante deseja levar 𝑛 itens em sua viagem A carga de cada item 𝑖 é dado por 𝑤𝑖 O valor de cada item 𝑖 é dado por 𝑝𝑖 Os itens devem ser carregados em uma mochila cuja capacidade é B Quando a soma dos pesos 𝑤𝑖 de todos os itens escolhidos não ultrapassa B então todos os itens podem ser carregados na mochila Caso contrário alguns itens devem ser deixados para trás Quais itens deveriam ser levados deixados Problema da Mochila Aplicações Carregamento de veículos Problemas de corte e empacotamento Orçamento etc Exemplo Uma empresa pode investir até B reais em diferentes projetos S 1 n Cada projeto 𝑖 necessita um investimento de wi reais e tem um lucro esperado de pi reais O objetivo do problema é escolher os projetos que maximizam o lucro total da empresa sem ultrapassar o limite do orçamento B Exemplo Formulação Variáveis de decisão 𝑥𝑖 ቊ1 𝑠𝑒 𝑜 𝑝𝑟𝑜𝑗𝑒𝑡𝑜 𝑖 𝑝𝑒𝑟𝑡𝑒𝑛𝑐𝑒 à 𝑠𝑜𝑙𝑢çã𝑜 0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜 Formulação 𝑀𝑎𝑥 𝑧 𝑖𝑆 𝑝𝑖𝑥𝑖 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝑖𝑆 𝑤𝑖𝑥𝑖 𝐵 𝑥𝑖 01 𝑖 Onde 𝑆 1 𝑛 Repare que se uma variável 𝑥𝑖 é igual a 1 o gasto com seu investimento é contabilizado do lado esquerdo da restrição de orçamento e seu retorno esperado é contabilizado na função objetivo Exercício 1 Suponha que um viajante deseja acampar e levar consigo 5 itens mas estes juntos excedem o limite de 60 quilos que ele consegue carregar Precisamos então auxiliálo na decisão sobre quais itens levar de acordo com seus pesos w cargas e seus valores p ordens de importância para ele na viagem Sejam então os seguintes dados n 5 B 60 w 52 23 35 15 7 p 100 60 70 15 8 Formule o problema de modo a atingir o objetivo desejado Exercício 1 Solução Objetivo Minimizar custo Variáveis de decisão VDs 𝑥𝑖 ቊ1 𝑠𝑒 𝑖𝑡𝑒𝑚 𝑖 é 𝑙𝑒𝑣𝑎𝑑𝑜 0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜 𝑖 12 5 𝑀𝑎𝑥 𝑧 100𝑥1 60𝑥2 70𝑥3 15𝑥4 8𝑥5 𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 52𝑥1 23𝑥2 35𝑥3 15𝑥4 7𝑥5 60 𝑥𝑖 𝑏𝑖𝑛á𝑟𝑖𝑜 𝑖 12 5 LINDO acrescentar INT x1 para definir variável binária para 𝑥1 Exercício 1 Solução Lindo MAX 100x1 60x2 70x3 15x4 8x5 ST 52x1 23x2 35x3 15x4 7x5 60 end INT x1 INT x2 INT x3 INT x4 INT x5 OBJECTIVE FUNCTION VALUE 1 1300000 VARIABLE VALUE REDUCED COST X1 0000000 100000000 X2 1000000 60000000 X3 1000000 70000000 X4 0000000 15000000 X5 0000000 8000000 ROW SLACK OR SURPLUS DUAL PRICES 2 2000000 0000000 NO ITERATIONS 2 BRANCHES 0 DETERM 1000E 0 INT Variável xi só pode assumir valores 0 ou 1 Exercício 2 Uma câmara municipal tem 250000 orçamentados para a instalação de novas áreas de tratamento de lixo Estão disponíveis 7 localizações cujas capacidades projetadas tonelada por semana tonsemana e custos de implantação em milhares de são dados na Tabela adiante Que localizações deve a câmara selecionar Localização A B C D E F G Capacidade 20 17 15 15 10 8 5 Custo 145 92 70 70 84 14 47 Exercício 2 Solução Objetivo Maximizar capacidade instalada VDs 𝑥𝑖 ቊ1 𝑠𝑒 𝑙𝑜𝑐𝑎𝑙𝑖𝑧𝑎çã𝑜 𝑖 𝑝𝑒𝑟𝑡𝑒𝑛𝑐𝑒 à 𝑠𝑜𝑙𝑢çã𝑜 0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜 𝑖 12 7 𝑀𝑎𝑥 𝑧 20𝑥1 17𝑥2 15𝑥3 15𝑥4 10𝑥5 8𝑥6 5𝑥7 𝑆𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 145𝑥1 92𝑥2 70𝑥3 70𝑥4 84𝑥5 14𝑥6 47𝑥7 250 𝑥𝑖 𝑏𝑖𝑛á𝑟𝑖𝑜 𝑖 12 7 LINDO acrescentar INT x1 para definir variável binária para 𝑥1 Exercício 2 Solução Lindo MAX 20x1 17x2 15x3 15x4 10x5 8x6 5x7 ST 145x1 92x2 70x3 70x4 84x5 14x6 47x7 250 END INT x1 INT x2 INT x3 INT x4 INT x5 INT x6 INT x7 Resposta A câmara municipal deve investir nas localizações 2 3 4 e 6 de modo a obter a capacidade máxima de 55 tonsemana a um custo de 24600000 250 4 Algoritmo de Força Bruta Compara todas as possibilidades de preenchimento da mochila que não violem a restrição de capacidade e retorna a melhor solução encontrada Conforme o número de objetos aumenta o problema cresce de forma a ser impossível gerar e analisar todas as possíveis soluções em tempo aceitável Algoritmo Guloso Para que a heurística tenha melhor desempenho calcula se o valor de utilidade de cada objeto do conjunto como 𝑉𝑢𝑖 𝑣𝑎𝑙𝑜𝑟𝑖𝑝𝑒𝑠𝑜𝑖 Algoritmo Guloso Enquanto existir objeto no conjunto S que caiba na mochila Escolha desses objetos aquele de maior valor de utilidade Item Valor p Peso w Utilidade Vu A 100 52 192 B 60 23 261 C 70 35 200 D 15 15 100 E 8 7 114 Problema das Múltiplas Mochilas Neste problema há 𝑛 itens que devem ser colocados em m mochilas de capacidades distintas 𝑏𝑖 Assim como antes o peso de cada item 𝑗 é dado por 𝑤𝑗 e o valor de cada item 𝑗 é dado por 𝑝𝑗 O problema consiste então em selecionar 𝑚 subconjuntos distintos de itens de forma que cada subconjunto ocupe uma capacidade de no máximo 𝑏𝑖 e o valor total dos itens carregados nas 𝑚 mochilas seja maximizado Este problema aparece muito no corte de diversos produtos nas indústrias de papel aço e tecido e também no carregamento de contêineres nos problemas de corte e empacotamento Exemplo Formulação Variáveis de decisão 𝑥𝑖𝑗 ቊ1 𝑠𝑒 𝑖𝑡𝑒𝑚 𝑗 é 𝑙𝑒𝑣𝑎𝑑𝑜 𝑛𝑎 𝑚𝑜𝑐ℎ𝑖𝑙𝑎 𝑖 0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜 Formulação 𝑀𝑎𝑥 𝑧 𝑖 𝑚𝑜𝑐ℎ𝑖𝑙𝑎𝑠 𝑗 𝑖𝑡𝑒𝑛𝑠 𝑝𝑖𝑥𝑖𝑗 𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎 𝑗 𝑖𝑡𝑒𝑛𝑠 𝑤𝑗𝑥𝑖𝑗 𝑏𝑖 𝑖 𝑚𝑜𝑐ℎ𝑖𝑙𝑎𝑠 𝑖 𝑚𝑜𝑐ℎ𝑖𝑙𝑎𝑠 𝑥𝑖𝑗 1 𝑗 𝑖𝑡𝑒𝑛𝑠 𝑥𝑖𝑗 01 𝑖 𝑚𝑜𝑐ℎ𝑖𝑙𝑎𝑠 𝑗 𝑖𝑡𝑒𝑛𝑠 Cada item j não pode ser alocado a mais de uma mochila Onde pj wj bi 0 𝑗 𝑖𝑡𝑒𝑛𝑠 𝑖 𝑚𝑜𝑐ℎ𝑖𝑙𝑎𝑠 𝑤𝑗 max 𝑏𝑖 𝑗 𝑖𝑡𝑒𝑛𝑠 𝑏𝑖 min 𝑤𝑗 𝑖 𝑚𝑜𝑐ℎ𝑖𝑙𝑎𝑠 𝑤𝑗 𝑏𝑖 𝑖 𝑚𝑜𝑐ℎ𝑖𝑙𝑎𝑠 Cada mochila i só pode comportar sua capacidade Facens