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

2.3 多期間計画問題

　多期間計画問題とは，多期間にわたり期間ごとに意思決定をする問題のことをいいます．多期間計画問題を定式化する場合は，期間ごとに変数を定義するのが一般的です．

例題

　2種類の原料A，Bを加工して2種類の製品I, IIを生産している工場が，向こう3ヶ月間の生産計画を立てようとしています．各製品を1単位生産するために必要な原料の使用量，各製品の生産／在庫コスト，各製品の月ごとの出荷量，各原料の月ごとの利用可能量は以下のように与えられています．

原料使用量 生産／在庫コスト
  I II   I II
A 2 7 生産 75 50
B 5 3 在庫 8 7

　

製品の出荷量 原料の利用可能量
  I II   A B
1 30 20 1 920 790
2 60 50 2 750 600
3 80 90 3 500 480

　

　各月に出荷する製品をその月中に全て生産できるとは限らないので，前の月に生産した製品を在庫として保管して来月に出荷することも考えられます．このような状況の下で，要求された製品の出荷量と与えられた原料の利用可能量の制約を満たしつつ総コストを最小にするには，各月における各製品の生産量と在庫量をどのように決定すればよいでしょうか．

　この問題をNuorium Optimizerで解くために定式化を行います．本例題は文献[2]からの引用です．

　まず，変数として各月における製品I，IIの生産量をそれぞれ$x_{{\rm I}, 1}, x_{{\rm II}, 1}, x_{{\rm I}, 2}, x_{{\rm II}, 2}, x_{{\rm I}, 3}, x_{{\rm II}, 3}$とし，在庫量をそれぞれ$y_{{\rm I}, 1}, y_{{\rm II}, 1}, y_{{\rm I}, 2}, y_{{\rm II}, 2}$としましょう．

　次に，最小化するべき目的関数は，各生産量／在庫量とその単位量あたりのコストとの積の総和として表現することができます．

　最後に制約条件です．まず，各変数に対して非負制約が必要です．次に，1ヶ月に利用できる原料が決められているので，各月ごとに各原料に関する制約が必要です．さらに，各製品に対して在庫量は次の月に持ち越せますので，それを踏まえた出荷量の制約を加えます．

　以上のことから，次のように定式化することができます．

変数
$x_{{\rm I}, 1}$ 製品Iの1ヶ月目の生産量
$x_{{\rm II}, 1}$ 製品IIの1ヶ月目の生産量
$x_{{\rm I}, 2}$ 製品Iの2ヶ月目の生産量
$x_{{\rm II}, 2}$ 製品IIの2ヶ月目の生産量
$x_{{\rm I}, 3}$ 製品Iの3ヶ月目の生産量
$x_{{\rm II}, 3}$ 製品IIの3ヶ月目の生産量
$y_{{\rm I}, 1}$ 製品Iの1ヶ月目の在庫量
$y_{{\rm II}, 1}$ 製品IIの1ヶ月目の在庫量
$y_{{\rm I}, 2}$ 製品Iの2ヶ月目の在庫量
$y_{{\rm II}, 2}$ 製品IIの2ヶ月目の在庫量
　
目的関数（最小化）
$75x_{{\rm I}, 1} + 50x_{{\rm II}, 1} + 8y_{{\rm I}, 1} + 7y_{{\rm II}, 1} + 75x_{{\rm I}, 2} + 50x_{{\rm II}, 2} + 8y_{{\rm I}, 2} + 7y_{{\rm II}, 2} + 75x_{{\rm I}, 3} + 50x_{{\rm II}, 3}$ 総コスト
　
非負制約
$x_{{\rm I}, 1} \ge 0$, $x_{{\rm II}, 1} \ge 0$ 　
$x_{{\rm I}, 2} \ge 0$, $x_{{\rm II}, 2} \ge 0$ 　
$x_{{\rm I}, 3} \ge 0$, $x_{{\rm II}, 3} \ge 0$ 　
$y_{{\rm I}, 1} \ge 0$, $y_{{\rm II}, 1} \ge 0$ 　
$y_{{\rm I}, 2} \ge 0$, $y_{{\rm II}, 2} \ge 0$ 　
　
原料の制約
$2x_{{\rm I}, 1} + 7x_{{\rm II}, 1} \le 920$ 原料Aについて（1ヶ月目）
$5x_{{\rm I}, 1} + 3x_{{\rm II}, 1} \le 790$ 原料Bについて（1ヶ月目）
$2x_{{\rm I}, 2} + 7x_{{\rm II}, 2} \le 750$ 原料Aについて（2ヶ月目）
$5x_{{\rm I}, 2} + 3x_{{\rm II}, 2} \le 600$ 原料Bについて（2ヶ月目）
$2x_{{\rm I}, 3} + 7x_{{\rm II}, 3} \le 500$ 原料Aについて（3ヶ月目）
$5x_{{\rm I}, 3} + 3x_{{\rm II}, 3} \le 480$ 原料Bについて（3ヶ月目）
　
出荷量の制約
$x_{{\rm I}, 1} - y_{{\rm I}, 1} = 30$ 製品Iについて（1ヶ月目）
$x_{{\rm II}, 1} - y_{{\rm II}, 1} = 20$ 製品IIについて（1ヶ月目）
$x_{{\rm I}, 2} + y_{{\rm I}, 1} - y_{{\rm I}, 2} = 60$ 製品Iについて（2ヶ月目）
$x_{{\rm II}, 2} + y_{{\rm II}, 1} - y_{{\rm II}, 2} = 50$ 製品IIについて（2ヶ月目）
$x_{{\rm I}, 3} + y_{{\rm I}, 2} = 80$ 製品Iについて（3ヶ月目）
$x_{{\rm II}, 3} + y_{{\rm II}, 2} = 90$ 製品IIについて（3ヶ月目）

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

