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

в 15:51, , рубрики: cvxopt, PuLP, python, алгоритм решения, математика, разработка под windows, транспортная задача, метки: ,

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

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

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

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

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

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

Решение закрытой транспортной задачи с дополнительными условиями средствами 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.

Автор: Scorobey

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js