Problema – Transporte de Produtos

Visualizando 2 posts - 1 até 2 (de 2 do total)
  • Autor
    Posts
  • #21532
    Fabio
    Participante

      Bom dia Prof.  Jones

      O problema de transporte de produtos proposto como exercício no tópico Algortimos de Otimização também pode ser resolvido utilizando Pesquisa Operacional. Este é um problema clássico da área de otimização chamado problema da mochila (knapsack problem) e pode ser resolvido com programação linear inteira (e neste exercício em especial com prog. linear inteira binária). As vantagens desta abordagem são: a) se existe uma solução factível então é um ótimo global; b) velocidade de execução

      Podemos utilizar o pacote glpk  e o glpsol para solucionar este problema. Em python podemos utilizar o pacote pulp que faz a interface com o glpk. Seguem abaixo as sugestões de solução.

      Obrigado e até mais

      Abtaços

      Solução utilizando o GLPK
      Comando para resolver o problema proposto, onde ex08-MochilaIA.lp é o arquivo de entrada
      com as definições do problema e ex08-MochilaIA.out é o arquivo de saída com as respostas
      
      $ glpsol --cpxlp ex08-MochilaIA.lp -o ex08-MochilaIA.out
      
      Arquivo ex08-MochilaIA.lp
      \* MochilaIA *\
      Maximize
      valor_Total_Produtos: 2911 Celular + 308 Microondas_A + 429 Microondas_B
      + 300 Microondas_C + 2500 Notebook_A + 2000 Notebook_B + 4000 Notebook_C
      + 1000 Refrigerador_A + 850 Refrigerador_B + 1200 Refrigerador_C + 3000 TV_42
      + 4000 TV_50 + 4347 TV_55 + 200 Ventilador
      Subject To
      Espaco_caminhao: 8.99e-05 Celular + 0.0424 Microondas_A + 0.0544 Microondas_B
      + 0.0319 Microondas_C + 0.0035 Notebook_A + 0.498 Notebook_B
      + 0.527 Notebook_C + 0.751 Refrigerador_A + 0.635 Refrigerador_B
      + 0.87 Refrigerador_C + 0.2 TV_42 + 0.29 TV_50 + 0.4 TV_55 + 0.496 Ventilador
      <= 3
      Binaries
      Celular
      Microondas_A
      Microondas_B
      Microondas_C
      Notebook_A
      Notebook_B
      Notebook_C
      Refrigerador_A
      Refrigerador_B
      Refrigerador_C
      TV_42
      TV_50
      TV_55
      Ventilador
      End
      
      Solução em python utilizando o PULP
      from pulp import *
      
      produtos = [('Refrigerador A', 0.751, 999.90),
      ('Celular', 0.0000899, 2911.12),
      ('TV 55', 0.400, 4346.99),
      ('TV 50', 0.290, 3999.90),
      ('TV 42', 0.200, 2999.00),
      ('Notebook A', 0.00350, 2499.90),
      ('Ventilador', 0.496, 199.90),
      ('Microondas A', 0.0424, 308.66),
      ('Microondas B', 0.0544, 429.90),
      ('Microondas C', 0.0319, 299.29),
      ('Refrigerador B', 0.635, 849.00),
      ('Refrigerador C', 0.870, 1199.89),
      ('Notebook B', 0.498, 1999.90),
      ('Notebook C', 0.527, 3999.00)]
      
      # Cria o problema
      prob = LpProblem("MochilaIA", LpMaximize)
      
      # Cria as variaveis
      x1 = LpVariable(produtos[0][0],0,1,cat="Binary")
      x2 = LpVariable(produtos[1][0],0,1,cat="Binary")
      x3 = LpVariable(produtos[2][0],0,1,cat="Binary")
      x4 = LpVariable(produtos[3][0],0,1,cat="Binary")
      x5 = LpVariable(produtos[4][0],0,1,cat="Binary")
      x6 = LpVariable(produtos[5][0],0,1,cat="Binary")
      x7 = LpVariable(produtos[6][0],0,1,cat="Binary")
      x8 = LpVariable(produtos[7][0],0,1,cat="Binary")
      x9 = LpVariable(produtos[8][0],0,1,cat="Binary")
      x10 = LpVariable(produtos[9][0],0,1,cat="Binary")
      x11 = LpVariable(produtos[10][0],0,1,cat="Binary")
      x12 = LpVariable(produtos[11][0],0,1,cat="Binary")
      x13 = LpVariable(produtos[12][0],0,1,cat="Binary")
      x14 = LpVariable(produtos[13][0],0,1,cat="Binary")
      
      # Cria a funcao objetivo
      prob += 1000 * x1 + 2911 * x2 + 4347 * x3 + 4000 * x4 + 3000 * x5 + 2500 * x6 + 200 * x7 + 308 * x8 + 429 * x9 + 300 * x10 + 850 * x11 + 1200 * x12 + 2000 * x13 + 4000 * x14, "valor Total Produtos"
      
      # Restricoes
      prob += 0.751 * x1 + 0.0000899 * x2 + 0.4 * x3 + 0.29 * x4 + 0.2 * x5 + 0.0035 * x6 + 0.496 * x7 + 0.0424 * x8 + 0.0544 * x9 + 0.0319 * x10 + 0.635 * x11 + 0.870 * x12 + 0.498 * x13 + 0.527 * x14 <= 3, "Espaco caminhao"
      
      # Escreve o modelo no arquivo
      prob.writeLP("ex08-MochilaIA.lp")
      
      # Resolve o problema
      prob.solve()
      
      # Imprime o status da resolucao
      print("Status:", LpStatus[prob.status])
      
      # Solucoes otimas das variaveis
      for variable in prob.variables():
      print("%s = %f" % (variable.name, variable.varValue))
      
      # Objetivo otimizado
      print("Valor total dos produtos: R$ %0.2f" % value(prob.objective))
      
      
      #21533
      Jones Granatyr
      Moderador

        Olá Fabio,

        Muito obrigado pela solução usando outra abordagem! Não conhecia esse pacote e é bem tranquila a implementação 🙂

        Jones

      Visualizando 2 posts - 1 até 2 (de 2 do total)
      • Você deve fazer login para responder a este tópico.