数理解析研究所講究録 1207 巻 2001 年 22-32

22
不確実性下における需要処理配分問題
関西大学情報処理センター 北尾匡史 (Masachika KITAO)
北條仁志 (Hitoshi HOHJO)
大阪府立大学総合科学部
仲川勇二 (Yuji NAKAGAWA)
関西大学総合情報学部
寺岡義伸 (Yoshinobu TERAOKA)
大阪府立大学総合科学部

1. モデルと定式化
ある地域内に $m$ 個の需要点と呼ばれる点と 個の施設が散在している. そして需要点とをもつポアソン過程に従って要施設は固定されているものとする. 需要点 では, rate
$n$

$i$

$\gamma_{j}$求が発生する. この要求は全需要点に対して共通の種目の要求となっており, 発生の仕方は各需要点に関して独立であるものとする $(i=1,\cdots, m)$ . 各需要点で要求が発生するとこの要求を処理するため, 施設 $j$ へ送る $(j=1,\cdots, n)$ . 需要点 から施設 $j$ へ要求を送るに際し$i$ては,$d_{jj}$の時間がかかるものとし,また施設 $j$ では各要求に対して rate$\lambda_{j}$の指数分布に従って処理されるものとする.
ここで我々の問題は,rateで発生する需要点 での要求を$i$$\gamma_{j}$$n$個の施設の中のどれに送って処理すると最も短い時間で処理できるかということである. すなわち, 需要点 で発生した要求をどの割合で施設 へ送るかを考える. そこで,
$i$

$j$

$x_{jj}=$

需要点 で rate
$i$$\gamma_{j}$のポアソン過程で発生した要求のうち施設 $j$ へ配分される rateとすると,$x_{j1}+\cdots\cdots+x_{jn}=\gamma_{j}$,$x_{j1}\geq 0,\cdots\cdots,x_{n},\geq 0$を満足する$x_{j}j$(1)$(i=1,\cdots\cdots,m)$,を決定する問題ということになる. そうすると施設 $j$ への要求の到着は到着率$x_{j}=x_{1j}$\dagger $\cdots\cdots+x_{mj}$; $j=1,\cdots\cdots,n$をもつポアソン到着ということになり, 各 $j$ での処理時間も rateので,(2)$\lambda_{j}$をもつ指数分布に従う要求が発生してから処理を開始するまでの平均所要時間は待ち行列における$\mathrm{M}/\mathrm{M}/1$

待ちシステムの期待待ち時間と需要点から施設への移動時間として評価することができる.
目的は,

己分

このシステム全体で発生した要求の処理完了までの期待時間を最小にするような, ただし $i=1,\cdots\cdots,m$ ; $j=1,\cdots\cdots,n$ を決定することとなる.

$x_{jj}\geq 0$

2. 一般的定式化
あるシスデム内で複数の要求が発生し,これらの要求を複数の施設で処理しようとする

場合, システム全体としての要求処理完了までの時間を最小にするとは, 要求発生場所か23
ら施設までの移動時間を含め処理の待ち時間と処理に要する時間の和が最も長くかかりそうな部所を最小時間ですませるような要求配分を考えることに他ならない. そう考えると我々のモデルは下記のように定式化できる.
$w_{j}=$

施設 $j$ での待ち時間を示す確率変数$S_{j}=$

施設 $j$ での処理時間を示す確率変数$d_{jj}=$

