数理解析研究所講究録 1297 巻 2002 年 136-144

136
直角ノルムを用いた多目的配置問題の有効解
金正道 Masamichi KON

弘前大学理工学部 Faculty of Science and Technology, Hirosaki University

概要における直角ノルムを用いた多目的配置問題を考える。 その問題の有効解の特徴付けを与え、 すべての有効$\mathbb{R}^{n}$解を求めるアルゴリズムを提案する。

1. はじめににおいて需要点が与えられたとき、 新たに単一の施設を配置する位置を決める問題は単一$\mathbb{R}^{n}$

施設配置問題とよばれる。 この問題は通常、 施設と需要点の間の距離を含む関数の最小化問題として定式化される。 需要点$||$

$d_{i}\equiv(d_{i}^{1}, d_{\dot{0}}^{2}, \cdots, d_{\dot{l}}^{n})^{T}\in \mathbb{R}^{n},$. [が与えられていると仮定する。

$D\equiv\{d_{1}, d_{2}, \cdots, d_{m}\}$

して$x\equiv(x^{1}, x^{2}, \cdots, x^{n})^{T}\in \mathbb{R}^{n}$こで考える問題はと$\mathbb{R}^{n}$上定義された直角ノルムを配置する施設の位置を表す変数とし、とする。 一般性を失うことなく、 各 $j\in J\equiv\{1,2, \cdots, n\}$ と任意の$D\not\subset\{(x^{1}, x^{2}, \cdots, x^{n})^{T}\in \mathbb{R}^{n} :$n$$i\in M\equiv\{1,2, \cdots, m\}$x^{j}=x_{0}\}$に対$x_{0}\in \mathbb{R}$であると仮定する。 もし、 この仮定が満たされなければこより低い次元の問題に帰着できる。 多目的配置問題は次のように定式化される。

(P)$\min f(x)\equiv(||x-d_{1}||_{1}, ||x-d_{2}||_{1}, \cdots, ||x-d_{m}||_{1})^{T}$$X\in \mathrm{R}^{\mathfrak{n}}$[こ対して $f(x)\leq f(x_{0})$ かつ $f(x)\neq f(x_{0})$ となるが(P) は有効解を求める問題である。
$E(D)$
をを集合
存在しないとき(P) の有効解という。
(P) のすべての有効解の集合とする。 上の定義
$x\in \mathbb{R}^{n}$$x_{0}\in \mathbb{R}^{n}$$x_{0}$

よりとなることがわかる。 多目的配置問題の有効解を特徴付けるために次の minisum 型配置$D\subset E(D)$問題も考える。

$\min_{X\in \mathrm{R}^{n}}g(x)\equiv\dot{.}\sum_{=1}^{m}\lambda^{i}.||x-d_{i}||_{1}$$(\mathrm{P}\lambda)$

ここで$\lambda^{i}$は各適解の集合を$\mathbb{R}^{2}$

および$d_{i},$$i\in M$

$S^{*}(\lambda)$に付随する正の重みである。

とし、$(\mathrm{P}\lambda)$のすべての最で定義する。

における (P) のすべての有効解の集合はそれぞれ [1] および [6] におけるアルゴリズムを$\mathbb{R}^{3}$

用いて求めることができる。

$(\mathrm{P}\lambda)$

は [2] におけるアルゴリズムを用いて解くことができる。 本稿では、における直角ノルムを用いた (P) およひ

第 2 節では、$\lambda\equiv(\lambda^{1}, \lambda^{2}, \cdots, \lambda^{m})^{T}$$(\mathrm{P}\lambda)$$(\mathrm{P}\lambda)$$\mathbb{R}^{n}$を考え、 $E(D)$ を求めるためのアルゴリズムを提案する。

の最適解のいくつかの性質を与える。 第 3 節では、$(\mathrm{P})\lambda$の最適解を用いて (P) の有

効解のいくつかの性質を与える。 第 4 節では、 $E(D)$ を求めるフレーム生成アルゴリズムを提案する。 最後に、 第 5 節において結論を述べる。

2.

$(\mathrm{P}\lambda)$の最適性 本節では、次の定理は (P) の有効解と定理 1([8] 参照)$x_{0}\in \mathbb{R}^{n}$の最適解のいくつかの性質を与える。

$(\mathrm{P}\lambda)$$(\mathrm{P}\lambda)$の最適解の間の関係を与える。

が (P) の有効解であるための必要十分条件は$x_{0}$がある $\lambda>0$ に対するの最適解になることである。
定理 1 より $E(D)$ は次のように表すことができる。

(1)$E(D)=${$x^{*}\in \mathbb{R}^{n}$:$x^{*}\in S^{*}(\lambda)$

for some $\lambda>0$ }$(\mathrm{P})\lambda$

137
よって、 以下では$(\mathrm{P}\lambda)$$(\mathrm{P})\lambda$

の目的関数

$g$

の最適解の性質を調べる。

は$g(x)= \sum_{i=1}^{m}\lambda^{i}||x-d_{i}||_{1}=\sum_{i=1}^{m}\lambda^{i}\sum_{j=1}^{n}|x^{j}-d_{i}^{j}|=\sum_{j=1}^{n}\sum_{i=1}^{m}\lambda^{i}|x^{j}-d_{i}^{j}|$と書き直せるので$\in S^{*}(\lambda)$$(\mathrm{P}\lambda)$

は $n$ 個の独立な 1 次元の問題に帰着される。 すなわち、 $x^{*}\equiv(x^{1*}, x^{2*}, \cdots, x^{n*})^{T}$であるための必要十分条件は各(Pj)$x^{j*},$$j\in J$ が次の

1 次元の問題の最適解となることである。

$\min_{x\in \mathrm{R}}gj(x)\equiv\sum_{i=1}^{m}\lambda^{i}|x-d_{i}^{j}|$これらの 1 次元の問題は [2] におけるアルゴリズムを用いて解くことができる。 各 $j\in J$ に対して

する
$n\}$

$(\mathrm{P}_{j})$のすべての最適解の集合を

に関しても

$f$

:

$\mathbb{R}arrow \mathbb{R}$$(\mathrm{P}_{1})$$S_{j}^{*}(\lambda)$で定義する。 以下、$(\mathrm{P}_{1})$を考える。 他の$(\mathrm{P}_{j})$に対$\lambda$, $j\in\{2,3,$$\cdots$,と同様の結果が得られる。

を凸関数とする。 その左側微分、右側微分および劣微分をそれぞれ$[perp] dfx[perp] dx^{-}’+_{dx}^{dfx}$

および$f(x)$

で定義する。 すなわち$\frac{df(x)}{dx^{-}}=\lim_{\alpha\uparrow 0}\frac{f(x+\alpha)-f(x)}{\alpha},$$\frac{df(x)}{dx^{+}}=\lim_{\alpha\downarrow 0}\frac{f(x+\alpha)-f(x)}{\alpha}$

および$\partial f(x)=[\frac{df(x)}{dx^{-}},$ $\frac{df(x)}{dx^{+}}]\equiv\{y\in \mathbb{R}$である。

[4] 参照)$x\in \mathbb{R}$とする。

$x_{0}\in \mathbb{R}$:$\frac{df(x)}{dx^{-}}\leq y\leq\frac{df(x)}{dx^{+}}\}$(例えば、

において $f$ が最小となるための必要十分条件は $0\in\partial f(x_{0})$ となることである。

[こ対して $L(x)\equiv\{i\in M : d_{i}^{1}<x\},$ $R(x)\equiv\{i\in M : d_{i}^{1}>x\}$ および $I(x)\equiv\{i\in M : d!|=x\}$$(\mathrm{P}_{1})$の目的関数

は区分的線形凸関数となり、 それは各$g_{1}$$d_{k}^{1},$$k\in M$ においてのみ微分不可能であり$\frac{dg_{1}(x)}{dx^{-}}|_{x=d_{k}^{1}}=$$\lambda^{i}-$$\sum$$\sum$$\lambda^{i}$,$\frac{dg_{1}(x)}{dx^{+}}|_{x=d_{k}^{1}}=$$i\in R(d_{k}^{1})\cup I(d_{k}^{1})$$i\in L(d_{k}^{1})$$\sum$$\lambda^{:}-$$\mathrm{i}\in L(d_{k}^{1})\cup I(d_{k}^{1})$$\sum$$\lambda^{i}$$:\in R(d_{k}^{1})$

およひ

(2)

$\partial g_{1}(d_{k}^{1})=[\sum_{i\in L(d_{k}^{1})}\lambda^{i}-\sum_{i\in R(d_{k}^{1})\cup I(d_{k}^{1})}\lambda:,\sum_{i\in L(d_{k}^{1})\cup I(d_{k}^{1})}\lambda^{i}-\sum_{i\in R(d_{k}^{1})}\lambda^{\mathrm{i}}]$を得る。 (2) より$d_{k}^{1}\in S_{1}^{*}(\lambda)$となるための必要十分条件は$\frac{dg_{1}(x)}{dx^{-}}|_{x=d_{k}^{1}}=\sum_{i\in L(d_{k}^{1})}\lambda^{:}-\sum_{i\in R(d_{k}^{1})\cup I(d_{k}^{1})}\lambda:\leq 0$

(3)

$\{$

$\frac{dg_{1}(x)}{dx^{+}}|_{x=d_{k}^{1}}=\sum_{i\in L(d_{k}^{1})\cup I(d_{k}^{1})}\lambda^{i}-\sum_{i\in R(d_{k}^{1})}\lambda^{i}\geq 0$となることである。 $d_{\min} \equiv\min\{d_{i}^{1} : i\in M\}$ とし $d_{\max} \equiv\max\{d_{i}^{1} : i\in M\}$ とする。
補題 1([6])任意に固定された $\lambda>0$ に対して $S_{1}^{*}(\lambda)\subset[d_{\min}, d_{\max}]$ となる。

3. 有効解の性質 本節では、$(\mathrm{P}\lambda)$の最適解を用いて (P) の有効解のいくつかの性質を与える。

138$x_{0}\ovalbox{\tt\small REJECT}(x\ovalbox{\tt\small REJECT}, x3, \cdots, x\ovalbox{\tt\small REJECT})^{T}\in \mathbb{R}^{n}$の交点の集合を(こ対して$x\ovalbox{\tt\small REJECT}\in\{d\ovalbox{\tt\small REJECT}_{\ovalbox{\tt\small REJECT}}i\in M\},$$j\in J$であるとき

$x_{0}$

を交点とよぶ。 すべて

で定義し

$I$

$d_{\min}^{j} \equiv\min\{d_{i}^{j} :i\in M\},$$d_{\max}^{j} \equiv\max\{d_{i}^{j} :i\in M\},$$j\in J$とおく。 このとき$B\equiv\{(x^{1}, x^{2}, \cdots, x^{n})^{T}\in \mathbb{R}^{n} :を交点ボックスとよぶ (図 1) 。定理 1 と補題 1 より

図 1
を$\{e_{1}, e_{2}, \cdots, e_{n}\}$ある。

$\mathbb{R}^{n}$$j’\neq j$$x_{k}^{j’}=x_{h}^{j’},$

存在しないとき$x_{k}$

を

各 $j\in J$ [こ対して$E(D)\subset B$となる。

交点, 交点ボックス, ボックスの標準基底とする。 すなわち、 各 $e_{j},j\in J$ は第$x_{k}\equiv(x_{k}^{1}, x_{k}^{2}, \cdots, x_{k}^{n})^{T}$$x_{k}^{j}<x_{h}^{j}),$d_{\min}^{j}\leq x^{j}\leq d_{\max}^{j},j\in J\}$

$x_{h}$と$x_{h}\equiv(x_{h}^{1}, x_{h}^{2}, \cdots, x_{h}^{n})^{T}$

かつ $x_{h}^{j}<x_{s}^{j}<x_{k}^{j}$の$e_{j}$$d_{[1]}^{j},$ $d_{[2]}^{j},$(resp.

$j$

成分が 1 で他の成分は 0 でを交点とする。 各 $j\in J$ (こ対して$x_{k}^{j}<x_{s}^{j}<x_{h}^{\mathrm{j}}$) となる$x_{k}^{j}>x_{h}^{j}$(resp.

$x_{s}\equiv(x_{s}^{1}, x_{s}^{2}, \cdots, x_{\theta}^{n})^{T}\in I$

が-方向隣接交点 (resp. $-ej$ -方向隣接交点) という。

$\cdots,$$d_{[m_{\mathrm{J}}]}^{j}$を$d_{1}^{j},$$d_{2}^{j},$$\cdots,$$d_{m}^{j}$の中のすべての異なる実数で $d_{[1]}^{j}<d_{[2]}^{j}<\cdots<$であるとし、$d^{\mathrm{j}}$$[m_{\mathrm{j}}]$$F_{2k-1}^{j}\equiv\{d_{[k]}^{j}\},$$k=1,2,$$d_{[k+1]}^{j}],$$k=1,2,$$\cdots,$ $m_{j}$とし$F_{2k}^{j}\equiv[d_{[k]}^{j},$とする。 $k_{j}\in\{1,2, \cdots, 2m_{j}-1\},$ $j\in J$ [こ対してし$k_{1},$$k_{2},$$\lambda>0$$F_{k_{n}}^{n}$$\cdots,$$k_{n}$のなかで$k$個が偶数のとき$\cdots$, mj–l$F_{k_{1}}^{1}\cross F_{k_{2}}^{2}\cross\cdots\cross F_{k_{\mathfrak{n}}}^{n}$$F_{k_{1}}^{1}\cross F_{k_{2}}^{2}\cross\cdots\cross F_{k_{\mathrm{n}}}^{n}$を$k$をボツクスとよぶ。 さら [こ、 も-次元ボックスとよぶ (図 1)

を任意に固定するとある $k_{j}\in\{1,2, \cdots, 2mj-1\},$ $j\in J$ に対して。

$S^{*}(\lambda)=F_{k_{1}}^{1}\cross F_{k_{2}}^{2}\cross\cdots\cross$となる。 ゆえに、 $E(D)$ はいくつかのボックスの和集合となる。 $E(D)$ に含まれるすべての 1-次元ボッ139
クスの和集合を $E(D)$ のフレームとよぶ。
定理 2([11])となり$h_{1}(w)$$w_{1}<w_{2}$とを$h_{2}(w)$上定義された凸関数とし、 各 $i=1,2$ に対して h。は$\mathbb{R}$とする。 このとき、 与えられた任意の$w_{i}$にお$\mathrm{A}\mathrm{a}$て最小に対してある $\theta\in[0,1]$ が存在して$\overline{w}\in[w_{1}, w_{2}]$$\overline{w}$において $\theta h_{2}(w)+(1-\theta)h_{1}(w)$ が最小となる。

系 1([7])であり、$x_{2}^{j_{0}}$く。 もしとする. ある $j_{0}\in J$ (こ対して$x_{1}\equiv(x_{1}^{1}, x_{1}^{2}, \cdots, x_{1}^{n})^{T},$ $x_{2}\equiv(x_{2}^{1}, x_{2}^{2}, \cdots, x_{2}^{n})^{T}\in B$$x_{1}^{j}=x_{2}^{j},$と仮定する。 $x^{*}\equiv\alpha x_{1}+(1-\alpha)x_{2},$ $\alpha\in(0,1)\equiv\{y\in \mathbb{R}:0<y<1\}$ とお$j\neq j_{0}$$x_{2}\in E(D)$$x_{1},$$x_{1}^{j_{0}}\neq$

ならば $x^{*}\in E(D)$ となる。

系 1 より、 もしあるボックスのすべての端点が (P) の有効解ならばそのボツクスの任意の点は (P) の有効解となる。
定理 3([6])となり$h_{1}(w)$$w_{1}\leq w_{2}$と$h_{2}(w)$を$\mathbb{R}$

上定義された凸関数とし、 各 $i=1,2$ に対してとする。 このとき、 与えられた任意の{$\theta\in[0,1]$:$\overline{w}$$\overline{w}\in[w_{1}, w_{2}]$$h_{:}$

は$w_{i}$にお$\mathrm{A}^{\mathrm{a}}$

て最小

に対して

minimizes $\theta h_{2}(w)+(1-\theta)h_{1}(w)$ }は閉区間となる。
系 2([7])$x_{k}^{j}\}\neq\emptyset$の$x_{k}$$e_{j}$$x_{h}\equiv(x_{h}^{1}, x_{h}^{2}, \cdots, x_{h}^{n})^{T},$$x_{k}\equiv(x_{k}^{1}, x_{k}^{2}, \cdots, x_{k}^{n})^{T}\in E(D)\cap I\}$と仮定する。 各 $j\in J_{0}$ [こ対してもし-方向隣接交点 (resp.

$-e_{j}$$x_{h}^{j}>x_{k}^{j}$(resp.

$x_{h}^{j}<x_{k}^{j}$

こ対して $J_{0}\equiv\{j\in J$ :) ならば-方向隣接交点) とする。 このとき、 ある$x_{h}^{\mathrm{j}}\neq$$y_{j}\equiv(y_{j}^{1}, y_{j}^{2}, \cdots, y_{j}^{n})^{T}$$j_{0}\in J_{0}$をが存在して $y_{j_{0}}\in E(D)$となる。
系 1 と 2 より $E(D)$ は連結であり、 (P) の任意の 2 つの有効解の間には“ジグザグパス” が存在する。 もし、 $E(D)$ のフレームが求まれば $E(D)$ が構成できる。 次節では、 $E(D)$ のフレームを求めるアルゴリズ

ムを与える。

4. すべての有効解を求めるアルゴリズム 本節では、 $E(D)$ を求めるフレーム生成アルゴリズムを提案する。
フレーム生威アルゴリズムにおいて、 交点が (P) の有効解であるかどうかを調べる必要がある。 そのため、 以下でどのように調べるかを述べる。

を交点とする。 定理 1 より、 $x_{0}\in E(D)$ となるための必要十分条件はあるとなることである。 (3) より、 $\lambda>0$ に対して $x_{0}\in S^{*}(\lambda)$ となるための必要十分$\lambda>$$x_{0}\equiv(x_{0}^{1}, x_{0}^{2}, \cdots, x_{0}^{n})^{T}$$0$に対して $x_{0}\in S^{*}(\lambda)$

条件は$j\in J$$\frac{dg_{j}(x)}{dx^{-}}|_{x=x_{0}^{\mathrm{j}}}=\sum_{i\in L_{j}(x_{0}^{j})}\lambda^{i}-\sum_{i\in R_{j}(x_{0}^{j})\cup I_{j}(x_{0}^{J})}\lambda^{i}\leq 0,$

(4)

.

$\{$

$\frac{dg_{j}(x)}{dx^{+}}|_{x=x_{0}^{j}}=\sum_{:\in L_{j}(x_{0}^{j})\cup I_{j}(x_{0}^{j})}\lambda^{i}-$$\sum \mathit{9}$$i\in R_{j}(x\mathit{9}$、\lambda i$\geq 0,$$j\in J$、となることである。 ここで、 各 $j\in J$ [こ対して $L_{j}(x_{0}^{j})\equiv\{i\in M:d_{i}^{j}<x_{0}^{j}\},$ $R_{\mathrm{j}}(x_{0}^{j})\equiv\{i\in M:d_{i}^{j}>x_{0}^{j}\}$ ,となるための必要十分条件は (4) をみたす
$I_{j}(x_{0}^{j})\equiv\{i\in M:d_{i}^{j}=x_{0}^{j}\}$ である。 ゆえに、 $x_{0}\in E(D)$$\lambda>$$0$が存在することである。 各 $i\in M,$ $j\in J$ に対して
$a_{ij}=\{$-1+1$a_{i,n+j}=\{$

-1
+1

if
if

$i\in L_{j}(x_{0}^{j})$$i\in R_{j}(x_{0}^{j})\cup Ij(x_{0}^{j})$ifif$i\in R_{j}(x_{0}^{j})$$i\in L_{j}(x_{0}^{j})\cup I_{\mathrm{j}}(x_{0}^{j},)$140とし $A=(a_{ji})\in \mathbb{R}^{2n\cross m}$ とすると (4) (ま $A\lambda\geq 0$ と表すことができる。 言い換えると、 $x_{0}\in E(D)$ となるための必要十分条件は $A\lambda\geq 0,$ $\lambda>0$ が解$\lambda$をもつことである。 後者の条件がみたされるかどうかを調べるために次の定理を適用できる。
定理 4([10])$A$を与えられた行列とするとき

I $A^{T}\mu\leq 0,$ $A^{T}\mu\neq 0,$ $\mu\geq 0$ に (ま解

$\mu$

がある。

または
$\mathrm{I}\mathrm{I}A\lambda\geq 0,$$\lambda>0$には解$\lambda$がある。

しかし、 同時に成立することはない。

定理 4 より、 $A\lambda\geq 0,$ $\lambda>0$ が解$\lambda$をもっための必要十分条件は$\min$(LP)$x_{0}$

に関する線形計画問題$\sum_{i=1}^{m}a_{i}^{T}\mu$

subject to$A^{T}\mu\leq 0$$\mu\geq 0$の最適値が 0 となることである。 ここで$a_{i}$

は $A$ の第$i$列ベクトルである。 よって、 交点$x_{0}$が (P) の有効解であるかどうかは (LP) を解くことによって調べることができ、 次の定理を得る。
定理 5$x_{0}\in I$

に対して、 $x_{0}\in E(D)$ となるための必要十分条件は $x0$ に関する (LP) の最適値が 0 となることである。
$E(D)$ のフレームは $E(D)$に含まれるすべての 1-次元ボックスの和集合であり、それは連結であるのでそれを連結グラフ $(V, E)$ とみなすことができる。 ここで $V=I\cap E(D)$ であり $E$ はそのグラフのすべての辺の集合である。

$x_{1},$$x_{2}\in I\cap E(D)$

まれるための必要十分条件は$x_{1}$と$x_{2}$が与えられたとき、$x_{1}$と$x_{2}$

を連結する辺 $a(x_{1}, x_{2})$ が $E$ に含が隣接していて (P) の有効解となることとする。 $E(D)$ のフレームを求めるアルゴリズムはこの考え方を基に構成される。

フレーム生成アルゴリズムにおいてすべての交点の集合$I[] \mathrm{I}$$I=\{(d_{[k_{1}]}^{1}, d_{[k_{2}]}^{2}, \cdots, d_{[k_{n}]}^{n})^{T}\in \mathbb{R}^{n} :k_{j}\in\{1,2, \cdots, mj\},j\in J\}$と表されている。 フレーム生成アルゴリズムは任意の需要点を初期点として交点を辿って連結されている$E(D)$に含まれる 1-次元ボックスを求める。 $L$ は初期点と交点を辿って連結されていることが判定された交点の集合である。 $S\subset L$ は交点の集合でそれらの交点に連結している 1-次元ボックスが $E(D)$ に含まれるかどうかを既に判定されたものである。 $G$ , H\subset I’ まそれぞれ (P) の有効解であると判定された交点の集合と (P) の有効解ではないと判定された交点の集合である。 $T$ を $E(D)$ に含まれると既に判定された 1-次

元ボックスの和集合とする。 さら [こ、 $x,$$y\in \mathbb{R}^{n}$[こ対して $[x, y]\equiv\{(1-\lambda)x+\lambda y:\lambda\in[0,1]\}$ とする。

フレーム生成アルゴリズム
ステップ 0$S=\emptyset,$

ステップ 1

もし $L=S$ ならば終了。 ( $T$ が $E(D)$ のフレームである。)

ステップ 2 任意}こステップ 3$W=\emptyset$$H=\emptyset,$$G=D,$$T=\emptyset$とする。 任意に $d_{k}\in D$ を選び、 $L=\{d_{k}\}$ とする。

$x_{0}=(d_{[k_{1}]}^{1}, d_{[k_{2}]}^{2}, \cdots, d_{[k_{n}]}^{n})^{T}$とする。 各 $j\in J$ (こ対して$\in L\backslash S$

を選び、 $S=S\cup\{x_{0}\}$ とする。

141(a) もし $k_{j}>1$ ならば$x_{-j}=(d_{[k_{1}]}^{1}, \cdots, d_{[k_{g}-1]}^{j}, \cdots, d_{[k_{\mathrm{n}}}^{n}])^{T}$(b) もし $k_{j}<m_{j}$ ならば $x_{j}=$ ($d_{[k_{1}]}^{1},$$\cdots,$$d_{[k_{\mathit{3}}+1]}^{j},$$\cdots$とし $W=W\cup\{x_{-j}\}$ とする。

, dn[k、])T とし $W=W\cup\{x_{j}\}$ とする。

ステップ 4 もし $W=\emptyset$ ならばステツプ 1^。 そうでなかったら、 任意に $x_{\eta}\in W$ を選び、$\{x_{\eta}\}$$W=W\backslash$とする。

ステンプ 5 もし(a) もし(b) もし$[x_{0}, x_{\eta}]\subset T$$x_{\eta}\in G$

ならばステツプ 4^。

ならば $T=T\cup[x_{0}, x_{\eta}]$ とし、$x_{\eta}\not\in L$

ならば $L=L\cup\{x_{\eta}\}$ としステツプ$4\wedge\text{。}$に関する (LP) を解くことによって $x_{\eta}\in E(D)$ であるかどうかを調べる。 もし $x_{\eta}\in E(D)$ ならば $T=T\cup[x_{0}, x_{\eta}],$ $G=G\cup\{x_{\eta}\},$ $L=L\cup\{x_{\eta}\}$ としステツプ

4$x_{\eta}\not\in H$

ならば$x_{\eta}$

へ$\circ$(c) もし $x_{\eta}\in H$ または $x_{\eta}\not\in H\cup E(D)$ ならば $j=|\eta|$ として$H\cup\{(d_{[k_{1}]}^{1}, \cdots, d_{[p]}^{j}, \cdots, d_{[k_{n}]}^{n})^{T} :p=1,2, \cdots, k_{j}-1\}$$H\cup\{(d_{[k_{1}]}^{1}, \cdots, d_{[p]}^{j}, \cdots, d_{[k_{n}]}^{n})^{T} :p=k_{j}+1, \cdots, m_{j}\}$$H=\{$としステップ 4

if $\eta<0$
if $\eta>0$へ$\circ$

数値例

次の多目的配置問題 (P) を考える。
$\min(||x-d_{1}||_{1}, ||x-d_{2}||_{1}, ||x-d_{3}||_{1}, ||x-d_{4}||_{1}, ||x-d_{5}||_{1})^{T}$$X\in \mathrm{R}^{4}$

ここで $d_{1}=(3,0,4,1)^{T},$ $d_{2}=(4,2,0,2)^{T},$ $d_{3}=(2,1,3,3)^{T},$ $d_{4}=(0,4,5,4)^{T},$ $d_{5}=(1,5,2,5)^{T}$ である。 いまの場合、 $n=4,$ $m=5,$ $J=\{1,2,3,4\},$ $M=\{1,2,3,4,5\}$ である。 この問題にフレーム生成
アルゴリズムを適用すると図 2-1 0 に示されているような $E(D)$ のフレームが得られる。

図 2$E(D)$ のフレーム$(x^{1}=0)$

図 3$E(D)$ のフレーム$(0<x^{1}<1)$

142

図4

$E(D)$ のフレーム$(x^{1}=1)$

図5$E(D)$ のフレーム$(1<x^{1}<2)$

図 6$E(D)$ のフレーム$(x^{1}=2)$

図 7$E(D)$ のフレーム$(2<x^{1}<3)$

図8$E(D)$ のフレーム$(x^{1}=3)$

図 9$E(D)$ のフレーム$(4<x^{1}<4)$

143

図 10

$E(D)$ のフレーム$(x^{1}=4)$

5. 結論
における直角ノルムを用いた多目的配置問題と minisum 型配置問題を扱い、 $E(D)$ を求めることを考えた。 ます、 (P) の有効解の性質によって $E(D)$ のフレームが求まれば $E(D)$ が構成できることを示し$\mathbb{R}^{n}$た。 次に、 定理 5 として (P) の有効解のもう一つの性質を与えた。 その性質によって交点が (P) の有効解であるかどうかが判定できる。 最後に、 これらの結果に基づいて $E(D)$ のフレームを求めるフレーム生成
アルゴリズムを提案した。 フレーム生成アルゴリズムは $E(D)$ に含まれる 1-次元ボックスを順次辿っていくことによって $E(D)$ のフレームを生成する。

参考文献[1] L. G. Chalmet, R. L. Francis and A. Kolen, Finding efficient solutions for rectilinear distance location(1981), 117-124.
problems efficiently, Eur. J. Oper.
${\rm Res}.,$$6$[2] Z. Drezner and G. 0. Wesolowsky, The asymmetric distance location problem, Trans. Sci., 23 (1989),

201-207.
[3] R. Durier, On Pareto optima, the Fermat-Weber problem, and polyhedral gauges, Math. Programming, 47 (1990), 65-79.
[4] J. -B. Hiriart-Urruty and C. Lemar\’echal, Convex analysis and minimization algorithms :Fundamentals, Springer-Verlag, Berlin, 1993.
$I$[5] M. Kon, Efficient solutions for
Japonica, 47 (1998), 295-303.

$multicr^{\backslash }iteria$

location problems under the block norm, Mathematica[6] M. Kon, Efficient solutions of multicriteria location problems with rectilinear $nom$ in
Mathematicae Japonicae, 54 (2001), 289-299.

$R^{3}$, Scientiae[7] M. Kon, On efficient solutions of multicriteria location problems with rectilinear norm (in Japanese),
RIMS Kokyuroku 1241 (2001), 94-102

144[8] M. Kon and S. Kushimoto, On efficient solutions of multicriteria location problems with the block
norm, Scientiae Mathematicae, 2(1999), 245-254.

[9] T. J. Lowe, J.-F. Thisse, J. E. Ward and R. E. Wendell, On efficient solutions to multiple objective
mathematical programs, Manage. Sci., 30 (1984), 1346-1349.

[10] 0. L. Mangasarian, Nonlinear programming, McGraw-Hill, New York, 1969.
[11] R. E. Wendell, A. P. Hurter, Jr. and T. J. Lowe, Efficient points in location problems, AIIE Trans.,
9(1977), 238-246.