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

扱うテーマ: 待ち行列（M/M/1・M/M/c）の平均待ち時間・系内人数、在庫管理（経済的発注量）、割当問題・輸送問題の最適値、最短路・PERT の最早開始時刻とクリティカルパス、マルコフ決定過程の最適価値

難易度の目安（大学数学）

難易度 1 教科書の例題レベル
難易度 2 教科書の演習問題レベル
難易度 3 期末試験の応用レベル
難易度 4 大学院入試の標準レベル
難易度 5 大学院入試の難問・数学コンテストレベル

キーワードで探す →

難易度 1（教科書の例題レベル）
駐車スペースが $3$ 台分だけある小さな駐車場がある。時刻 $t$ に駐車している車の台数を $X (t)$ とし、 $X (t)$ は状態 $0, 1, 2, 3$ をとる出生死滅過程であるとする。推移率は次のとおりである。
- 到着率： $n = 0, 1, 2$ のとき $λ_{n} = 2$ （台/時）。満車（ $n = 3$ ）のときは到着した車は入らずに去るので $λ_{3} = 0$ 。
- 退去率： $n = 1, 2, 3$ のとき $μ_{n} = n$ （台/時）。これは、駐車している各車が平均 $1$ 時間の指数分布に従う時間で互いに独立に出ていくことを表す。
定常状態で駐車場が満車である確率 $p_{3}$ を求めよ。
難易度 1（教科書の例題レベル）
ある工場に同じ型の機械が $2$ 台あり、修理係が $1$ 人いる。各機械は、動いている間、故障率 $\frac{1}{2}$ （回/日）で互いに独立に故障する。つまり、動いている時間は平均 $2$ 日の指数分布に従う。故障した機械は修理係が $1$ 台ずつ修理する。修理時間は平均 $\frac{1}{2}$ 日の指数分布に従う（修理率 $2$ （台/日））。修理中でない故障機械は待つ。
時刻 $t$ に故障している機械の台数を $X (t)$ とする。 $X (t)$ は状態 $0, 1, 2$ をとる出生死滅過程である。状態 $n$ からの「出生率」（故障が起こる率）は $λ_{n} = (2 - n) \cdot \frac{1}{2}$ 、「死滅率」（修理が終わる率）は $μ_{n} = 2 (n = 1, 2)$ である。
十分長い時間がたった後（定常状態）に、 $2$ 台とも故障している確率 $p_{2}$ を求めよ。
難易度 1（教科書の例題レベル）
ある工場に機械が $2$ 台あり、修理係が $1$ 人いる。稼働中の機械は、それぞれ互いに独立に、平均 $1$ 時間の指数分布に従う時間だけ動いた後に故障する（ $1$ 台あたりの故障率は $1$ （回/時））。故障した機械は修理係が $1$ 台ずつ修理し、修理時間は平均 $30$ 分の指数分布に従う（修理率 $2$ （台/時））。修理中にもう $1$ 台が故障したときは、その機械は修理を待つ。修理が終わった機械はすぐに稼働を再開する。
故障している機械の台数（修理中と修理待ちの合計）を状態 $n (n = 0, 1, 2)$ とする出生死滅過程を考える。定常状態において、 $2$ 台とも故障している確率 $p_{2}$ を求めよ。
難易度 1（教科書の例題レベル）
あるコーヒー焙煎所では、原料の生豆を年間 $6000 kg$ 使う。使用は一年を通して一定の割合で進む。生豆は毎回 $Q kg$ （ $Q > 0$ は実数）ずつ発注し、次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $3000$ 円の発注費用がかかる。
- 発注した生豆は、在庫がちょうど $0$ になった瞬間に一度に全部届く（納入までの期間は $0$ とみなし、品切れは起こさない）。
- 生豆 $1 kg$ を $1$ 年間保管すると $100$ 円の保管費用がかかり、保管費用は平均在庫量に比例する。
- 生豆の購入代金は発注量によらないので考えない。
年間の発注費用と保管費用の合計（年間総費用）が最小になるように $Q$ を選ぶとき、年間総費用の最小値は何円か。
難易度 1（教科書の例題レベル）
ある喫茶店では、コーヒー豆を袋単位で仕入れている。コーヒー豆の需要は年間 $2000$ 袋で、一年を通じて一定の割合で生じる。在庫管理について、次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $500$ 円の発注費用がかかる。
- $1$ 袋を $1$ 年間保管すると $50$ 円の保管費用がかかる。
- 毎回 $Q$ 袋（ $Q > 0$ ）ずつ発注し、在庫がちょうど $0$ になった瞬間に $Q$ 袋が一度に届く（調達期間は $0$ 、品切れは起こさない）。
- 発注費用と保管費用以外の費用は考えない。
$1$ 年間の発注費用と保管費用の合計を年間総費用とする。 $Q$ を正の実数の範囲で動かすとき、年間総費用の最小値は何円か。
難易度 1（教科書の例題レベル）
ある喫茶店では、コーヒー豆を年間 $1600$ kg 使用する。使用は一年を通じて一定の割合で行われる。コーヒー豆の仕入れについて、次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $5000$ 円の発注費用がかかる。
- 毎回 $Q$ kg ずつ発注し、発注したコーヒー豆は在庫がちょうど $0$ になった瞬間に一度に全部届く（品切れは起こさない）。
- コーヒー豆 $1$ kg を $1$ 年間保管するのに $400$ 円の保管費用がかかる。保管費用は平均在庫量 $\frac{Q}{2}$ kg に対してかかるものとする。
- 年間総費用は、年間の発注費用と年間の保管費用の和とする（豆の購入代金は発注量によらないので含めない）。
$Q$ を正の実数として、年間総費用の最小値（円）を求めよ。
難易度 1（教科書の例題レベル）
タクシー会社が、4 台のタクシー $T_{1}, T_{2}, T_{3}, T_{4}$ を 4 人の客 $C_{1}, C_{2}, C_{3}, C_{4}$ のもとへ配車する。各タクシーはちょうど 1 人の客を担当し、各客にはちょうど 1 台のタクシーが向かう。タクシー $T_{i}$ が客 $C_{j}$ のもとに着くまでの時間（分）は次の表のとおりである。
$T_{1} T_{2} T_{3} T_{4} C_{1} 9685 C_{2} 4376 C_{3} 7548 C_{4} 8967$
4 台の到着時間の合計を最小にするとき、その最小値（分）を求めよ。
難易度 1（教科書の例題レベル）
ある工場に 4 台の機械 $M_{1}, M_{2}, M_{3}, M_{4}$ があり、4 種類の製品 $P_{1}, P_{2}, P_{3}, P_{4}$ を 1 種類ずつ加工させる。各機械はちょうど 1 種類の製品を担当し、各製品はちょうど 1 台の機械が担当する。機械 $M_{i}$ が製品 $P_{j}$ を加工するのにかかる時間（単位：時間）は、次の表の第 $i$ 行・第 $j$ 列の値である。
$M_{1} M_{2} M_{3} M_{4} P_{1} 55410 P_{2} 7476 P_{3} 8388 P_{4} 6666$
4 台の加工時間の合計が最小になるように割り当てるとき、その合計時間の最小値を求めよ。
難易度 1（教科書の例題レベル）
ある配送センターで、4 台の配送車 $T_{1}, T_{2}, T_{3}, T_{4}$ を 4 つの配送地区 $A_{1}, A_{2}, A_{3}, A_{4}$ に 1 台ずつ割り当てる。各配送車はちょうど 1 つの地区を担当し、各地区はちょうど 1 台が担当する。配送車 $T_{i}$ が地区 $A_{j}$ を担当したときにかかる時間（分）は、次の表の $i$ 行 $j$ 列の値である。
$T_{1} T_{2} T_{3} T_{4} A_{1} 5378 A_{2} 8746 A_{3} 7367 A_{4} 781011$
4 台の所要時間の合計の最小値（分）を求めよ。
難易度 1（教科書の例題レベル）
2 つの倉庫 $P_{1}, P_{2}$ から 3 つの店舗 $Q_{1}, Q_{2}, Q_{3}$ へ、ある商品を輸送する。各倉庫の在庫量（送り出せる量の上限）は $P_{1}$ が $40$ 、 $P_{2}$ が $50$ である。各店舗の需要量は $Q_{1}$ が $20$ 、 $Q_{2}$ が $30$ 、 $Q_{3}$ が $25$ で、需要はちょうど満たさなければならない。商品 1 単位あたりの輸送費（千円）は次の表のとおりである。
$P_{1} P_{2} Q_{1} 45 Q_{2} 62 Q_{3} 37$
在庫量の合計と需要量の合計を比べ、供給が余る場合は輸送費 $0$ のダミーの店舗 $Q_{4}$ を表のいちばん右の列に加えて需給を釣り合わせる（ $Q_{4}$ へ送る量は倉庫に残る量を表す）。このように釣り合わせた輸送表に北西隅法を用いて初期の実行可能解を作るとき、その解の総輸送費（千円）を求めよ。
難易度 1（教科書の例題レベル）
2 つの倉庫 $P_{1}, P_{2}$ から 3 つの営業所 $Q_{1}, Q_{2}, Q_{3}$ へ、ある部品を輸送する。各倉庫から出荷できる量（上限）は $P_{1}$ が $50$ 、 $P_{2}$ が $40$ であり、各営業所の需要量は $Q_{1}$ が $30$ 、 $Q_{2}$ が $30$ 、 $Q_{3}$ が $20$ である。各営業所には需要量ちょうどを届ける。部品 1 単位あたりの輸送費は次の表のとおりである。
$Q_{1}$ $Q_{2}$ $Q_{3}$
$P_{1}$ $4$ $6$ $3$
$P_{2}$ $5$ $2$ $7$
供給量の合計と需要量の合計を比べ、余る分を受け入れるダミーの営業所 $Q_{4}$ （各倉庫からの 1 単位あたりの輸送費は $0$ ）を表の右端の列として加えて需給を釣り合わせる。この表（行の順は $P_{1}, P_{2}$ 、列の順は $Q_{1}, Q_{2}, Q_{3}, Q_{4}$ ）に北西隅法を適用して初期の実行可能解を作るとき、その総輸送費を求めよ。
難易度 1（教科書の例題レベル）
2 つの倉庫 $P_{1}, P_{2}$ から 3 つの店舗 $Q_{1}, Q_{2}, Q_{3}$ へ、ある商品を輸送する。各倉庫の在庫量（出荷できる量の上限）は $P_{1}$ が $50$ 、 $P_{2}$ が $40$ であり、各店舗の需要量は $Q_{1}$ が $20$ 、 $Q_{2}$ が $25$ 、 $Q_{3}$ が $30$ で、需要はちょうど満たさなければならない。商品 1 単位あたりの輸送費は次の表のとおりである。
$Q_{1}$ $Q_{2}$ $Q_{3}$
$P_{1}$ $4$ $6$ $3$
$P_{2}$ $5$ $2$ $7$
需給を釣り合わせるため、輸送費がすべて $0$ のダミーの店舗 $Q_{4}$ を表の最も右の列に加える。行の順を $P_{1}, P_{2}$ 、列の順を $Q_{1}, Q_{2}, Q_{3}, Q_{4}$ とした輸送表に北西隅法を用いて初期の実行可能解を作るとき、その総輸送費を求めよ。
難易度 1（教科書の例題レベル）
頂点 $S, A, B, C, D, T$ からなる無向グラフがあり、各辺の長さ（正の整数）は次のとおりである。ここに書かれていない辺はない。
辺長さ辺長さ辺長さ
$S$ – $A$ $2$ $A$ – $C$ $3$ $C$ – $D$ $1$
$S$ – $B$ $3$ $B$ – $C$ $2$ $C$ – $T$ $4$
$A$ – $B$ $1$ $B$ – $D$ $4$ $D$ – $T$ $3$
各辺はどちらの向きにも通ることができ、経路の長さは通った辺の長さの和とする。 $S$ から $T$ への最短路（長さが最小の経路）は何本あるか求めよ。
難易度 1（教科書の例題レベル）
6 つの地点 $S, A, B, C, D, T$ を結ぶ道路網があり、次の 9 本の道路はどれも両方向に通行できる。各道路の長さ（km）は次のとおりで、ここに書かれていない道路はない。
道路長さ道路長さ道路長さ
$S$ – $A$ $2$ $A$ – $C$ $3$ $C$ – $D$ $1$
$S$ – $B$ $3$ $B$ – $C$ $2$ $C$ – $T$ $4$
$A$ – $B$ $1$ $B$ – $D$ $4$ $D$ – $T$ $3$
地点 $S$ から地点 $T$ へ行く経路のうち、通る道路の長さの合計が最小となる経路（最短路）は何通りあるか求めよ。
難易度 1（教科書の例題レベル）
頂点 $s, a, b, c, d, t$ からなる無向グラフがあり、辺とその長さは次のとおりである。ここに書かれていない辺はない。
辺長さ辺長さ辺長さ
$s$ — $a$ $2$ $a$ — $c$ $3$ $c$ — $d$ $1$
$s$ — $b$ $3$ $b$ — $c$ $2$ $c$ — $t$ $4$
$a$ — $b$ $1$ $b$ — $d$ $4$ $d$ — $t$ $3$
路の長さを、通る辺の長さの和とする。頂点 $s$ から頂点 $t$ への最短路（長さが最小の路）は何本あるか求めよ。
難易度 1（教科書の例題レベル）
あるプロジェクトは作業 $A, B, C, D, E$ の $5$ つからなる。各作業の所要時間（単位は時間）と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。
作業所要時間先行作業
$A$ $3$ なし
$B$ $5$ なし
$C$ $2$ $A$
$D$ $4$ $A, B$
$E$ $3$ $C, D$
プロジェクトは時刻 $0$ に開始する。どの作業も、先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はないものとする。プロジェクトの最短完了時刻（時間）と、作業 $C$ の全余裕（時間）を、この順に組で答えよ。
難易度 1（教科書の例題レベル）
あるプロジェクトは作業 $A, B, C, D, E$ の $5$ つからなる。各作業の所要日数と先行作業は次の表のとおりである。先行作業とは、その作業を始める前にすべて終わっていなければならない作業のことである。
作業所要日数先行作業
$A$ $3$ なし
$B$ $4$ なし
$C$ $2$ $A$
$D$ $2$ $A$
$E$ $3$ $B, C$
プロジェクトは時刻 $0$ に始まり、すべての作業が終わった時点で完了する。各作業は、先行作業がすべて終わればすぐに始められる。また、同時に進められる作業の数に制限はないものとする。
このプロジェクトの最短完了時刻（日）と、作業 $D$ の全余裕（日）を、この順に組で求めよ。
難易度 1（教科書の例題レベル）
ある作業計画は作業 $A, B, C, D, E$ の $5$ つからなる。各作業の所要時間（時間）と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。
作業所要時間先行作業
$A$ $3$ なし
$B$ $5$ なし
$C$ $2$ $A$
$D$ $2$ $B$
$E$ $3$ $C, D$
計画の開始時刻を $0$ とし、各作業は先行作業がすべて終わればすぐに始められ、作業どうしは同時に並行して進められるものとする。また、計画全体を最短完了時刻までに終えるものとして最遅開始時刻を考える。この計画の最短完了時刻と、作業 $C$ の最遅開始時刻を、この順に組で求めよ。
難易度 1（教科書の例題レベル）
ある会員制サービスの会員は、各週のはじめに「利用中」（状態 $1$ ）か「休眠中」（状態 $2$ ）のどちらかの状態にある。運営会社は各週のはじめに会員の状態を見て施策を $1$ つ選ぶ。ここでは方策を次のように固定する。
- 状態 $1$ では「お知らせメールを送る」。このとき、その週の利益は $10$ であり、次の週のはじめの状態は確率 $\frac{3}{4}$ で状態 $1$ 、確率 $\frac{1}{4}$ で状態 $2$ になる。
- 状態 $2$ では「割引クーポンを送る」。このとき、その週の利益は $2$ であり、次の週のはじめの状態は確率 $\frac{1}{2}$ で状態 $1$ 、確率 $\frac{1}{2}$ で状態 $2$ になる。
割引率を $γ = 0.8$ とし、状態 $s$ から始めたときのこの方策による期待割引総利益（第 $t$ 週（ $t = 0, 1, 2, \dots$ ）の利益に $γ^{t}$ を掛けて足し合わせたものの期待値）を $V (s)$ とする。 $V (1)$ と $V (2)$ をこの順に求めよ。
難易度 1（教科書の例題レベル）
ある書店は、アプリ会員 1 人の状態を各期のはじめに「よく来店する」（状態 $1$ ）と「ときどき来店する」（状態 $2$ ）の 2 つに分けている。書店は方策 $π$ として「どちらの状態でも毎期クーポンを配る」ことに決めた。この方策のもとで、その期に得られる利益（即時報酬） $r (s)$ と、次の期の状態への推移確率 $P (s^{'} ∣ s)$ は次のとおりである。
- 状態 $1$ ： $r (1) = 18$ ， $P (1 ∣ 1) = \frac{1}{2}$ ， $P (2 ∣ 1) = \frac{1}{2}$
- 状態 $2$ ： $r (2) = 2$ ， $P (1 ∣ 2) = \frac{1}{4}$ ， $P (2 ∣ 2) = \frac{3}{4}$
割引率を $γ = 0.8$ とし、状態 $s$ から始めたときの期待割引総報酬を $V (s)$ とする。 $V (s)$ はベルマン方程式
$V (s) = r (s) + γ s^{'} \sum P (s^{'} ∣ s) V (s^{'}) (s = 1, 2)$
を満たす。 $V (1)$ と $V (2)$ をこの順に組 $(V (1), V (2))$ で求めよ。
難易度 1（教科書の例題レベル）
ある通販サイトは、各顧客を毎月のはじめに「常連」（状態 $1$ ）か「離脱しかけ」（状態 $2$ ）のどちらかに分類している。サイトは次の方策 $π$ に固定して運営している。
- 状態 $1$ の顧客には通常対応をする。その月の報酬（利益）は $5$ で、翌月は確率 $\frac{3}{4}$ で状態 $1$ 、確率 $\frac{1}{4}$ で状態 $2$ になる。
- 状態 $2$ の顧客にはクーポンを送る。その月の報酬は $- 1$ （クーポンの費用が利益を上回る）で、翌月は確率 $\frac{1}{2}$ で状態 $1$ 、確率 $\frac{1}{2}$ で状態 $2$ になる。
時刻 $t = 0, 1, 2, \dots$ の状態を $s_{t}$ 、その月の報酬を $r (s_{t})$ とし、割引率を $γ = \frac{4}{5}$ とする。状態 $s$ から始めたときの期待割引総報酬
$V (s) = E [t = 0 \sum \infty γ^{t} r (s_{t}) s_{0} = s]$
について、 $V (1)$ と $V (2)$ をこの順に組 $(V (1), V (2))$ で求めよ。
難易度 1（教科書の例題レベル）
あるコーヒースタンドには店員が $1$ 人だけいて、客を $1$ 列に並ばせ、先着順に $1$ 人ずつ注文を受けて商品を渡す。客は到着率 $λ = 12$ （人/時）のポアソン過程に従って到着し、 $1$ 人あたりのサービス時間は互いに独立に平均 $4$ 分の指数分布に従う。待ち行列の長さに上限はなく、到着した客は必ず列に並ぶものとする。この系を M/M/1 待ち行列とみなすとき、定常状態において、客がサービスを受け始めるまでに列で待つ時間の平均 $W_{q}$ は何分か。
難易度 1（教科書の例題レベル）
ある駅に ATM が $1$ 台だけある。利用者は到着率 $λ = 10$ （人/時）のポアソン過程に従って到着する。 $1$ 人あたりの利用時間は、平均 $4$ 分の指数分布に従う。利用者は $1$ 列に並んで先着順に ATM を使い、並べる人数に上限はない。この系を M/M/1 待ち行列とみなし、十分時間がたって定常状態になっているとする。
利用者が ATM の前に並んでから ATM を使い始めるまでの平均待ち時間 $W_{q}$ は何分か。
難易度 1（教科書の例題レベル）
ある駅の構内に、現金自動預払機（ATM）が $1$ 台だけ設置されている。利用客は到着率 $λ = 12$ （人/時）のポアソン過程に従って到着し、 $1$ 人あたりの利用時間は平均 $4$ 分の指数分布に従う。客は $1$ 列に並んで先着順に利用し、待ち行列の長さに制限はない。この待ち行列を M/M/1 とみなし、定常状態を考える。
客が到着してから ATM の利用を始めるまでの平均待ち時間 $W_{q}$ は何分か。
難易度 1（教科書の例題レベル）
ある部品メーカーでは、ある部品の需要が年間 $3000$ 個あり、一定の割合で生じる。この部品の在庫管理について、次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $200$ 円の発注費用がかかる。発注した部品は一度に納入され、納入までの時間は無視できる。
- 在庫 $1$ 個を $1$ 年間保管するのに $40$ 円の保管費用がかかる。
- 欠品を許し、欠品した分は次の納入時にすべて補充する（受注残）。欠品 $1$ 個が $1$ 年間続くごとに $120$ 円の欠品費用がかかる。
$1$ 回の発注量を $Q$ 個、各サイクルの最大欠品量を $S$ 個とすると、年間総費用は
$f (Q, S) = \frac{200 \cdot 3000}{Q} + \frac{40 ( Q - S ) ^{2}}{2 Q} + \frac{120 S ^{2}}{2 Q}$
で表される。 $Q$ を正の実数、 $S$ を $0 \leq S < Q$ を満たす実数の範囲で動かすとき、 $f (Q, S)$ を最小にする発注量 $Q$ と、そのときの年間総費用の最小値（円）を、この順に組で求めよ。
難易度 1（教科書の例題レベル）
ある工場では、ある部品を年間 $3600$ 個、一定の割合で使用している。この部品の在庫管理について、次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $400$ 円の発注費用がかかる。発注した部品は一度に納入され、納入までの時間は無視できる。
- 部品 $1$ 個を $1$ 年間保管すると $3$ 円の保管費用がかかる。
- 在庫切れ（欠品）を許し、欠品した分は次の納入時にすぐに補充される（受注残）。欠品 $1$ 個が $1$ 年間続くと $6$ 円の欠品費用がかかる。
$1$ 回の発注量を $Q$ 個、最大欠品量を $S$ 個（ $Q > 0$ , $0 \leq S \leq Q$ とし、ともに実数として扱う）とすると、年間総費用は
$C (Q, S) = \frac{400 \cdot 3600}{Q} + \frac{3 ( Q - S ) ^{2}}{2 Q} + \frac{6 S ^{2}}{2 Q} （円）$
で表される。 $C (Q, S)$ を最小にする $Q$ , $S$ と、そのときの年間総費用の最小値を、組 $(Q, S, 最小値)$ の形でこの順に求めよ。
難易度 1（教科書の例題レベル）
ある商店では、ある部品の需要が年間 $900$ 個で、一定の割合で生じる。在庫管理について次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $200$ 円の発注費用がかかる。発注した部品は一度に納入される。
- 在庫を $1$ 個 $1$ 年間保管すると $9$ 円の保管費用がかかる。
- 欠品を許し、欠品した分は次の納入時にまとめて補充する（受注残）。欠品 $1$ 個が $1$ 年間続くと $16$ 円の欠品費用がかかる。
$1$ 回の発注量を $Q$ 個、納入直前の最大欠品量を $S$ 個とすると（ $Q, S$ は $0 \leq S < Q$ を満たす実数とみなす）、年間総費用 $C (Q, S)$ （円）は
$C (Q, S) = \frac{200 \cdot 900}{Q} + \frac{9 ( Q - S ) ^{2}}{2 Q} + \frac{16 S ^{2}}{2 Q}$
で表される。 $C (Q, S)$ を最小にする $Q$ 、 $S$ と、そのときの最小の年間総費用を、組 $(Q, S, C)$ の形でこの順に求めよ。
難易度 1（教科書の例題レベル）
2 つの農場 $P_{1}, P_{2}$ から 3 つの市場 $Q_{1}, Q_{2}, Q_{3}$ へ野菜を輸送する。農場の出荷量は $P_{1}$ が $50$ 、 $P_{2}$ が $40$ （単位：トン）であり、すべて出荷する。市場の需要量は $Q_{1}$ が $30$ 、 $Q_{2}$ が $35$ 、 $Q_{3}$ が $25$ であり、ちょうど満たす。 $P_{i}$ から $Q_{j}$ へ $1$ トン運ぶ費用 $c_{ij}$ （単位：万円）は次の表のとおりである。
$P_{1} P_{2} Q_{1} 45 Q_{2} 63 Q_{3} 97$
輸送費は輸送量に比例し、輸送量 $x_{ij}$ は $0$ 以上の実数とする。北西隅法による初期解
$x_{11} = 30, x_{12} = 20, x_{22} = 15, x_{23} = 25 (ほかは 0)$
から出発し、ポテンシャル法を用いて総輸送費の最小値（万円）を求めよ。
難易度 1（教科書の例題レベル）
2 つの農場 $P_{1}, P_{2}$ から 3 つの市場 $Q_{1}, Q_{2}, Q_{3}$ へ野菜を輸送する。出荷量は $P_{1}$ が $50$ トン、 $P_{2}$ が $40$ トンで、すべて出荷する。需要量は $Q_{1}$ が $30$ トン、 $Q_{2}$ が $35$ トン、 $Q_{3}$ が $25$ トンで、ちょうど満たす。 $1$ トンあたりの輸送費（単位：千円）は次の表のとおりである。
$P_{1} P_{2} 需要量 Q_{1} 4630 Q_{2} 6535 Q_{3} 3425 出荷量 5040$
各輸送量は $0$ 以上の実数とし、輸送費は輸送量に比例するものとする。北西隅法で初期の実行可能解を作り、ポテンシャル法で最適性の判定と改善を行って、総輸送費の最小値（千円）を求めよ。
難易度 1（教科書の例題レベル）
2 つの農場 $A_{1}, A_{2}$ から 3 つの市場 $B_{1}, B_{2}, B_{3}$ へ野菜を輸送する。農場の出荷量は $A_{1}$ が $30$ トン、 $A_{2}$ が $20$ トンで、すべて出荷する。市場の需要量は $B_{1}$ が $15$ トン、 $B_{2}$ が $25$ トン、 $B_{3}$ が $10$ トンで、ちょうど満たす。 $1$ トンあたりの輸送費（単位: 千円）は次の表のとおりである。
$A_{1} A_{2} B_{1} 45 B_{2} 63 B_{3} 87$
輸送量は $0$ 以上の実数とし、総輸送費は各経路の「輸送量 $\times$ 単価」の和とする。北西隅法で初期の実行可能解を作り、ポテンシャル法で最適性を判定・改善して、総輸送費の最小値（単位: 千円）を求めよ。
難易度 1（教科書の例題レベル）
あるプロジェクトは作業 $A, B, C, D, E$ の $5$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、短縮できる最大日数、 $1$ 日短縮するごとにかかる追加費用は次のとおりである。
作業先行作業通常の所要日数短縮できる最大日数 1日あたりの短縮費用（万円）
$A$ なし $3$ $1$ $3$
$B$ なし $5$ $2$ $2$
$C$ $A$ $4$ $2$ $5$
$D$ $B$ $2$ $1$ $4$
$E$ $C, D$ $3$ $1$ $8$
各作業は $1$ 日単位で短縮でき、短縮費用は短縮した日数に比例する。プロジェクト全体の完了までの日数を $8$ 日にするために必要な追加費用の最小値は何万円か。
難易度 1（教科書の例題レベル）
あるプロジェクトは作業 $A, B, C, D, E$ の $5$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、短縮できる最大日数、 $1$ 日短縮するごとにかかる追加費用は次の表のとおりである。
作業通常の所要日数先行作業短縮できる最大日数 1日あたりの短縮費用（万円）
$A$ $4$ なし $1$ $3$
$B$ $6$ なし $2$ $2$
$C$ $5$ $A$ $2$ $5$
$D$ $3$ $B$ $1$ $4$
$E$ $2$ $C, D$ $1$ $6$
各作業は $1$ 日単位で短縮でき、短縮費用は短縮日数に比例するものとする。プロジェクトの完了までの日数を $9$ 日にするために必要な追加費用の最小値は何万円か。
難易度 1（教科書の例題レベル）
あるプロジェクトは作業 $A, B, C, D, E$ の $5$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、短縮できる最大日数、 $1$ 日短縮するごとにかかる追加費用は次の表のとおりである。
作業通常の所要日数先行作業短縮できる最大日数 $1$ 日あたりの短縮費用（万円）
$A$ $3$ なし $1$ $4$
$B$ $5$ なし $2$ $3$
$C$ $4$ $A$ $2$ $2$
$D$ $2$ $B$ $1$ $2$
$E$ $3$ $C, D$ $1$ $6$
短縮は $1$ 日単位で行い、短縮費用は短縮した日数に比例するものとする。プロジェクト全体の完了までの日数を $8$ 日にするために必要な追加費用の最小値は何万円か。
難易度 1（教科書の例題レベル）
ある人の体調は、毎日のはじめに「元気」（状態 $1$ ）か「疲労」（状態 $2$ ）のどちらかである。毎日のはじめに体調を見て行動を $1$ つ選ぶと、その日の報酬（満足度）が得られ、翌日のはじめの状態が次の確率で決まる。
- 状態 $1$ で行動「働く」：報酬 $4$ 。翌日は確率 $\frac{1}{2}$ で状態 $1$ 、確率 $\frac{1}{2}$ で状態 $2$ 。
- 状態 $1$ で行動「休む」：報酬 $3$ 。翌日は確率 $1$ で状態 $1$ 。
- 状態 $2$ で行動「休む」（選べる行動はこれだけ）：報酬 $0$ 。翌日は確率 $1$ で状態 $1$ 。
割引率を $γ = \frac{1}{2}$ とし、無限に続く期間の期待割引総報酬を最大にする。最適価値 $V^{*} (s)$ は
$V^{*} (s) = a max {r (s, a) + γ s^{'} \sum P (s^{'} ∣ s, a) V^{*} (s^{'})}$
を満たす。状態 $1$ から始めたときの最適価値 $V^{*} (1)$ を求めよ。
難易度 1（教科書の例題レベル）
ある大学生の体調は、毎日のはじめに「元気」（状態 $1$ ）か「疲労」（状態 $2$ ）のどちらかである。毎日のはじめに体調を見て行動を $1$ つ選ぶと、その日の報酬が得られ、翌日のはじめの状態が次の確率で決まる。
- 状態 $1$ で行動「長時間アルバイト」：報酬 $6$ 。翌日は確率 $\frac{1}{2}$ で状態 $1$ 、確率 $\frac{1}{2}$ で状態 $2$
- 状態 $1$ で行動「短時間アルバイト」：報酬 $4$ 。翌日は確率 $1$ で状態 $1$
- 状態 $2$ で行動「休養」（状態 $2$ で選べる行動はこれだけ）：報酬 $0$ 。翌日は確率 $1$ で状態 $1$
割引率を $γ = \frac{1}{2}$ とし、無限期間の期待割引総報酬を最大化する。最適価値 $V^{*} (s)$ はベルマン最適方程式
$V^{*} (s) = a max {r (s, a) + γ s^{'} \sum P (s^{'} ∣ s, a) V^{*} (s^{'})}$
を満たす。最適価値 $V^{*} (1)$ , $V^{*} (2)$ をこの順に組で求めよ。
難易度 1（教科書の例題レベル）
ある掃除ロボットのバッテリーの状態は、各時刻 $t = 0, 1, 2, \dots$ に「十分」（状態 $1$ ）か「残りわずか」（状態 $2$ ）のどちらかである。各時刻に状態を見て行動を $1$ つ選ぶと、その時刻の報酬が得られ、次の時刻の状態が次の確率で決まる。
- 状態 $1$ で行動「通常掃除」：報酬 $4$ 。次の状態は確率 $\frac{1}{2}$ で状態 $1$ 、確率 $\frac{1}{2}$ で状態 $2$ 。
- 状態 $1$ で行動「待機」：報酬 $1$ 。次の状態は確率 $1$ で状態 $1$ 。
- 状態 $2$ で行動「充電」：報酬 $0$ 。次の状態は確率 $1$ で状態 $1$ 。
- 状態 $2$ で行動「省電力掃除」：報酬 $2$ 。次の状態は確率 $1$ で状態 $2$ 。
割引率を $γ = \frac{1}{2}$ とし、状態 $s$ から始めたときの期待割引総報酬の最大値（最適価値）を $V^{*} (s)$ とする。 $V^{*}$ はベルマン最適方程式
$V^{*} (s) = a max {r (s, a) + γ s^{'} \sum P (s^{'} ∣ s, a) V^{*} (s^{'})}$
を満たす。 $V^{*} (1)$ と $V^{*} (2)$ をこの順に組 $(V^{*} (1), V^{*} (2))$ で求めよ。
難易度 1（教科書の例題レベル）
あるセルフ洗車場には洗車機が $2$ 台ある。車は到着率 $λ = 6$ （台/時）のポアソン過程に従って到着する。車は $1$ 列に並び、空いた洗車機から先着順に使う。 $1$ 台あたりの洗車時間は、互いに独立に平均 $10$ 分の指数分布に従う。この系を M/M/2 待ち行列とみなすとき、定常状態における車 $1$ 台あたりの平均系内滞在時間 $W$ （待ち時間と洗車時間の合計の平均）は何分か。
難易度 1（教科書の例題レベル）
ある駅の券売機コーナーには券売機が $2$ 台ある。
- 客は到着率 $λ = 1$ （人/分）のポアソン過程に従って到着する。
- 客は $1$ 列に並び、空いた券売機を先着順に使う。
- $1$ 人が券売機を使う時間は、互いに独立に平均 $1.5$ 分の指数分布に従う。
この系を M/M/2 待ち行列とみなし、定常状態を考える。客が到着してから券を買い終えて券売機を離れるまでの平均系内滞在時間 $W$ （分）を求めよ。
難易度 1（教科書の例題レベル）
ある図書館には自動貸出機が $2$ 台ある。利用者は到着率 $λ = 8$ （人/時）のポアソン過程に従って到着する。利用者は $1$ 列に並び、空いた貸出機から先着順に使う。 $1$ 人あたりの利用時間は、互いに独立に平均 $12$ 分（すなわちサービス率 $μ = 5$ （人/時））の指数分布に従う。この待ち行列を M/M/2 とみなし、定常状態における利用者 $1$ 人あたりの平均系内滞在時間 $W$ （並んで待つ時間と貸出機を使う時間の和の平均）を、時間を単位として求めよ。
難易度 2（教科書の演習問題レベル）
状態が $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$ にとどまる。
割引率を $γ = \frac{1}{2}$ とし、無限期間の期待割引総報酬 $E [t = 0 \sum \infty γ^{t} r_{t}]$ （ $r_{t}$ は時刻 $t$ の報酬）を最大化する。状態 $1$ から始めたときの最適価値 $V^{*} (1)$ を求めよ。
難易度 2（教科書の演習問題レベル）
4 人の作業員 $W_{1}, W_{2}, W_{3}, W_{4}$ に 4 つの仕事 $J_{1}, J_{2}, J_{3}, J_{4}$ を 1 つずつ割り当てる。各作業員はちょうど 1 つの仕事を担当し、各仕事はちょうど 1 人が担当する。作業員 $W_{i}$ が仕事 $J_{j}$ を行うのにかかる時間（単位：時間） $c_{ij}$ は次の表のとおりである。
$J_{1}$ $J_{2}$ $J_{3}$ $J_{4}$
$W_{1}$ $8$ $4$ $7$ $6$
$W_{2}$ $5$ $9$ $6$ $3$
$W_{3}$ $7$ $6$ $10$ $8$
$W_{4}$ $6$ $7$ $5$ $9$
4 人の作業時間の合計が最小になるように割り当てるとき、作業時間の合計の最小値を求めよ。
難易度 2（教科書の演習問題レベル）
ある店舗では、ある部品を年間 $9000$ 個、一定の割合で販売している。この部品を仕入れるとき、 $1$ 回の発注ごとに発注量によらず $2000$ 円の発注費用がかかる。また、部品の単価は $500$ 円で、 $1$ 個を $1$ 年間保管するのにかかる在庫保管費用は単価の $20%$ である。
発注はいつも同じ量 $Q$ 個（ $Q > 0$ ）ずつ行い、在庫がちょうど $0$ になった瞬間に注文した部品が届く（リードタイム $0$ 、品切れは起こさない）ものとする。年間の発注費用と年間の在庫保管費用の和（部品の購入代金は含めない）を年間総費用とするとき、 $Q$ を正の実数の範囲で動かしたときの年間総費用の最小値（円）を求めよ。
難易度 2（教科書の演習問題レベル）
あるプロジェクトは作業 $1$ から作業 $8$ までの $8$ つの作業からなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。
作業所要日数先行作業
$1$ $3$ なし
$2$ $5$ なし
$3$ $4$ $1$
$4$ $2$ $1$
$5$ $6$ $2, 4$
$6$ $3$ $3$
$7$ $4$ $5, 6$
$8$ $2$ $3$
各作業は、先行作業がすべて終わればすぐに始めることができ、同時に進められる作業の数に制限はない。プロジェクトは時刻 $0$ に始まり、すべての作業が終わった時点で完了する。プロジェクトの完了時刻を最も早い値にしたとき、全余裕（最遅開始時刻と最早開始時刻の差）が $0$ である作業の番号の集合を求めよ。
難易度 2（教科書の演習問題レベル）
ある工場の機械の状態は、各期のはじめに「良好」「劣化」「故障」のいずれかである。各期のはじめに機械の状態を見て行動を 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$ とする）ものとし、割引は行わない。このとき、利益の合計の期待値の最大値を求めよ。
難易度 2（教科書の演習問題レベル）
ある工場では、ある製品を自社で生産して在庫し、そこから一定の割合で出荷している。製品の需要は年間 $12000$ 個で一定である。生産は 1 回ごとにまとめて $Q$ 個（ロットサイズ）を行い、生産中は年間 $48000$ 個の一定の速さで製品ができあがる。生産中も出荷は続けるので、生産中の在庫は（生産の速さ） $-$ （需要の速さ）の割合で増え、生産が終わると需要の速さで減っていく。在庫が $0$ になった時点で次の生産を始めるものとし、品切れは起こさない。
1 回の生産ごとに、ロットサイズによらず段取り費用 $9000$ 円がかかる。また、製品 $1$ 個を $1$ 年間保管する費用は $200$ 円であり、保管費用は平均在庫量に比例するものとする。
1 年あたりの段取り費用と保管費用の合計を最小にするロットサイズ $Q$ （個）を求めよ。ただし $Q$ は正の実数として扱ってよい。
難易度 2（教科書の演習問題レベル）
有限集合 $S$ を状態の集合、有限集合 $A$ を行動の集合とする（ともに空でない）。各 $s \in S, a \in A$ に対して遷移確率 $p (s^{'} ∣ s, a) \geq 0$ （ $\sum_{s^{'} \in S} p (s^{'} ∣ s, a) = 1$ ）が与えられ、割引率 $γ$ は $0 < γ < 1$ を満たすとする。
2 つの報酬関数 $r, r^{'} : S \times A \to R$ が、すべての $s \in S, a \in A$ で $r (s, a) \leq r^{'} (s, a)$ を満たすとし、
$δ = s \in S, a \in A max (r^{'} (s, a) - r (s, a))$
とおく。関数 $W, U : S \to R$ はそれぞれ、報酬 $r$ , $r^{'}$ に対するベルマン最適方程式
$W (s) = a \in A max {r (s, a) + γ s^{'} \in S \sum p (s^{'} ∣ s, a) W (s^{'})}, U (s) = a \in A max {r^{'} (s, a) + γ s^{'} \in S \sum p (s^{'} ∣ s, a) U (s^{'})} (s \in S)$
を満たすとする（このような $W$ , $U$ が存在することは用いてよい）。
すべての $s \in S$ について
$0 \leq U (s) - W (s) \leq \frac{δ}{1 - γ}$
が成り立つことを証明せよ。
難易度 2（教科書の演習問題レベル）
$n \geq 2$ を整数とし、頂点集合 ${1, 2, \dots, n}$ と有向辺の集合 $A$ からなる有向グラフ（PERT のアローダイアグラム）を考える。各辺 $(i, j) \in A$ は $i < j$ を満たし、作業時間 $d_{ij}$ （実数）をもつ。また、 $j = 2, 3, \dots, n$ のどの頂点 $j$ にも、 $j$ に入る辺 $(i, j) \in A$ が少なくとも 1 本あるとする。
最早結合点時刻 $E (1), E (2), \dots, E (n)$ を
$E (1) = 0, E (j) = i : (i, j) \in A max (E (i) + d_{ij}) (j = 2, 3, \dots, n)$
により $j$ の小さい順に定める。また、頂点 $1$ から頂点 $j$ への有向路（辺を 0 本以上つないだもの。 $1$ から $1$ へは辺を 1 本も含まない路だけを考える）について、含まれる辺の作業時間の和をその路の長さとよぶ。
各 $j = 1, 2, \dots, n$ について、頂点 $1$ から頂点 $j$ への有向路が存在し、 $E (j)$ はそれらの有向路の長さの最大値に等しいことを証明せよ。
難易度 2（教科書の演習問題レベル）
あるプロジェクトは作業 $A, B, C, D, E, F, G$ の $7$ つからなる。各作業の所要日数には、楽観値 $a$ 、最可能値 $m$ 、悲観値 $b$ の $3$ つの見積もりが与えられている。先行作業とは、その作業を始める前にすべて終わっていなければならない作業のことである。
作業先行作業 $a$ $m$ $b$
$A$ なし $2$ $4$ $6$
$B$ なし $3$ $5$ $13$
$C$ $A$ $1$ $3$ $5$
$D$ $A$ $4$ $6$ $14$
$E$ $B, C$ $2$ $5$ $8$
$F$ $D, E$ $3$ $4$ $11$
$G$ $E$ $1$ $2$ $9$
PERT の手法に従い、各作業の所要日数の期待値 $t_{e}$ と分散 $σ^{2}$ を
$t_{e} = \frac{a + 4 m + b}{6}, σ^{2} = (\frac{b - a}{6})^{2}$
で定める。各作業の所要日数を $t_{e}$ として最早開始時刻を計算し、プロジェクトの完了時刻（期待値） $T$ とクリティカルパスを求める。さらに、クリティカルパス上の作業の所要日数は互いに独立であるとして、クリティカルパス上の作業の分散の和 $V$ を求める。
$T$ と $V$ をこの順に組 $(T, V)$ で答えよ。なお、プロジェクトは時刻 $0$ に開始し、先行作業がすべて終わればその作業はすぐに開始できるものとする。
難易度 2（教科書の演習問題レベル）
ある工場では、ある部品を自社の生産ラインで製造している。この部品の需要は年間 $9000$ 個で、一定の割合で生じる。部品の生産と在庫について、次を仮定する。
- 生産中は部品が年間 $27000$ 個の一定の割合で完成し、完成した部品はただちに在庫に加わる。生産中も需要は同じ割合で生じ続ける。
- $1$ 回の生産（ロット）ごとに、生産量によらず $4000$ 円の段取り費用がかかる。
- 部品 $1$ 個を $1$ 年間保管するのに $300$ 円の保管費用がかかり、保管費用は在庫量の時間平均に比例する。
- 品切れは許さず、在庫がちょうど $0$ になった時点で次の生産を始める。毎回の生産量は同じ $Q$ 個とし、 $Q$ は正の実数として扱ってよい。
$1$ 年あたりの段取り費用と保管費用の合計の最小値（円）を求めよ。
難易度 2（教科書の演習問題レベル）
5 人の作業者 $W_{1}, W_{2}, W_{3}, W_{4}, W_{5}$ を 5 つの仕事 $J_{1}, J_{2}, J_{3}, J_{4}, J_{5}$ に 1 人 1 つずつ割り当てる（各仕事にはちょうど 1 人を割り当てる）。作業者 $W_{i}$ が仕事 $J_{j}$ を行うときの費用 $c_{ij}$ は次の表のとおりである。ただし $t$ は実数の定数である。
$J_{1}$ $J_{2}$ $J_{3}$ $J_{4}$ $J_{5}$
$W_{1}$ $t$ $7$ $9$ $8$ $11$
$W_{2}$ $6$ $10$ $4$ $9$ $7$
$W_{3}$ $9$ $5$ $8$ $6$ $10$
$W_{4}$ $4$ $8$ $7$ $11$ $6$
$W_{5}$ $8$ $9$ $6$ $7$ $5$
費用の総和を最小にする割当て（最適割当て）のうちに、 $W_{1}$ を $J_{1}$ に割り当てるものが存在するような $t$ の最大値を求めよ。
難易度 2（教科書の演習問題レベル）
状態が $1, 2, 3$ の $3$ つであるマルコフ決定過程を考える。各時刻 $t = 0, 1, 2, \dots$ に現在の状態を見て行動を $1$ つ選ぶと、その時刻の報酬を受け取り、次の時刻の状態が次の確率で決まる（ $p_{ij}$ は状態 $i$ から状態 $j$ へ遷移する確率）。
- 状態 $1$ で行動 $a$ ：報酬 $2$ 、 $(p_{11}, p_{12}, p_{13}) = (\frac{1}{2}, \frac{1}{2}, 0)$
- 状態 $1$ で行動 $b$ ：報酬 $0$ 、 $(p_{11}, p_{12}, p_{13}) = (0, 0, 1)$
- 状態 $2$ で行動 $a$ ：報酬 $4$ 、 $(p_{21}, p_{22}, p_{23}) = (\frac{1}{3}, \frac{2}{3}, 0)$
- 状態 $2$ で行動 $b$ ：報酬 $1$ 、 $(p_{21}, p_{22}, p_{23}) = (0, \frac{1}{2}, \frac{1}{2})$
- 状態 $3$ で行動 $c$ （選べる行動はこれのみ）：報酬 $6$ 、 $(p_{31}, p_{32}, p_{33}) = (\frac{1}{2}, \frac{1}{4}, \frac{1}{4})$
方策 $π$ のもとで時刻 $t$ に得る報酬を $R_{t}$ とし、初期状態 $i$ からの長期平均報酬を
$g^{π} (i) = N \to \infty lim \frac{1}{N} E^{π} [t = 0 \sum N - 1 R_{t} X_{0} = i]$
で定める。この長期平均報酬のすべての方策にわたる最大値（最適平均報酬）を求めよ。なお、状態と行動が有限のこのマルコフ決定過程では、最適な方策が定常な決定的方策（各状態で常に同じ行動を選ぶ方策）の中に存在し、その最適平均報酬は初期状態によらないことを用いてよい。
難易度 3（期末試験の応用レベル）
ある窓口には、客が平均到着率 $λ = 6$ （人/時）のポアソン過程に従って到着する。窓口の運営方法として、次の 2 案を比べる。
- 案 A: 窓口係を 1 人置く。サービス時間は平均 $\frac{1}{8}$ 時間の指数分布に従う（サービス率 $μ_{A} = 8$ （人/時））。
- 案 B: 窓口係を 2 人置き、客は 1 列に並んで、空いた窓口係から先着順にサービスを受ける。各窓口係のサービス時間は互いに独立に平均 $\frac{1}{4}$ 時間の指数分布に従う（1 人あたりのサービス率 $μ_{B} = 4$ （人/時））。
すなわち案 A は M/M/1 モデル、案 B は M/M/2 モデルである。待合室の容量に制限はなく、どちらの案でも系は定常状態にあるものとする。客が到着してからサービスを終えて出ていくまでの平均時間（平均系内滞在時間）について、案 B の値は案 A の値より何分長いか求めよ。
難易度 3（期末試験の応用レベル）
ある役所の受付に、客が平均到着率 $λ = 6$ （人/時）のポアソン過程に従って到着する。受付の体制として次の 2 案を考える。
- 案 A：窓口を 1 つだけ置き、1 人あたりのサービス時間が平均 $\frac{1}{8}$ 時間の指数分布に従う職員 1 人が担当する（M/M/1 モデル）。
- 案 B：窓口を 2 つ置き、それぞれ 1 人あたりのサービス時間が平均 $\frac{1}{4}$ 時間の指数分布に従う職員が担当する。待ち行列は 1 列で、空いた窓口に先頭の客から順に入る（M/M/2 モデル）。
いずれの案でも待合室の容量に制限はなく、系は定常状態にあるものとする。客が到着してからサービスを終えて立ち去るまでの平均時間（平均系内滞在時間）について、案 B の値は案 A の値より何分長いか求めよ。
難易度 3（期末試験の応用レベル）
頂点 $1, 2, \dots, 7$ からなる有向グラフがあり、各有向辺 $i \to j$ の長さ（正の整数）は次のとおりである。ここに書かれていない辺はない。
辺長さ辺長さ
$1 \to 2$ $3$ $3 \to 6$ $7$
$1 \to 3$ $2$ $2 \to 5$ $5$
$1 \to 4$ $6$ $2 \to 6$ $6$
$3 \to 2$ $1$ $4 \to 5$ $2$
$2 \to 4$ $2$ $4 \to 6$ $3$
$3 \to 4$ $3$ $5 \to 7$ $3$
$6 \to 7$ $2$
経路の長さを、通る辺の長さの和と定める。頂点 $1$ から頂点 $7$ への最短路の長さを $L$ 、長さがちょうど $L$ である頂点 $1$ から頂点 $7$ への経路の本数を $N$ とするとき、組 $(L, N)$ を求めよ。
難易度 3（期末試験の応用レベル）
ある卸売業者は、ある商品を年間 $6000$ 個、一定の割合で出荷している。この商品の在庫管理について、次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $500$ 円の発注費用がかかる。発注した商品は発注と同時に一度に納入される（リードタイムは $0$ ）。
- 在庫 $1$ 個を $1$ 年間保管するのに $200$ 円の保管費用がかかる（保管費用は在庫量と保管期間に比例する）。
- 在庫が切れている間に来た注文は欠品（受注残）として記録され、次の納入時にすべて直ちに出荷される。欠品 $1$ 個が $1$ 年間続くごとに $600$ 円の欠品費用がかかる（欠品費用は欠品量と欠品期間に比例する）。
- 毎回の発注量を $Q$ 個、納入直前の欠品量（最大欠品量）を $S$ 個とし、これらは毎回同じとする（ $Q > 0, 0 \leq S \leq Q$ の実数として扱う）。
商品の購入単価は発注量によらず一定で、年間の購入費用は $Q, S$ によらないものとする。 $1$ 年あたりの発注費用・保管費用・欠品費用の合計を最小にする $Q$ と $S$ を、組 $(Q, S)$ の形でこの順に求めよ。
難易度 3（期末試験の応用レベル）
あるコールセンターには、電話が到着率 $λ = 10$ （件/時）のポアソン過程に従ってかかってくる。オペレーター $1$ 人あたりの対応時間は、互いに独立に平均 $15$ 分の指数分布に従う。オペレーターを $c$ 人（ $c$ は正の整数）置き、かかってきた電話は $1$ 本の待ち行列に並んで、空いたオペレーターから先着順に対応される（M/M/ $c$ 待ち行列。待ち行列の長さに上限はなく、途中で電話を切る客はいない）。
定常状態が存在し、かつ定常状態での平均待ち時間（対応が始まるまでの時間の平均で、対応時間は含めない） $W_{q}$ が $3$ 分以下となるような $c$ の最小値を求めよ。
難易度 3（期末試験の応用レベル）
倉庫内を移動する配送ロボットを考える。ロボットの位置は、各時刻に地点 $1$ 、地点 $2$ 、出口 $G$ のいずれかであり、出口 $G$ に着いた時点で移動は終了する。地点 $1, 2$ では、各時刻に行動を $1$ つ選ぶと、その時刻の費用がかかり、次の時刻の位置が次の確率で決まる。
- 地点 $1$ で行動 $a$ ：費用 $2$ 、確率 $1$ で地点 $2$ へ
- 地点 $1$ で行動 $b$ ：費用 $1$ 、確率 $\frac{1}{5}$ で出口 $G$ へ、確率 $\frac{3}{5}$ で地点 $1$ にとどまり、確率 $\frac{1}{5}$ で地点 $2$ へ
- 地点 $2$ で行動 $c$ ：費用 $5$ 、確率 $1$ で出口 $G$ へ
- 地点 $2$ で行動 $d$ ：費用 $1$ 、確率 $\frac{1}{3}$ で出口 $G$ へ、確率 $\frac{2}{3}$ で地点 $1$ へ
遷移はマルコフ性をもち、行動は各時刻の位置を見て選べる。地点 $1$ から出発して出口 $G$ に着くまでにかかる費用の合計（割引なし）の期待値を、行動の選び方（方策）全体にわたって最小化したときの最小値を求めよ。
難易度 3（期末試験の応用レベル）
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}$
$A_{1}$ $6$ $9$ $4$
$A_{2}$ $5$ $7$ $8$
$A_{3}$ $8$ $4$ $7$
総供給量が総需要量より少ないため、需要を満たせない店舗が出る。店舗 $B_{1}, B_{2}, B_{3}$ で不足する製品 $1$ 単位あたり、それぞれ $12$ , $10$ , $9$ の不足費用がかかる。輸送量は $0$ 以上の実数とする。輸送費用と不足費用の合計の最小値を求めよ。
難易度 3（期末試験の応用レベル）
ある修理受付カウンターに、客が到着率 $λ = 6$ （人/時）のポアソン過程に従って到着する。カウンターには $c$ 人（ $c$ は正の整数）の係員を置き、客は $1$ 列に並んで、空いた係員から先着順にサービスを受ける。各係員のサービス時間は互いに独立で、平均 $15$ 分の指数分布に従う。待合室の広さに制限はなく、到着した客は必ず列に加わり、途中で離脱しない。
ここで「平均待ち時間」とは、客が到着してからサービスを受け始めるまでの時間の平均であり、サービスを受けている時間は含めない。定常状態での客 $1$ 人あたりの平均待ち時間が $3$ 分以下となるような最小の $c$ をとるとき、定常状態での平均系内人数（列に並んでいる客とサービス中の客の合計の平均）を求めよ。
難易度 3（期末試験の応用レベル）
ある販売店では、ある商品の需要が年間 $4500$ 個で、一定の割合で生じる。この商品の在庫管理について、次を仮定する。
- $1$ 回の発注ごとに、発注量によらず $400$ 円の発注費用がかかる。発注した商品は一度に納入され、納入までの時間は $0$ とみなす。
- 在庫 $1$ 個を $1$ 年間保管すると $250$ 円の保管費用がかかる（保管費用は在庫量と時間に比例する）。
- 在庫が $0$ のときに生じた需要は品切れ（受注残）として残し、次の納入時にすべて満たす。受注残 $1$ 個を $1$ 年間残すと $200$ 円の品切れ費用がかかる（品切れ費用は受注残の量と時間に比例する）。
- 毎回の発注量は同じ $Q$ 個であり、毎回、受注残が同じ量 $B$ 個（ $0 \leq B \leq Q$ ）に達した時点で発注・納入して受注残をすべて満たす。
$Q, B$ は正の実数（ $B$ は $0$ 以上の実数）として扱い、商品の購入単価は考えない。年間の発注費用・保管費用・品切れ費用の合計を最小にする発注量 $Q$ と、そのときの年間費用の合計（円）を、この順に組で求めよ。
難易度 3（期末試験の応用レベル）
客が到着率 $λ > 0$ のポアソン過程に従って到着する、待合室の容量に制限のない次の 2 つの待ち行列システムを考える。 $μ > 0$ とし、 $λ < 2 μ$ とする。
- システム A: 窓口が 1 つで、サービス時間は平均 $\frac{1}{2 μ}$ の指数分布に従う（M/M/1）。
- システム B: 窓口が 2 つで、各窓口のサービス時間は平均 $\frac{1}{μ}$ の指数分布に従う（M/M/2）。客は空いている窓口があればすぐにサービスを受け、なければ 1 列に並んで先着順に待つ。
どちらのシステムでも、サービス時間は互いに独立で到着とも独立とする。系内人数（待っている客とサービス中の客の合計）の定常分布を ${p_{n}}_{n \geq 0}$ とすると、系内人数が $n$ 人のときのサービス終了率を $μ_{n}$ として、定常分布はつり合いの式
$λ p_{n} = μ_{n + 1} p_{n + 1} (n = 0, 1, 2, \dots), n = 0 \sum \infty p_{n} = 1$
のただ 1 つの解であることを用いてよい（ $μ_{n}$ は各システムの設定から定まる）。
定常状態における平均系内人数を、システム A について $L_{A}$ 、システム B について $L_{B}$ とするとき、 $L_{A} < L_{B}$ であることを証明せよ。
難易度 3（期末試験の応用レベル）
3 つの工場 $A_{1}, A_{2}, A_{3}$ から 3 つの販売店 $B_{1}, B_{2}, B_{3}$ へ、ある製品を輸送する。各工場の生産量は $A_{1}$ が $25$ 、 $A_{2}$ が $35$ 、 $A_{3}$ が $40$ で、すべて輸送しなければならない。各販売店の需要量は $B_{1}$ が $30$ 、 $B_{2}$ が $45$ 、 $B_{3}$ が $25$ で、ちょうど需要量を受け取らなければならない。製品 $1$ 単位あたりの輸送費用は次の表のとおりである。ただし、 $A_{3}$ から $B_{1}$ への輸送費用 $t$ だけは未定であり、 $t$ は $t \geq 0$ を満たす実数とする。
$B_{1}$ $B_{2}$ $B_{3}$
$A_{1}$ $4$ $6$ $9$
$A_{2}$ $5$ $3$ $7$
$A_{3}$ $t$ $8$ $4$
輸送量は $0$ 以上の実数とし、総輸送費用の最小値を $f (t)$ とする。「すべての $t^{'} \geq t$ について $f (t^{'}) = f (t)$ が成り立つ」ような $t (\geq 0)$ の最小値 $t_{0}$ を求めよ。
難易度 3（期末試験の応用レベル）
ある工場の機械は、各期のはじめに「良好」（状態 $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}$ とし、割引率を $β = \frac{4}{5}$ とする。無限期間の期待割引総費用 $E [t = 0 \sum \infty β^{t} c_{t}]$ を最小にするように行動を選ぶとき、第 $0$ 期のはじめの状態が $1$ である場合の期待割引総費用の最小値 $V^{*} (1)$ を求めよ。
難易度 3（期末試験の応用レベル）
ある検査センターには窓口 $1$ （受付）と窓口 $2$ （検査）がある。客は外部から到着率 $6$ （人/時）のポアソン過程に従って窓口 $1$ に到着する。
- 窓口 $1$ には係員が $1$ 人いる。サービス時間は平均 $6$ 分の指数分布に従う。
- 窓口 $1$ を終えた客は、全員が窓口 $2$ へ進む。窓口 $2$ には検査員が $2$ 人いて、客は $1$ 列に並び、空いた検査員から先着順にサービスを受ける。検査員 $1$ 人あたりのサービス時間は平均 $12$ 分の指数分布に従う。
- 窓口 $2$ を終えた客は、確率 $\frac{1}{4}$ で再検査のために窓口 $1$ に戻って並び直し、確率 $\frac{3}{4}$ でセンターを退出する。この振り分けは、過去の経緯とは独立に毎回行われる。
どちらの窓口も待合室の容量に制限はなく、先着順でサービスする。すべてのサービス時間・到着・振り分けは互いに独立であり、サービス時間は訪問のたびに新たに上の分布に従う。系が定常状態にあるとき、客が外部から到着してから最終的にセンターを退出するまでの平均滞在時間は何分か。
難易度 3（期末試験の応用レベル）
あるプロジェクトは作業 $A, B, C, D, E, F, G, H$ の $8$ つからなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。
作業所要日数先行作業
$A$ $3$ なし
$B$ $5$ なし
$C$ $4$ $A$
$D$ $6$ $A$
$E$ $2$ $B, C$
$F$ $5$ $D$
$G$ $4$ $E$
$H$ $3$ $F, G$
さらに、作業の開始時刻について次の $2$ つの制約がある。
- 制約 $(1)$ ：作業 $G$ は、作業 $D$ の開始から $10$ 日以上たってから開始する。
- 制約 $(2)$ ：作業 $F$ は、作業 $C$ の開始から $3$ 日以内に開始する（ $F$ の開始時刻は $C$ の開始時刻に $3$ を足した値以下である）。
プロジェクトの開始時刻を $0$ とし、各作業 $X$ の開始時刻を $s_{X} (≧ 0)$ とする。各作業は開始したら中断せずに所要日数で終わり、作業は同時にいくつでも並行して行える。上の先行関係と制約 $(1)$ 、 $(2)$ をすべて満たすスケジュールのうち、すべての作業が終わる時刻が最も早いものを考え、その時刻を最短完了日数 $T$ とする。
また、作業 $X$ の最早開始時刻を「すべての条件を満たすスケジュールにおける $s_{X}$ の最小値」、最遅開始時刻を「すべての条件を満たし、かつすべての作業が時刻 $T$ までに終わるスケジュールにおける $s_{X}$ の最大値」とし、全余裕を（最遅開始時刻） $-$ （最早開始時刻）と定める。
最短完了日数 $T$ と、作業 $F$ の全余裕を、この順に組で求めよ。
難易度 3（期末試験の応用レベル）
ある販売店は、ある部品を仕入れて販売している。部品の需要は年間 $3600$ 個で一定である。毎回 $Q$ 個（ $Q$ は正の整数）ずつ発注し、発注した部品は在庫がちょうど $0$ になった瞬間に一度に全部届く（調達期間は $0$ とみなし、品切れは起こさない）。発注 $1$ 回あたりの発注費用は $2500$ 円である。年間の保管費用は、部品 $1$ 個あたり単価の $20%$ とし、平均在庫量 $\frac{Q}{2}$ 個に対してかかるものとする。
仕入れ先は、 $1$ 回の発注量 $Q$ に応じて次の数量割引を行っている（割引は発注した全数に適用される）。
発注量 $Q$ 単価
$1 \leq Q < 500$ $1000$ 円
$500 \leq Q < 1500$ $960$ 円
$1500 \leq Q$ $945$ 円
年間の総費用を（購入費用） $+$ （発注費用） $+$ （保管費用）とするとき、年間の総費用を最小にする発注量 $Q$ と、そのときの年間の総費用（円）を、この順に組で求めよ。
難易度 4（大学院入試の標準レベル）
3 つの工場 $A_{1}, A_{2}, A_{3}$ から 3 つの店舗 $B_{1}, B_{2}, B_{3}$ へ、ある製品を輸送する。各工場の供給可能量（上限）は $A_{1}$ が $20$ 、 $A_{2}$ が $30$ 、 $A_{3}$ が $30$ であり、各店舗の需要量は $B_{1}$ が $15$ 、 $B_{2}$ が $35$ 、 $B_{3}$ が $25$ で、需要はちょうど満たさなければならない（工場は供給可能量をすべて出荷しなくてもよい）。製品 1 単位あたりの輸送費は次の表のとおりである。
$B_{1}$ $B_{2}$ $B_{3}$
$A_{1}$ $4$ $6$ $9$
$A_{2}$ $5$ $3$ $7$
$A_{3}$ $8$ $5$ $4$
工場 $A_{i}$ から店舗 $B_{j}$ への輸送量 $x_{ij}$ は $0$ 以上の実数とする。総輸送費 $i = 1 \sum 3 j = 1 \sum 3 c_{ij} x_{ij}$ の最小値を求めよ（ $c_{ij}$ は表の輸送費）。
難易度 4（大学院入試の標準レベル）
ある農家の畑の状態は、各期のはじめに「やせ地」（状態 $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$
割引率を $γ = \frac{4}{5}$ とし、無限期間にわたる割引総報酬の期待値 $E [t = 0 \sum \infty γ^{t} r_{t}]$ （ $r_{t}$ は第 $t$ 期の報酬）を最大化する。状態 $1$ から始めたときの最適価値 $V^{*} (1)$ と、状態 $2$ から始めたときの最適価値 $V^{*} (2)$ を、この順に組 $(V^{*} (1), V^{*} (2))$ で求めよ。
難易度 4（大学院入試の標準レベル）
ある窓口に、客が到着率 $λ = 4$ （人/時）のポアソン過程に従って到着する。この窓口の運営について、次の 2 つの案を比べる。
- 案 A: 窓口係を $2$ 人置き、客は $1$ 列に並んで、空いた窓口係から先着順にサービスを受ける。各窓口係のサービス時間は互いに独立に、平均 $\frac{1}{3}$ 時間の指数分布に従う（M/M/2 モデル）。
- 案 B: 窓口係を $1$ 人だけ置き、客は先着順にサービスを受ける。サービス時間は平均 $\frac{1}{μ}$ 時間の指数分布に従う（M/M/1 モデル）。ただし $μ > 4$ とする。
どちらの案でも待合室の容量に制限はなく、系は定常状態にあるとする。客 $1$ 人が系に滞在する平均時間（待ち時間とサービス時間の和）が、案 B でちょうど案 A と等しくなるような $μ$ （人/時）を求めよ。
難易度 4（大学院入試の標準レベル）
あるプロジェクトは作業 $A, B, C, D, E, F$ の $6$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、および短縮のデータは次のとおりである。
作業通常の所要日数先行作業 1 日短縮あたりの追加費用（万円）短縮できる最大日数
$A$ $4$ なし $5$ $1$
$B$ $6$ なし $2$ $2$
$C$ $5$ $A$ $3$ $2$
$D$ $3$ $A$ $4$ $1$
$E$ $4$ $B, D$ $6$ $2$
$F$ $3$ $C, E$ $10$ $1$
各作業は、先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はない。各作業の所要日数は $1$ 日単位で、表の「短縮できる最大日数」まで短縮でき、追加費用は短縮した日数に比例する。
プロジェクト全体の所要日数（すべての作業が終わるまでの日数）を $11$ 日以下にするために必要な追加費用の合計の最小値は何万円か。
難易度 4（大学院入試の標準レベル）
ある倉庫で 2 種類の商品 $P_{1}, P_{2}$ を扱っている。それぞれの年間需要量は一定の割合で生じ、 $P_{1}$ が $4000$ 個、 $P_{2}$ が $6000$ 個である。 $1$ 回の発注費用（発注量によらない）は $P_{1}$ が $300$ 円、 $P_{2}$ が $750$ 円であり、 $1$ 個を $1$ 年間保管する費用は $P_{1}$ が $20$ 円、 $P_{2}$ が $60$ 円である。各商品は在庫が $0$ になった瞬間に発注し、注文はただちに納入される（品切れは起こさない）。 $P_{1}, P_{2}$ の $1$ 回の発注量をそれぞれ $Q_{1}, Q_{2}$ （正の実数）とし、各商品の在庫は $Q_{i}$ から $0$ まで一定の速さで減るものとする（年間保管費用は平均在庫量 $Q_{i} /2$ に比例する）。
この倉庫には商品を合計 $500$ 個までしか置けないため、両商品の最大在庫量が同時に生じてもよいように
$Q_{1} + Q_{2} \leq 500$
という制約を課す。この制約のもとで、2 商品の年間発注費用と年間保管費用の総和の最小値（円）を求めよ。
難易度 4（大学院入試の標準レベル）
あるプロジェクトは作業 $A, B, C, D, E, F$ の $6$ つからなる。各作業の通常の所要日数、先行作業（その作業を始める前にすべて終わっていなければならない作業）、短縮できる最大日数、 $1$ 日短縮するごとにかかる追加費用（千円）は次のとおりである。
作業通常の所要日数先行作業最大短縮日数 $1$ 日あたりの短縮費用
$A$ $4$ なし $1$ $30$
$B$ $6$ なし $2$ $20$
$C$ $5$ $A$ $2$ $25$
$D$ $3$ $A$ $1$ $10$
$E$ $4$ $B, D$ $2$ $15$
$F$ $3$ $C, E$ $1$ $40$
各作業について短縮日数 $s$ を $0$ 以上その作業の最大短縮日数以下の整数から作業ごとに独立に選ぶ。このとき、その作業の所要日数は（通常の所要日数） $- s$ 日になり、追加費用は（ $1$ 日あたりの短縮費用） $\times s$ 千円かかる。各作業は先行作業がすべて終わりしだい直ちに開始でき、同時に進められる作業の数に制限はない。プロジェクトの開始からすべての作業が完了するまでの日数を $11$ 日以下にするとき、 $6$ つの作業の追加費用の合計の最小値（千円）を求めよ。
難易度 4（大学院入試の標準レベル）
ある小売店の売り場は、各期のはじめに「通常」（状態 $1$ ）か「繁盛」（状態 $2$ ）のどちらかの状態にある。各期のはじめに状態を見て行動を 1 つ選ぶと、その期の報酬が得られ、次の期のはじめの状態が次の確率で決まる。
- 状態 $1$ で行動「通常営業」: 報酬 $4$ 。次の期は確率 $\frac{4}{5}$ で状態 $1$ 、確率 $\frac{1}{5}$ で状態 $2$ 。
- 状態 $1$ で行動「宣伝」: 報酬 $1$ 。次の期は確率 $1$ で状態 $2$ 。
- 状態 $2$ で行動「値上げ」: 報酬 $10$ 。次の期は確率 $1$ で状態 $1$ 。
- 状態 $2$ で行動「維持」: 報酬 $8$ 。次の期は確率 $\frac{4}{5}$ で状態 $2$ 、確率 $\frac{1}{5}$ で状態 $1$ 。
第 $t$ 期（ $t = 1, 2, \dots$ ）の報酬を $R_{t}$ とする。過去の状態と行動の履歴に基づいて行動を選ぶ規則（方策） $π$ に対し、長期平均報酬を
$g^{π} = N \to \infty lim inf \frac{1}{N} E^{π} [t = 1 \sum N R_{t}]$
で定める。すべての方策の中での $g^{π}$ の最大値を求めよ（この値は第 $1$ 期の状態によらない）。
難易度 4（大学院入試の標準レベル）
3 つの倉庫 $A_{1}, A_{2}, A_{3}$ から 4 つの店舗 $B_{1}, B_{2}, B_{3}, B_{4}$ へ、ある商品を輸送する。倉庫の在庫量は $A_{1}$ が $30$ 、 $A_{2}$ が $40$ 、 $A_{3}$ が $30$ であり、在庫はすべて出荷する。店舗の需要量は $B_{1}$ が $20$ 、 $B_{2}$ が $30$ 、 $B_{3}$ が $25$ 、 $B_{4}$ が $25$ であり、需要はちょうど満たす（総在庫量と総需要量はともに $100$ で等しい）。倉庫 $A_{i}$ から店舗 $B_{j}$ へ $1$ 単位輸送する費用 $c_{ij}$ は次の表のとおりである。
$B_{1}$ $B_{2}$ $B_{3}$ $B_{4}$
$A_{1}$ $5$ $10$ $8$ $7$
$A_{2}$ $9$ $9$ $12$ $6$
$A_{3}$ $8$ $6$ $7$ $1$
ただし、経路 $A_{3} \to B_{4}$ は輸送能力に制限があり、この経路で輸送できる量は $10$ 以下である。ほかの経路には輸送量の上限はない。 $A_{i}$ から $B_{j}$ への輸送量 $x_{ij}$ は $0$ 以上の実数とし、総輸送費用 $i = 1 \sum 3 j = 1 \sum 4 c_{ij} x_{ij}$ を最小にする。総輸送費用の最小値を求めよ。
難易度 4（大学院入試の標準レベル）
あるプロジェクトは作業 $A, B, C, D, E, F, G, H, I$ の $9$ つからなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。
作業所要日数先行作業
$A$ $4$ なし
$B$ $6$ なし
$C$ $3$ $A$
$D$ $5$ $A$
$E$ $7$ $B, C$
$F$ $4$ $B$
$G$ $6$ $D, E$
$H$ $5$ $D, F$
$I$ $3$ $G, H$
プロジェクトは時刻 $0$ に始まり、各作業は先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はないものとする。
この計画どおりのときのプロジェクトの最短完了日数を $T_{1}$ とする。次に、作業 $B$ は時刻 $3$ より前には始められず、さらに作業 $F$ の所要日数が $9$ 日に増えたとする（ほかの条件は変わらない）。このときのプロジェクトの最短完了日数を $T_{2}$ とする。 $T_{1}, T_{2}$ をこの順に求めよ。
難易度 4（大学院入試の標準レベル）
ある小さな修理店には修理係が $1$ 人いて、店内には修理中の $1$ 人のほかに、待つための椅子が $2$ 脚だけある。客は到着率 $λ = 6$ （人/時）のポアソン過程に従って到着する。到着したときに店内の客（修理中の客を含む）が $3$ 人いれば、その客は店に入らずに去り、二度と戻らない。そうでなければ店に入り、先着順に修理を受ける。 $1$ 人の修理時間は、互いに独立に平均 $20$ 分の指数分布に従う（到着とも独立である）。
この系が定常状態にあるとき、店に入った客が修理を受け始めるまでに待つ時間の平均は何分か。
難易度 4（大学院入試の標準レベル）
ある品目の需要は一定の速さ $D > 0$ （単位時間あたりの個数）で連続的に生じるとする。品切れは許さず、発注した品物は直ちに届く（リードタイム $0$ ）。1 回の発注ごとに固定費 $K > 0$ がかかり、在庫 1 個を単位時間保管するごとに保管費 $h > 0$ がかかる。正の実数 $T$ に対し、「在庫がちょうど $0$ になった時刻ごとに $D T$ 個を発注する」方策（発注間隔 $T$ の方策）の単位時間あたりの平均費用（1 周期 $[0, T]$ の発注費と保管費の和を $T$ で割ったもの）を $C (T)$ とし、 $C (T)$ を最小にする $T$ を $T^{*}$ とする。
いま、発注間隔は基準時間 $T_{B} > 0$ の $2^{k}$ 倍（ $k$ は整数）に限るとする。どのような $D, K, h, T_{B}$ に対しても、ある整数 $k$ が存在して
$\frac{C ( 2 ^{k} T _{B} )}{C ( T ^{*} )} \leq \frac{3}{2 2}$
が成り立つことを証明せよ（ $T^{*}$ が存在することも示すこと）。
難易度 4（大学院入試の標準レベル）
$n \geq 2$ を整数とし、 $n$ 人の作業者 $1, \dots, n$ を $n$ 個の仕事 $1, \dots, n$ に 1 対 1 に割り当てる割当問題を考える。作業者 $i$ に仕事 $j$ を割り当てたときの費用を実数 $c_{ij}$ とし、 ${1, \dots, n}$ 上の置換 $σ$ （作業者 $i$ に仕事 $σ (i)$ を割り当てる）の総費用を
$F (σ) = i = 1 \sum n c_{i σ (i)}$
とする。費用が次の条件（モンジュ条件）を満たすとする:
$1 \leq i < k \leq n, 1 \leq j < l \leq n を満たすすべての i, j, k, l について c_{ij} + c_{k l} \leq c_{i l} + c_{k j} .$
このとき、恒等置換 $id$ （作業者 $i$ に仕事 $i$ を割り当てる）は割当問題の最適解であること、すなわちすべての置換 $σ$ に対して $F (id) \leq F (σ)$ が成り立つことを証明せよ。
難易度 4（大学院入試の標準レベル）
ある検査センターには、受付（窓口 $1$ ）と検査室（窓口 $2$ ）がある。客は外部から到着率 $4$ （人/時）のポアソン過程に従って受付に到着する。運営のしくみは次のとおりである。
- 受付には係員が $1$ 人いて、サービス時間は平均 $\frac{1}{10}$ 時間の指数分布に従う。
- 受付を終えた客は、すべて検査室へ進む。検査室には検査員が $2$ 人いて、客は $1$ 列に並び、空いた検査員から先着順に検査を受ける。各検査員の検査時間は平均 $\frac{1}{3}$ 時間の指数分布に従う。
- 検査を終えた客は、確率 $\frac{1}{5}$ で再検査のため受付に戻って再び並び、確率 $\frac{4}{5}$ でセンターを去る。この行き先の選択は、毎回ほかのすべてと独立に行われる。
どちらの窓口も待合室の容量に制限はなく、受付も先着順である。すべてのサービス時間は互いに独立であり、外部からの到着とも独立とする。この系が定常状態にあるとき、 $1$ 人の客がセンターに到着してから去るまでにセンター内で過ごす時間（待ち時間とサービス時間をすべて含み、何回受付に戻ってもその分も含める）の平均を、時間を単位として求めよ。

辺	長さ	辺	長さ	辺	長さ
$S$ – $A$	$2$	$A$ – $C$	$3$	$C$ – $D$	$1$
$S$ – $B$	$3$	$B$ – $C$	$2$	$C$ – $T$	$4$
$A$ – $B$	$1$	$B$ – $D$	$4$	$D$ – $T$	$3$

辺	長さ	辺	長さ	辺	長さ
$s$ — $a$	$2$	$a$ — $c$	$3$	$c$ — $d$	$1$
$s$ — $b$	$3$	$b$ — $c$	$2$	$c$ — $t$	$4$
$a$ — $b$	$1$	$b$ — $d$	$4$	$d$ — $t$	$3$

作業	先行作業	通常の所要日数	短縮できる最大日数	1日あたりの短縮費用（万円）
$A$	なし	$3$	$1$	$3$
$B$	なし	$5$	$2$	$2$
$C$	$A$	$4$	$2$	$5$
$D$	$B$	$2$	$1$	$4$
$E$	$C, D$	$3$	$1$	$8$

	$J_{1}$	$J_{2}$	$J_{3}$	$J_{4}$
$W_{1}$	$8$	$4$	$7$	$6$
$W_{2}$	$5$	$9$	$6$	$3$
$W_{3}$	$7$	$6$	$10$	$8$
$W_{4}$	$6$	$7$	$5$	$9$

作業	所要日数	先行作業
$1$	$3$	なし
$2$	$5$	なし
$3$	$4$	$1$
$4$	$2$	$1$
$5$	$6$	$2, 4$
$6$	$3$	$3$
$7$	$4$	$5, 6$
$8$	$2$	$3$

作業	先行作業	$a$	$m$	$b$
$A$	なし	$2$	$4$	$6$
$B$	なし	$3$	$5$	$13$
$C$	$A$	$1$	$3$	$5$
$D$	$A$	$4$	$6$	$14$
$E$	$B, C$	$2$	$5$	$8$
$F$	$D, E$	$3$	$4$	$11$
$G$	$E$	$1$	$2$	$9$

辺	長さ	辺	長さ
$1 \to 2$	$3$	$3 \to 6$	$7$
$1 \to 3$	$2$	$2 \to 5$	$5$
$1 \to 4$	$6$	$2 \to 6$	$6$
$3 \to 2$	$1$	$4 \to 5$	$2$
$2 \to 4$	$2$	$4 \to 6$	$3$
$3 \to 4$	$3$	$5 \to 7$	$3$
		$6 \to 7$	$2$

発注量 $Q$	単価
$1 \leq Q < 500$	$1000$ 円
$500 \leq Q < 1500$	$960$ 円
$1500 \leq Q$	$945$ 円

作業	通常の所要日数	先行作業	1 日短縮あたりの追加費用（万円）	短縮できる最大日数
$A$	$4$	なし	$5$	$1$
$B$	$6$	なし	$2$	$2$
$C$	$5$	$A$	$3$	$2$
$D$	$3$	$A$	$4$	$1$
$E$	$4$	$B, D$	$6$	$2$
$F$	$3$	$C, E$	$10$	$1$

作業	通常の所要日数	先行作業	最大短縮日数	$1$ 日あたりの短縮費用
$A$	$4$	なし	$1$	$30$
$B$	$6$	なし	$2$	$20$
$C$	$5$	$A$	$2$	$25$
$D$	$3$	$A$	$1$	$10$
$E$	$4$	$B, D$	$2$	$15$
$F$	$3$	$C, E$	$1$	$40$