// 変数
Variable x11(name = "製品 I の 1 ヶ月目の生産量");
Variable x21(name = "製品 II の 1 ヶ月目の生産量");
Variable x12(name = "製品 I の 2 ヶ月目の生産量");
Variable x22(name = "製品 II の 2 ヶ月目の生産量");
Variable x13(name = "製品 I の 3 ヶ月目の生産量");
Variable x23(name = "製品 II の 3 ヶ月目の生産量");
Variable y11(name = "製品 I の 1 ヶ月目の在庫量");
Variable y21(name = "製品 II の 1 ヶ月目の在庫量");
Variable y12(name = "製品 I の 2 ヶ月目の在庫量");
Variable y22(name = "製品 II の 2 ヶ月目の在庫量");

// 目的関数
Objective z(name = "総コスト", type = minimize);
z = 75 * x11 + 50 * x21 + 8 * y11 + 7 * y21 + 75 * x12 +
    50 * x22 + 8 * y12 + 7 * y22 + 75 * x13 + 50 * x23;

// 非負制約
x11 >= 0; x21 >= 0;
x12 >= 0; x22 >= 0;
x13 >= 0; x23 >= 0;
y11 >= 0; y21 >= 0;
y12 >= 0; y22 >= 0;

// 原料の制約
2 * x11 + 7 * x21 <= 920;
5 * x11 + 3 * x21 <= 790;
2 * x12 + 7 * x22 <= 750;
5 * x12 + 3 * x22 <= 600;
2 * x13 + 7 * x23 <= 500;
5 * x13 + 3 * x23 <= 480;

// 出荷量の制約
x11       - y11 == 30;
x21       - y21 == 20;
x12 + y11 - y12 == 60;
x22 + y21 - y22 == 50;
x13 + y12       == 80;
x23 + y22       == 90;

// 求解
solve();

// 出力
z.val.print();

　より汎用的に問題を定式化すると以下のようになります．

集合
$Product = \{ {\rm I}, {\rm II}\} $ 製品
$Material = \{ A, B\} $ 原料
$Period = \{ 1, 2, 3\} $ 期間
　
定数
$use_{i, j}, i \in Product, j \in Material$ 製品$i$を生産するのに必要な原料$j$の使用量
$out_{i, t}, i \in Product, t \in Period$ $t$ヶ月目の製品$i$の出荷量
$upper_{j, t}, j \in Material, t \in Period$ $t$ヶ月目の原料$j$の利用可能量
$cost{p_i}, i \in Product$ 製品$i$の生産コスト
$cost{i_i}, i \in Product$ 製品$i$の在庫コスト
　
変数
$x_{i, t}, i \in Product, t \in Period$ 製品$i$の$t$ヶ月目の生産量
$y_{i, t}, i \in Product, t \in Period$ 製品$i$の$t$ヶ月目の在庫量
　
目的関数（最小化）
$\displaystyle\sum_{t \in Period} \sum_{i \in Product} (costp_{i} x_{i, t} + costi_{i} y_{i, t})$ 総コスト
　
制約
$x_{i, t} \ge 0, \forall i \in Product, \forall t \in Period$ 生産量の非負制約
$y_{i,t} \ge 0, \forall i \in Product, \forall t \in Period$ 在庫量の非負制約
$\displaystyle\sum_{i \in Product} use_{i, j} x_{i, t} \le upper_{j, t}, \forall j \in Material, \forall t \in Period$ 原料の使用量の制約
$x_{i, 1} - y_{i, 1} = out_{i, 1}$ 1ヶ月目の出荷量について
$x_{i, 2} + y_{i, 1} - y_{i, 2} = out_{i, 2}$ 2ヶ月目の出荷量について
$x_{i, 3} + y_{i, 2} = out_{i, 3}$ 3ヶ月目の出荷量について

