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

ある農家の畑の状態は、各期のはじめに「やせ地」（状態 $1$）か「肥沃地」（状態 $2$）のどちらかである。各期のはじめに状態を見て行動を 1 つ選ぶと、その期の報酬が得られ、次の期のはじめの状態が次の確率で決まる。

• 状態 $1$ で行動「耕作」：報酬 $1$、次の状態は確率 $1$ で状態 $1$
• 状態 $1$ で行動「土壌改良」：報酬 $0$、次の状態は確率 $\frac{1}{2}$ で状態 $1$、確率 $\frac{1}{2}$ で状態 $2$
• 状態 $2$ で行動「集約栽培」：報酬 $3$、次の状態は確率 $\frac{3}{4}$ で状態 $2$、確率 $\frac{1}{4}$ で状態 $1$
• 状態 $2$ で行動「休耕併用」：報酬 $2$、次の状態は確率 $1$ で状態 $2$

割引率を $\gamma =\frac{4}{5}$ とし、無限期間にわたる割引総報酬の期待値 $E\left[\sum _{t=0}^{\infty }{\gamma }^t{r}_t\right]$（$r_t$ は第 $t$ 期の報酬）を最大化する。状態 $1$ から始めたときの最適価値 $V^{\ast }(1)$ と、状態 $2$ から始めたときの最適価値 $V^{\ast }(2)$ を、この順に組 $(V^{\ast }(1),V^{\ast }(2))$ で求めよ。

状態が $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]$$
で定める。この長期平均報酬のすべての方策にわたる最大値（最適平均報酬）を求めよ。なお、状態と行動が有限のこのマルコフ決定過程では、最適な方策が定常な決定的方策（各状態で常に同じ行動を選ぶ方策）の中に存在し、その最適平均報酬は初期状態によらないことを用いてよい。

ある工場の機械は、各期のはじめに「良好」（状態 $1$）、「劣化」（状態 $2$）、「故障」（状態 $3$）のいずれかの状態にある。各期のはじめに状態を観測して行動を $1$ つ選ぶ。行動を選ぶと、その期の費用がかかる。次の期のはじめの状態は、現在の状態と選んだ行動だけで、次の確率で決まる。

• 状態 $1$：
• 行動「運転」：費用 $0$。次の状態は確率 $\frac{3}{4}$ で $1$、確率 $\frac{1}{4}$ で $2$。
• 行動「予防点検」：費用 $\frac{3}{2}$。次の状態は確率 $1$ で $1$。
• 状態 $2$：
• 行動「運転」：費用 $2$。次の状態は確率 $\frac{1}{2}$ で $2$、確率 $\frac{1}{2}$ で $3$。
• 行動「修理」：費用 $9$。次の状態は確率 $1$ で $1$。
• 状態 $3$：
• 行動「交換」（これしか選べない）：費用 $10$。次の状態は確率 $1$ で $1$。

第 $t$ 期（$t=0,1,2,\dots$）にかかる費用を $c_t$ とし、割引率を $\beta =\frac{4}{5}$ とする。無限期間の期待割引総費用 $E\left[\sum _{t=0}^{\infty }{\beta }^t{c}_t\right]$ を最小にするように行動を選ぶとき、第 $0$ 期のはじめの状態が $1$ である場合の期待割引総費用の最小値 $V^{\ast }(1)$ を求めよ。

ある工場の機械の状態は、各期のはじめに「良好」「劣化」「故障」のいずれかである。各期のはじめに機械の状態を見て行動を 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$ とする）ものとし、割引は行わない。このとき、利益の合計の期待値の最大値を求めよ。

$n\ge 2$ を整数とし、$n$ 人の作業者 $1,\dots ,n$ を $n$ 個の仕事 $1,\dots ,n$ に 1 対 1 に割り当てる割当問題を考える。作業者 $i$ に仕事 $j$ を割り当てたときの費用を実数 $c_{ij}$ とし、$\{1,\dots ,n\}$ 上の置換 $\sigma$（作業者 $i$ に仕事 $\sigma (i)$ を割り当てる）の総費用を
$$F(\sigma )=\sum _{i=1}^n{c}_{i\sigma (i)}$$
とする。費用が次の条件（モンジュ条件）を満たすとする:
$$1\le i<k\le n,1\le j<l\le n\text{ を満たすすべての }i,j,k,l\text{ について}{c}_{ij}+c_{kl}\le c_{il}+c_{kj}.$$
このとき、恒等置換 $\mathrm{id}$（作業者 $i$ に仕事 $i$ を割り当てる）は割当問題の最適解であること、すなわちすべての置換 $\sigma$ に対して $F(\mathrm{id})\le F(\sigma )$ が成り立つことを証明せよ。