Giovanni Bruno Travassos de Carvalho - 11506849
UFPB - 2019.4
O projeto consiste na modelagem e implementação de um problema de Programação Linear Inteira, localização de facilidades. Na temática, o problema consiste em aplicar os conhecimentos adquiridos na disciplina de Pesquisa Operacional, tendo em vista a modelagem do problema, definindo as restrições básicas. Por fim a implementação do programa, desenvolvida em Python, para que funcione em qualquer conjunto de dados e forneça a resposta completa. A implementação contou com auxílio da biblioteca de programação linear DOCPLEX(Decision Optimization CPLEX), e também a MATPLOTLIB para plotagem.
No problema de Localização de UPAs, existem n distritos numa região metropolitana, cuja distância entre um distrito e outro é dada pela equação da distância euclidiana:
Com isso deseja-se escolher em quais localidades as UPAs devem ser instaladas. Em regra, é obrigatório que se siga as seguintes restrições:
- Distância entre distrito e UPA mais próxima deve ser no máximo K km;
- Distância entre distrito e segunda UPA mais próxima deve ser no máximo Y km;
- Distância entre duas UPAs de no máximo Z km.
É necessário que suas respectivas saídas, para resolução do problema, contenha as seguintes indicações:
- Saída 1 = Quais distritos foram instaladas UPAs;
- Saída 2 = Distância de cada distrito para a primeira e segunda UPA mais próxima.
O objetivo do problema é buscar a minimização do número de UPAs, respeitando as restrições impostas.
Para resolução do problema foi preciso criar n variáveis binárias que são representadas no distrito n existindo ou não uma UPA. Os valores de K, Y e Z são fornecidos no arquivo de entrada, assim como as coordenadas (X,Y) de cada distrito.
(a)Função Objetiva: Minimizar um somatório de todas as variáveis binárias para cada distrito;
(b)Primeira Restrição: Para todo j pertencente a {1,...,n}, é feito um somatório das variáveis binárias, se a distância dij for menor que o valor K fornecido, cujo valor tem que ser maior ou igual a 1. Essa restrição indica que é preciso ter ao menos uma UPA dentro dessa distância mínima;
(c)Segunda Restrição: Para todo j pertencente a {1,...,n}, é feito um somatório das variáveis binárias, se a distância dij for menor que o valor Y fornecido, cujo valor tem que ser maior ou igual a 2. Essa restrição indica que é preciso ter ao menos duas UPA dentro dessa distância mínima;
(d)Terceira Restrição: Para todo i e j pertencente a {1,...,n}, se a distância dij for menor que Z, a soma das variáveis binárias tem que ser 1, ou seja, apenas um dos distritos poderá receber uma UPA;
(e)Declaração das variáveis binárias.
O projeto foi feito em Python no Anaconda Navigator com auxílio da biblioteca DOCPLEX. Para instalar a biblioteca, é preciso digitar o seguinte comando no Prompt do Anaconda ou no terminal do Linux: $ pip install docplex.
Essa biblioteca nos permite adicionar de forma rápida e fácil o poder de otimização do CPLEX, e possibilita modelar e resolver os problemas na API do Python.
Usamos também a biblioteca chamada Matplotlib, o Anaconda já vem com esse recurso instalado, mas caso fosse usado outro ambiente, seria necessário instalá-la com o seguinte comando: $ pip install matplotlib ou $conda install matplotlib.
O formato do arquivo de entrada foi definido da seguinte maneira:
- n #Número de Distritos
- K #Distância mínima de um distrito para UPA mais próxima
- Y #Distância mínima de um distrito para segunda UPA mais próxima
- Z #Distância máxima de uma UPA para outra
- (x,y) #Coordenada de cada distrito
Figura 1 - Exemplo de arquivo de entrada
Executando e printando o comando export_to_string() , conseguimos ver a modelagem feita pelo programa, e como resultado do exemplo de “entrada2.txt” obtivemos:
Figura 2 - Comando "export_to_string()"
Podemos observar na execução desse comando, que a função objetiva descrita em obj foi feita corretamente, assim como as 30 restrições c, e as 10 variáveis binárias também foram criadas corretamente para o problema da entrada “entrada2.txt”.
Utilizamos o comando print_information() para obter outras informações sobre o modelo criado, como o número de variáveis e seu tipo, e o número de restrições e seu tipo.
Figura 3 - Comando "print_information()"
Agora, executando o solver e printando sua solução através do comando display(), obtemos:
Figura 4 - Comando "display()"
Através do comando acima podemos observar que o resultado da função objetiva em “objetive”, que para o arquivo de entrada “entrada2.txt” foi 5. Também podemos observar as variáveis binárias com 1, que representam o distrito que receberá uma UPA.
Em seguida, printamos a saída da maneira que foi pedida no apêndice 2 da descrição do problema, mostrando em qual distrito serão localizadas as UPAs.
Figura 5 - Saída do programa
Por fim, plotamos os distritos em um sistema de coordenadas, pintando o lugar que receberá UPA de vermelho, e os demais de preto:
Figura 6 - Distritos no sistema de coordenadas
O primeiro problema encontrado foi na criação da segunda restrição, ao colocar ‘maior igual a 2’ alguns somatórios que só entraram duas variáveis deram erro, pois não era possível que uma variável binária fosse maior ou igual a 2. Portanto deixamos a segunda restrição com ‘maior igual a 1’.
Tivemos dificuldade e por consequência não conseguimos printar corretamente a distância do distrito que não tem UPA para a UPA mais próxima, nem para segunda UPA mais próxima.
Por fim, para melhoria do projeto, também sugerimos plotar raios de valor K, Y e Z para cada distrito, facilitando a visualização do problema. Nessa mesma plotagem, é preciso ainda criar uma função que descubra os maiores valores de x e y para usar de coordenada na criação do sistema.