離散型最大原理による非線型輸送問題解法について
その他のタイトル On the Solving Technique of Non‑linear
Transportation Problem with Discrete Maximum Principle
著者 広田 俊郎
雑誌名 關西大學商學論集
巻 20
号 1
ページ 40‑50
発行年 1975‑04‑25
URL http://hdl.handle.net/10112/00021087
離散型最大原理による非線型輸送問題 解法について
広 田
俊 郎
l． は じ め に
工場一需要地間の輸送費用関数が線形である場合の最過輸送パターンを求 める技法は，踏み石法， MODI法， LPなどすでに開発しつくされ， また それらのアルゴリズムの意味も明らかにされている。それに対して，工場一 需要地間の輸送費用閲数が非線形である場合についての最適輸送パクーン導 出については，離散型最大原理を用いての解法などが示されているものの，
それらのアルゴリズムが，どのような現実的含意を持っているかについては 明らかとなっていない。そこで，本稿は，そのアルゴリズムのもつ現実的含 意を，とくに補助変数の意味を明らかにすることによって示そうとするもの
である。
2. 離 散 型 最 大 問 題 に よ る 非 線 型 輸 送 問 題 の 解 法
工場が2ケ所で，倉庫が10ケ所ある場合を考える。そのとき， 2工場の総 供給量と， 10倉庫の総需要量は常に等しいとする。 Xiを工場i(i=l, 2)
離散型最大原理による非線型輸送問題解法について（広田俊） （41) 41 の供給量， Diを倉庫j(j= 1, 2…..., 10)の需要量とすると， 前述の仮 定より
2 10
•こ瓦＝四Di
9‑1 J ‑1
(1)
が成り立つ。
また，商品を工場から倉庫へ輸送するときの輸送費用は次式で与えられる とする。
Fp(O) ＝ap伊 十B戌＋rp(O) (2)
ここで，
Fj(O)；工場iから倉庫がヽ製品を 0単位輸送するときの輸送費用。
この輸送開数は， i) 大量輸送によるメリットがある場合，
佑">o, ii)段取費が無視できない大きさのとき T1"(fJ)>O, などとすることによって，色々な非線形の費用状況を取り扱え るようになっている。
さて以上のような状況のもとで，
1, 2
] = :E :E F;• (8) (3)
n‑1 n~l
を最小にするような輸送パターンはいかなるものかが問題とされる。この問 題を離散型最大原理を用いて解くために，多段決定問題としてこの問題を解 釈する。
段階ー1,倉庫が1ケ所あるとしたとき，その需要量を満足するように，
2ケ所の工場から商品を輸送するときの最適パターンを見つける。
段階ー2'倉庫が2ヶ所あるとしたとき，その需要量を満足するように2 ケ所の工場から商品を輸送するときの最適パターンを見つける。
同様にして，
段階ー10,倉庫が10ケ所あるとき， その10ケ所の需要量を満足するよう に， 2ケ所の倉庫から商品を輸送するときのパターンを見つける。
以上のようにして，最適な工場一需要地間の輸送パターンを求めることと して，具体的な解の禅出過程を述べよう。
今，変数を次のように定義する。
〔状態変数〕
(1)
r ;Fl工場から最初のnヶ所の倉庫に輸送された製品の単位数
(1)
Cn ；最初のnヶ所の倉庫に製品を輸送したために必要とされた総輸送費用
〔決定変数〕
{}" ；凡工場から， n番目の倉庫への輸送量
これらの変数を用いて，状態方程式は次のように示される。
炉＝ X” ー 1+0•
Cn=C•-1+Fげ({)”)＋Fが(D ―か）
︑J ) 4 5
︵
︵
．
そして，境界条件は次のように示される。
x•=O C•=O x10=X1
ヽノ
︑ー
︑ー ノ 6 7 8
︵
︵
︵
(1) 時間的広がりを持った経済問題において，ある時点における経済諸量は，過去 の経済諸最の累積したものであることが多く （ストック）， 最大原理を用いての 最適制御問題においては，それを状態変数としてとらえる。空間的な広がりをも った問題に，この最大原理を適用するためには，やはり，諸量を前の段階から累 積したものと考えることが必要なため， x•, C"の上のような定義が行なわれた のである，と考えられる。
離散型最大原理による非線型輸送問題解法について（広田俊） （43) 43 また，決定変数には次のような制約条件がつく。
0~(j•~D.. (n= 1, 2,……,10) (9) ここで，ハミルトニアン H"と補助変数Z1"，かを導入する。
H=Z1"(X ー1+{})+z2•{C”—l+Fl"({}”) ＋Fが(D謬ーが）｝ （10) (n= 1, 2・・・・・・10)
ここで，補助変数は次のように定義されている。
Zt•-I = iJH•
む•-1
Zが―1 OH oC•-1
しかしながら，上式の右辺を計算することにより，
. = oH•
紐n‑1 Z1", OH oC―1 =z2•
を得，この問題では，
z1•-1 = z1•
Z2"-l=z2•
(11)
(12)
(13)
(14)
であることがわかる。ところで，炉＝100＝指定， CN＝未定で，評価関数は ]=Ox炉 ＋lXCNであって， その中に XNは含まれないから， 補助変数の 境界条件として，
z110= k （＝任意の定数） (15)
z210= 1 （＝評価関数のCNの係数） (16)
が成立しなくてはならない。だから， （13), (14), (15), (16)より，各段 階を通じて，
z1•=k (n=O, 1, 2, ・・・・・・, 10)
Z2" = 1 (n=O, 1, 2,......, 10)
となる。そこで，これらの値をハミルトニアンに代入して，
(17)
•(18)
H•=k(x• ー 1+{J•) ＋ C• ー 1+F1•({J•) ＋ Fが (D.-{J•) （19)
が得られる。つまり
H霧＝ g({}•) (20)
が得られたわけである。
(1)式の輸送コスト関数の係数として，表 1のように仮定し，各倉庫の需要
(2)
量を同じく表1におけるように仮定することにする。
そのとき，最適解を見つけるための計算手順は次のようになる。
a) kに任意の値をあてはめる。
b) n= 1,すなわち1段階目に位置するとする。 ただし， d)までの作 業を完了し， e)のステップを経て， b)にもどったときには，段階数 が一つ進められる。
c)(19) 式で定義したハミルトニアン H• が最小になるように，がを決定す る。つまり，がのおのおのの値に対するハミルトニアン H• を計算し，
(2) この仮設例は，宇野利雄，菊池豊彦著「最大原理入門」に掲載されていたもの を利用したものである。
離散型最大原理による非線型輸送問題解法について（広田俊） （45) 45
表ー1
倉 庫 需 要 量D,
1 I 10 II。
工 場 1 か ら a
2 3 4 5 6 7 8 9
5 5 5 5 5 0 5 0 2 4 1 1 2 1 1
ー
゜
0 0
/
3 I r
1 2 3
0 1 0 0 0 0 0 0 8 0
ー
工 場 2 か ら a I (3 I r
O I 3.1 I 2.0 0
゜
I 4.1 I 0 2.1゜
5 5 5 3 6 6
． ．
1 2 1 5 0 0
．
．
0 0 0 0 0 0
l
‑
10 I 20 IIo I 6 I I
0.1
︒
゜
0.01
1.1 I o
2.6,I 0 3.0 I 0 0.2 i 1.0 I s.o I
0 I 2.0 I 0 0 I 2.0 I 0 5.0 I 0
•—ー・ー•‑ ‑‑ ‑
その中から H＂を最小にするかを求める。
d)次に状態変数が， C1を求める。
e), d)が終るとb)にもどり， これまでの計算を n=lO, つまり10段 階目まで繰り返す。
f) X110=100ならば， 指定された境界条件が満されているから， 計算は 完了， そうでないならばKの値を修正して初めから計算をやり直す。
またこの手続きをフロー・チャートで示すと図1のようになる。
さて，以上の手順にしたがって計算を実行することにより，表2のような 解を得た。次にこの計算手順がどういう意味をもっており，それが解にどの ように表わされているかを次に論じよう。
亭亨宇
ニを〗
G
亜 つ
図 1
表ー2
倉 庫 ！ 工 場1から！工場2から 1 10
゜
2 25
゜
3 5 40 4 15
゜
5 5
゜
6
゜
157 20
゜
8
゜
15， ゜ 10
10 20
゜
I離散型最大原理による非線型輸送問題解法について（広田俊） （47) 47
3. 離 散 型 最 大 原 理 に よ る 非 線 型 輸 送 問 題 の 解 法 の 含 意
今，第1段階を考えよう。その段階における最適な決定変数は，
H1 = k(x~ ＋が）＋ C・＋ F沢が）＋ F21(D1 ーが）
=kが＋F沢が）＋F11(D1ーQI)
を最小するようながである。
(21)
このことの含意は，第1段階における最適なかは，輸送コスト F沢が）
+F21(D1ーが）を最小にするがと必ずしも一致しないということである。
通常k<Oが仮定されるから，ががある大きさを持つとき， F11（が）＋F21 (D1‑‑‑.01)の部分が最小の場合より少し大であっても， それがハミルトニア ン HIを最小にするがであることがある。すなわちが (=k)は， 工場が 供給を行ったことを評価する評価値と考えられ，それを考慮に入れて各段階 での輸送量決定を行うことによって，全体として，倉庫の需要と工場の供給 の一致を条件とする最適輸送パクーンが得られるのである。
、また，第n段階を考えよう。その段階における最適な決定変数は，
H•=k(x" ― 1 十が）＋ C＂― 1+F1精 (O•) +Fが (Dr—か）
= (kx―I+C ―l)+kが＋Fl"（か）＋Fが(D.-0•) (22)
を最小にするようながである。 この式の kx•-1+C算ー 1 は， すでにその大き さが確定されている。だから，第 段階における決定変数の選ぴ方は第1段 階のそれと全く同じこととなる。すなわち，第 段階における輸送コストの みならず，工場の供給行動にある評価を加えて，最適な決定変数がを決定 するのである。
このような段階を繰り返して，第10段階目おける最適な決定変数の選択を 終えた後に， 第1工場の累積供給量X1=100のとき， 工場の供給量の評価
値Z1(=k)は適正なものであったと言えるのである。
通常の資源配分問題では，幾つかの条件のもとで，市場で形成された価格 をもとにして，最適な資源配分が達成されると論ぜられる。だが，ここで取 りあげている輸送問題のような企業内の限定された資源の配分にかかわる問 題，丁度ここで取り扱っているような企業内でのロジスティック問題のよう に市場が欠落している問題の場合には，市場で形成された価格的指標にのみ 頼るわけにはいかず，企業内部で想定した価値的指標を考慮して資源の量的 制約を満足させることが必要であり，そしてそのための価値的指標として，
が(=k)が機能しているのだ，というのが本稿の結論である。
（数学注）ケイツ，ファンおよびワンの離散型最大原理について。
彼らの離散型最大原理の主要な要素は次のように示される。
(1) 状態方程式
r = T”(x•-1, 0"）
ここで，
か； n期（段階）の状態変数（ベクトル）
か； n期（段階）の決定変数（ベクトル）
(2) 決定変数（ペクトル）の束縛条件 g((}")~o
(3) 評価関数
￠（がり
ここで，
N；終期（最終段階）
(23)
(24)
これらの要素で問題を把握するが，それを解くのにあたっては，補助変数
（ペクトル）およびハミルトニアン H"を考える。
離散型最大原理による非線型輸送問題解法について（広田俊） （49) 49 (4) ハミルトニアン H
H"＝Zl"XI" ＋Z2X2十・・・・・・・・・十zpx,＂ (25)
＝四ZfTiu（か―1，か）
ここで，（X1, X2,…x,）と (z1, Z2,…， z,)
は 双 対 空 間 を な し ， 前 者 の ベ ク ト ル は 実 体 的 な も の を 表 わ す の に 対 し ， 後 者 は価値的なもの， shadowprice的なものを示している。
(5) 補 助 変 数 Z
Z―I ＝ i)x• ー 1iJH• (26)
この式は， z•-1 Iま X” ー 1 が H• しこどれだけ寄与するかを示す尺度であるこ とを意味する。と同時に， H” を構成するものとして， z• があったから，
OH
oxn‑1 ￠＝ (Z) (27)
である。 したがって (26)式は， zの 変 化 を 指 示 す る 定 差 方 程 式 で も あ る。
(6) 境 界 条 件
ま た ， 終 期 に お い て ， 状 態 変 数 （ ベ ク ト ル ） の 値 が 指 定 さ れ て い る と き ， 境 界 条 件 と し て ， 状 態 変 数 と 補 助 変 数 に 関 し て ， あ る 値 が 指 定 さ れ るc
(7) ハミルトニアン H＂の最大（小）化
離散型最大原理によれば， 最 適 な 関 数 パ ク ー ン を も た ら す 解{j"が 満 足
す べ き 必 要 条 件 は ， 炉 が 各 段 階 で ハ ミ ル ト ニ ア ン H"を 最 大 に す る こ と で ある。
H"＝区N Zi"Tj(X ー1'{}n)→Max(min)
i‑1
〔参考文献J
宇野利雄，菊池豊彦，「最大原理入門」， 1967年，共立出版