需要点 から施設 $j$ への移動時間$\min_{X}$m, 霊 $\{E(W_{j}+S_{j})+u(x_{jj})d_{ij}\}$ ,$i$とすると,ここに,$E(Z)$ は確率変数 $Z$ の期待値を意味し,$u(x)=\{$

である.

また,

$X$

1,0,$u(\cdot)$(3)は$x\geq 0$$x\geq 0$

は制約条件を満足する $mn$ 組の配分 $x_{jj}>0$ 全体の集合である$(i=1,\cdots\cdots,m ; j=1,\cdots\cdots,n)$.

上記の定式化は, 要求の発生や処理がポアソン過程に従うことを限定せず, 独立性さえ仮定すればどのような確立法則に対しても通用できる定式化である. 要求の発生や処理がを待ち時間ポアソン過程に従うことに限定した場合の形式で表現してみよう.
$W_{j}$$\mathrm{M}/\mathrm{M}/1$とすると,(4),$E(W_{j})=, \frac{x_{j}}{\lambda(\lambda-x_{j})}$であることが知られており,$x,$

これに伴うトラフイック条件として,$<\lambda$が課せられることも知られている. 従って制約条件として,(5)$x_{1j}+\cdots\cdots+x_{mj}=x_{j}<\lambda$が要請される.
また, 後の議論のため,$R=\gamma,$$+\cdots\cdots\gamma_{m}$;$M=\lambda_{1}+\cdots\cdots+\lambda_{m}$とおくと, (1), (2) $,(5)$ より(6)$R<M$を前提とするのは言うまでもない. 次に施設 $j$ での処理時間も rate$\lambda_{J}$の指数分布を仮定してあるので$E(S,)= \frac{1}{\lambda}$,(7)

24となる. (1),(2) $,(3),(4),(5),(7)$ をまとめると, 我々の問題は次のような数理計画問題として表現することができる.
$\min_{x_{d}}\max_{jj},[\frac{1}{\lambda_{j}-x_{j}}+u(x_{ij})d_{jj}]$

subject to$x_{i1}+\cdots\cdots+x_{jn}=\gamma_{j}$,$x_{1j}+\cdots\cdots+x_{mj}=x_{j}<\lambda_{j}$(A),$x_{jj}\geq 0$$i=1,\cdots\cdots,m$; $j=1,\cdots\cdots,n$

ここに,$u(x)=\{$

1,0,

$x>0$
$x=0$

これは, 非線形の数理計画問題であり, 一般的取扱いは非常に難しい.

以後, 需要点から施設への移動時間がそれらの位置に関係せず一定と考えられる場合, および移動時間は需要点と施設の位置に依存するが施設の数が 2 の場合の特別な場合につぃて考察する. ここで, 需要点全体の集合を $D$ で, 施設全体の集合を $F$ で表すこととする.
すなわち,$D=\{1,\cdots\cdots n\}$;$F=\{1,\cdots\cdots m\}$.

3. 移動時間が一定の場合
本節では, 需要点から施設への移動時間がそれらの位置に関係せす一定の場合, すなわち
. $=d$$d\text{リ}$for all $(i,j)\in D\mathrm{x}F$(8)となっている場合を考察する. このとき問題 (A) の目的関数は,$\min_{x_{\ddot{y}}}\max_{jj}.[\frac{1}{\lambda_{j}-x_{j}}+u(x_{jj})d]$$= \min_{x_{j}}\max(j\frac{1}{\lambda_{j}-x_{j}})+d$(9)25となる.

これは,とりあえず$x$$\sim$を求める問題である. そこで,$\lambda_{1}-x_{1}=\cdots\cdots=\lambda_{n}-x_{n}=\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}$

を満足する

をそれぞれ

$x_{1},\cdots,x_{n}$$x_{1}.,\cdots,x_{n}$

.

とおくと,

すなわち
$x_{1}+\cdots\cdots+x_{n}=R$であるから.
$x_{J}$(10)$= \lambda_{j}-\frac{M-R}{n},\dot{]}=1,\cdots\cdots,n$

とおくと,$\min_{x_{/}}\max(\frac{1}{\lambda_{j}-x_{J}})=\frac{1}{\lambda_{j}-x_{J}^{\mathrm{s}}}$を得る. なぜならば (10) を満足しない$x_{j}$

