ORWiki - 利用者の投稿記録 [ja]

ロジスティックモデル

2007-07-11T09:23:35Z

211.9.146.139:

'''【ろじすてぃっくもでる (logistic model)】'''

ロジスティックモデルは, 生態学モデルの中で最も単純な1種の個体群の時間変化を記述したモデルである. <math>N\,</math>を時刻<math>t\,</math>における個体数として, <math>N=k/(1+m \rm {e}}^{-\lambda t})\,</math>と表現する. ここで, <math>k\,</math>は飽和個体数であり, <math>\lambda\,</math>は定数である. ロジスティックモデルは, 生態学にとどまらず, 人口の増加過程, 新製品の普及過程など様々な社会的現象, ソフトウェア信頼度成長モデルなどの工学にも適用されている.

劣モジュラシステム

2007-07-11T09:20:07Z

211.9.146.139:

'''【れつもじゅらしすてむ (submodular system)】'''

有限集合 <math>N\,</math> の部分集合族 <math>\mathcal{D}\subseteq 2^{N}\,</math> に関して, <math>\emptyset,N\in \mathcal{D}\,</math> かつ <math>X,Y\in\mathcal{D}\Rightarrow X\cup Y, X\cap Y\in{\mathcal D}\,</math> が成り立つものとする. このとき, <math>{\mathcal D}\,</math> は分配束をなす. 劣モジュラ関数 <math>f:{\mathcal D}\to{\mathbf R}\,</math> が <math>f(\emptyset)=0\,</math> を満たすとき, <math>(\mathcal{D},f)\,</math> を劣モジュラシステムという.

劣モジュラ関数

2007-07-11T09:18:49Z

211.9.146.139:

'''【れつもじゅらかんすう (submodular function)】'''

分配束 <math>{\mathcal D}\,</math> 上の関数 <math>f\,</math> が, 任意の <math>X,Y\in{\mathcal D}\,</math> に対して

\[
f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)
\]

を満たすとき, <math>f\,</math> を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.

劣勾配

2007-07-11T09:17:21Z

211.9.146.139:

'''【れつこうばい (subgradient)】'''

真凸関数 <math>f: {\mathbf R}^n \to (-\infty,+\infty)\,</math> に対して, 次式を満足するベクトル <math>\xi \in {\mathbf R}^n\,</math> を <math>f\,</math> の <math>x\,</math> における劣勾配といい, 劣勾配全体の集合を <math>\partial f(x)\,</math> と表す.

\[
f(y) \ge f(x) + \xi^{\top}(y-x) \quad\quad \forall \, y \in {\bf R}^n
\]

真凸関数はその実効定義域 <math>\mbox{dom} \, f := \{ x \, | \, f(x) < \infty \}\,</math> の任意の相対的内点において, 少なくとも1つの劣勾配をもつ. 特に, 凸関数 <math>f\,</math> が点 <math>x\,</math> において微分可能ならば, <math>f\,</math> の <math>x\,</math> における劣勾配は唯一存在し, 通常の勾配 <math>\nabla f(x)\,</math> に等しい.

レオンティエフ逆行列

2007-07-11T09:14:33Z

211.9.146.139:

'''【れおんてぃえふぎゃくぎょうれつ (Leontief inverse matrix)】'''

産業連関分析において, 産業の生産額を<math>X\,</math>, 投入係数表を<math>A\,</math>, 最終需要を<math>F\,</math>, 輸入を<math>M\,</math>とすれば, 生産と需要のバランスは<math>AX+F-M=X\,</math>となる. この式を<math>X\,</math>について解くと<math>X=(I-A)^{-1}(F-M)\,</math>と求められる. <math>I\,</math>は単位行列である. 行列<math>(I-A)^{-1}\,</math>をレオンティエフ逆行列と呼ぶ. この行列は逆行列が存在すれば<math>(I-A)^{-1} = I+A+A^2+\cdots\,</math>と展開することができる. 第1項は直接の需要の生産に, 第2項以降は波及的間接需要の生産に対応している.

リンドレーの方程式

2007-07-11T09:12:43Z

211.9.146.139:

'''【りんどれーのほうていしき (Lindley's equation)】'''

客の到着が再生過程にしたがう GI/G/1 モデルにおいて, 到着間隔分布とサービス時間分布をそれぞれ <math>F(t)\,</math>, <math>H(t)\,</math> と表すとき, 先着順サービスでの待ち時間の定常分布 <math>W(t)\,</math> に関する次の積分方程式をリンドレーの方程式という. %ただし, <math>C(t)\,</math> は"サービス時間<math>-\,</math>到着間隔"を表す分布関数である.

