Trabalho Computacional - Otimização 2023-2

Trabalho Computacional 1 Instrucoes Gerais Neste trabalho, vocé deve resolver problema de otimizacao com estrutura linear utilizando alguma das técnicas aprendidas em sala. Vocé pode resolver o Problema Sugerido, que esta descrito na préxima secao, OU pode resolver um Problema Escolhido por vocé mesmo; nesse ultimo caso, as intrucdes estao na secao final. 2 Problema Sugerido A construcaéo em locais adequados de estruturas de atendimento 4 populacaéo, como postos de saude, bombeiros, policia, escolas, hospitais, d4reas de recreacao, etc., é algo essencial para um planejamento urbano eficiente. Neste projeto, veremos a seguir um modelo simplificado para a determinacao do local 6timo de construgao de um posto de bombeiros. Suponha que a populagao de uma cidade esta concentrada em J bairros, e que cada bairro 2 possui p; moradores. Uma andalise preliminar encomendada pela prefeitura é capaz de indicar J locais ptblicos onde seria possivel realizar a construcao de um posto de bombeiros. Seja d;; > 0 a distancia do centro de cada bairro i até o possivel local de construgao 7. O objetivo é determina a melhor selecao do local para construgao dos postos de bombeiros e a melhor designacao de qual bairro devera ser atendido por qual posto. Considere as seguintes varidveis, definidas paraz = 1,..., Jej=1,..., J: __ J 1, se um posto de bombeiros for alocado no local 7 4i 1 Q caso contrario. e te 1, seo bairro 72 for atendido pelo posto construido em j I~) 0 caso contrario. Detalhes da formulagao: e Cada bairro 7 deve ser atendido por um tnico posto de bombeiro J Sorjy=l, Wisl,..., 1 j=l e Cada bairro 7 deve ser atendido pelo local 7 somente se nele for construido um posto de bombeiro, ou seja, se y; = Dentao x7j;; =0 Vi=1,..., I. Essa exigencia pode ser atendida incorporando a restrigao I Soy <ul, Vis... J i=1 uma vez que, como 2; Sao varidveis binarias, sua soma nao deve exceder I; além disso, se yj; = 9, a soma das varidveis binarias deve ser < 0, obrigando-as a serem nulas. e A distancia entre o centro de cada bairro até o posto de bombeiros designado para atendé-lo é dada por J d= So dye Wi=1,..., 1 j=l uma vez que, para cada 7 fixo, apenas uma varidvel x;; tem valor 1 e os demais sao nulos. e O total de moradores atendidos pelo local 7 é dada por I sj = SS pitij i=1 e Essa quantidade de pessoas influenciara diretamente no tamanho do posto de bombeiros que devera ser construido, fazendo com que seu custo de construgao f; seja maior ou menor de acordo com a demanda f5 (53) Como ha um valor maximo B de reais disponibilizado pela prefeitura para realizar as construcoes, o valor total gasto nao deve ultrapassar esse limite J Y_ fils;)) < B j=l O principal objetivo para determinar a alocacao deve ser o bem-estar da populacgao, refletido dire- tamente na agilidade do atendimento. Assim, uma funcao objetivo seria dada pelo deslocamento da populacao: min D onde D= max dj. i=1,...,1 O objetivo acima pode ser reescrito incorporando algumas restricdes min D sujeitoa D> d;,, W=1,..., 1 2.1 Formulacao Final Todas as informagoes mencionadas na secao anterior corroboram para o modelo final min D J S.a D—- So djxiz > 0 i=l,..., 1 j=l J So vi = 1 1=1,...,/ j=l I (*) So taj Syl jg=l,..., J i=1 I 8; — S > pixiz = 0 j=l,..., J 7 a Y_ fils) < B j=l Lig, Yj € {0, 1} a=1,...,]1 j=l,..., J 2.2 Dados para Implementacgao Em uma cidade existem J = 5 bairros que necessitam de atendimento dos bombeiros, cada um deles com a seguinte estimativa para o total de habitantes: 1 1 2 3 4 5 p; | 107300 22140 11760 58910 37650 A prefeitura possui o valor de B = R$50.000.000, 00 (50 milhoes) que devem ser alocados para a construcao dos postos de bombeiros; para isso, selecionou J = 8 possiveis locais para a cons- trucao. As distancias (em Km) entre o centro dos bairros 7 e os possiveis locais de construgao 7 estao colocadas na tabela abaixo: ij} 1 2 38 4 5 6 7 8 1 23,7 11,1 7,2 13,1 20,2 33,5 9,9 1,5 2 |12,1 5,5 12,3 10,7 12,7 11,1 2,2 17,8 3 6,2 25,5 23,4 8,3 7,4 22,6 13,1 6,2 4 |22,1 12,3 11,9 7,2 12,8 17,3 18,5 13,4 5 | 7,7 11,2 18,0 15,1 23,1 17,9 12,3 20,2 Suponha que cada poss´ıvel local j tenha um custo fixo estimatido de rj reais para o m2 do posto de bombeiro a ser constr´ıdo no local. j 1 2 3 4 5 6 7 8 rj 833, 77 1100, 12 922, 25 1300, 12 712, 39 1122, 42 1321, 23 917, 52 Esse custo est´a relacionado com o tamanho do terreno, tipo de solo, pre¸co dos materiais e m˜ao- de-obra. Outro fator relevante ´e que quanto maior a demanda por atendimento maior deve ser o tamanho do posto. Assim, considere durante a implementa¸c˜ao que fj(sj) = rj sj ∀j = 1, . . . , J 2.3 Resolu¸c˜ao Num´erica ˆ Resolva o problema modelado (*) com os dados fornecidos na subse¸c˜ao anterior, utilizando o m´etodo de Branch & Bound onde, uma vez decidida qual ´e a vari´avel que ir´a gerar a ramifica¸c˜ao, o primeiro n´o “filho” ser´a gerado utilizado essa vari´avel como 0 e o segundo n´o “filho” ser´a gerado utilizado essa vari´avel como 1. ˆ Exiba a ´arbove B & B criada. ˆ Exiba sempre a solu¸c˜ao encontrada na resolu¸c˜ao do PPLI relaxado de cada n´o, assim como o valor da imagem ´otima. Indique se esse n´o ser´a podado (por inviabilidade, otimalidade ou qualidade) ou se ser´a ramificado. A cada ramifica¸c˜ao, indique nas arestas o que est´a sendo inclu´ıdo para gerar o n´o filho (conforme descrito no item anterior). ˆ Exiba a solu¸c˜ao final encontrada. Onde ser˜ao constru´ıdos os pontos de bombeiros? Quais postos atender˜ao quais bairros? Qual ser´a o valor total gasto pela prefeitura na constru¸c˜ao desses postos? Qual foi o bairro “mais prejudicado” (ou seja, qual ficou mais distante do posto de bombeiro a que foi designado)? Qual foi o bairro “mais beneficiado” (ou seja, qual ficou mais pr´oximo do posto de bombeiro a que foi designado)? 3 Problema Escolhido Busque por um problema real em fontes confi´aveis (artigos, grupos de pesquisa, empresas...) que possa ser modelado matematicamente como um problema de programa¸c˜ao linear, onde as vari´aveis podem ser reais, inteiras ou bin´arias. Uma vez escolhido o problema a ser abordado, escreva um pouco sobre ele (nada muito longo, o importante ´e que seja claro): ˆ Conte como surge esse problema (em que ´area, em que situa¸c˜ao, sua utilidade, ...). ˆ Descreva sua modelagem matem´atica, ou seja, como s˜ao suas vari´aveis (o que representam, se s˜ao bin´arias, reais, ...), como ´e a express˜ao da fun¸c˜ao objetivo e o que ela afere, indique o que as restri¸c˜oes representam e como s˜ao. ˆ Caso tenha descoberto em suas pesquisas, comente como esse problema ´e resolvido atual- mente, se os resultados obtidos s˜ao satisfat´orios, etc. ˆ Fa¸ca uma se¸c˜ao (no final de tudo) incluindo a bibliografia, com todos os sites, artigos, livros... que vocˆe tiver consultado para desenvolver esse trabalho. Ap´os essa descri¸c˜ao, indique qual m´etodo utilizou para resolver (Simplex, Dual Simplex, Duas Fases, Planos Cortantes, Branch & Bound, etc.). Se precisou fazer alguma adapta¸c˜ao ou es- colha espec´ıfica para parˆametros, gera¸c˜ao do corte ou ramifica¸c˜ao, etc., n˜ao deixe de comen- tar/descrever. Ap´os a resolu¸c˜ao, coloque uma vis˜ao geral do resultado: Quantas itera¸c˜oes gastou? Qual a solu¸c˜ao encontrada? Qual o valor da imagem ´otima? A solu¸c˜ao encontrada faz sentido (considerando a natureza do problema)? Qual linguagem de programa¸c˜ao utilizou?