に対しては少なくとも 1 つ(11)$\frac{1}{\lambda_{k}-x_{k}}>\frac{1}{\lambda_{J}-x_{J}.*}=\frac{n}{M-R}$となる$x_{k}$が存在する. もしそうでなければ, すべての D こ対して,$\lambda,\cdot-x,$であり,さら}こある$k$$\cdot$:$\leq\frac{M-R}{n}$[こ対して\lambda k-x、$< \frac{M-R}{n}$でなければならない. そうすると$\sum_{=/1}^{n}x_{j}<R$となってしまうからである. (9),(10) $,(11)$ を比較すると (10) で与えられる$x_{J}^{\mathrm{s}}$が目的関数を満足する施設 $j$ への配分の和であることがわかる.
さて, (10) によって, が求まると, 需要点$x_{1}x_{l}^{\mathrm{s}}*,\cdots,$$\mathrm{C}$から施設 $j$ への配分 x。は (1) と (2) の両方を満足しなければならないから, 需要点から施設への輸送費が一定である輸送問題

26
1

2

$x_{11}$$x_{12}$$\mathrm{D}\backslash \mathrm{F}$

1

2

...

...

$j$

...

$J2$

...

$x_{1j}$...

$x_{1n}$$\gamma$$1$$\gamma$$2$$x_{21}$$x_{22}$...

$x_{2j}$...

$x_{2’ r}$

...

...

...

...

...

...

x,-,

...

$x_{j_{J}}$.

...

$x_{jn}$

...

...

...

...

...

$x_{11}$...

...

$x_{\iota n},$.

$x,,,j$...

$x_{j}$...

$i$$x_{j\mathrm{I}}$

...

...

$m$

$x_{t|},$,.

$3\mathrm{p}+$$x_{2}$$x_{1}$

.

,

$x,$

,

.

$\equiv\beta+$...
$\gamma$$\mathrm{i}$...
$\gamma$$\mathrm{m}$$R$の解より得られることとなる. この解は無数に存在するが, 北西隅法による解が簡便な解といえよう.

4. 施設の数が 2 のとき
本節では, 需要点の個数は $m$ であるが施設の個数は 2 という簡単な場合を考察する.

したがって,$D=\{1,\cdots\cdots,m\}$

ここで,集合$D_{2}$$D$;$F=\{1,2\}$.の中で施設 1 への配分を行う需要点の集合と施設 2 への配分を行う需要点のを定義する. すなわち,$D_{1}=\{i|x_{j1}>0\}$

もちろん,$D_{1}\cap D_{2}=\emptyset$;$D_{2}=\{i|x_{j2}>0\}$とは限らない. このことは,点の可能性も考慮に入れていることを意味する.
そうすると,$x_{1}= \sum_{j\mathrm{e}lJ_{\mathrm{I}}}x_{j\mathrm{I}}$となる.

$D_{1}$

さらに実行可能なく鳥 ;$D_{1}$と$D_{2}$$x_{2}= \sum_{\iota \mathrm{e}lJ_{2}}x_{j2}<\lambda_{2}$に対して2 つの施設の両方に配分を行う需要27. .

$d$$\ovalbox{\tt\small REJECT} \mathrm{m}\mathrm{a}\mathrm{x}d,$$\mathrm{f}_{7}\ovalbox{\tt\small REJECT} \mathrm{m}\mathrm{a}\mathrm{x}d_{\ovalbox{\tt\small REJECT}}$-$\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$$tej)_{2}$$rej)_{1}$と定義する.
そうすると, 問題 (A) への$\mathit{1}2=2$に対する暫定問題として$\max(\frac{1}{\lambda_{1}-x_{1}}+d_{1},\frac{1}{h-x_{\tau\sim}}+d_{2})$$\min_{x_{l}},$subject to$x_{1},+x_{j2}=\gamma_{j}$也$\sum_{j\in\prime)_{1}}x_{i1}=x_{1}<$(T)$\sum_{\mathfrak{l}\in lJ_{2}}x_{j2}=x_{2}<\lambda_{2}$$x_{1}+x_{?,\sim}= \sum_{j=1}^{n}\gamma_{j}=R$$x_{\ovalbox{\tt\small REJECT}}>0$$i=1,\cdots\cdots,m$が考えられる. これは, よく観察するとていることがわかる. そして,

$d_{1}$と$d_{2}$; $j=1,2$$x_{j_{J}}$を決定する以前に$x_{1}$と$x_{2}$を決定する問題となっも可能な限り小さくなるように$D_{1}$とべきこともわかる. 次に,$x_{1}+x_{2}=R$であるから, 問題 (T) の目的関数を $u(x_{1})$ とおくと

$u(x_{1})= \min_{x_{\mathrm{I}}}\max(\frac{1}{\lambda_{1}-x_{1}}+d_{1},\frac{1}{l_{\sim}+x_{1}-R}+d_{2})$と書ける. そこで,

$x_{1}$に関する方程式(12)$\frac{1}{\lambda_{1}-X_{1}}+d_{1}=\frac{1}{l+x_{1}-R,-}+d_{?,\sim}$