%\[
W(t) = \left\{
\begin{array}{ll}
\displaystyle\int^{\infty}_{0-} C(t-x) \mbox{\rm d} W(x) & (t \geq 0)
\\
0 & (t < 0)
\end{array}
\right.
\]

ただし,
<math>C(t)=\int^{\infty}_{x=0} H(t+x) \mathrm {d}F(x)
\ \ \ -\infty < t < +\infty \,</math>

である.

利用率

2007-07-11T09:09:08Z

211.9.146.139:

'''【りようりつ (traffic intensity)】'''

待ち行列モデルにおいて, 負荷の程度を表す重要なパラメータで, \[ \rho = \frac{\mbox{サービス要求量}}{\mbox{サービス処理能力}}\]で定義される. 待合室の容量が無限のモデルでは, システムが平衡状態に向かうための条件が <math>\rho<1\,</math> である. 標準的な GI/G/<math>c\,</math> モデルでは, 平均到着間隔を <math>\lambda^{-1}\,</math>, 平均サービス時間を <math>\mu^{-1}\,</math> としたとき, <math>\rho=\lambda/(c \mu)\,</math> で与えられる.

離散分離定理

2007-07-11T09:04:49Z

211.9.146.139:

'''【りさんぶんりていり (discrete separation theorem)】'''

一般に, あるクラスに属する関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ +\infty \}\,</math> と<math>g: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ -\infty \}\,</math>が <math>f(x) \geq g(x)\,</math> <math>(\forall \ x \in {\mathbf Z}^{n})\,</math>を満たすならば, ある<math>\alpha \in {\mathbf Z}\,</math>, <math>p \in {\mathbf Z}^{n}\,</math>が存在して <math> f(x) \geq \alpha + \langle p, x \rangle \geq g(x) \qquad (\forall \ x \in {\mathbf Z}^{n})\,</math> が成り立つ,という形の定理を離散分離定理という. ここで, <math>\langle p, x \rangle = \sum_{i=1}^{n}p_{i}x_{i}\,</math>であり, <math>p\,</math>が整数ベクトルに選べることが離散性の反映である.

ラグランジュ関数

2007-07-11T08:49:10Z

211.9.146.139:

'''【らぐらんじゅかんすう (Lagrangian function)】'''

非線形計画問題

\[
\begin{array}{lll}
\mbox{min.} & f_0(x) & \\
\mbox{\rm{s.t.}} & g_i(x) \le 0, & i=1,\dots,k, \\
& h_j(x) = 0, & j=1,\dots,l
\end{array}
\]

に対して次式で定義される関数 <math>L\,</math> をラグランジュ関数という.

\[
L(x,\lambda,\mu):=f_0(x)+\sum_{i=1}^{k}\lambda_{i}g_{i}(x)
+\sum_{j=1}^{l}\mu_{j}h_{j}(x)
\]

また,

<math>(\lambda,\mu)=(\lambda_{1},\dots,\lambda_{k},\mu_{1},\dots,\mu_{l})
\in{{\mathbf R}^{k}_{+}\times{{\mathbf R}^{l}}} \,</math>をラグランジュ乗数と呼ぶ.

ラグランジュ関数は数理計画全般において重要な役割を果たす.

割引き

2007-07-11T08:44:01Z

211.9.146.139:

'''【わりびき (discount)】'''

将来に発生する費用, 利得, 効用などを現在価値に評価する際に用いる操作. 例えば, 離散時間では割引き因子を <math>\beta \in [0, 1)\,</math> として, <math>n\,</math> (<math>= 0, 1, 2, \cdots\,</math>) 期後に発生する費用 <math>c\,</math> を現在価値 <math>\beta^{n} c\,</math> と評価する. 単に <math>\beta = 1/ (1 + \mbox{[無リスク利子率]})\,</math> とすることも多いが, 抽象的に, 意思決定者の時間選好, 異時点間の代替性のパラメータとみなすことも少なくない. 動的最適化を行う際の評価規範として, 割引きのある評価規範を用いることが多い.

割引き

2007-07-11T08:36:58Z

211.9.146.139:

'''【わりびき (discount)】'''

将来に発生する費用, 利得, 効用などを現在価値に評価する際に用いる操作. 例えば, 離散時間では割引き因子を <math>\beta \in [0, 1)\,</math> として, <math>n\,</math> (<math>= 0, 1, 2, \cdots\,</math>) 期後に発生する費用 <math>c\,</math> を現在価値 <math>\beta^{n} c\,</math> と評価する. 単に <math>\beta = 1/ (1 + \mbox{[\,</math>無リスク利子率<math>]})\,</math> とすることも多いが, 抽象的に, 意思決定者の時間選好, 異時点間の代替性のパラメータとみなすことも少なくない. 動的最適化を行う際の評価規範として, 割引きのある評価規範を用いることが多い.

