オペレーションズ・リサーチ

同義語:オペレーションズリサーチオペレーションリサーチoperations researchoperational research

概要

オペレーションズ・リサーチ(operations research)とは、物資・人員・時間・資金の使い方についての意思決定を数理モデルに書き表し、数学と計算によって良い決定を求める分野である。線形計画・ネットワーク・整数計画・非線形計画・動的計画は最適な決定を求める型のモデルで、待ち行列や模擬は与えた決定の結果を調べる型のモデルである。たとえば、一定の需要 $D$、1 回の発注費用 $K$、保管費 $h$ のもとで時間あたりの費用を最小にする発注量は $\sqrt{2KD/h}$ であり、作業の日程の最短の工期は先行関係の最長の道の長さに等しい。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 最適化, 線形計画法

オペレーションズ・リサーチ(operations research)とは、物資・人員・時間・資金の使い方についての意思決定を数理モデルに書き表し、数学と計算によって良い決定を求める分野である。中心の問いは、現実の問題をどの数理モデルに書けば解けるか、そのモデルをどう解くか、得られた解は仮定を変えるとどう動くか、の 3 つである。英国では operational research とよばれ、経営の意思決定に向けた分野としては management science の名でもよばれる(BHM77 p. 1)。
この記事は分野の地図である。扱う問題と代表的な結果を表にして、それぞれの記事へ案内する。続いて、この分野の味が分かる 2 つの計算として、在庫の発注量と作業の日程を証明つきで扱う。

定義

オペレーションズ・リサーチの対象は、「決められること」と「その良し悪しの測り方」を数式で書いたものである。

意思決定モデル

意思決定モデル とは、決定の候補の集合 $X$ と、決定 $x\in X$ の費用を与える関数 $f\colon X\to\mathbb{R}$ の組である。利益は符号を変えて費用として扱う。費用が不確実な要素にもよるときは、それを確率変数 $\omega$ で表して $f\colon X\times\Omega\to\mathbb{R}$ とし、たとえば期待値 $\mathbb{E}[f(x,\omega)]$ で決定 $x$ を評価する。費用またはその評価の値を $X$ の上で最小にする $x$ を 最適な決定 という。

$X$ を不等式で書いたものが 最適化 の最適化問題であり(BV04 §1.1、pp. 1–2)、現実の状況から $X$ と $f$ を書き下す作業を 定式化 という。同じ現実の問題でも定式化によって解きやすさが変わるので、定式化そのものが分野の主題の 1 つである(BHM77 Chapter 1)。
モデルの使い方は 2 通りある(BHM77 Table 1.1、p. 5)。

  • 候補を自動で生成するモデル:候補の範囲を制約で与え、手順によって最適な候補を求める。線形計画・ネットワーク・整数計画・非線形計画がこの型で、不確実性があるものとして動的計画や在庫の理論がある。
  • 与えた候補を評価するモデル:利用者が候補を決め、モデルでその結果を調べる。待ち行列の理論や Monte Carlo法 による模擬がこの型である。

主な問題と結果の一覧

問い代表的な結果入る記事
限られた資源をどう配分するか主問題と双対問題がともに実行可能なら 2 つの最適値は一致する(双対定理)線形計画法
網の上でどう流すか最大流の流量は最小カットの容量に等しく、容量が整数なら整数値の最大流があるネットワークフロー
最短の経路はどれか辺の長さが $0$ 以上なら、Dijkstra 法が 1 点から各頂点への距離を求めるDijkstra法
人と仕事をどう組むかハンガリー法は、費用が整数なら有限回で止まって最適な割り当てを与える割当問題
する・しないをどう選ぶか分枝限定法は有界な問題を有限回で解く。行列が完全単模で右辺が整数なら、線形計画緩和の頂点は整数である整数計画法、完全単模行列
順路をどう決めるか費用が三角不等式を満たす巡回セールスマン問題には $3/2$-近似の手順がある。費用に仮定がなければ、定数倍以内の多項式時間の手順があるだけで P $=$ NP となる巡回セールスマン問題、組合せ最適化
費用が 1 次式でないときどうするか微分できる凸最適化問題では、Slater 条件のもとで KKT条件 が最適性の必要十分条件である凸最適化、非線形計画法
何段にも重なる決定をどうするか最適な決定の列の後半はそれ自身最適であり、価値関数の漸化式を後ろから解けばよい動的計画法と最適制御
待ち行列はどれだけ伸びるか平均人数 $L$、到着率 $\lambda$、平均滞在時間 $W$ の間に $L=\lambda W$ が成り立つ待ち行列理論
競争相手がいるときどうするか行列ゲームの 2 人の値は一致する(最小最大定理)線形計画法
乱数で結果を調べる標本平均の誤差の標準偏差は標本数 $n$ について $\sigma/\sqrt n$ であるMonte Carlo法
いくつずつ発注するか一定の需要なら最適な発注量は $\sqrt{2KD/h}$ であるこの記事の prop-or-eoq
工事はいつ終わるか最短の工期は作業の鎖の最長の長さに等しいこの記事の thm-or-cpm

