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

2.2 輸送問題

　輸送問題は複数の供給地から複数の需要地への物の流れ方を決める問題ということができます．供給地と需要地をノード，物の流れる経路をアークとすれば，輸送問題はネットワークによって表現できる問題の一種と捉えることができます．輸送問題に対する定式化の方法は他のネットワークによって表現できる問題にも応用できます．

例題

　ある配送業者は二つの工場1，2から三つの店舗a，b，cへの製品の輸送を請け負っているとします．各工場，店舗について，それぞれ供給可能量と需要量が決められており，それらを満たしつつ，最もコストがかからない製品の運び方をどのように決定すればよいでしょうか．各工場の供給可能量，各店舗の需要量，単位量あたりの輸送コストは以下の通りです．

工場 供給可能量 店舗 需要量
1 250 a 200
2 450 b 200
    c 200

　

単位量あたりの輸送コスト
  a b c
1 3.4 2.2 2.9
2 3.4 2.4 2.5

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

　まず，変数として各工場から各店舗への輸送量を以下の図のように設定します．

　次に，目的関数は，工場から店舗への各経路について「単位量あたりの輸送コスト」と「輸送量」の積の総和として表現することができます．

　最後に制約条件です．輸送量は負にはなり得ないので，各変数に対して非負制約が必要です．さらに，各工場について工場からの輸送量の和が供給可能量以下である，各店舗について店舗への輸送量の和が需要量と等しい，という制約が加わります．

　

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

変数
$x_{1a}$ 工場1から店舗aへの輸送量
$x_{1b}$ 工場1から店舗bへの輸送量
$x_{1c}$ 工場1から店舗cへの輸送量
$x_{2a}$ 工場2から店舗aへの輸送量
$x_{2b}$ 工場2から店舗bへの輸送量
$x_{2c}$ 工場2から店舗cへの輸送量
　
目的関数（最小化）
$3.4x_{1a} + 2.2x_{1b} + 2.9x_{1c} + 3.4x_{2a} + 2.4x_{2b} + 2.5x_{2c}$ 総コスト
　
非負制約
$x_{1a} \ge 0$ 　
$x_{1b} \ge 0$ 　
$x_{1c} \ge 0$ 　
$x_{2a} \ge 0$ 　
$x_{2b} \ge 0$ 　
$x_{2c} \ge 0$ 　
　
工場の生産量の制約
$x_{1a} + x_{1b} + x_{1c} \le 250$ 工場1について
$x_{2a} + x_{2b} + x_{2c} \le 450$ 工場2について
　
店舗の需要量の制約
$x_{1a} + x_{2a} = 200$ 店舗aについて
$x_{1b} + x_{2b} = 200$ 店舗bについて
$x_{1c} + x_{2c} = 200$ 店舗cについて

　ネットワークで表現できる問題の多くは，上で見てきたように各アークに対して変数を定義し，各ノードについて制約をたてることによって定式化されます．

　

　定式化した結果をC++SIMPLEで記述すると以下のようになります．

// 変数
Variable x1a(name = "工場 1 から店舗 a への輸送量");
Variable x1b(name = "工場 1 から店舗 b への輸送量");
Variable x1c(name = "工場 1 から店舗 c への輸送量");
Variable x2a(name = "工場 2 から店舗 a への輸送量");
Variable x2b(name = "工場 2 から店舗 b への輸送量");
Variable x2c(name = "工場 2 から店舗 c への輸送量");

// 非負制約
x1a >= 0;
x1b >= 0;
x1c >= 0;
x2a >= 0;
x2b >= 0;
x2c >= 0;

// 工場の生産量の制約
x1a + x1b + x1c <= 250;
x2a + x2b + x2c <= 450;

// 店舗の需要量の制約
x1a + x2a == 200;
x1b + x2b == 200;
x1c + x2c == 200;

// 目的関数
Objective z(name = "総コスト", type = minimize);
z = 3.4 * x1a + 2.2 * x1b + 2.9 * x1c + 3.4 * x2a + 2.4 * x2b + 2.5 * x2c;

// 求解
solve();

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

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

集合
$Cannery = \{ 1,2\}$ 工場
$Warehouse = \{ a,b,c\}$ 店舗
　
定数
$upper_i,i \in Cannery$ 工場$i$の供給可能量
$demand_j,j \in Warehouse$ 店舗$j$の需要量
$c_{ij}, i \in Cannery,j \in Warehouse$ 工場$i$から店舗$j$への単位量あたりの輸送コスト
　
変数
$x_{ij},i \in Cannery,j \in Warehouse$ 工場$i$から店舗$j$への輸送量
　
目的関数（最小化）
$\displaystyle \sum_{i \in Cannery} \sum_{j \in Warehouse} c_{ij} x_{ij}$ 総コスト
　
制約
$x_{ij} \ge 0, \forall i \in Cannery, \forall j \in Warehouse$ 非負制約
$\displaystyle \sum_{j \in Warehouse} x_{ij} \le upper_i, \forall i \in Cannery$ 工場の生産量の制約
$\displaystyle \sum_{i \in Cannery} x_{ij} = demand_j, \forall j \in Warehouse$ 店舗の需要量の制約

　次に，入力データとモデルを分離したC++SIMPLEモデルを示します．

// 集合と添字
Set Cannery(name = "工場");
Element i(set = Cannery);
Set Warehouse(name = "店舗");
Element j(set = Warehouse);

// パラメータ
Parameter upper(name = "供給可能量", index = i);
Parameter demand(name = "需要量", index = j);
Parameter cost(name = "輸送コスト", index = (i, j));

// 変数
Variable x(name = "輸送量", index = (i, j));

// 目的関数
Objective z(name = "総コスト", type = minimize);
z = sum(cost[i, j] * x[i, j], (i, j));

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

// 工場の生産量の制約
sum(x[i, j], j) <= upper[i];

// 店舗の需要量の制約
sum(x[i, j], i) == demand[j];

// 求解
solve();

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

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

供給可能量 =
[1] 250
[2] 450
;

需要量 =
[a] 200
[b] 200
[c] 200
;

輸送コスト =
[1, a] 3.4
[1, b] 2.2
[1, c] 2.9
[2, a] 3.4
[2, b] 2.4
[2, c] 2.5
;

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

総コスト=1620
輸送量[1,"a"]=29.566
輸送量[1,"b"]=200
輸送量[1,"c"]=1.10617e-06
輸送量[2,"a"]=170.434
輸送量[2,"b"]=2.21238e-06
輸送量[2,"c"]=200
2.1 配合問題
2.3 多期間計画問題

 

 

上に戻る