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

有限集合 $S$ を状態の集合、有限集合 $A$ を行動の集合とする（ともに空でない）。各 $s\in S,a\in A$ に対して遷移確率 $p(s^{\prime }\mid s,a)\ge 0$（${\sum }_{s^{\prime }\in S}p(s^{\prime }\mid s,a)=1$）が与えられ、割引率 $\gamma$ は $0<\gamma <1$ を満たすとする。

2 つの報酬関数 $r,r^{\prime }:S\times A\to \mathbb{R}$ が、すべての $s\in S,a\in A$ で $r(s,a)\le r^{\prime }(s,a)$ を満たすとし、
$$\delta =\underset{s\in S,a\in A}{\max }(r^{\prime }(s,a)-r(s,a))$$
とおく。関数 $W,U:S\to \mathbb{R}$ はそれぞれ、報酬 $r$, $r^{\prime }$ に対するベルマン最適方程式
$$W(s)=\underset{a\in A}{\max }\{r(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)W(s^{\prime })\},U(s)=\underset{a\in A}{\max }\{r^{\prime }(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)U(s^{\prime })\}(s\in S)$$
を満たすとする（このような $W$, $U$ が存在することは用いてよい）。

すべての $s\in S$ について
$$0\le U(s)-W(s)\le \frac{\delta }{1-\gamma }$$
が成り立つことを証明せよ。

状態が $1,2,3$ の $3$ つであるマルコフ決定過程を考える。各時刻 $t=0,1,2,\dots$ に現在の状態を見て行動を $1$ つ選ぶと、その時刻の報酬を受け取り、次の時刻の状態が次の確率で決まる（$p_{ij}$ は状態 $i$ から状態 $j$ へ遷移する確率）。

• 状態 $1$ で行動 $a$：報酬 $2$、$(p_{11},p_{12},p_{13})=\left(\frac{1}{2},\frac{1}{2},0\right)$
• 状態 $1$ で行動 $b$：報酬 $0$、$(p_{11},p_{12},p_{13})=(0,0,1)$
• 状態 $2$ で行動 $a$：報酬 $4$、$(p_{21},p_{22},p_{23})=\left(\frac{1}{3},\frac{2}{3},0\right)$
• 状態 $2$ で行動 $b$：報酬 $1$、$(p_{21},p_{22},p_{23})=\left(0,\frac{1}{2},\frac{1}{2}\right)$
• 状態 $3$ で行動 $c$（選べる行動はこれのみ）：報酬 $6$、$(p_{31},p_{32},p_{33})=\left(\frac{1}{2},\frac{1}{4},\frac{1}{4}\right)$

方策 $\pi$ のもとで時刻 $t$ に得る報酬を $R_t$ とし、初期状態 $i$ からの長期平均報酬を
$$g^{\pi }(i)=\underset{N\to \infty }{\lim }\frac{1}{N}{E}^{\pi }\left[\sum _{t=0}^{N-1}{R}_t|X_0=i\right]$$
で定める。この長期平均報酬のすべての方策にわたる最大値（最適平均報酬）を求めよ。なお、状態と行動が有限のこのマルコフ決定過程では、最適な方策が定常な決定的方策（各状態で常に同じ行動を選ぶ方策）の中に存在し、その最適平均報酬は初期状態によらないことを用いてよい。

あるプロジェクトは作業 $A,B,C,D,E,F,G$ の $7$ つからなる。各作業の所要日数には、楽観値 $a$、最可能値 $m$、悲観値 $b$ の $3$ つの見積もりが与えられている。先行作業とは、その作業を始める前にすべて終わっていなければならない作業のことである。

PERT の手法に従い、各作業の所要日数の期待値 $t_e$ と分散 ${\sigma }^2$ を
$$t_e=\frac{a+4m+b}{6},{\sigma }^2={\left(\frac{b-a}{6}\right)}^2$$
で定める。各作業の所要日数を $t_e$ として最早開始時刻を計算し、プロジェクトの完了時刻（期待値）$T$ とクリティカルパスを求める。さらに、クリティカルパス上の作業の所要日数は互いに独立であるとして、クリティカルパス上の作業の分散の和 $V$ を求める。

$T$ と $V$ をこの順に組 $(T,V)$ で答えよ。なお、プロジェクトは時刻 $0$ に開始し、先行作業がすべて終わればその作業はすぐに開始できるものとする。

ある工場の機械の状態は、各期のはじめに「良好」「劣化」「故障」のいずれかである。各期のはじめに機械の状態を見て行動を 1 つ選ぶと、その期の利益（負の値は費用）が得られ、次の期のはじめの状態が次の確率で決まる。

• 良好のとき：行動は「運転」だけである。利益 $10$ を得て、次の期は確率 $\frac{7}{10}$ で良好、確率 $\frac{3}{10}$ で劣化になる。
• 劣化のとき：「運転」か「修理」を選ぶ。
• 運転：利益 $6$ を得て、次の期は確率 $\frac{1}{2}$ で劣化、確率 $\frac{1}{2}$ で故障になる。
• 修理：利益 $-2$ を得て、次の期は確率 $1$ で良好になる。
• 故障のとき：行動は「交換」だけである。利益 $-8$ を得て、次の期は確率 $1$ で良好になる。

第 $1$ 期のはじめに機械が良好であるとき、第 $1$ 期から第 $3$ 期までの $3$ 期間の利益の合計の期待値を最大にするように各期の行動を選ぶ。第 $3$ 期の終わりの機械の状態には価値がない（$0$ とする）ものとし、割引は行わない。このとき、利益の合計の期待値の最大値を求めよ。

あるプロジェクトは作業 $1$ から作業 $8$ までの $8$ つの作業からなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

各作業は、先行作業がすべて終わればすぐに始めることができ、同時に進められる作業の数に制限はない。プロジェクトは時刻 $0$ に始まり、すべての作業が終わった時点で完了する。プロジェクトの完了時刻を最も早い値にしたとき、全余裕（最遅開始時刻と最早開始時刻の差）が $0$ である作業の番号の集合を求めよ。