ＴＮＦＳ非凸型費用関数例

輸送網非凸型費用関数例

下図のようなネットワークをもつ輸送問題を考えます。

ネットワーク図

供給地②、③、④から需要地⑩、⑪、⑫、⑬、⑭に製品を輸送することを考えたとき、中継地点⑤、⑥、⑦、⑧、⑨を通る道があります。

供給地：②の供給量 12、③の供給量 15、④の供給量 9
需要地：合計需要量 20

この最小費用輸送問題は非凸型費用関数を持つ、この種の問題には今までのOut-Of-Kilter法が適用できません。そこでＴＮＦＳは「非凸型費用関数を持つ輸送問題」に適用でき、最適解を求める事のできるアルゴリズムを開発しました。
以下ＴＮＦＳを使って最適化計算を行います。

枝(1,2)の非凸型費用関数図

ネットワークの各アーク(枝)に対するデータは下の表の通りです。

From	To	Lower	固定費	Cost	Limit	Arc型
1	2	3	300	300	5	非凸型
			900	100	7
			1100	150	10
			1700	200	12
1	3	5	500	250	8	非凸型
			1550	200	11
			2150	100	15
1	4	3	200	100	5	凸型
			400	200	7
			800	300	9
2	5	4	400	300	7	非凸型
			1300	250	9
			1800	200	13
			2600	100	15
3	5	1	100	400	3	非凸型
			900	200	5
3	6	1	200	300	2	非凸型
			500	250	4
			1000	200	6
4	6	3	200	200	5	非凸型
			600	100	11
5	6	0	0	400	9	直線
5	7	2	150	300	5	非凸型
			1050	200	8
5	8	2	400	400	4	非凸型
			1200	200	8
			2000	100	13
6	8	1	200	500	3	非凸型
			1200	300	6
			2100	150	10
			2700	100	15
6	9	1	400	200	15	直線
7	10	0	0	400	3	非凸型
			1200	100	10
7	11	2	200	300	4	非凸型
			800	150	8
			1400	50	15
7	12	0	0	250	10	直線
8	12	1	300	300	4	非凸型
			1200	200	9
8	13	3	400	300	4	非凸型
			700	250	6
			1200	150	10
			1800	50	12
9	13	1	200	250	4	非凸型
			1100	200	7
			1700	100	12
9	14	0	0	500	2	非凸型
			1000	300	4
			1600	150	10
			2500	100	15
10	15	0	0	0	99999	直線
11	15	0	0	0	99999	直線
12	15	0	0	0	99999	直線
13	15	0	0	0	99999	直線
14	15	0	0	0	99999	直線
15	1	20	0	0	20	直線

　ＴＮＦＳ用インプット・データ

実際このモデルのインプット・データは‥‥\Program File\TNFS\のフォルダ内にあります。
TNFSメニューバーのファイル → 開く→ Sample12.TNFファイルを開くことによって見ることができます。

ショートカット
ツールバー:

キーボード: CTRL+O
インプット・データの与え方はＴＮＦＳ操作ガイドを参照して下さい。

インプット・データ一覧

!
! 非凸型費用関数例
!
TITLE Sample12
ARC(1,2) 3,300,300,5,900,100,7,1100,150,10,1700,200,12
ARC(1,3) 5,500,350,8,1550,200,11,2150,100,15
ARC(1,4) 3,200,100,5,400,200,7,800,300,9
ARC(2,5) 4,400,300,7,1300,250,9,1800,200,13,2600,100,15
ARC(3,5) 1,100,400,3,900,200,5
ARC(3,6) 1,200,300,2,500,250,4,1000,200,6
ARC(4,6) 3,200,200,5,600,100,11
ARC(5,6) 0,0,400,9
ARC(5,7) 2,150,300,5,1050,200,8
ARC(5,8) 2,400,400,4,1200,200,8,2000,100,13
ARC(6,8) 1,200,500,3,1200,300,6,2100,150,10,2700,100,15
ARC(6,9) 1,400,200,15
ARC(7,10) 0,0,400,3,1200,100,10
ARC(7,11) 2,200,300,4,800,150,8,1400,50,15
ARC(7,12) 0,0,250,10
ARC(8,12) 1,300,300,4,1200,200,9
ARC(8,13) 3,400,300,4,700,250,6,1200,150,10,1800,50,12
ARC(9,13) 1,200,250,4,1100,200,7,1700,100,12
ARC(9,14) 0,0,500,2,1000,300,4,1600,150,10,2500,100,15
ARC(10,15) 0,0,0,999999
ARC(11,15) 0,0,0,999999
ARC(12,15) 0,0,0,999999
ARC(13,15) 0,0,0,999999
ARC(14,15) 0,0,0,999999
ARC(15,1) 20,0,0,20
END

