数理解析研究所講究録1020 巻 1997 年 165-179

165

マックス代数によるシステム理論の基礎

潮

大阪大学大学院基礎工学研究科

1

俊光 (Toshimitsu Ushio)

はじめに-plus 代数は, 最適制御 (動的計画法) やマルコフ決定過程などで自然に現れる代数構造である田. 離散事象システムにおいても, 時間付きイベントグラフと呼ばれる
代
ペトリネットのサブクラスの記述に $\max$-plus 代数が応用されている $[2, 3]$ .
数で記述できる離散事象システムのクラスは理論的にはかなり限定されてはいるが, 生産システム, 交通システムなど, 工学画面用例は多くある. 離散事象システムにおいて
masc-plUs 代数が利用される最大の理由は, 記述されたシステムの方程式にある種の線形性があり, 解析が比較的容易になることである. さらに, 従来の線形システム理論との$\max$$\mathrm{m}\mathrm{a}3\mathrm{C}-\mathrm{P}\mathrm{l}\mathrm{u}\mathrm{S}$

対応関係がある程度あることも理論的には興味深い点である.
本稿では, $\max$-plus 代数の基本的な性質を述べ, 離散事象システムの $\max$-plus 代数によるモデリングをぺトリネットとの関連づけて簡単に触れる. さらに, max-plus 代数を拡張した対称化 $\max$-plus 代数について紹介し, それと漸近的等価性との関係について述
べる.

2

max-plus 代数-plus 代数$\max$$\bullet \mathcal{R}_{\epsilon}:=\mathcal{R}\cup\{\Xi\}$$\bullet x,$$y\in \mathcal{R}_{\epsilon}$

は以下のように定義される [3].

$R_{\max}:=(\mathcal{R}_{\mathcal{E}}, \oplus, \otimes)$. 但し,\epsilon$:=-..\infty$

である.

に対して
$x\oplus y$$:=$$\max(x, y)$$x\otimes y$

$:=$

$x+y$

この代数において指数は$x^{\otimes r}:=X\otimes x\otimes\ldots\otimes X=rx$$\overline{\prime \mathrm{f}\mathrm{f}\mathrm{l}}$と定義される. 但し,$x^{\otimes 0}\cdot=$

for

$0$

$\epsilon$$\epsilon^{\otimes t}=$