線形計画の解法である 単体法 は、1947 年に Dantzig が米国空軍の研究グループ Project SCOOP で開発した(BHM77 p. 1)。分野そのものが知識の体系として認められるようになったのは第二次世界大戦のころである(同)。

具体例 1:在庫の発注量

同じ品物を売り続ける店を考える。需要は時間あたり一定の $D>0$ 個で、品切れは許さない。1 回の発注には個数によらない費用 $K>0$ がかかり、発注した品はすぐに届く。在庫には 1 個・単位時間あたり $h>0$ の保管費がかかる。在庫が $0$ になるたびに同じ個数 $Q>0$ を発注する方法の中で、時間あたりの費用を最小にしたい。
周期は $Q/D$ で、在庫は 1 周期の間に $Q$ から $0$ まで直線的に減るので、平均在庫は $Q/2$ である。よって時間あたりの費用は
$$ C(Q)=\frac{KD}{Q}+\frac{hQ}{2} $$
である。第 1 項は発注の回数に比例して $Q$ とともに減り、第 2 項は平均在庫に比例して $Q$ とともに増える。

経済的発注量

$C(Q)$ は $Q^*:=\sqrt{2KD/h}$ でだけ最小になり、最小値は $C(Q^*)=\sqrt{2KDh}$ である。さらに、$r:=Q/Q^*$ とおくと
$$ \frac{C(Q)}{C(Q^*)}=\frac12\left(r+\frac1r\right) $$
である。

2 つの正の数の相加平均と相乗平均の不等式により
$$ C(Q)=\frac{KD}{Q}+\frac{hQ}{2}\ge2\sqrt{\frac{KD}{Q}\cdot\frac{hQ}{2}}=\sqrt{2KDh} $$
であり、等号は $\frac{KD}{Q}=\frac{hQ}{2}$、すなわち $Q^2=2KD/h$ のときに限る。$Q^*$ では 2 つの項が等しいので、どちらも $\frac12C(Q^*)$ である。$Q=rQ^*$ を代入すると、第 1 項は $Q^*$ での値の $1/r$ 倍、第 2 項は $r$ 倍になるので
$$ C(rQ^*)=\frac12C(Q^*)\cdot\frac1r+\frac12C(Q^*)\cdot r $$
を得る。$\square$

数値の例

$D=1200$(個/年)、$K=6000$(円/回)、$h=40$(円/個・年)とする。$Q^*=\sqrt{2\cdot6000\cdot1200/40}=600$ 個で、発注は年 2 回、費用は $C(Q^*)=12000+12000=24000$ 円/年である。発注量を半分の $300$ 個にすると、$r=\frac12$ なので費用は $\frac12(\frac12+2)=\frac54$ 倍の $30000$ 円/年になる。直接計算しても $24000+6000=30000$ である。

この比の式が、モデルの使い方を教える。$D,K,h$ の見積もりが多少ずれて $Q$ が最適の 2 倍や半分になっても、費用の増加は $25\%$ にとどまる。prop-or-eoq は「一定量ずつ発注する方法の中で最良」という主張であり、需要が変動する場合の計算は 動的計画法と最適制御 の例題「4 期の在庫管理」の型になる。

具体例 2:作業の日程

