問題の声明
サプライヤーと消費者の領土の不一致に関連する輸送問題を解決する必要性は明らかです。 ただし、追加の条件なしで輸送の問題を解決する必要がある場合、このような解決策は理論的にもソフトウェアによっても合理的に提供されるため、これは通常問題ではありません。
商品の供給者と消費者のための古典的な条件での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）
与えられた6変数のシステムは、輸送問題の典型的なものです。係数と変数の質量のリストCを考慮に入れると、ターゲットの関数を決定するために残ります：
問題= 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を一般条件に追加することにより、すべての変数Xに一度に制限を導入できることに注意してください。
クローズドトランスポートタスクの追加条件の形成
これらの条件の理由は異なる場合があります。たとえば、輸送の輸送能力の制限、考慮されていない通関の遅延、サプライヤーと消費者の優先順位とパリティなどです。 したがって、件名と制限の性質のみを示します。
さらに使用するために、クローズド輸送の問題について、次の追加条件に番号を付けます。
1.特定のサプライヤから特定の顧客への商品の供給量の特定のインストール。
これを行うには、対応する制限付きの新しい変数が導入されます。 たとえば、最初のサプライヤは、30個の商品を2番目の顧客-mass7 =（x [1] == 30）に正確に配送する必要があります。
2.特定の顧客に対する商品の供給量の変更。
これを行うために、商品の出荷量のテーブルの列の条件が変更されます。 たとえば、2人目の顧客の場合、注文量は45ユニットから30ユニットに減少しました。
条件の行mass5 =（x [1] + x [4] + x [7] == 45）は、
mass5 =（x [1] + x [4] + x [7] == 30） 。
3.サプライヤへの商品の供給量の上限を設定します。
これを行うには、商品の出荷量のテーブルの行の条件が変更されます。 たとえば、2番目のサプライヤの商品の配送量については、40以上からの制限があり、正確に40ユニットの商品を配送する必要が生じました。 条件変数mass2 =（x [3] + x [4] + x [5] <= 40）をmass2 =（x [3] + x [4] + x [5] == 40）に置き換えます。
4. 2番目と3番目のサプライヤの供給のパリティ
これを行うために、複数のサプライヤの供給量を平準化します。これは通常、ビジネス環境を改善するために行われます。 たとえば、輸送サービスの2番目と3番目のプロバイダーの商品の配送量は、それぞれ上記<= 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ソルバーを使用して、追加の条件で閉じたトランスポート問題を解決する
追加条件No.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ソルバーを使用して、追加の条件で閉じた輸送問題を解決します。 Pythonを最適化する
追加条件No.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)
結果：
楽しい：245.0
メッセージ：「最適化は正常に終了しました。」
nit：10
スラック：配列（[44.、10.、1.]）
ステータス：0
成功：真
x：配列（[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)
結果：
楽しい：170.0
メッセージ：「最適化は正常に終了しました。」
nit：7
スラック：配列（[44.、10.、16.]）
ステータス：0
成功：真
x：配列（[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)
結果：
楽しい：245.0
メッセージ：「最適化は正常に終了しました。」
nit：8
slack：配列（[29.、26.]）
ステータス：0
成功：真
x：配列（[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)
結果：
楽しい：235.0
メッセージ：「最適化は正常に終了しました。」
nit：8
スラック：配列（[39.]）
ステータス：0
成功：真
x：配列（[0.、35.、0.、0.、0.、30.、20.、10.、0.]）
時間：
0.05457925796508789
パルプPythonソルバーを使用して、追加の条件で閉じた輸送問題を解決する
追加条件No.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
おわりに
クローズド輸送の問題について出版物で得られた追加条件により、商品の配達の実際の状況により近いソリューションを得ることができます。 これらの追加は1つのタスクで複数使用でき、状況に応じて適用できます。 条件付きの輸送問題のソルバーを選択する問題が調査されます。 そのようなソルバーはシシーです。 最適化、cvxoptよりも機能が狭く、パルプよりも高速。 また、シシー。 最適化は、トランスポート問題の状態のよりコンパクトな記録を持ち、インターフェースとの作業を容易にします。
ご清聴ありがとうございました！