Lista - Problema de Transporte Pim - 2023-2

pt-pim-python-pulp-gusek-glpk [U2-T05] Problema de Transporte: PIM (Algoritmo Exato) com Python (PuLP) Implementação usando Funções com Somatório Prof. Werner Soares PREPARAÇÃO Acessar o Google Colaboratory: não é necessário instalar nada, mas o sistema usa notebooks. Este Tutorial foi montado para ser seguido considerando arquivos gerados no Excel, “.xlsx”. Mas é possível usar arquivos “.csv”, fazendo pequenas adaptações. Os arquivos a serem utilizados serão fornecidos pelo professor. Problema de Transporte O Problema de Transporte tem como objetivo definir o quanto deve ser enviado de cada depósito (fonte) para cada cliente (destino), buscando minimizar os custos de transporte e respeitando as capacidades desses armazéns e as demandas dos clientes. Modelo Matemático (1) Função objetivo visando minimizar os custos de transporte. Cada parcela é o produto do que foi enviado de i para j, xij, pelo custo unitário de enviar de i para j, cij; (2) Um total de n restrições de oferta. Tudo o que é enviado a partir de uma dada origem i não pode ultrapassar sua capacidade ai; (3) Um total de n restrições de demanda. Tudo o que é recebido por um dado destino j deve atender sua necessidade bj; (4) Variável de Decisão que resultará em quanto deve ser enviado de i para j. Exemplo Certa empresa possui dois armazéns, A1 e A2, onde dispõe de 100 e 50 unidades de determinado produto, respectivamente, com o que abastece três mercados, M1, M2 e M3, que consomem 80, 30 e 40 unidades. Sabendo que os custos de transporte são dados no quadro. Você pode garantir que a resposta dará inteira se as variáveis não forem inteiras? Justifique usando as matrizes A e b do Problema. Implementação do Modelo Matemático em Python Primeiramente, precisamos instalar (se já não estiverem instalados) e importar os pacotes do Python que iremos utilizar. Serão eles: • pandas: para manipular dados • PuLP: para resolver o problema de programação linear ou inteira mista • NumPy: para utilizar matrizes numéricas • ipython-autotime: para calcular automaticamente os tempos de cada célula do notebook (esta é opcional, mas é interessante para ter um certo controle do tempo de execução) • datetime: para calcular o tempo de execução e poder guardar o valor Preparação do “Computador Virtual” Instalar pacotes: Se você estiver usando o Google Colab, precisará colocar um ponto de exclamação para indicar que se trata de um comando de terminal. Ou seja, você pode requisitar a instalação dentro do próprio código que está montando. Isso é diferente se estiver usando um IDE instalado no seu computador (em que precisará procurar o terminal para realizar a instalação). Importar pacotes: Dica sobre instalação de pacotes Nem sempre é necessário instalar os pacotes. Se você estiver usando um IDE instalado no seu computador (como o VSCode, PyCharm, Spyder...) não precisará instalar de novo caso já tenha feito antes. Se estiver usando um notebook, como o Google COLAB ou o Jupyter diretamente, é preciso instalar boa parte dos pacotes (alguns já estão instalados por padrão). Importar arquivos do Excel (Google COLAB): Esse comando fará surgir um botão para importar os arquivos do Excel que pretende usar. Você pode selecionar vários de uma só vez. Os arquivos serão subidos e ficarão disponíveis para serem chamados pelos nome durante a sessão. Esta etapa só é necessária no COLAB. Isso acontece porque você não está usando o seu computador e sim um “computador virtual” da Google que só existe enquanto você está usando. Variáveis com os nomes do arquivo do Excel e suas abas: Criação dos data frames a partir dos arquivos do Excel subidos: Usaremos um para os custos de transporte, um para os dados de origem e um para as demandas, puxando de cada respectiva aba (perceba que colocou-se “df” antes para lembrarmos mais facilmente de que se trata de um data frame). Modelo Matemático Propriamente Dito Os modelo matemáticos colocam as variáveis de decisão, e os índices, como última informação apresentada. Você pode considerar como se fosse uma legenda, já que essas variáveis são usadas nas expressões apresentadas antes. Mas perceba que não faz muito sentido para o computador montar expressões com variáveis que ainda não foram introduzidas. Sendo assim, em implementações computacionais se coloca as variáveis de decisão antes das expressões. Por sua vez, os conjuntos de índices devem ser declarados antes das variáveis, pelo mesmo motivo. Conjuntos de índices: Aqui criamos duas listas de índices. No modelo eles são i e j, aqui, para uma melhor comunicação, usaremos origem e destino. Sendo a lista com cada origem chamada de origens e a com cada destino, de destinos. Para obter esses valores, basta pegar os nomes dos índices e das colunas do data frame, como mostrado na imagem: Variáveis de Decisão: A função do pulp, LpVariable(), constrói o nome para a variável (no caso será x_Natal_→_Mossoró, por exemplo, perceba que \u2192 é o símbolo de seta), o limite inferior (lowBound) e a categoria (colocamos como inteira, diferente do modelo, mas vamos perceber depois que isso não era necessário). Função Objetivo: Para facilitar a compreensão do código apresentado, será mostrada cada parte separada com destaque para a que trecho da expressão matemática do modelo está se referindo. Para esta primeira parte, podemos identificar z como prob e Min como pulp.LpMinimize. Além disso, colocamos o nome do problema. Ainda em relação à Função Objetivo, representamos os somatórios usando a função lpSum() do PuLP. Esta função irá somar tudo o que estiver dentro dela. No caso, os dois for irão iterar o que estiver no espaço, por ora vazio. Considere que para i de 1 até n é o mesmo que for origem in origens e que para j de 1 até m é o mesmo que for destino in destinos. Percebe que colocamos j depois i no código Python em vez de i depois j. Por fim, a parcela do somatório, dada por cij.xij será dada pela multiplicação de dfCustosUnitariosDeTransporte.at[origem, destino], que dá o valor do dataFrame para a posição em (“at”) linha origem (“i”) e coluna destino (“j”), multiplicada pela variável x para a mesma origem e destino. Veja que é fácil lembrar do que trata o dataFrame porque já está descrito no seu próprio nome. Todo o código junto para a função objetivo fica assim, com o prob recebendo essa nova informação através de “+=”: Use nomes compridos! Nomes de variáveis grandes lhe ajudam a ler melhor o que está acontecendo no código. Por exemplo, em vez de usar “c” para custos, como é feito na linguagem matemática, usar “dfCustosUnitariosDeTransporte” lhe informa que você tem um dataFrame, “df”, que guarda todos os custos unitários de transporte. As barras invertidas (“\”) servem para que o código possa ser continuado na linha de baixo como se tivesse continuado na mesma linha. Em outras palavras, é a forma que o Python quebra a linha (lembre-se que linguagens diferentes fazem isso de formas diferentes). Restrições de Oferta: A expressão ao fim da linha indica que teremos uma restrição para cada origem. Então, da mesma forma que termos para i de 1 até n, teremos no código para cada origem no conjunto de origens. O somatório segue a mesma lógica que você já viu para o caso da função objetivo, a diferença é que agora só temos um e percorre apenas os destinos. Restrições de Procura: Para as restrições de procura, basta seguir a mesma lógica vista para o conjunto de restrições de Oferta. Só que agora você produzirá uma restrição para cada destino e o somatório irá rodar para cada origem. Além disso, agora as restrições são de “>=”, em vez de “<=”. O lado esquerdo das expressões também é diferente. Agora você buscará informações no dataFrame dfDemandas e a linha e coluna onde a informação é procurada também muda. Veja na figura. Com tudo montado, o modelo fica: Resolução do Modelo Como visto antes, para resolver o modelo basta usar: Agora imprimimos a solução: O “se” da linha 1 garante que imprima a solução apenas se o resultado encontrado for ótimo. Assim você evita que seja mostrada uma resposta que não pode ser usada (o status da solução será impresso de toda forma na linha 6). Na linha 2 criamos uma variável chamada variavel que irá assumir os valores dentre as variáveis de prob (prob.variables), um de cada vez. A linha 3 serve para que não sejam impressas variáveis com valor 0. Assim temos uma resposta mais curta para analisar (sabendo que tudo que não for mostrado é zero). Finalmente, a linha 4 imprime o nome e o valor da variável, no formato “nome = valor”. Rodando várias vezes: Como o tempo muda a cada rodada, por fatores fora do nosso controle, desta vez iremos realizar várias rodadas e fazer a estatística descritiva para entender melhor o tempo de execução (isso é particularmente importante em Metaheurísticas, você consegue dizer o motivo?). Em rodadas indicamos quantas vezes queremos que o problema seja resolvido (vale ressaltar que as respostas sempre serão as mesmas porque são sempre ótimas para este caso em que temos algoritmos exatos). Na linha 2, um array do numpy chamado tempo é criado com o tamanho indicado por rodadas. Existem outras formas de criar um array sem precisar definir seu tamanho, aqui usamos dessa forma porque posteriormente faremos uma modificação nesse array. Agora chega a parte das resoluções em si. Na linha 4, para cada iteracao de 0 até rodadas-1 (ou seja, uma quantidade igual a rodadas), o algoritmo irá: guardar o tempo no relógio inicial, linha 5, resolver o problema, linha 7, guardar o tempo no relógio final, linha 9. Na linha 10, temos o delta t e na 11, guardamos o tempo no array tempos. Você pode verificar os tempos, imprimindo: Data frames do pandas têm a função describe(). Essa função mostra a estatística descritiva dos dados contidos (média, desvio padrão...) Também é possível desenhar o boxplot do data frame com o comando (consegue identificar as informações contidas nele? Compare com o obtido na describe()): Mude a quantidade de rodadas e veja o que ocorre com o boxplot. Teste para problemas maiores. Resolvendo vários problemas em sequência Agora que resolvemos o problema para uma única instância, vamos criar um procedimento para resolver várias instâncias em sequência. Crie um novo notebook! Para essa finalidade, nos limitaremos a acrescentar um laço e algumas poucas modificações. É possível melhorar o código através de funções depois, esse refinamento não será abordado. Importação: Como feita da outra vez, só atente para carregar todos os arquivos que vai precisar de uma só vez (basta selecionar todos). Código novo: Compare com o que tinha feito antes, mudamos apenas a parte de nome dos arquivos. Aqui entramos na linha 1 com um variável para indicar que problema estamos resolvendo, chamada conta (você pode usar um nome melhor se quiser). Então conta=0 é o primeiro problema. Precisaremos dela para poder iterar na matriz de tempos. A matriz de tempos agora tem duas dimensões, rodadas x quantidade de problemas (cuidado para não se perder na quantidade de parênteses). [endentação!!!] <criação de data frames e modelo matemático> (só copiar, colar e endentar para ficar dentro do for) Essa última parte do código é igual à anterior, a única diferença é a contagem para auxiliar e a matriz de tempos (que agora tem duas dimensões). Tome cuidado para não declarar rodadas e tempos de novo! Como da outra vez, faça: Você pode verificar os tempos, imprimindo: Data frames do pandas têm a função describe(). Essa função mostra a estatística descritiva dos dados contidos (média, desvio padrão...) Também é possível desenhar o boxplot do data frame com o comando (consegue identificar as informações contidas nele? Compare com o obtido na describe()): O que você pode dizer em relação ao tempo de execução?