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

ある工場の機械は、各期のはじめに「良好」（状態 $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,2$ の 2 つであるマルコフ決定過程を考える。各時刻に、現在の状態で行動を 1 つ選ぶと、即時報酬を受け取り、次の状態へ確率的に遷移する。行動・報酬・遷移確率は次のとおりである。

• 状態 $1$ で行動 $a$：報酬 $1$ を受け取り、確率 $1$ で状態 $1$ にとどまる。
• 状態 $1$ で行動 $b$：報酬 $0$ を受け取り、確率 $1$ で状態 $2$ へ移る。
• 状態 $2$ で行動 $c$：報酬 $4$ を受け取り、確率 $\frac{1}{2}$ で状態 $2$ にとどまり、確率 $\frac{1}{2}$ で状態 $1$ へ移る。
• 状態 $2$ で行動 $d$：報酬 $2$ を受け取り、確率 $1$ で状態 $2$ にとどまる。

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

ある農家の畑の状態は、各期のはじめに「やせ地」（状態 $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))$ で求めよ。

3 つの工場 $A_1,A_2,A_3$ から 3 つの店舗 $B_1,B_2,B_3$ へ、ある製品を輸送する。各工場の供給量は $A_1$ が $30$、$A_2$ が $40$、$A_3$ が $20$ であり、各工場は供給量をすべて出荷する。各店舗の需要量は $B_1$ が $35$、$B_2$ が $40$、$B_3$ が $35$ であり、各店舗へは需要量を超えて輸送しない。工場 $A_i$ から店舗 $B_j$ へ製品 $1$ 単位を輸送する費用は次の表のとおりである。

総供給量が総需要量より少ないため、需要を満たせない店舗が出る。店舗 $B_1,B_2,B_3$ で不足する製品 $1$ 単位あたり、それぞれ $12$, $10$, $9$ の不足費用がかかる。輸送量は $0$ 以上の実数とする。輸送費用と不足費用の合計の最小値を求めよ。

ある販売店では、ある商品の需要が年間 $4500$ 個で、一定の割合で生じる。この商品の在庫管理について、次を仮定する。

• $1$ 回の発注ごとに、発注量によらず $400$ 円の発注費用がかかる。発注した商品は一度に納入され、納入までの時間は $0$ とみなす。
• 在庫 $1$ 個を $1$ 年間保管すると $250$ 円の保管費用がかかる（保管費用は在庫量と時間に比例する）。
• 在庫が $0$ のときに生じた需要は品切れ（受注残）として残し、次の納入時にすべて満たす。受注残 $1$ 個を $1$ 年間残すと $200$ 円の品切れ費用がかかる（品切れ費用は受注残の量と時間に比例する）。
• 毎回の発注量は同じ $Q$ 個であり、毎回、受注残が同じ量 $B$ 個（$0\le B\le Q$）に達した時点で発注・納入して受注残をすべて満たす。

$Q,B$ は正の実数（$B$ は $0$ 以上の実数）として扱い、商品の購入単価は考えない。年間の発注費用・保管費用・品切れ費用の合計を最小にする発注量 $Q$ と、そのときの年間費用の合計（円）を、この順に組で求めよ。