最適化計算

最適化計算の操作

メニューバーのＴＮＦＳ最適流量計算をクリックします。
ショートカット
ツールバー:

キーボード: Alt+T

このような入力をもとに計算された結果は下の表の通りです。

//
//*****　TNFS計算経過一覧表　*****
//
T N F S Data Input 2005/09/27 14:03:10

Data = SAMPLE12
THIS PROBLEM HAS 15 Nodes, 25 Arcs DATA ERROR = 0

計算終了、最適解が求められました。 2005/09/27 14:03:11

Branches = 186

Elapsed Time = 00:00:01

計算結果

//
//*****　ネットワーク最適流量費用一覧表　*****
//

No. From To Lower Upper Arc Cost Flow

1 1 2 3 12 1000 6

2 1 3 5 15 500 5

3 1 4 3 9 1400 9

4 2 5 4 15 1000 6

5 3 5 1 5 100 1

6 3 6 1 6 1000 4

7 4 6 3 11 1000 9

8 5 6 0 9 0 0

9 5 7 2 8 750 4

10 5 8 2 13 800 3

11 6 8 1 15 200 1

12 6 9 1 15 2600 12

13 7 10 0 10 0 0

14 7 11 2 15 200 2

15 7 12 0 10 500 2

16 8 12 1 9 300 1

17 8 13 3 12 400 3

18 9 13 1 12 2200 12

19 9 14 0 15 0 0

20 10 15 0 99999 0 0

21 11 15 0 99999 0 2

22 12 15 0 99999 0 3

23 13 15 0 99999 0 15

24 14 15 0 99999 0 0

25 15 1 20 20 0 20

輸送費用合計 = 13950.

結果考察

この非凸型費用関数輸送問題は、１５個の枝が非凸型費用関数型を持ち、非凸型のコストカーブの組合せ(Segment Combination)は7,962,624組みありますが、ＴＮＦＳはたった１８６回で、しかも計算時間が一秒以内に最適解に到達するという、無駄のない画期的な計算方法と言えるでしょう。

[ 輸送網最適流量計算メンページへ]

[ 最適化ソフトメンページへ]

No.	From	To	Lower	Upper	Arc Cost	Flow
1	1	2	3	12	1000	6
2	1	3	5	15	500	5
3	1	4	3	9	1400	9
4	2	5	4	15	1000	6
5	3	5	1	5	100	1
6	3	6	1	6	1000	4
7	4	6	3	11	1000	9
8	5	6	0	9	0	0
9	5	7	2	8	750	4
10	5	8	2	13	800	3
11	6	8	1	15	200	1
12	6	9	1	15	2600	12
13	7	10	0	10	0	0
14	7	11	2	15	200	2
15	7	12	0	10	500	2
16	8	12	1	9	300	1
17	8	13	3	12	400	3
18	9	13	1	12	2200	12
19	9	14	0	15	0	0
20	10	15	0	99999	0	0
21	11	15	0	99999	0	2
22	12	15	0	99999	0	3
23	13	15	0	99999	0	15
24	14	15	0	99999	0	0
25	15	1	20	20	0	20