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

ある小売店の売り場は、各期のはじめに「通常」（状態 $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$ とする。過去の状態と行動の履歴に基づいて行動を選ぶ規則（方策）$\pi$ に対し、長期平均報酬を
$$g^{\pi }=\underset{N\to \infty }{\mathrm{liminf}}\frac{1}{N}{E}^{\pi }\left[\sum _{t=1}^N{R}_t\right]$$
で定める。すべての方策の中での $g^{\pi }$ の最大値を求めよ（この値は第 $1$ 期の状態によらない）。

ある品目の需要は一定の速さ $D>0$（単位時間あたりの個数）で連続的に生じるとする。品切れは許さず、発注した品物は直ちに届く（リードタイム $0$）。1 回の発注ごとに固定費 $K>0$ がかかり、在庫 1 個を単位時間保管するごとに保管費 $h>0$ がかかる。正の実数 $T$ に対し、「在庫がちょうど $0$ になった時刻ごとに $DT$ 個を発注する」方策（発注間隔 $T$ の方策）の単位時間あたりの平均費用（1 周期 $[0,T]$ の発注費と保管費の和を $T$ で割ったもの）を $C(T)$ とし、$C(T)$ を最小にする $T$ を $T^{\ast }$ とする。

いま、発注間隔は基準時間 $T_B>0$ の $2^k$ 倍（$k$ は整数）に限るとする。どのような $D,K,h,T_B$ に対しても、ある整数 $k$ が存在して
$$\frac{C(2^k{T}_B)}{C(T^{\ast })}\le \frac{3}{2\sqrt{2}}$$
が成り立つことを証明せよ（$T^{\ast }$ が存在することも示すこと）。

あるプロジェクトは作業 $A,B,C,D,E,F,G,H,I$ の $9$ つからなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

プロジェクトは時刻 $0$ に始まり、各作業は先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はないものとする。

この計画どおりのときのプロジェクトの最短完了日数を $T_1$ とする。次に、作業 $B$ は時刻 $3$ より前には始められず、さらに作業 $F$ の所要日数が $9$ 日に増えたとする（ほかの条件は変わらない）。このときのプロジェクトの最短完了日数を $T_2$ とする。$T_1,T_2$ をこの順に求めよ。

客が到着率 $\lambda >0$ のポアソン過程に従って到着する、待合室の容量に制限のない次の 2 つの待ち行列システムを考える。$\mu >0$ とし、$\lambda <2\mu$ とする。

• システム A: 窓口が 1 つで、サービス時間は平均 $\frac{1}{2\mu }$ の指数分布に従う（M/M/1）。
• システム B: 窓口が 2 つで、各窓口のサービス時間は平均 $\frac{1}{\mu }$ の指数分布に従う（M/M/2）。客は空いている窓口があればすぐにサービスを受け、なければ 1 列に並んで先着順に待つ。

どちらのシステムでも、サービス時間は互いに独立で到着とも独立とする。系内人数（待っている客とサービス中の客の合計）の定常分布を $\{p_n{\}}_{n\ge 0}$ とすると、系内人数が $n$ 人のときのサービス終了率を ${\mu }_n$ として、定常分布はつり合いの式
$$\lambda p_n={\mu }_{n+1}{p}_{n+1}(n=0,1,2,\dots ),\sum _{n=0}^{\infty }{p}_n=1$$
のただ 1 つの解であることを用いてよい（${\mu }_n$ は各システムの設定から定まる）。

定常状態における平均系内人数を、システム A について $L_A$、システム B について $L_B$ とするとき、$L_A<L_B$ であることを証明せよ。

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}$ は次の表のとおりである。

ただし、経路 $A_3\to B_4$ は輸送能力に制限があり、この経路で輸送できる量は $10$ 以下である。ほかの経路には輸送量の上限はない。$A_i$ から $B_j$ への輸送量 $x_{ij}$ は $0$ 以上の実数とし、総輸送費用 $\sum _{i=1}^3\sum _{j=1}^4{c}_{ij}{x}_{ij}$ を最小にする。総輸送費用の最小値を求めよ。