最適化セミナーのご案内

2.26 遷移確率行列

 ここでは,遷移確率行列を用いた問題を紹介します.Vector/Matrixクラスを利用すると,遷移確率行列を用いた問題が記述し易くなります.

例題

 ある地域には小学校が3校,中学校が2校,高等学校が2校ある.それぞれの学校には入学者の人数制限が決められており,どの学校へ進学するかの遷移確率がわかっているとする.

 いま,ある年度の小学校入学予定者人数を予測すると,小学校2の入学者上限を大幅に超えてしまったため,小学校2から小学校1,小学校3への入学者人数の調整を行うことにした.この年度の児童が与えられた遷移確率に従って中学校,高等学校に進学すると仮定したとき,入学者上限制約を満たし,かつ最小の人数調整で解決したい場合,どのような人数調整を行えばよいか.

 この問題をNumerical Optimizerで解くために定式化を行います.

 変数は,小学校2から小学校1への調整人数$x$と小学校2から小学校3への調整人数$y$とします.目的関数は調整人数の最小化ですので$x + y$となります.また,現実問題を考慮すると変数は整数値をとるが,ここでは連続変数として扱い,得られた解の値を整数値に丸めて取り扱うことにします.

 次に制約条件を考えます.まず,調整人数についての制約として,非負制約,および調整人数の総和が小学校2の入学予定人数を超えてはならないという制約があります.また,各遷移確率に従って進学をした場合にそれぞれの学校の入学人数制限を満たすという制約があります.

 以上をふまえて次のように定式化されます.

集合
$E = \{ E1,E2,E3 \}$ 小学校の集合
$J = \{ J1,J2 \}$ 中学校の集合
$H = \{ H1,H2 \}$ 高等学校の集合
 
定数
$EJ_{ej}, e \in E, j \in J$ 各小学校から各中学校への遷移確率行列
$JH_{jh}, j \in J, h \in H$ 各中学校から各高等学校への遷移確率行列
$flow_e, e \in E$ 各小学校への入学予定人数ベクトル
$Eup_e, e \in E$ 各小学校の入学者上限ベクトル
$Jup_j, j \in J$ 各中学校の入学者上限ベクトル
$Hup_h, h \in H$ 各高等学校の入学者上限ベクトル
 
変数
$x$ 小学校2から小学校1への調整人数
$y$ 小学校2から小学校3への調整人数
$X_e, e \in E$ 人数調整後の各小学校への入学人数ベクトル
$X_{E1} = flow_{E1} + x$

$X_{E2} = flow_{E2} - x - y$

$X_{E3} = flow_{E3} + y$
 
 
目的関数(最小化)
$x + y$ 調整人数の最小化
 
制約
$x,y \ge 0$ 非負制約
$x + y \le flow_{E2}$ 調整人数の総和は小学校2への入学予定人数を超えてはならない
$X \le Eup$ 各小学校の入学人数の制限
$(X^T \cdot EJ)^T \le Jup$ 各中学校の入学人数の制限
$(X^T \cdot EJ \cdot JH)^T \le Hup$ 各高等学校の入学人数の制限

 次に,ベクトルと行列をデータファイルから与えるSIMPLEモデルを示します.

// 集合と添え字
Set E; Element e(set=E); // 小学校
Set J; Element j(set=J); // 中学校
Set H; Element h(set=H); // 高等学校

// 行列パラメータとベクトルパラメータ
Matrix EJ((e,j)), JH((j,h));
Vector flow(e), Eup(e), Jup(j), Hup(h);

// 変数
Variable  x,y;
0 <= x;
0 <= y;
x + y <= flow["E2"];

// 変数ベクトル
Vector X(e);
X["E1"] = flow["E1"] + x;
X["E2"] = flow["E2"] - x - y;
X["E3"] = flow["E3"] + y;

// 制約
X <= Eup;
trans(trans(X) * EJ) <= Jup;
trans(trans(X) * EJ * JH) <= Hup;

// 目的関数値
Objective obj(type=minimize);
obj = x + y;
// 求解
solve();

// 出力
x.val.print();
y.val.print();

 データファイル(.csv形式)は以下のようになります.

 各小学校への入学人数と,各学校への進学の遷移確率行列

e,flow
E1,200
E2,280
E3,200
EJ,J1,J2
E1,0.8,0.2
E2,0.4,0.6
E3,0.3,0.7
JH,H1,H2
J1,0.6,0.4
J2,0.45,0.55

 各学校の入学上限

e,Eup
E1,240
E2,240
E3,240
j,Jup
J1,360
J2,360
h,Hup
H1,360
H2,360

 このモデルを実行すると,$x = 15.2907$$y = 24.7093$が求まりますので,整数値に丸めて小学校2から小学校1への調整人数15人と小学校2から小学校3への調整人数25人が得られます.また,その結果,以下のように進学予定人数がわかります.


 

 

上に戻る