大きな工事は多くの作業からなり、ある作業は別の作業が終わらないと始められない。これを有向グラフで表す(BHM77 §8.3 の Critical-Path Method、pp. 234–237 の考え方)。
有限個の作業の集合 $V$ と、各作業 $v$ の所要時間 $d(v)\ge0$、閉路のない有向グラフ $G=(V,A)$ が与えられているとする。$(u,v)\in A$ は「$u$ が終わるまで $v$ を始められない」ことを表す。日程 とは、すべての $(u,v)\in A$ で $s(v)\ge s(u)+d(u)$ を満たす $s\colon V\to[0,\infty)$($s(v)$ は $v$ の開始時刻)であり、その 工期 は $\max_{v}\,(s(v)+d(v))$ である。$G$ の有向道 $v_1\to\dots\to v_k$ の 長さ を $d(v_1)+\dots+d(v_k)$ とする($k=1$ も含める)。

最短の工期は最長の道の長さ

$V$ が空でないとき、日程の工期の最小値は $G$ の有向道の長さの最大値 $T$ に等しい。

任意の日程 $s$ と有向道 $v_1\to\dots\to v_k$ について、$s(v_{i+1})\ge s(v_i)+d(v_i)$ を足し合わせると $s(v_k)+d(v_k)\ge s(v_1)+\sum_{i=1}^kd(v_i)\ge\sum_{i=1}^kd(v_i)$ なので、工期は $T$ 以上である。
逆に、$G$ は閉路をもたないので頂点を位相的整列で並べられ、先行する作業のない $v$ で $e(v):=0$、それ以外の $v$ で
$$ e(v):=\max_{(u,v)\in A}\,(e(u)+d(u)) $$
と順に定められる。$e$ は定義から日程である。並べた順の帰納法で、$e(v)+d(v)$ は $v$ で終わる有向道の長さの最大値に等しい。よって $e$ の工期は $T$ である。$\square$

$e(v)$ を 最早開始時刻 という。後ろからも同様に、後続の作業のない $v$ で $l(v):=T-d(v)$、それ以外で $l(v):=\min_{(v,w)\in A}l(w)-d(v)$ と定めたものを 最遅開始時刻 といい、$l(v)-e(v)$ を 余裕 という。余裕が $0$ の作業を遅らせると工期が延びるので、管理はそこに集中すればよい。

5 つの作業

作業 A〜E の所要時間と先行関係を次の表の左の 3 列とする。

作業所要先行する作業$e$$l$余裕
A3なし000
B2なし033
C4A330
D2A, B352
E3C, D770

極大な有向道は A→C→E(長さ 10)、A→D→E(長さ 8)、B→D→E(長さ 7)の 3 本なので、最短の工期は $T=10$ である。余裕が $0$ の作業 A, C, E が最長の道をなす。

反例:平均だけではモデルにならない

「到着と処理の平均の速さが同じなら、窓口の混み方も同じ」は成り立たない。1 分あたりの平均到着数 $\lambda=0.9$ で、処理に平均 1 分かかる窓口を 2 通り考える。

モデル到着と処理平均人数 $L$
確定的到着はちょうど $10/9$ 分おき、処理はちょうど 1 分$0.9$
確率的(M/M/1)到着は Poisson 過程、処理時間は平均 1 分の指数分布$9$

確定的なモデルでは誰も待たず、滞在時間は 1 分なので、待ち行列理論 の公式 $L=\lambda W$ により $L=0.9$ である。確率的なモデルでは利用率 $\rho=0.9$ で $L=\rho/(1-\rho)=9$ である。平均の速さはどちらも同じで、変わったのはばらつきだけである。不確実性をモデルに入れるかどうかは、結論を桁で変えることがある。

読み進め方

段階記事身につくこと
1. 土台最適化 → 線形計画法問題の書き方、双対、単体法の仕組み
2. 網と組合せDijkstra法 → ネットワークフロー → 割当問題 → 組合せ最適化グラフの上の問題と、整数の解が出る理由
3. 整数と非線形整数計画法、凸最適化 → 非線形計画法緩和と分枝限定、KKT 条件と反復法
4. 時間と不確実性動的計画法と最適制御、Markov連鎖 → Markov決定過程、待ち行列理論、Monte Carlo法段階の決定、確率的なモデルと模擬

段階 2 と段階 3 は独立に読める。段階 4 の確率の部分は、確率論の基礎を前提にする。

関連項目

参考文献

[1]
Stephen P. Bradley, Arnoldo C. Hax, Thomas L. Magnanti, Applied Mathematical Programming, Addison-Wesley, 1977, Chapter 1:導入(分野の名前、Dantzig と Project SCOOP、p. 1)、Table 1.1(p. 5)、§8.3 The Critical-Path Method(pp. 234–237)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する