Numerical Optimizer SIMPLE例題集 V19

2.8 最小費用流問題

　前節の最大流問題では，小麦粉の輸送を例にネットワークに流れる量をできるだけ多くしようという方針で最適化を行いました．このため，小麦粉を輸送する際にかかる燃料費などの様々なコストを考慮していませんでした．また，製粉工場から1日に出荷する小麦粉の量が決まっているような場合には別の方針で最適化を行う必要があります．

　決まった量をネットワーク上で始点から終点まで流す際にかかる費用（コスト）を最小にしようという問題のことを最小費用流問題といいます．なお，最大流問題のときと同様に，保存則が成立する必要があります．また，「決まった量」が1である場合には最小路問題と呼ばれ，カーナビゲーションシステムでのルート探索や鉄道の経路案内などに応用されています．

　定式化について，前節の最大流問題の時との違いは

• 総輸送量（前節の例題でのtotalという変数）が8に決まっている．
• 目的関数が総費用の最小化に変わっている．

の2点です．この2点以外については，前節の例題と同じ定式化となりますので必要に応じて前節を参考にしてください．なお，総費用は各輸送ルートについて「小麦粉1kgあたりの費用」と「輸送した小麦粉の量」の積を求め総和をとることで求められます．

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

　この結果をSIMPLEで記述すると以下のようになります．

//変数の宣言
Variable f_XA(name="製粉工場から地点Aへの輸送量");
Variable f_XB(name="製粉工場から地点Bへの輸送量");
Variable f_AC(name="地点Aから地点Cへの輸送量");
Variable f_BC(name="地点Bから地点Cへの輸送量");
Variable f_BD(name="地点Bから地点Dへの輸送量");
Variable f_CY(name="地点Cからレストランへの輸送量");
Variable f_DY(name="地点Dからレストランへの輸送量");
//総費用の最小化
Objective totalcost(name="総費用",type=minimize);
totalcost=250*f_XA+200*f_XB+270*f_AC+300*f_BC+220*f_BD+190*f_CY+
170*f_DY;
//各地点での輸送量
8==f_XA+f_XB;
f_XA==f_AC;
f_XB==f_BC+f_BD;
f_AC+f_BC==f_CY;
f_BD==f_DY;
f_CY+f_DY==8;
//輸送量に関する上下限制約
0<=f_XA<=4;
0<=f_XB<=6;
0<=f_AC<=5;
0<=f_BC<=4;
0<=f_BD<=3;
0<=f_CY<=8;
0<=f_DY<=5;
//求解して値を出力する
solve();
f_XA.val.print();
f_XB.val.print();
f_AC.val.print();
f_BC.val.print();
f_BD.val.print();
f_CY.val.print();
f_DY.val.print();
totalcost.val.print();

　このモデルを実行させると，

製粉工場から地点Aへの輸送量=2
製粉工場から地点Bへの輸送量=6
地点Aから地点Cへの輸送量=2
地点Bから地点Cへの輸送量=3
地点Bから地点Dへの輸送量=3
地点Cからレストランへの輸送量=5
地点Dからレストランへの輸送量=3
総費用=5260

という表示がされ，結果を確認できます．

　ところで，このままの記述では都市の数が多い問題に応用することが困難です．そこで，都市の集合という概念を導入し，必要なデータを定数として外部から与えるようにすることで大規模な問題に対しても応用しやすいようにします．まず，この方針で定式化をしなおすと次のようになります．なお，保存則については「他の地点からの輸送量の和」と「他の地点への輸送量の和」の差のデータを外部から与える形式を取りました．ちなみに，この値が負の地点が製粉工場，正の地点がレストラン，そして0の地点が問屋ということになります．

　この定式化をし直した結果をSIMPLEで記述すると次のようになります．

//都市の集合の宣言
Set City;
Element i(set=City),j(set=City),k(set=City);

//変数の宣言
Variable f(name="輸送量",index=(i,j));

//パラメータの宣言
Parameter upper(name="輸送量の上限",index=(i,j));
Parameter cost(name="輸送費用",index=(i,j));
Parameter supply(name="supply",index=k);

//総費用の最小化
Objective total_cost(name="総費用",type=minimize);
total_cost=sum(cost[i,j]*f[i,j], (i,j));

//各地点での輸送量
sum(f[i,k],i)-sum(f[k,j],j)==supply[k];

//輸送量に関する上下限制約
0<=f[i,j]<=upper[i,j];

//求解して解を出力する
solve();
total_cost.val.print();

　なお，実行時には次の2つのcsvファイルと1つのdatファイルを与えます．

輸送量の上限,A,B,C,D,X,Y
A,0,0,5,0,0,0
B,0,0,4,3,0,0
C,0,0,0,0,0,8
D,0,0,0,0,0,5
X,4,6,0,0,0,0
Y,0,0,0,0,0,0

輸送費用,A,B,C,D,X,Y
A,0,0,270,0,0,0
B,0,0,300,220,0,0
C,0,0,0,0,0,190
D,0,0,0,0,0,170
X,250,200,0,0,0,0
Y,0,0,0,0,0, 0

supply=
[A]0 
[B]0 
[C]0 
[D]0 
[X]-8 
[Y]8;

---

 

 

上に戻る