Решение закрытой транспортной задачи с дополнительными условиями средствами Python

    Постановка задачи


    Необходимость решения транспортных задач в связи с территориальной разобщённостью поставщиков и потребителей очевидна. Однако, когда необходимо решить транспортную задачу без дополнительных условий это как правило не является проблемой поскольку такие решения достаточно хорошо обеспечены как теоретически, так и программными средствами.

    Решение закрытой транспортной задачи средствами Python с классическим условиями для поставщиков и потребителей товара приведено в моей статье “Решение задач линейного программирования с использованием Python” [1].

    Реальная транспортная задача усложняется дополнительными условиями и вот некоторые из них. Ограниченная грузоподъёмность транспорта, не учитываемые задержки при оформлении груза на таможне, приоритеты и паритеты для поставщиков и потребителей. Поэтому решение закрытой транспортной задачи с учётом дополнительных условий и стало целью данной публикации.

    Алгоритм решения транспортной задачи с классическими условиями


    Рассмотрим пример исходных данных в виде таблицы (матрицы).



    где C= [7,3,6,4,8,2,1,5,9]– список стоимости перевозки единицы товара от заказчиков к потребителям; X – список объёмов перевозимых товаров, обеспечивающих минимальные затраты; a= [74,40,36] – список объёмов однородных товаров на складах поставщиков; b= [20,45,30] – список объёмов спроса заказчиками однородных товаров.

    Задача закрытая поскольку sum(a)> sum(b), поэтому для X из строк таблицы запишем неравенства ограниченные сверху, а для X из столбцов таблицы равенства. Для дальнейшей обработки возьмём полученные соотношения в скобки и приравняем их переменным.

    mass1 = (x[0] + x[1] +x[2] <= 74)
    mass2 = (x[3] + x[4] +x[5] <= 40)
    mass3 = (x[6] + x[7] + x[8] <= 36
    mass4 = (x[0] + x[3] + x[6] == 20
    mass5 = (x[1] +x[4] + x[7] == 45)
    mass6 = (x[2] + x[5] + x[8] == 30)

    Приведенная система из шести переменных является типовой для транспортной задачи, остаётся определить функцию цели, которая с учётом списка С для коэффициентов и переменных mass будит иметь вид:

    problem =op(C[0]*x[0] + C[1]*x[1] +C[2]* x[2] +C[3]*x[3] + C[4]*x[4] +C[5]* x[5]+C[6]*x[6] + C[7]*x[7] +C[8]* x[8], [mass1, mass2, mass3, mass4, mass5, mass6,x_non_negative])

    Следует отметить возможности некоторых решателей по введению ограничений сразу на все переменные Х, например, добавлением к общим условиям условия не отрицательности –x_non_negative.

    Формирование дополнительных условий для закрытой транспортной задачи


    Причины этих условий могут быть различными, например, ограниченная грузоподъёмность транспорта, не учитываемые задержки при оформлении груза на таможне, приоритеты и паритеты для поставщиков и потребителей. Поэтому мы будем указывать только субъектов и характер ограничения.
    Для дальнейшего использования пронумеруем следующие дополнительные условия к закрытой транспортной задаче.

    1.Установка заданного объёма поставки товара от определённого поставщика определённому заказчику.

    Для этого вводиться новая переменная с соответствующим ограничением. Например первый поставщик должен поставить второму заказчику ровно 30 единиц товара– mass7 = (x[1] == 30).

    2.Изменение объёма поставки товара для определённого заказчика.

    Для этого меняются условия на столбец таблицы объёмов доставок товаров. Например, для второго заказчика объём заказа уменьшился с 45 единиц товара до 30.

    Строку условий mass5 = (x[1] +x[4] + x[7] == 45) следует заменить на
    mass5 = (x[1] +x[4] + x[7] == 30).

    3. Установка верхней границы объёма поставок товара для поставщика.

    Для этого меняются условия на строку таблицы объёмов доставок товаров. Например, для объёмов доставки товаров второго поставщика было ограничение сверху <= 40, а возникла необходимость доставки ровно 40 единиц товара. Переменную условий mass2 = (x[3] + x[4] +x[5] <= 40) заменим на mass2 = (x[3] + x[4] +x[5] == 40).

    4. Паритет на поставки второго и третьего поставщиков
    Для этого приравниваются объёмы поставок нескольких поставоких поставщиков, что обычно делается для улучшения бизнес климата. Например 6объёмы доставок товаров второго и третьего поставщика транспортных услуг соответственно ограничены сверху <=40 и <=36. Заменим строки mass2 = (x[3] + x[4] +x[5] <= 40) и mass3 = (x[6] + x[7] + x[8] <= 36) на mass2 = (x[3] + x[4] +x[5] == 30) и mass3 = (x[6] + x[7] + x[8] == 30).

    Решение закрытой транспортной задачи с дополнительными условиями средствами решателя cvxopt Python


    Программа для дополнительного условия №1
    from cvxopt.modeling import variable, op
    import time
    start = time.time()
    x = variable(9, 'x')
    c= [7,3,6,4,8,2,1,5,9]
    z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
    mass1 = (x[0] + x[1] +x[2] <= 74)
    mass2 = (x[3] + x[4] +x[5] <= 40)
    mass3 = (x[6] + x[7] + x[8] <= 36)
    mass4 = (x[0] + x[3] + x[6] == 20)
    mass5 = (x[1] +x[4] + x[7] == 45)
    mass6 = (x[2] + x[5] + x[8] == 30)
    mass7 = (x[1] == 30)
    x_non_negative = (x >= 0)    
    problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6, mass7,x_non_negative])
    problem.solve(solver='glpk')  
    print("Результат Xopt:")
    for i in x.value:
             print(i)
    print("Стоимость доставки:")
    print(problem.objective.value()[0])
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат Xopt:
    0.0
    30.0
    0.0
    0.0
    0.0
    30.0
    20.0
    15.0
    0.0
    Стоимость доставки:
    245.0
    Время:
    0.04002642631530762

    Программа для дополнительного условия №2
    from cvxopt.modeling import variable, op
    import time
    start = time.time()
    x = variable(9, 'x')
    c= [7,3,6,4,8,2,1,5,9]
    z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
    mass1 = (x[0] + x[1] +x[2] <= 74)
    mass2 = (x[3] + x[4] +x[5] <= 40)
    mass3 = (x[6] + x[7] + x[8] <= 36)
    mass4 = (x[0] + x[3] + x[6] == 20)
    mass5 = (x[1] +x[4] + x[7] == 30)
    mass6 = (x[2] + x[5] + x[8] == 30)
    x_non_negative = (x >= 0)    
    problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6,x_non_negative])
    problem.solve(solver='glpk')  
    print("Результат Xopt:")
    for i in x.value:
             print(i)
    print("Стоимость доставки:")
    print(problem.objective.value()[0])
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат Xopt:
    0.0
    30.0
    0.0
    0.0
    0.0
    30.0
    20.0
    0.0
    0.0
    Стоимость доставки:
    170.0
    Время:
    0.040003299713134766

    Программа для дополнительного условия №3
    from cvxopt.modeling import variable, op
    import time
    start = time.time()
    x = variable(9, 'x')
    c= [7,3,6,4,8,2,1,5,9]
    z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
    mass1 = (x[0] + x[1] +x[2] <= 74)
    mass2 = (x[3] + x[4] +x[5] == 40)
    mass3 = (x[6] + x[7] + x[8] <= 36)
    mass4 = (x[0] + x[3] + x[6] == 20)
    mass5 = (x[1] +x[4] + x[7] == 45)
    mass6 = (x[2] + x[5] + x[8] == 30)
    x_non_negative = (x >= 0)    
    problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6,x_non_negative])
    problem.solve(solver='glpk')  
    print("Результат Xopt:")
    for i in x.value:
             print(i)
    print("Стоимость доставки:")
    print(problem.objective.value()[0])
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат Xopt:
    0.0
    45.0
    0.0
    10.0
    0.0
    30.0
    10.0
    0.0
    0.0
    Стоимость доставки:
    245.0
    Время:
    0.041509151458740234

    Программа для дополнительного условия №4
    from cvxopt.modeling import variable, op
    import time
    start = time.time()
    x = variable(9, 'x')
    c= [7,3,6,4,8,2,1,5,9]
    z=(c[0]*x[0] + c[1]*x[1] +c[2]* x[2] +c[3]*x[3] + c[4]*x[4] +c[5]* x[5]+c[6]*x[6] +c[7]*x[7] +c[8]* x[8])
    mass1 = (x[0] + x[1] +x[2] <= 74)
    mass2 = (x[3] + x[4] +x[5] == 30)
    mass3 = (x[6] + x[7] + x[8] == 30)
    mass4 = (x[0] + x[3] + x[6] == 20)
    mass5 = (x[1] +x[4] + x[7] == 45)
    mass6 = (x[2] + x[5] + x[8] == 30)
    x_non_negative = (x >= 0)    
    problem =op(z,[mass1,mass2,mass3,mass4 ,mass5,mass6,x_non_negative])
    problem.solve(solver='glpk')  
    print("Результат Xopt:")
    for i in x.value:
             print(i)
    print("Стоимость доставки:")
    print(problem.objective.value()[0])
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат Xopt:
    0.0
    35.0
    0.0
    0.0
    0.0
    30.0
    20.0
    10.0
    0.0
    Стоимость доставки:
    235.0
    Время:
    0.039984941482543945

    Решение закрытой транспортной задачи с дополнительными условиями средствами решателя scipy. optimize Python


    Программа для дополнительного условия №1
    from scipy.optimize import linprog
    import time
    start = time.time()
    c = [7, 3,6,4,8,2,1,5,9]
    b_ub = [74,40,36] 
    A_ub = [[1,1,1,0,0,0,0,0,0],
                   [0,0,0,1,1,1,0,0,0],
                   [0,0,0,0,0,0,1,1,1]] 
    b_eq = [20,45,30,30] 
    A_eq = [[1,0,0,1,0,0,1,0,0],
                   [0,1,0,0,1,0,0,1,0],
                   [0,0,1,0,0,1,0,0,1],
                   [0,1,0,0,0,0,0,0,0]] 
    print(linprog(c, A_ub, b_ub, A_eq, b_eq))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    fun: 245.0
    message: 'Optimization terminated successfully.'
    nit: 10
    slack: array([ 44., 10., 1.])
    status: 0
    success: True
    x: array([ 0., 30., 0., 0., 0., 30., 20., 15., 0.])
    Время:
    0.01000523567199707

    Программа для дополнительного условия №2
    from scipy.optimize import linprog
    import time
    start = time.time()
    c = [7, 3,6,4,8,2,1,5,9]
    b_ub = [74,40,36] 
    A_ub = [[1,1,1,0,0,0,0,0,0],
                   [0,0,0,1,1,1,0,0,0],
                   [0,0,0,0,0,0,1,1,1]] 
    b_eq = [20,30,30] 
    A_eq = [[1,0,0,1,0,0,1,0,0],
                   [0,1,0,0,1,0,0,1,0],
                   [0,0,1,0,0,1,0,0,1]]                
    print(linprog(c, A_ub, b_ub, A_eq, b_eq))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    fun: 170.0
    message: 'Optimization terminated successfully.'
    nit: 7
    slack: array([ 44., 10., 16.])
    status: 0
    success: True
    x: array([ 0., 30., 0., 0., 0., 30., 20., 0., 0.])
    Время:
    0.04005861282348633

    Программа для дополнительного условия №3
    from scipy.optimize import linprog
    import time
    start = time.time()
    c = [7, 3,6,4,8,2,1,5,9]
    b_ub = [74,36] 
    A_ub = [[1,1,1,0,0,0,0,0,0],             
                   [0,0,0,0,0,0,1,1,1]] 
    b_eq = [20,45,30,40] 
    A_eq = [[1,0,0,1,0,0,1,0,0],
                   [0,1,0,0,1,0,0,1,0],
                   [0,0,1,0,0,1,0,0,1],
                   [0,0,0,1,1,1,0,0,0]]                
    print(linprog(c, A_ub, b_ub, A_eq, b_eq))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    fun: 245.0
    message: 'Optimization terminated successfully.'
    nit: 8
    slack: array([ 29., 26.])
    status: 0
    success: True
    x: array([ 0., 45., 0., 10., 0., 30., 10., 0., 0.])
    Время:
    0.04979825019836426

    Программа для дополнительного условия №4
    from scipy.optimize import linprog
    import time
    start = time.time()
    c = [7, 3,6,4,8,2,1,5,9]
    b_ub = [74] 
    A_ub = [[1,1,1,0,0,0,0,0,0]]             
    b_eq = [20,45,30,30,30] 
    A_eq = [[1,0,0,1,0,0,1,0,0],
                   [0,1,0,0,1,0,0,1,0],
                   [0,0,1,0,0,1,0,0,1],
                   [0,0,0,1,1,1,0,0,0],
                   [0,0,0,0,0,0,1,1,1]]                
    print(linprog(c, A_ub, b_ub, A_eq, b_eq))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    fun: 235.0
    message: 'Optimization terminated successfully.'
    nit: 8
    slack: array([ 39.])
    status: 0
    success: True
    x: array([ 0., 35., 0., 0., 0., 30., 20., 10., 0.])
    Время:
    0.05457925796508789

    Решение закрытой транспортной задачи с дополнительными условиями средствами решателя pulp Python


    Программа для дополнительного условия №1
    from pulp import *
    import time
    start = time.time()
    x1 = pulp.LpVariable("x1", lowBound=0)
    x2 = pulp.LpVariable("x2", lowBound=0)
    x3 = pulp.LpVariable("x3", lowBound=0)
    x4 = pulp.LpVariable("x4", lowBound=0)
    x5 = pulp.LpVariable("x5", lowBound=0)
    x6 = pulp.LpVariable("x6", lowBound=0)
    x7 = pulp.LpVariable("x7", lowBound=0)
    x8 = pulp.LpVariable("x8", lowBound=0)
    x9 = pulp.LpVariable("x9", lowBound=0)
    problem = pulp.LpProblem('0',pulp.LpMaximize)
    problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
    problem +=x2==30
    problem +=x1 + x2 +x3<= 74,"1" 
    problem +=x4 + x5 +x6 <= 40, "2"
    problem +=x7 + x8+ x9 <= 36, "3"
    problem +=x1+ x4+ x7 == 20, "4"
    problem +=x2+x5+ x8 == 45, "5"
    problem +=x3 + x6+x9 == 30, "6"
    problem.solve()
    print ("Результат:")
    for variable in problem.variables():
        print (variable.name, "=", variable.varValue)
    print ("Стоимость доставки:")
    print (abs(value(problem.objective)))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    x1 = 0.0
    x2 = 30.0
    x3 = 0.0
    x4 = 0.0
    x5 = 0.0
    x6 = 30.0
    x7 = 20.0
    x8 = 15.0
    x9 = 0.0
    Стоимость доставки:
    245.0
    Время:
    0.16973495483398438

    Программа для дополнительного условия №2
    from pulp import *
    import time
    start = time.time()
    x1 = pulp.LpVariable("x1", lowBound=0)
    x2 = pulp.LpVariable("x2", lowBound=0)
    x3 = pulp.LpVariable("x3", lowBound=0)
    x4 = pulp.LpVariable("x4", lowBound=0)
    x5 = pulp.LpVariable("x5", lowBound=0)
    x6 = pulp.LpVariable("x6", lowBound=0)
    x7 = pulp.LpVariable("x7", lowBound=0)
    x8 = pulp.LpVariable("x8", lowBound=0)
    x9 = pulp.LpVariable("x9", lowBound=0)
    problem = pulp.LpProblem('0',pulp.LpMaximize)
    problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
    problem +=x1 + x2 +x3<= 74,"1" 
    problem +=x4 + x5 +x6 <= 40, "2"
    problem +=x7 + x8+ x9 <= 36, "3"
    problem +=x1+ x4+ x7 == 20, "4"
    problem +=x2+x5+ x8 == 30, "5"
    problem +=x3 + x6+x9 == 30, "6"
    problem.solve()
    print ("Результат:")
    for variable in problem.variables():
        print (variable.name, "=", variable.varValue)
    print ("Стоимость доставки:")
    print (abs(value(problem.objective)))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    x1 = 0.0
    x2 = 30.0
    x3 = 0.0
    x4 = 0.0
    x5 = 0.0
    x6 = 30.0
    x7 = 20.0
    x8 = 0.0
    x9 = 0.0
    Стоимость доставки:
    170.0
    Время:
    0.18919610977172852

    Программа для дополнительного условия №3
    from pulp import *
    import time
    start = time.time()
    x1 = pulp.LpVariable("x1", lowBound=0)
    x2 = pulp.LpVariable("x2", lowBound=0)
    x3 = pulp.LpVariable("x3", lowBound=0)
    x4 = pulp.LpVariable("x4", lowBound=0)
    x5 = pulp.LpVariable("x5", lowBound=0)
    x6 = pulp.LpVariable("x6", lowBound=0)
    x7 = pulp.LpVariable("x7", lowBound=0)
    x8 = pulp.LpVariable("x8", lowBound=0)
    x9 = pulp.LpVariable("x9", lowBound=0)
    problem = pulp.LpProblem('0',pulp.LpMaximize)
    problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
    problem +=x1 + x2 +x3<= 74,"1" 
    problem +=x4 + x5 +x6 == 40, "2"
    problem +=x7 + x8+ x9 <= 36, "3"
    problem +=x1+ x4+ x7 == 20, "4"
    problem +=x2+x5+ x8 == 45, "5"
    problem +=x3 + x6+x9 == 30, "6"
    problem.solve()
    print ("Результат:")
    for variable in problem.variables():
        print (variable.name, "=", variable.varValue)
    print ("Стоимость доставки:")
    print (abs(value(problem.objective)))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    x1 = 0.0
    x2 = 45.0
    x3 = 0.0
    x4 = 10.0
    x5 = 0.0
    x6 = 30.0
    x7 = 10.0
    x8 = 0.0
    x9 = 0.0
    Стоимость доставки:
    245.0
    Время:
    0.17000865936279297

    Программа для дополнительного условия №4
    from pulp import *
    import time
    start = time.time()
    x1 = pulp.LpVariable("x1", lowBound=0)
    x2 = pulp.LpVariable("x2", lowBound=0)
    x3 = pulp.LpVariable("x3", lowBound=0)
    x4 = pulp.LpVariable("x4", lowBound=0)
    x5 = pulp.LpVariable("x5", lowBound=0)
    x6 = pulp.LpVariable("x6", lowBound=0)
    x7 = pulp.LpVariable("x7", lowBound=0)
    x8 = pulp.LpVariable("x8", lowBound=0)
    x9 = pulp.LpVariable("x9", lowBound=0)
    problem = pulp.LpProblem('0',pulp.LpMaximize)
    problem += -7*x1 - 3*x2 - 6* x3 - 4*x4 - 8*x5 -2* x6-1*x7- 5*x8-9* x9, "Функция цели"
    problem +=x1 + x2 +x3<= 74,"1" 
    problem +=x4 + x5 +x6 == 30, "2"
    problem +=x7 + x8+ x9 == 30, "3"
    problem +=x1+ x4+ x7 == 20, "4"
    problem +=x2+x5+ x8 == 45, "5"
    problem +=x3 + x6+x9 == 30, "6"
    problem.solve()
    print ("Результат:")
    for variable in problem.variables():
        print (variable.name, "=", variable.varValue)
    print ("Стоимость доставки:")
    print (abs(value(problem.objective)))
    stop = time.time()
    print ("Время :")
    print(stop - start)
    


    Результат:
    x1 = 0.0
    x2 = 35.0
    x3 = 0.0
    x4 = 0.0
    x5 = 0.0
    x6 = 30.0
    x7 = 20.0
    x8 = 10.0
    x9 = 0.0
    Стоимость доставки:
    235.0
    Время:
    0.17965340614318848

    Вывод


    Полученные в публикации дополнительные условия к закрытой транспортной задаче позволяют получать решения, более приближенные к реальной ситуации по доставке товаров. Приведенные дополнения можно использовать по несколько в одной задаче применяя их в зависимости от возникшей ситуации. Исследован вопрос выбора решателя для транспортной задачи с условиями. Таким решателем является scipy. optimize, как более узко функциональный чем cvxopt и более быстрый чем pulp. Кроме того scipy. optimize имеет более компактную запись условий транспортной задачи, что облегчает его работу с интерфейсом.

    Всем спасибо за внимание!

    Ссылки


    1. Решение задач линейного программирования с использованием Python.
    2. CVXOPT Modeling.
    3. Optimization.
    4. Optimization with PuLP.
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 2
    • 0
      Полезно, спасибо! Интересно, а как можно учитывать «пробки» при учете времени. Ведь расстояние одинаковое, а время доставки — разное.
      • 0
        Я думаю, что увеличивать транспортный тариф в пересчёте времени на потерянную сумму в результате простоя.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.