は区間 $(R-l_{-},\lambda_{1})$ で必ず唯一根を持つから, これを$\frac{1}{l_{-}+x_{1}-R}+d_{2}$ ラ$x_{1}*$$R-$ 本くとおくと,$X_{1}\leq x_{1}^{\mathrm{s}}$(13)$u_{1}(x_{1})= \min_{x_{1}}\{$$\frac{1}{\lambda_{1}-x_{1}}+d_{1}$,$x_{1}^{\mathrm{s}}\leq x_{1}$く也$D_{2}$の元を選ぶ

28
したがって, この$x_{1}^{\circ}$により構成される配分が問題 (T) の制約条件を満たしているならば, この$\ovalbox{\tt\small REJECT}>0$$x_{1}*$と$x_{2}\ovalbox{\tt\small REJECT} R-x_{1}$が問題 (T) の解ということになり, このときの目的関数の値は,.

$u_{1}(x_{1}.)= \frac{1}{\lambda_{1}-x_{1}}$$+d_{1}= \frac{1}{\lambda_{2}+x_{1}-R}.+d_{2}$となる. また, 問題 (T) は我々の最終的な問題 (自) の暫定問題であることを考えると,$\max(d_{1},d_{2})=\max_{j}\min_{j}d_{jj}$で与えられることもわかる. そして, 上記の値が定まると (13) 式より記の値に一致しても, 他方は可能な限り小さい方が$u_{1}(x_{1}.)$$d_{1}$と$d_{2}$のどちらが上を減少させることもわかる.

が定まると (13) 式により目的関数の値が求まるから, 第 1 段階としての問題 (T) の$d_{2}$$D_{2}$$d_{1}$と$D_{1}$との設定は,$x_{1}=4- \frac{M-R}{2}$を満たす配分$x_{ij}$; $x_{2}=h- \frac{M-R}{2}$をもとに行い, その後 (12) 式の根として与えられるを施せばよいこともわかる.
以上の考察のもとに, 以下のような手順が得られる.

解法の手順

1. ます,$\min_{j}d_{jj}$を求め, 下記のように非減少順に並べる.

$d_{[1]}\leq d_{[2]}\leq\cdots\cdots\leq d_{[m]}$2.

$d_{[j]}$に対応する施設の番号を $[j]$ とおき,$[j]=\{\begin{array}{l}\mathrm{l}2\end{array}\}\Rightarrow x_{[j]1}=\{\begin{array}{l}\gamma_{i}0\end{array}\}$;$x_{[j]2}=\{\begin{array}{l}0\gamma_{j}\end{array}\}$

とおく.

3.

$x_{1}^{\mathrm{Q}}$と$x_{2}^{\mathrm{o}}$を$x_{1}^{\mathrm{Q}}=4- \frac{M-R}{2}$;$x_{2}^{\mathrm{o}}= \lambda_{2}-\frac{M-R}{2}$により定める.

4.

$d_{[i]m}$の大きいほうから順に$\sum_{-}^{m}x_{[j]1}$を計算し,$x_{1}$. .と$x_{2}$に従って修正29$n$’$\sum x_{[’ 11}\ovalbox{\tt\small REJECT} x$,あるい}ま$\sum x_{[\ovalbox{\tt\small REJECT} 12}\ovalbox{\tt\small REJECT} x_{2}$$j_{\ovalbox{\tt\small REJECT}}k$$1^{\ovalbox{\tt\small REJECT}}k$を満足する最大の5.

$k^{\mathrm{o}}$が$\sum$を$k$

作,1とする.

$k^{\mathrm{Q}}$に対して得られるものならば,$D_{1}=\{i|x_{[j]1}>0, i=k^{\mathrm{o}},\cdots\cdots,m\}$とし, 逆に,$D_{2}=D-D_{1}$に対して得られるものならば$\sum x_{[’]2}$$D_{1}=\{i|x_{[j]2}>0, i=k^{\mathrm{o}},\cdots\cdots,m\}$,$D_{1}=D-D_{2}$とする.

6.

ここで,

;

$d_{1}= \max_{\in j\mathit{1}J_{1}}d_{j1}$$d_{?,\sim}= \max_{j\epsilon/J_{2}}d_{j2}$とおき,$\frac{1}{\lambda_{1}-x_{1}}+d_{1}=\frac{1}{h+x_{1}-R}+d_{2}$の根を求め, これを7.

$x_{1}*>0$$x_{1}^{\mathrm{s}}$のとき,$D_{1}$に適当に入れ換えたり,とおく. また,および$\gamma_{j}$$\sum_{j\in/)_{\mathrm{I}}}x_{j1}=x_{1}*$$x_{1},\geq 0$

を満足する

8.

$x,*\leq 0$$x_{\ovalbox{\tt\small REJECT}}\geq 0$,$D_{2}$$x_{2}^{\iota}=R-x_{1}*$の中で移動時間とする.
$d_{j1}$と$d_{j2}$を分割することにより,;$\sum_{l\in/)_{2}}x_{\underline{?}},=x_{\gamma,\sim}^{\mathrm{s}}$$i\in D_{1}$

を求める.

;