　次に，定数をデータファイルから与える場合のモデルを示します．

// 集合と添字
Set Product(name = "製品");
Element i(set = Product);
Set Material(name = "原料");
Element j(set = Material);
Set Period(name = "期間");
Element t(set = Period);

// パラメータ
Parameter use(name = "原料使用量", index = (i, j));
Parameter out(name = "出荷量", index = (i, t));
Parameter upper(name = "利用可能量", index = (j, t));
Parameter costp(name = "生産コスト", index = i);
Parameter costi(name = "在庫コスト", index = i);

// 変数
Variable x(name = "生産量", index = (i, t));
Variable y(name = "在庫量", index = (i, t));

// 目的関数
Objective z(name = "総コスト", type = minimize);
z = sum(costp[i] * x[i, t] + costi[i] * y[i, t], (i, t));

// 非負制約
x[i, t] >= 0;
y[i, t] >= 0;

// 原料の制約
sum(use[i, j] * x[i, t], i) <= upper[j, t];

// 出荷量の制約
x[i, t]               - y[i, t] == out[i, t], t == 1;
x[i, t] + y[i, t - 1] - y[i, t] == out[i, t], t == 2;
x[i, t] + y[i, t - 1]           == out[i, t], t == 3;

// 求解
solve();

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

　データファイル（.dat形式）は以下のようになります．

原料使用量 =
[I, A] 2
[I, B] 5
[II, A] 7
[II, B] 3
;

出荷量 =
[I, 1] 30
[I, 2] 60
[I, 3] 80
[II, 1] 20
[II, 2] 50
[II, 3] 90
;

利用可能量 =
[A, 1] 920
[A, 2] 750
[A, 3] 500
[B, 1] 790
[B, 2] 600
[B, 3] 480
;

生産コスト =
[I] 75
[II] 50
;

在庫コスト =
[I] 8
[II] 7
;

　このモデルを実行すると，以下のような結果が得られます．

総コスト=21199.2
生産量["I",1] = 38
生産量["I",2] = 67.8621
生産量["I",3] = 64.1379
生産量["II",1] = 20
生産量["II",2] = 86.8966
生産量["II",3] = 53.1034
在庫量["I",1] = 8
在庫量["I",2] = 15.8621
在庫量["I",3] = 1.44466e-08
在庫量["II",1] = 5.25339e-08
在庫量["II",2] = 36.8966
在庫量["II",3] = 1.65103e-08

　なお，一つ注意点があります．

　上記の求解実行において，在庫量に関する添字付きの変数を3ヶ月目についても用意しています（在庫量["I", 3]，在庫量["II", 3]）．これらは，この章のはじめに定式化した際には，用意していなかった変数です．

　しかし，これらの変数について非負制約以外の制約がないこと，および目的関数（総コスト）は最小化についてのものであること，この両者から，在庫量["I", 3]，在庫量["II", 3]の求解結果は上記のようにほぼ0と等しい値になります．

　従って在庫量["I", 3]，在庫量["II", 3]を定義しても，一般性は失われません．

　最後に，これまでのモデルは出荷量の制約について3ヶ月分の計画であるということを利用した記述となっていました．このため，例えば向こう6ヶ月の生産計画を立てようとした場合モデルの修正が必要となります．ここでは，順序集合OrderedSetを利用し，計画期間が変化した場合でも対応できるようにしたモデルを紹介します．

　これまでのモデルの「2ヶ月目の出荷量について」という制約条件は，最初の月と最後の月以外の月に対して課すことになります．このため，向こうTヶ月の生産計画を立てるとした場合の定式化は以下のようになります．

