Problema – Transporte de Produtos

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

    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
    Profile photo ofjonesJones 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.