$x_{j2}\geq 0$,$i\in D_{\gamma,\sim}$(北西隅法が使える. )のとき,$\frac{1}{A_{1}-R}+d_{1}\{\begin{array}{l}<>\end{array}\}\frac{1}{\lambda_{\underline{7}}-R}+d_{2}\Rightarrow\{\begin{array}{l}=x_{j[}=\gamma_{j},0x_{j2}=0,x_{j2}=\gamma x_{j|}\end{array}\}$とする.
この手順に従うと,目的関数の値$v^{*}$

は.

$\frac{1}{4-x_{1}*}+d_{1}=\frac{1}{\lambda_{2}-x_{\underline{?}}}$ $+d_{2}$,$x_{j}*>0$$v^{*}=\{$$\min(\frac{1}{\lambda_{1}-R}+d_{1},\frac{1}{\lambda_{2}-R}+d_{2})$,$x,\cdot\leq 0$の小さいほうから順30

5. 簡単な例
まず最初に, 需要点は 4 点, 施設は 2 施設あり$\gamma_{j}=1,$$i=1,\cdots\cdots,4$$j=1,2$$\lambda_{j}=2.5,$のボアソン発生とポアソン処理, そして移動時間は,12で与えられている場合を扱う.

であり,

3.

$\min_{/}$$d_{jj}$33221210$j\backslash i$

を小さいほうから順に並べると$\min_{j}d_{j}/\cdot$

012$i$

12,43$j$

11, 22となるから, 暫定的に

$x_{1}^{\mathrm{o}}=x_{2}^{\mathrm{o}}=2$$D_{2}=\{3,4\}$

したがって$D_{1}=\{1,2\}$が得られ$d_{1}=1$; $d_{2}=2$を得る. そうすると$\frac{1}{2.5-x_{1}}+1=\frac{1}{2.5-(4-x)}+2$

より.
$x_{1}$$=2.22$,$x_{2}$.

44
1$=1.78$となるから, 輸送問題

31
12$x_{11}$$x_{12}$$x_{21}$$x_{22}$$x_{31}$$x_{32}$$x_{41}$$x_{42}$

2.22

1.78

$i\backslash j$

1234$x_{j}$.

$\gamma$

1

1
114を北西隅法によって解くと, 最適解は,,$x_{11}=1$$x_{12}=0$となる. また,,,$x_{22}=0$$x_{31}=0.22$,$x_{32}=0.78$

このとき目的関数の値
$v$

もし,

.

$x_{21}=1$$\gamma_{1}=\gamma_{?}=1.2\sim$$v$.

,$x_{41}=0$,$x_{42}=1$

は$=4.75$$\gamma_{3}=\gamma_{4}=1$’,$x_{11}=1.2$$x_{12}=0$,とすると, まったく同様にして,$x_{21}=1.04$,$x_{22}=0.16$$x^{*}=2.24$$x_{31}=x_{41}=0$$x_{32}=x_{4\sim?}=1$

また$v^{\mathrm{s}}=4.85$となる.
次に, 需要点が 6 点, 施設が 2 施設あり$\gamma_{j}=1,$$\lambda_{J}=4,$$i=1,\cdots\cdots,6$$j=1,2$

そして$j\backslash i$

12

156が移動時間となっている場合を扱う.

378267.

$\min$$d_{\dot{\ovalbox{\tt\small REJECT}}}$

489591061011

は上の表の第 1 段で与えられが得られ.

32$x_{1}^{\mathrm{o}}=3,$$x_{2}^{\mathrm{o}}=3$であるから, 暫定的に
$D_{1}=\{4,5,6\}$$1_{\vee}$

たがって$D_{2}^{\cdot}=\{1,2,3\}$となり,$d_{1}=10,$$d_{?,\sim}=8$を得る. そうすると,$\frac{1}{4-x_{1}}+10$より,.
$x_{1}$$=2.31$$= \frac{1}{4-(6-x)}+8,2<x_{1}<4$が得られ,.
$x_{2}$$=3.69$より同様にして$x_{11}=x_{21}=x_{31}=0$,$x_{41}=0.31$$x_{21}=x_{22}=x_{32}=1$,$x_{42}=0.69,$.

,$x_{\mathit{5}1}=x_{61}=1$$x_{52}=x_{62}=0$が解となる. この時, 目的関数の値は$v$$=10.59$となる.

参考文献

Berman, O. and Larson, R. (1985) Optimal
Presence of Queuing, Transpotation Science, v19,$2\cdot \mathrm{F}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}\mathrm{y}$$\mathrm{C}\infty \mathrm{p}\mathrm{e}\mathrm{r}$Network Districting in the$\mathrm{p}.261\cdot 277$.

, R. B. (1990) Queuing theory.

Management Science, 2, D.

$\mathrm{P}$In Handbooks in Operations Research and, New York.
Heyman and. Sobel (eds).
$\mathrm{M}\mathrm{J}$$\mathrm{N}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{h}\cdot \mathrm{H}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{d}$