$\{$

$0$

$\forall x\in \mathcal{R}_{e}$

$r>0$
$r=0$

undefinffi $r<0$

166である. さらに, 指数 r が実数に対しても容易に拡張できる.

-plus 代数には以下の性質がある.

$\max$$\bullet$$\oplus$に関する零元は$\epsilon(=-\infty)$である.

$x\oplus\epsilon=\epsilon\oplus x_{-}=x$$\bullet$$\otimes$に関する単位元は$0$$\otimes$$\forall x\in \mathcal{R}_{\epsilon}$,$\forall x\in \mathcal{R}_{\mathcal{E}}$である.
$x\otimes 0=0\otimes x=x$$\bullet$,に関する逆元は$x^{\otimes-1}=[\mathrm{u}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}-x\mathrm{n}\mathrm{e}\mathrm{d}$$x=\epsilon x\in \mathcal{R}$となる.
$\bullet$$x\in \mathcal{R}$に対して$x\oplus\hat{x}=\hat{x}\oplus x=\xi$を満たす x^ は存在しない. すなわち, 一般に,$\bullet$$\oplus$$\oplus$に関して逆元は存在しない.

に関してべき等 (idempotent) である.
$x\oplus x=x$$\forall x\in \mathcal{R}_{\epsilon}$

max-plus 代数は dioid という代数構造をもつことが知られている. 一般に,が以下の条件を満足するとき, dioid であるという.

1. 加法の結合律$(a\oplus b)\oplus C=a\oplus(b\oplus c)$

2. 加法の交換律$a\oplus b=b\oplus a$3. 乗法の結合律$(a\otimes b)\otimes C=a\otimes(b\otimes c)$

4. 加法に関する乗法の分配律

5. 零元$\epsilon$$(a\oplus b)\otimes C=$$(a\otimes c)\oplus(b\otimes c)$$c\otimes(a\oplus b)$$(c\otimes a)\oplus(c\otimes b)$

$=$

の存在
$a\oplus\epsilon=a$$(D, \oplus, \otimes)$167

6. 零歳への吸収$a\otimes\epsilon=\epsilon\otimes a=\in$

7. 単位元$e$の存在$a\otimes e=e\otimes a=a$

8. 加法のべき等$a\oplus a=a$1$\max_{\prime}.--$$\bullet$plus. 代数上の行列演算も通常の行列演算と同様に以下のように定義される.

スカラー$\alpha\in \mathcal{R}_{e}$と行列$A\in \mathcal{R}_{\epsilon}^{m\mathrm{x}n}$の積$\alpha\otimes A$$(\alpha\otimes A)ij:=\alpha\otimes aij$$\bullet$

行列 $A,$$B\in \mathcal{R}_{\epsilon}^{m\mathrm{x}n}$の和 $A\oplus B$$(A\oplus B)_{ij}:=aij\oplus b_{ij}$$\bullet A\in \mathcal{R}_{\mathcal{E}}^{m\mathrm{x}p}$と$B\in \mathcal{R}_{e}^{\mathrm{P}}\mathrm{X}n$の積 $A\otimes B$$(A \otimes B)_{ij}:=\bigoplus_{k=1}^{p}a_{ik}\otimes b_{kj}(=k1,$$\mathrm{p}\max_{=}\{a_{ik}+b_{kj}\})$$\ldots,$

以上のように行列演算を定義すると, 単位行列は対角要素が で, 非対角要素がである行列となり, 全ての要素が である行列が零行列となる. また, 通常の行列とmax-plus 代数上の行列とは性質が多少異なっている. 例えば, 以下の命題で示されるよ
うに, max-plus 代数上の行列の逆行列が存在するための必要十分条件は, 通常の行列の場合に比べてかなり厳しいものとなっている.
$E_{n\mathrm{x}n}$$0$$\epsilon$$\epsilon$【命題 1] [3] 行列が max-plus 代数において可逆であるための必要十分条件はは対角要素の\epsilon を持たない対角$T=D\otimes P$ と分割できることである. 但し,
行列であり,
は置換行列を表す. さらに,$T\in \mathcal{R}_{\epsilon}^{n\cross n}$$D\in \mathcal{R}_{\epsilon}^{n\mathrm{x}n}$$P\in \mathcal{R}_{\epsilon}^{n_{\mathrm{i}}}\mathrm{x}n$$(D^{\otimes-1})_{ij}.$$–\{$$-d_{ii}i=j$$\epsilon$$i\neq j$.

と表すことができる. 但し,$P^{T}$$P^{\otimes-1}$$=$$P^{T}$$T^{\otimes-1}$$=$$P^{\otimes-1}\otimes D\otimes-1$は転置行列を表す.

168

max-plus 代数とペトリネット

3

ペトリネットはコンカレントシステムのモデルとして有名であり, 通信システム, 生産システムなど様々な分野に応用されている. ペトリネットは, その応用目的に応じて様々な拡張が提案されている. まず, 基本的なペトリネットについて簡単に説明する [4].
ペトリネットは 5 項組 $PN=(P, T, F, M_{0})$ で表される. 但し, $P$ はブレースの集合,$T$ はトークンの集合,$F\subseteq(P\cross T)\cup(T\cross P)$ は有向枝の集合,
ぽ初期マーキングを表す. 各ブレースには非負整数が割り当てられる. これをトークン数という. 各ブレー
$M_{0}$

スでのトークン数をベクトル的に表したものをマーキングという.

このマーキングがシステムの状態を表す. 以下, ブレース のトークン数を $M(p)$ とおく. トークンの移動はトランジションの発火によって生じる. 各トランジション に対して, $(p, t)\in F$ を満たすブレース $p\in P$ を入力ブレース, $(t,p)\in F$ を満たすブレースを出力ブレースという.
と書く. トラ
トランジション の入力ブレース及び出力ブレースの集合をそれぞれ u,
ンジション が以下の条件を満足するとき, 発火可能という.
$P$

$t$

$t$

$t$

.

$t$

$M(p)\geq 1$$\forall p\in.t$

発火可能なトランジション が発火することにより, マーキング $M$ は M’ に変化する. 但し,$t$$M’(p)=$.

$M(_{\mathrm{P}})+1$$p\in t\cdot-\cdot t$$M(p)-1$$p\in.t-t$$M(p)$

otherwise[注意】 ここでは, トランジションの発火によりトークン数の変動が高々 1 個としているが, 多重アークを認めることにより, より -般的な発火規則に拡張することができる.
$\cdot$ペトリネットはそのグラフ的な特徴によって様々なクラスに分類することができる.
その中の–つにイベントグラフがある. イベントグラフは各ブレースにおいて入力アー
クと出力アークが 1 本あるペトリネットのことである [5]. イベントグラフはグラフ的な構造がシンプルなので, その構造的特徴を利用して可到達問題などの必要十分条件が明らかにされている. また, 工学的にもイベントグラフで記述できるシステムが多くあり,実用上も有用なペトリネットである.
ところで, ペトリネットでは.

トランジションの発火する時刻については考慮していな

いが, システムの性能を評価する場合には発火時間に関する規則を導入する必要がある.

トランジションの発火時間に関する規則を定めたペトリネットは時間付きペトリネットと呼ばれ, $TPN=(PN, H)$ で表される. 但し, $PN$ はペトリネットであり,は各ブレースに対する発火時間を規定する. すなわち, あるトランジションの発火によ$H:Parrow \mathcal{R}^{+}$.

りトークンがブレース $P\in P$ に入ったとき, そのトークンは $H(p)$ 時間経過しないと次の発火に寄与できない. 時間付きペトリネット $TPN=(PN, H)$ において PN がイベン
トグラフとなるとき, $TPN$ を時間付きイベントグラフと呼ぶ.
線形な差分方程式で記
時間付きイベントグラフで記述される離散事象システムは述できる [3]. ここでは, フレキシブル生産システムにおける基本的な問題である, 入力$\mathrm{m}\mathrm{a}3\mathrm{C}$169

ステーションと出力ステーション間でパーツを運搬する台車の解析を例にとり, 時間付
きイベントグラフから $\max$ 線形方程式への変換について述べる [6]. ここでは図 1 に示すシステムを考える., 図 1 における各トランジションの意味を表 1 に示す.

図 1: 例題

表 1: 例題におけるトランジションの意味

トランジションちの発火時刻を次式となる.

$x_{i}$

と書くと,

$k+1$

回目のトランジションの発火時刻は$x_{1}(k+1)=1\otimes x_{2}(k)$$x_{2}(k+1)=1\otimes x_{1}(k+1)\oplus 1\otimes x_{3}(k+1)$$x_{3}(k+1)=2\otimes X_{5}(k+1)$$\{$$x_{4}(k+.1)=2\otimes x_{2}(k)$$x_{5}(k+1)=1\otimes x_{4}(k+1)\oplus 1\otimes x_{6}.(k)$$x_{6}(k+1)=1\otimes x_{5()}k+1$

上式を行列表現すると,$x(k+1)$

$:=$

$–$

$[_{\epsilon}^{\mathcal{E}}\epsilon\epsilon\epsilon 1-\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon$$\epsilon\epsilon\epsilon \mathcal{E}\epsilon 1$$\epsilon\epsilon\epsilon\epsilon\epsilon 1$$\epsilon\epsilon\epsilon\epsilon 21$$\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon]\otimes$

170$\oplus[_{\mathcal{E}}^{\epsilon}\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon 2\epsilon\epsilon 1\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon 1]\otimes$$:=$$A_{0}\otimes x(k+1)\oplus A_{1}\otimes x(k)$従って, 次式が得られる$x(k+1)=A_{0}^{*}.\otimes A_{1}\otimes.x(k)$但し,$A_{0}^{*}:=k \geq\bigoplus_{0}A_{0}^{\otimes k}=[_{\mathcal{E}}^{0}\epsilon\epsilon\epsilon 1\epsilon\epsilon\epsilon 0\epsilon\epsilon$$\epsilon\epsilon\epsilon 0\epsilon 1- 2430\epsilon 10\epsilon 23\epsilon 10\epsilon\epsilon\epsilon\epsilon\epsilon]$

以上より, このシステムは次式で表される $\max$ 線形な方程式でモデル化されることがわかる.

$x(k+1)=-$$\otimes x(k)$ここで, 初期値として,「$0\wedge$.

$x(0)=|00.\cdot$を与えたときの $x(k)$ は以下のようになる.
$\ulcorner 19$$\cdot.\cdot$$arrow$$arrow$$arrow$$arrow$$arrow$

21
22.
$x(\mathrm{O})$

$.\{$

24
23
20

$x(1)$$x(2)$$x(3)$$x(4)$$x(5)$

171

ここで$\epsilon 432\epsilon 1|\otimes$$432561\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon$$\epsilon\epsilon\epsilon\epsilon\epsilon\epsilon$$A\in \mathcal{R}_{\epsilon}^{n\mathrm{x}n}$$=$$6\otimes$に対して$A\otimes v=\lambda\otimes v$

のとき,
を固有値,
なり, 以下の性質がある.
$\lambda\in \mathcal{R}_{e}$$v\in$

聯を固有ベクトルという. 固有値は通常の行列とは異.

’【命題 ] $[3]$ 任意の正方行列は固有値を持つが, その個数は行列が既約ならば固有値は 1 個しかない.
$2$

4

$n$

以下である. 特に, その対称化

max-plus 代数における基本的問題点の–つに\oplus に関して–般に逆元が存在しないという点がある. この問題点を解決するために. 対称化という操作を行う [3].
, 集合乃$.\text{まず}$を乃と定義し, P\epsilon 上の演算\oplus ,

このとき,
なる.
は

$\otimes$$(0, \epsilon)$$\otimes$$:=\mathcal{R}_{e}\cross \mathcal{R}_{\epsilon}$

を以下のように定義する.

$(x_{1}, x_{2})\oplus(y_{1}, y_{2})$$:=$$(x_{1}\oplus y_{1}, x_{2}\oplus y_{2})$$(x_{1}, x_{2})\otimes(y_{1}, y_{2})$$:=$$(_{X_{1}\otimes y2}1\oplus x\otimes y2, x_{1}\otimes y_{2}\oplus x2\otimes y1)$に関して結合律, 交換律, およびべき等性が成り立ち, 零元はとに関して結合律, 交換律, および加法に関する分配律が成り立ち, 単位元となる. さらに; 以下に示すように,はに対して吸収的となる.
$\oplus$$(\epsilon, \epsilon)$$\oplus$$(\epsilon, \epsilon)$$(x_{1}, x_{2})\otimes(_{\mathcal{E}}, \epsilon)$$\otimes$$=$$(_{X_{1}\otimes}\epsilon\oplus x_{2}\otimes\epsilon, x_{1}\otimes \mathcal{E}\oplus x_{2}\otimes\epsilon)$$=$$(\epsilon\oplus\epsilon, \in\oplus \mathcal{E})=(_{\mathcal{E}}, \epsilon)$

以上より,は可換 dioid となることがわかる.
次に, $u=(x_{1}, x_{2})\in P_{\epsilon}$ に対して以下の示す 1 項演算を定義する.
$(P_{\epsilon}.’\oplus, \otimes)$$\bullet$$u$の $( \max)$ 絶対値$|u|_{\oplus}:=X_{1}\oplus X_{2}$172$\bullet$-項演算$u\oplus(\ominus v)$$\bullet$$\ominus$eu$:=(x_{2}, x_{1})$を $u\ominus v$ と書く.

バランス演算$u$.

$:=.u\oplus(\mathrm{e}u)=(|u|_{\oplus}, |u|_{\oplus})$

以下の等式が成り立つ.
$u$$u\otimes v$.
.

(eu). $=(u.)$$=$$(u\otimes v)$.

$\ominus(u\oplus v)$$=$$(\ominus u)\oplus(\ominus v)$$\ominus(u\otimes v)$$=$$(\ominus u)\otimes v$$u\neq(\epsilon, \epsilon)$

.

$=u$

$\ominus(\ominus u)$

ところで, 任意の

$=$

に対して

$u\ominus u=u\oplus(\ominus u)=u\neq(\epsilon, \epsilon)$($=\oplus$の逆元)となる. この問題を解決するために, まずバランス (balance) と呼ばれる関係$\nabla$を以下のように定義する.
【定義 1]$u=(u_{1}, u_{2}),$ $v=(v_{1}, v_{2})\in P_{e}$に対して$u_{1}\oplus v_{2}=u_{2}\oplus v_{1}$のとき,$u_{\nabla^{v}}$と書く.
以下の例が示すように,$\nabla$は推移的ではない.

$((2,1)_{\nabla}(2,2)$$(2, 2)$ $\nabla(1,2)$ ,,$(2, 1)$$\text{ノ}\nabla(1,2))$

そこでさらに, 新しい関係を定義する.

【定義 2】$P_{e}$

上の関係 $B$ を以下のように定義する.

$(u_{1}, u_{2})\mathcal{B}(v_{1}, v_{2})$$(u_{1}, u_{2})\nabla(v_{1}, v_{2})$$\Leftrightarrow$$(u_{1}, u_{2})=(v_{1}, v_{2})$このとき,$\mathcal{B}$は同値関係となり, 演算$\oplus,$$\otimes$ifotherwise$u_{1}\neq u_{2}\wedge v_{1}\neq v_{2}$と両立する. そして, 以下の 3 種類の同値類が存在する.
$\overline{(w,\epsilon)}$$=$$\{(w, x)\in P_{\epsilon}|X<w\}$$(\epsilon, w)$$=$$\{(x, w)\in P_{\mathcal{E}}|X<w\}$$\overline{(w,w)}=$$\{(w, w)\}$

173

ここで,

$\overline{(w,\epsilon)},$さらに,$\overline{(\epsilon,\epsilon)}$$\overline{(\epsilon,w)},$$\overline{(w,w)}$

をそれぞれ$(\mathrm{m}\mathrm{a}3\mathrm{c})$正数,$( \max)$

負数, バランス数という.

を max 零という.

とおくと,を対称化 $\max$-plus 代数という. こをのとき,は $S$ の $\max$ 正と $\max$ 零と対応させることにより,のクラスからなる集合
は $\max$ 負と同–視できる. さらに,と $\max$ 零のクラスからなる集合, $S:=\{w|w\in S^{\oplus}\}$ はバランスのクラスからなる集合となり, 以下の式が成り立つ.
ここで,$S:=^{p_{\mathcal{E}}/}\mathcal{B}$$S_{\max}:=(S, \oplus, \otimes)$$\overline{(w,\epsilon)}\in S-$$w\in \mathcal{R}_{e}$$\mathcal{R}_{\epsilon}$$S^{\oplus}$$S^{\mathrm{e}}:=\{\ominus w|w\in S^{\oplus}\}$.

$S=S^{\oplus}\cup s^{\mathrm{e}}\cup s$$s^{\oplus}\mathrm{n}S^{\ominus}\mathrm{n}S^{\cdot}=\{\overline{(\epsilon,\mathcal{E})}\}(=\{\epsilon\})$$\mathcal{E}=\ominus \mathcal{E}=\mathcal{E}^{\cdot}$

集合$S^{\vee}:=S\oplus\cup S^{\mathrm{e}}$の要素を符号付き要素という. また, $x,$$x$$x\oplus(\mathrm{e}y)=\{$$\ominus y$$x.$$y\in \mathcal{R}_{e}$に対して,if $x>y$
if $x<y$
if $x=y$となる.

5$\nabla$関係$\nabla$$\bullet\forall a,$の性質の基本的な性質を以下にまとめておく [3].
$b,$$c\in S$$a\oplus b\nabla c$$\bullet\forall a,$

$b,$

$c,$

$b,$

弱い代入 :$\forall a,$$b,$$\Rightarrow$

弱推移性 :$\forall a,$$.\Rightarrow.$$a_{\nabla^{b}}$,$c\otimes$ $x_{\nabla^{b}}$.

$a\oplus c_{\nabla^{b}}\oplus d$$a\otimes c_{\nabla\otimes}bc$,$x\in..S^{\mathrm{v}}$$\Rightarrow$$c\otimes a_{\nabla^{b}}$$x\in S^{\vee}$$\Rightarrow$$a_{\nabla^{b}}$$b\in S$$a_{\nabla^{X}}$$\bullet$$c_{\nabla^{d}}$$c\in S$$x_{\nabla^{a}}$$\bullet$,$c\in S$.
$\bullet$$a_{\nabla^{C\ominus}}b$$d\in S$$a_{\nabla^{b}}$$\bullet\forall a,$$\Leftrightarrow$,$x_{\nabla^{b}}$,バランス関係から等式の導出$x_{\nabla y}$

,

$x,$

$y\in S^{\vee}$$\Rightarrow$

$x=y$

174

線形方程式と線形バランス式の解の間には以下の関係がある.
【定理 1] [3]線形方程式$A\otimes x\oplus b=C\otimes x.\oplus\cdot d$

の解

$x$

$x\in \mathcal{R}_{e}^{n}$の集合とバランス式’$x\in S^{n}$$(A\ominus C)\otimes X\oplus(b\ominus d)_{\nabla}\epsilon$の $\max$ 正の解 $x$ の集合は–致する.

線形方程式を解くときに, それをバランス式に置き換え, それを解くことにより元の線形方程式の解を求めることが可能であることを上の定理は示している. そこで, 次にバランス式の解法について簡単に紹介する.
を置換とおく.
$\sigma$$0\sigma i^{\backslash }\backslash \{\backslash \mathrm{F}\ovalbox{\tt\small REJECT}\llcorner\Re\succeq 3$$s\mathrm{g}\mathrm{n}(\sigma):=\{$$\ominus 0\sigma.\delta^{\backslash }\backslash \Leftrightarrow\backslash \dot{\ovalbox{\tt\small REJECT}}\llcorner\dot{\Re}\circ\succeq\doteqdot$

行列$A\in S^{n\cross n}$の (max 代数) 行列式を$\det A:=\oplus\sigma \mathrm{s}\mathrm{g}\mathrm{n}(\sigma)\otimes\otimes i=1A_{i,\sigma(i)}$と定義する. バランス式に対する Cramer の定理が証明されている.
【定理 2] (Cramer の定理) [7]$A\otimes x_{\nabla^{b}}$$A\in S^{n\cross n}$,$b\in S^{n}$の解は, 次式を満足する.
$\det A\otimes x_{\nabla^{A^{adj}}}\otimes b$

さらに,$A^{adj}\otimes b$$\det A$$\in$$(S^{\mathrm{v}})^{n}$$\kappa\epsilon$のとき, 符号付き解は–意に存在し, 次式で与えられる.
$x=(\det A)^{\otimes-}1\otimes A^{adj}\otimes b$

但し,$A^{adj}$

は $A$ の余因子行列である.

【例題 1】バランス式$\otimes\nabla\vee$$\sim A$

$b$

175

を考える. このとき,$\det A=-1\otimes 2^{\cdot}\cdot\ominus 4\otimes(\ominus 1)=1\oplus 5=5\ovalbox{\tt\small REJECT}\nabla^{\xi}$となり,$(\det A)^{\otimes-1}=-5$

となる.

さらに,
$A^{adj}\otimes b$$=$$\otimes=$$=$$=\in(S^{\vee})^{2}$となるので, Cramer の定理から, バランス式の解は$\nabla(\det A)^{\otimes-}1\otimes A^{adj}\otimes b==$となる. さらに,$A^{adj}.\otimes b$.

意解を持つ.

6かつ$\det A,\sigma\epsilon,$が符号付き数であることより, この方程式は漸近的等価性の利用
以下の対応があることはよく知られている $[3, 7]$ .
$x\oplus y=$$x\otimes y$$=$$\lim_{sarrow\infty}s^{-1}(\ln(e^{xs}+e^{ys}))$$S^{-1}\ln(.e^{x}e^{y})ss$

上記の関係を対称化 $\max$-plus 代数に拡張できることを述べる [8].

【定義 3】

1.

$\alpha$$\alpha\in \mathcal{R}\cup\{\infty\}$と実数値関数 $f,$$\alpha\in \mathcal{R}$$\alpha=\infty$$xarrow\alpha$のとき$f(x)\sim \mathrm{o}$

3.

に対して,

の近傍で $f$ と g. は漸近的に等価$f(x)\sim g(X)$ ,

2.

$g$

$\Leftrightarrow$$\lim_{xarrow\alpha}\frac{f(x)}{g(x)}=1$$\vee \mathrm{e}$,$xarrow\alpha$$\Leftrightarrow$$\exists\delta,\forall x\in(\alpha-\delta, \alpha+\delta)$: $f(X)=0$のとき$f(x)\sim 0$,$xarrow\infty$.

.
$\Leftrightarrow$$\exists K\in \mathcal{R},\forall x>K$

: $f(X)=0$

176

4. $A(x),$ $B(x)$ が $m\cross n$ の行列のとき$A(x)\sim B(x)$,$xarrow\alpha$

関数 $F$ を次のように定義する. 任意の$x\in \mathcal{R}_{\epsilon}$$F(x, s)$$F(\ominus x, s)$$F(x., s)$

但し,$\mu>0,$ $\nu\in \mathcal{R}-\{0\}$

【注意】
$F$

$A(x)_{i,j}\sim B(x)i,j$$\Leftrightarrow$$xarrow\alpha$と実数値パラメータ

$s$

に対して

$=\mu e^{xs}$$=\cdot-\mu e^{xs}$$=$$\nu e^{xs}$である.

$F(\epsilon, s)=0$の逆写像を $R$ と書くと,$f(s)\sim\mu e^{xs}$,$sarrow\infty$$\Rightarrow$$R(f(\cdot))=x$$f(s)\sim-\mu e^{xs}$,$sarrow\infty$$\Rightarrow$$R(f(\cdot))=\ominus x$$f(s)\sim\nu e^{x}s$,$sarrow\infty$$\Rightarrow$$R(f(\cdot))=x$.

の係数に数値を与えて逆写像を取ると, 必ず符号付き数になることに注意されたい. このとき, 以下の性質が成り立つ.

ここで,$e^{xs}$$a\oplus b=c$$\Rightarrow$$F(a, s)+F(b, s)\sim F(c, s)$ ,$sarrow\infty$$a\oplus b_{\nabla}c$$\Leftarrow$$F(a, s)+F(b, s)\sim F(c, s)$ ,$sarrow\infty$$a\otimes b=c$$\Leftrightarrow$$F(a, s)\cross F(b, s)\sim F(c, s)$ ,$\forall s\in_{r}R$

以上より,=Rnax が, $(\mathcal{R}, +,-)$ とそれぞれ対応することがわかる. さらに, 行列の場合には,$(\mathcal{R}^{+}, +,-)$と$(\mathcal{R}_{e}, \oplus, \otimes)$$(S^{\cdot}, \oplus, \otimes)=S_{\max}$$A\in S^{n\cross n}$$F(A, \cdot)$に対して,を以下のように定義する.
$F(A, s)_{i,j}:=F(A_{i,j}, s)$$R(\tilde{A}(\cdot))_{i,j}:=R(\tilde{A}_{i,j}(\cdot))$

このとき,$A,$ $B,$ $C$

を $S$ での行列とおくと以下の性質が成り立つ.

$A\oplus B=C$$\Rightarrow$$F(A, s)+F(B, s)\sim F(C, s)$ ,$sarrow\infty$$A\oplus B_{\nabla}C$$\Leftarrow$$F(A, s)+F(.B, s)\sim F(C, s)$ ,$sarrow\infty$$A\otimes B=C$$\Rightarrow$$F(A, s)\cross F(B, s)\sim F(C, s)$ ,$sarrow\infty$$A\otimes B_{\nabla}C$$\Leftarrow$$F(A, s)\cross F(B, s)\sim F(C, s)$ ,$sarrow\infty$が$\tilde{A}(\cdot):=$177【例題 2】 直接的に計算すると次式が得られる.

$\otimes=$

上式の左辺を漸近表現して計算すると,となる. ここで, パラメータを変えると以下のようになる.
$\bullet\nu_{2}:=-\nu_{1}\mu_{3},$ $\nu_{3}:=\mu_{2}\mu 4-\mu_{1}\mu 3,$$\bullet\nu_{1}=1,$$\mu_{6}:=\mu 2\mu_{5}$$\mu_{1}=.\mu_{2\mu 3\mu=}==4\mu_{5}=1$$\bullet\nu_{1}=-1,$ $\mu_{1}=\mu_{2}=\mu_{3}=1,$

とおく.

とおく.

$\mu 4=\mu_{5}=2$

とおく.

以上より, パラメータの与え方に依存して得られる行列は異なるが, いずれもバランス関係が成り立っていることがわかる.

最後に, 漸近等価性を利用した線形代数方程式の解法アルゴリズムを以下に示す.

1. 代数方程式$A\otimes x=c$に対して,$\tilde{A}(s)\tilde{X}(S)=\tilde{c}(S)$

を考える.

2.

$\tilde{x}(s)=\tilde{A}-1(S)\tilde{C}(s)$3.

$\hat{x}=R(\tilde{x}(s))$

を計算する.

を計算する. このとき,$A\otimes\hat{x}_{\nabla}c$が成り立つ.

178

4. もし符号付きの–意解を持つならば$A\otimes\hat{x}=c$となる.

【例題 3】例題 1 で考察したバランス式に対応する方程式$\otimes=$を考える. この式に対して,$\otimes=$の解を求めると,$= \frac{1}{\mu_{1}\nu e^{S}+\mu 2\mu 3e^{5}s}=$となり, 次式が得られる.
$xy|\nabla|\ominus 0-2$

7

あとがき
ここでは, max-plus 代数の基本的な性質を紹介し, 以下の関係があることを述べた.

max-plus 代数は離散事象システムのモデルとして, しばしば用いられているが, 適用できる範囲が時間付きイベントグラフでモデル化されるシステムに限定されいている.
より広いクラスのペトリネットへの拡張の研究も行われれている [9]. また, 離散事象シ
ステムにおける制御問題は近年急速に進歩したが $[10, 11]$ , $\max$-plus 代数で記述されるシステムにおける制御問題についても検討されている $[12, 13]$ . また, $\max$-plus 代数の代数的特徴はべき等解析とも関連している [14].

179

参考文献
Algebra,”Plus, “Methods and Applications of[1] S. Gaubert and
STACKS97, Lecture Notes in Computer Science Vol. 1200, pp. 261-282, 1997.
${\rm Max}$$( \max,+)\mathrm{L}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{a}\mathrm{r}$[2] G. Cohen, D. Dubois, J. P. Quadrat, and M. Viot, “A
View of Discrete-Event Proc\’eses and Its Use for Perforamce Evaluation in Manufacturing,” IEEE Trans. Automatic Control, vol. AC-30, no. 3, pp. 210-220, 1985.
$\mathrm{L}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{a}\mathrm{r}- \mathrm{S}\mathrm{y}\mathrm{S}\mathrm{t}\mathrm{e}\mathrm{m}- \mathrm{T}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{i}\mathrm{C}$[3] F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat, Synchronization and Linearity, John Wiley&Son, 1992.

[4] J. L. Peterson, Petri Net Theory and the Modeling of Systems, Prentice-Hall, 1981.
[5] G. Cohen, P. Moller, J.-P. Quadrat, and M. Viot, “Algebraic Tools for the Performance Evaluation of Discrete Event Systems,” Proc. IEEE, vol. 77, no. 1, pp.
39-58, 1989.

-Plus 代数による生産システムのモデル化と解析, 大阪大学工学部電子工学科平成 7 年度卒業論文, 1996.

[6] 松浦,${\rm Max}$[7] G. J. Olsder and C. Roos, “Cramer and Cayley-Hamilton in the
Linear Algebra and Its Applications, vol. 101, pp. 87-108, 1988.

${\rm Max}$

Algebra,”[8] B. D. Schutter and B. D. Moor, “The Singular-Value Decomposition in the Extended
Algebra,” Linear Algebra and Its Applications, vol. 250, pp. 143-176, 1997.
${\rm Max}$, and B. Gaujal, “Free-Choice Petri Nets-An Algebraic Ap[9] F. Baccelli, S.
proach,” IEEE Trans. Automa $tic$ Control, vol. 41, no. 12, pp. 1751-1778, 1996.
$\mathrm{F}_{\mathrm{o}\mathrm{S}}\mathrm{S}$[10] P. J. Ramadge and W. M. Wonham, “Supervisory Control of a Class of Discrete
Event Systems,” SIAM J. Control and Optim ization, vol. 25, no. 3, pp. 637-659,

1987.
[11] 潮, “離散事象システムにおける制御問題とスーパバイザ,” システム/制御/情報,
vol. 34, no. 9, pp. 531-538, 1990.

[12] D. D. Cofer and V. K. Garg, “Supervisory Control of Real-Time Discrete-Event
Systems Using Lattice Theory,” IEEE Trans. Automatic Control, vol. 41, no. 2, pp.
199-209, 1996.
[13] S. Takai, “A Characterization of Realizable Behavior in Supervisory Control ofTimed Event Graphs,” Automatica, vol. 33, no. 11, 1997.
[14] V. P. Maslov and S. N. Samborskii, Idempotent Analysis, Advances in Soviet Mathematics, vol. 13, 1992.