割当問題

2007-07-11T08:33:44Z

211.9.146.139:

'''【わりあてもんだい (assignment problem)】'''

<math>|V^+| = |V^-|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\mathbf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

割当問題

2007-07-11T08:32:38Z

211.9.146.139:

'''【わりあてもんだい (assignment problem)】'''

<math>|V^+| = |V^-|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \mathin A\,</math> の重み <math>w(a) \in {\bf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

割当問題

2007-07-11T08:29:33Z

211.9.146.139:

'''【わりあてもんだい (assignment problem)】'''

<math>|V^+| = |V^-|\,</math> なる2部グラフ <math>G = (V^+, V^-; A)\,</math> および各枝 <math>a \in A\,</math> の重み <math>w(a) \in {\bf R}\,</math>が与えられたときに, 枝の重みの和 <math>\sum_{a \in M}w(a)\,</math> を最大にする完全マッチング <math>M \subseteq A\,</math> を求める問題を割り当て問題と呼ぶ. 最大重み完全マッチング問題とも呼ばれるこの問題は, 最小費用流問題の特殊ケースと見ることもできる. この問題に対し, 効率的な多項式時間解法が数多く提案されている.

ロバース数

2007-07-11T08:23:11Z

211.9.146.139:

'''【ろばーすすう (Lov\'asz number)】'''

与えられた無向グラフ<math>G\,</math>に対して定義される数値 (<math>\vartheta (G)\,</math>と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. <math>G\,</math>のクリーク数<math>w(G)\,</math>と彩色数<math>\chi (G)\,</math>に対し, <math>w(G) \leq \vartheta (\overline{G}) \leq \chi (G)\,</math> が成り立つ事が知られている, ただし <math>\overline{G}\,</math> は<math>G\,</math>の補グラフである.<math>w(G), \chi (G)\,</math> を求めるのはNP困難であるのに対し, <math>\vartheta (\overline{G})\,</math>は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.

ロジットモデル

2007-07-11T08:20:16Z

211.9.146.139:

'''【ろじっともでる (logit model)】'''

非集計行動モデルの中でもっとも広く利用されているモデル. 式の意味が理解しやすく, パラメータの推定も比較的に容易であり, 操作性に優れている. 効用関数の誤差項の確率分布としてガンベル分布を想定しており, 次の一般式が求められる. <math>P_{in}={\mbox{\rm exp}}(V_{in}) / \sum_{j=1}^{J_n}{\mbox{\rm exp}}(V_{jn})\,</math>. ここで, <math>P_{in}\,</math>: 個人 <math>n\,</math> の選択肢 <math>i\,</math> の選択確率, <math>V_{in}\,</math>: 個人 <math>n\,</math> の選択肢 <math>i\,</math> の効用確定項, <math>J_n\,</math>: 個人 <math>n\,</math> の選択肢数.

劣モジュラシステム

2007-07-11T08:15:12Z

211.9.146.139:

'''【れつもじゅらしすてむ (submodular system)】'''

有限集合 <math>N\,</math> の部分集合族 <math>\mathcal{D}\subseteq 2^{N}\,</math> に関して, <math>\emptyset,N\in \mathcal{D}\,</math> かつ <math>X,Y\in\mathcal{D}\Rightarrow X\cup Y, X\cap Y\in{\mathcal D}\,</math> が成り立つものとする. このとき, <math>{\mathcal D}\,</math> は分配束をなす. 劣モジュラ関数 <math>f:{\mathcal D}\to{\bf R}\,</math> が <math>f(\emptyset)=0\,</math> を満たすとき, <math>(\mathcal{D},f)\,</math> を劣モジュラシステムという.

劣モジュラシステム

2007-07-11T08:13:13Z

211.9.146.139:

'''【れつもじゅらしすてむ (submodular system)】'''

有限集合 <math>N\,</math> の部分集合族 <math>\mathcal{D}\subseteq 2^{N}\,</math> に関して, <math>\emptyset,N\in \mathcal{D}\,</math> かつ <math>X,Y\in\mathcal{D}\Rightarrow X\cup Y, X\cap Y\in{\mathcal D}\,</math> が成り立つものとする. このとき, <math>{\mathcal D}\,</math> は分配束をなす. 劣モジュラ関数 <math>f:{\mathcal D}\to{\bf R}\,</math> が <math>f(\emptyset)=0\,</math> を満たすとき, <math>({\mathcal D},f)\,</math> を劣モジュラシステムという.

ロジスティックモデル

2007-07-11T08:09:19Z

211.9.146.139:

'''【ろじすてぃっくもでる (logistic model)】'''

ロジスティックモデルは, 生態学モデルの中で最も単純な1種の個体群の時間変化を記述したモデルである. <math>N\,</math>を時刻<math>t\,</math>における個体数として, <math>N=k/(1+m{\mbox{\rm e}}^{-\lambda t})\,</math>と表現する. ここで, <math>k\,</math>は飽和個体数であり, <math>\lambda\,</math>は定数である. ロジスティックモデルは, 生態学にとどまらず, 人口の増加過程, 新製品の普及過程など様々な社会的現象, ソフトウェア信頼度成長モデルなどの工学にも適用されている.

連続最適化問題

2007-07-11T08:05:06Z

211.9.146.139:

'''【れんぞくさいてきかもんだい (continuous optimization problem)】'''

最適化問題(数理計画問題)

\[
\begin{array}{llll}
\mbox{max.} & f(x) \ \mbox{(あるいは, min. \ $f(x)$)} \\
\mbox{s.t.} & x = (x_1,x_2,\ldots,x_n) \in F,
\end{array}
\]

において, 実行可能集合 <math>F\,</math> が連続関数 <math>g_i\,</math> <math>(i=1,2,\ldots,m)\,</math> と開集合 <math>S\,</math> を用いて,

\[
F = \{ x \in S : g_i(x) \leq 0 \ (i=1,2,\ldots,m) \}
\]

の様に表現され, 変数ベクトル <math>x\,</math> が実数値をとる問題.

連結度 (グラフの)

2007-07-11T07:59:51Z

211.9.146.139:

'''【れんけつど (connectivity of graph)】'''

無向(有向)グラフ<math>G\,</math>の辺の部分集合は, それを除去するとグラフが連結(強連結)でなくなるとき, 辺カットという. <math>G\,</math>の点の部分集合は, それを除去すると残ったグラフが2点以上をもち, かつ連結(強連結)でなくなるとき, 点カットという. 辺カット(点カット)の大きさの最小値を辺連結度(点連結度)という.

レベル (計算幾何における)

2007-07-11T07:56:39Z

211.9.146.139:

'''【れべる (level)】'''

<math>d\,</math>次元超平面アレンジメントにおいて, <math>x_d\,</math>軸に平行な直線で貫いたときに下から <math>k\,</math>番目となる交点をもつフェイス全体の集合を, <math>k\,</math>-レベル, または単にレベルという. 2次元の場合, 高々<math>k\,</math>までのレベルのサイズは<math>{\rm O}(kn)\,</math>であり, <math>k\,</math>-レベルのサイズは<math>{\rm O}(\sqrt{k}n)\,</math>となる. 双対性より, これは平面の<math>n\,</math> 点を直線で等分割する方法の数が<math>{\rm O}(n^{1.5})\,</math>であることも意味する. <math>k\,</math>-レベルを<math>{\rm O}(\sqrt{k}n(\log n)^2)\,</math>時間で求める平面走査法アルゴリズムが知られている.

劣モジュラシステム

2007-07-11T07:50:04Z

211.9.146.139:

'''【れつもじゅらしすてむ (submodular system)】'''

有限集合 <math>N\,</math> の部分集合族 <math>{\cal D}\subseteq 2^{N}\,</math> に関して, <math>\emptyset,N\in{\cal D}\,</math> かつ <math>X,Y\in{\cal D}\Rightarrow X\cup Y, X\cap Y\in{\cal D}\,</math> が成り立つものとする. このとき, <math>{\cal D}\,</math> は分配束をなす. 劣モジュラ関数 <math>f:{\cal D}\to{\bf R}\,</math> が <math>f(\emptyset)=0\,</math> を満たすとき, <math>({\cal D},f)\,</math> を劣モジュラシステムという.

劣モジュラシステム

2007-07-11T07:07:31Z

211.9.146.139:

'''【れつもじゅらしすてむ (submodular system)】'''

有限集合 <math>N\,</math> の部分集合族 <math>{\cal D}\subseteq 2^N\,</math> に関して, <math>\emptyset,N\in{\cal D}\,</math> かつ <math>X,Y\in{\cal D}\Rightarrow X\cup Y, X\cap Y\in{\cal D}\,</math> が成り立つものとする. このとき, <math>{\cal D}\,</math> は分配束をなす. 劣モジュラ関数 <math>f:{\cal D}\to{\bf R}\,</math> が <math>f(\emptyset)=0\,</math> を満たすとき, <math>({\cal D},f)\,</math> を劣モジュラシステムという.