数理最適化セミナーのご案内

2.4 包絡分析法（DEA）モデル

　包絡分析法（DEA；Data Envelopment Analysis）とは，複数の企業体の相対的な効率性を測定する方法で，評価対象の具体例としては，銀行・病院があげられます．

　以下の例題では，チェーン展開している6店舗に対して，DEAに基づいた効率性の評価を行います．なお，本節では[3]を参考文献としています．

例題

　ある会社は，以下の6店舗を抱えている．

店舗番号 1 2 3 4 5 6
店員数 5 10 20 20 30 50
稼働時間 24 12 12 24 12 12
売上 2 6 10 12 12 20

　

　各店舗が，全店舗に対して相対的に効率的であるかどうかを判定せよ．

　この問題の定式化は次のようになります．

集合
$I$ 入力項目集合
$J$ 出力項目集合
$K$ 店舗集合
$\overline{K}$ 対象店舗（単一要素からなる集合）
　
定数
$inD_{k, i}, k \in K, i \in I$ 入力データ
$outD_{k, j}, k \in K, j \in J$ 出力データ
　
変数
$inW_i, i \in I$ 入力項目に対する重み
$outW_j, j \in J$ 出力項目に対する重み
　
目的関数（最大化）
$\displaystyle \sum_{\overline{k}, j} outD_{\overline{k}, j} outW_j$ 対象店舗に対する出力
　
制約式
$\displaystyle \sum_i inD_{\overline{k}, i} inW_i = 1, \forall \overline{k} \in \overline{K}$ 対象店舗の入力条件
$\displaystyle \sum_j outD_{k, j} outW_j \le \sum_i inD_{k, i} inW_i, \forall k \in K$ 全店舗に対する入出力条件
$0 \le inW_i, \forall i \in I$ 重みの非負条件
$0 \le outW_j, \forall j \in J$ 　

　以下で，本問題の定式化の説明を行います．

　DEAでは，本例題の店舗のような分析対象をDMU（Decision Making Unit）と呼びます．全てのDMUを一度に評価することは困難なため，店舗集合$K$に属するある店舗$\overline{k} \in \overline{K} \subset K$に着目した問題を考えます．

　対象とする問題は，効率を最大化するような問題です．この効率$f_{\overline{k}}$を以下で定義することとします．

\[f_{\overline{k}} = \frac{\displaystyle \sum\nolimits_j outD_{\overline{k}, j} outW_j}{\displaystyle \sum\nolimits_i inD_{\overline{k}, i} inW_i}\]

即ち，対象店舗$\overline{k}$に対する，(総出力/総入力)を効率と定め，これを最大化するような問題を扱います．なお，この問題の変数となる各入出力項目に対する重みは，各店舗共通で与えられるものとします．制約条件としては，任意の店舗に関して，(総出力/総入力)が1以下になるという条件が必要です．即ち，

\[\frac{\displaystyle \sum\nolimits_j outD_{k, j} outW_j}{\displaystyle \sum\nolimits_i inD_{k, i} inW_i} \le 1, \forall k \in K\]

となります．また，各入出力項目に対する重みの非負制約も考慮する必要があります．なお，この問題は目的関数・制約式ともに分数式で表わされる分数計画問題となります．これらの分数関数の分母は正であるため，制約式は両辺に分母部分をかけても一般性は失われなく，また目的関数$f_{\overline{k}}$についても，分母部分を1と等価であるという制約式で表わして，分子部分のみを目的関数としても一般性は失われません．

　このようにして，等価な線形計画問題に置き換えた問題の定式化がはじめに示したものとなります．

　以上が，本問題に対する定式化の説明です．

　

　この問題をC++SIMPLEで記述すると，以下のようになります．

// 集合と添字
Set I(name = "入力項目集合");
Element i(set = I);
Set J(name = "出力項目集合");
Element j(set = J);
Set K(name = "店舗集合");
Element k(set = K);
Set Kbar(name = "対象店舗", superSet = K);
Element kbar(set = Kbar);

/// パラメータ
Parameter inD(name = "入力データ", index = (k, i));
Parameter outD(name = "出力データ", index = (k, j));

// 変数
Variable inW(name = "inW", index = i);   // 入力項目に対する重み
Variable outW(name = "outW", index = j); // 出力

// 目的関数
Objective f(name = "f", type = maximize);
f = sum(outD[kbar, j] * outW[j], (kbar, j));

// 非負制約
0 <= inW[i];
0 <= outW[j];

// 制約式
sum(inD[kbar, i] * inW[i], i) == 1;
sum(outD[k, j] * outW[j], j) <= sum(inD[k, i] * inW[i], i);

// 求解
options.method = "simplex"; // 単体法の利用
solve();

// 結果出力
f.val.print();
inW.val.print();
outW.val.print();

　入力データとしては以下の3種類（csvファイル：2種類，datファイル：1種類）を用意する必要があります．

入力データ, 店員数, 稼働時間
1, 5, 24
2, 10, 12
3, 20, 12
4, 20, 24
5, 30, 12
6, 50, 12
出力データ, 売上
1, 2
2, 6
3, 10
4, 12
5, 12
6, 20
対象店舗 = 1;

　対象店舗（店舗番号：1～6）をKbar.datにおいて逐次変化させて解いた結果を以下の表にまとめます．なお，一部結果は小数点以下第四位を四捨五入した値で表わしています．

店舗番号 1 2 3 4 5 6
目的関数値 0.667 1 1 1 0.9 1
入力項目 重み（店員数） 0.2 0.067 0.04 0.033 0.025 0.017
重み（稼働時間） 0 0.028 0.017 0.014 0.021 0.014
出力項目 重み（売上） 0.333 0.167 0.1 0.083 0.075 0.05

　

　目的関数値が1となる店舗（店舗番号：2，3，4，6）は効率的であるといえます．一方，1より小さな値となる店舗（店舗番号：1，5）は，各種制約を満たすどのような重みを選択しても効率が1になりえないということで，非効率であるということになります．

　非効率な店舗に関しては，非効率となっている原因を形成している店舗集合を参照集合として導きだすことも可能です．詳細については，[4]を参照ください．

2.3 多期間計画問題
2.5 ナップサック問題

 

 

上に戻る