集合
$Product = \{ {\rm I}, {\rm II}\} $ 製品
$Material = \{ A, B\} $ 原料
$Period = \{ 1, ..., T\} $ 期間（順序集合）
　
定数
$use_{i, j}, i \in Product, j \in Material$ 製品$i$を生産するのに必要な原料$j$の使用量
$out_{i, t}, i \in Product, t \in Period$ $t$ヶ月目の製品$i$の出荷量
$upper_{j, t}, j \in Material, t \in Period$ $t$ヶ月目の原料$j$の利用可能量
$cost{p_i}, i \in Product$ 製品$i$の生産コスト
$cost{i_i}, i \in Product$ 製品$i$の在庫コスト
　
変数
$x_{i, t}, i \in Product, t \in Period$ 製品$i$の$t$ヶ月目の生産量
$y_{i, t}, i \in Product, t \in Period$ 製品$i$の$t$ヶ月目の在庫量
　
目的関数（最小化）
$\displaystyle\sum_{t \in Period} \sum_{i \in Product} (costp_{i} x_{i, t} + costi_{i} y_{i, t})$ 総コスト
　
制約
$x_{i, t} \ge 0, \forall i \in Product, \forall t \in Period$ 生産量の非負制約
$y_{i, t} \ge 0, \forall i \in Product, \forall t \in Period$ 在庫量の非負制約
$\displaystyle\sum_{i \in Product} use_{i, j} x_{it} \le upper_{j, t}, \forall j \in Material, \forall t \in Period$ 原料の使用量の制約
$x_{i, 1} - y_{i, 1} = out_{i, 1}$ 1ヶ月目の出荷量について
$x_{i, t} + y_{i, t - 1} - y_{i, t} = out_{i, t}, \forall t \in \{2, \cdots, T - 1\}$ tヶ月目の出荷量について（tは2からT-1まで）
$x_{i, T} + y_{i, T - 1} = out_{i, T}$ Tヶ月目の出荷量について

　順序集合を利用した場合のモデルとデータファイル（.dat形式）はそれぞれ以下のようになります．なお，モデルでは1ヶ月目とTヶ月目をそれぞれPeriod.first()（順序集合Periodの最初の要素），Period.last()（順序集合Periodの最後の要素）と表現しています． 

// 集合と添字
Set Product(name = "製品");
Element i(set = Product);
Set Material(name = "原料");
Element j(set = Material);
OrderedSet Period(name = "期間");
Element t(set = Period);

// パラメータ
Parameter use(name = "原料使用量", index = (i, j));
Parameter out(name = "出荷量", index = (i, t));
Parameter upper(name = "利用可能量", index = (j, t));
Parameter costp(name = "生産コスト", index = i);
Parameter costi(name = "在庫コスト", index = i);

// 変数
Variable x(name = "生産量", index = (i, t));
Variable y(name = "在庫量", index = (i, t));

// 目的関数
Objective z(name = "総コスト", type = minimize);
z = sum(costp[i] * x[i, t] + costi[i] * y[i, t], (i, t));

// 非負制約
x[i, t] >= 0;
y[i, t] >= 0;

// 原料の制約
sum(use[i, j] * x[i, t], i) <= upper[j, t];

// 出荷量の制約
x[i, t]                        - y[i, t] == out[i, t], t == Period.first();
x[i, t] + y[i, Period.prev(t)] - y[i, t] == out[i, t], t != Period.first(), t != Period.last();
x[i, t] + y[i, Period.prev(t)]           == out[i, t], t == Period.last();

// 求解
solve();

// 出力
z.val.print();
x.val.print();
y.val.print();
期間 = 1 .. 3;

原料使用量 =
[I, A] 2
[I, B] 5
[II, A] 7
[II, B] 3
;

出荷量 =
[I, 2] 60
[I, 3] 80
[II, 1] 20
[II, 2] 50
[II, 3] 90
[I, 1] 30
;

利用可能量 =
[A, 1] 920
[A, 2] 750
[A, 3] 500
[B, 1] 790
[B, 2] 600
[B, 3] 480
;

生産コスト =
[I] 75
[II] 50
;

在庫コスト =
[I] 8
[II] 7
;
2.2 輸送問題
2.4 包絡分析法（DEA）モデル

 

 

上に戻る