人為変数や二段階を不要とする 実数型 simplex 法の解き方の 提案と検証

人為変数や二段階を不要とする 実数型 simplex 法の解き方の

提案と検証

　 　 　 　 環 境 都 市 デ ザ イ ン 工 学 科　 　 　 ６ 番　 鎌 倉 勇 輝

　 　 　 　 １ ５ 番　 中 平 歩

　 　 　 　 指 導 教 員　 　 　 　竹 内 光 生　 　

研究の背景と目的

 本研究では、２段階単体法の人為変数や２段階なしの１ 段階の解法を提案している。

 ２段階単体法はピボット選択が常に列・行の順であるが

、提案する解法では等式・逆式は行・列の順としている

 。 この方法は、２変数問題については提案済みであるが、

多変数問題にも適用できるかの実証がないと指摘をうけ ている。

背景

 昨年示した２変数問題について提案 simplex 法の再検証を

 行う。 多変数問題に対応するためのプログラミングの作成をす

 る。 ２変数問題と同様に人為変数を追加しなくても解けるこ とを、巡回問題や人員配置問題など多変数問題を用いて検 証する。

目的

プログラミングの特徴

図１ .提案 simplex 法の流れ図

•

従来の２段階単体法や図解法 を用いることなく、巡回問題 や多変数問題が簡単な操作で 解ける

• Fortran

プログラムを用いる

•

最小化問題に対応している

•

等式、逆式、順式の順番で解 く

•

逆式の段階で実行可能解の有 無の判定可能

特徴

提案 simplex 法の fortran プログラム

生産計画問題 (3 変数 )

問

)

ある工場で４種類の原料Ａ，Ｂ，Ｃ，Ｄを用いて、３種類の製品

Ⅰ, ,Ⅱ Ⅲ を生産する。利益が最大となる組み合わせを求めよ。

使用可能量原料の

A 80kg

C 100kg B

50kg

D 70kg

製品Ⅰ

(70

万円

)

D:3kg D:3kg C:7kg

C:7kg A:5kgA:5kg

製品Ⅱ

(120

万円

)

B:2kg B:2kg

D:11kg D:11kg

製品Ⅲ

(30

万円

)

B:8kg B:8kg

C:15kg

C:15kg A:6kgA:6kg

定式化 ( 数式を使って表現 )



変数の決定

　 　 　　

→各製品Ⅰ

, ,

Ⅱ Ⅲ の生産量を

x1,x2,x3

とおく



目的関数

　 　 　　

総利益は

Z=70x1+120x2+30x3(

万円

)



制約条件式

(

原料の使用可能量を超えない

) 　 　 　　

原料Ａ：

5x1 　 　 　 +6x3 80

≦

　　　　　　　　

原料Ｂ：

　 　 　 2x2+8x3 50

≦

　 　 　　 　 　

　 　 　

原料Ｃ：

7x1 　 　 　 +15x3 100

≦

　 　 　 　 　 　 　

原料Ｄ：

3x1+11x2 　 　 　

≦

70



生産量は

0

以上

　 　 　 x1 0,x2

≧ ≧

0,x3

≧

0

テキストにデータ入力

Max Z= 70x1+120x2+30x3

　 　 　

最小化問題にする！

Mini Z= -70x1-120x2-30x3

Subject to 5x1+6x3

≦

80

　 　 　 　 　　　　　　　　 2x2+8x3

≦

50 　 　 　 　 　　　　　　　　 7x1+15x3

≦

100 　 　 　 　 　　　　　　　　 3x1+11x2

≦

70 And x1

≧

0,x2

≧

0,x3

≧

0

3,4

0,-70,-120,-30 80,5,0,6

50,0,2,8 100,7,0,15 70,3,11,0 1,1,1,1

≦( 順式

)

：１　

,

＝

(

等式

)

：

0 , (

≧ 逆 式

)

：－１

変数の数と

← 制約条件式の数

← 目的関数

← 制約条件式

← 制約条件式の順式

、等式、逆式の判断

ファイル名： seisan_in.txt

プログラムでの処理

① プログラムのファイル名を変える 入力データ：

seisan_in.txt 　

出力結果：

seisan_out.txt

② 上書き保

存 ③ コンパイ

ル ④ 実行

出力結果

答え．

＜各製品の生産量＞

製品Ⅰ：

X( 1)= 14.286 14.3kg ≒

製品Ⅱ：

X( 2)= 2.468 2.5g ≒

製品Ⅲ：

X( 3)= 0kg

＜最大の利益＞

Z= 1296.104 1296 ≒

万円

ファイル名：

　

seisan_out.txt

3 variables 4 constraints 0.000 -70.000 -120.000 -30.000 80.000 5.000 0.000 6.000 50.000 0.000 2.000 8.000 100.000 7.000 0.000 15.000 70.000 3.000 11.000 0.000 Inequality sign

1 1 1 1

0.000 -70.000 -120.000 -30.000 0.000 0.000 0.000 0.000 80.000 5.000 0.000 6.000 1.000 0.000 0.000 0.000 50.000 0.000 2.000 8.000 0.000 1.000 0.000 0.000 100.000 7.000 0.000 15.000 0.000 0.000 1.000 0.000 70.000 3.000 11.000 0.000 0.000 0.000 0.000 1.000 763.636 -37.273 0.000 -30.000 0.000 0.000 0.000 10.909 80.000 5.000 0.000 6.000 1.000 0.000 0.000 0.000 37.273 -0.545 0.000 8.000 0.000 1.000 0.000 -0.182 100.000 7.000 0.000 15.000 0.000 0.000 1.000 0.000 6.364 0.273 1.000 0.000 0.000 0.000 0.000 0.091 1296.104 0.000 0.000 49.870 0.000 0.000 5.325 10.909 8.571 0.000 0.000 -4.714 1.000 0.000 -0.714 0.000 45.065 0.000 0.000 9.169 0.000 1.000 0.078 -0.182 14.286 1.000 0.000 2.143 0.000 0.000 0.143 0.000 2.468 0.000 1.000 -0.584 0.000 0.000 -0.039 0.091 Calculation Feasible Result

X( 1)= 14.286 X( 2)= 2.468 X( 3)= 0.000 Z= 1296.104

← 問題の答 え

ピボット選択・操作２ 回

→

データ入力した値 制約条件式の → MUKI を示す

→ _≦(

_順式

_{) →}

１

人員配置問題 (24 変数 )

問 1) シカゴ校外の北東有料道路の料金所は、 24 時間に以下の 人員を必要とする。料金所の人間は４時間働き、 1 時間休み、

又 4 時間働く。何時から働いてもよい。雇う人数の最少を求め たい。

時間 必要とする人 員

0

時から午前

6

時

2

午前

6

時から

10

時

8

午前

10

時から正 午

4

正午から午後

16

時

3

午後

16

時から

18

時

6

午後

18

時から

22

時

5

午後

22

時から

24

時

3

 変数の決定

　 X

_{1 = 真夜中から働く人の数}

　 X

_{2 =} 午前１時から働く人の数

　 X

_{3 = 午前 2 時から働く人の数}

　 　 　 　 ・

　 　 　 　 ・ 　 　 　 　 ・

　 X

^{23 = 午後 10 時から働く人の数}

　 X

_{24 = 午後 11 時から働く人の数}

表４．各時間内での必要とする人 員

問題の定式化

制約行 ｘ１ ｘ２ ｘ３ ｘ４ ｘ５ ｘ６ ｘ７ ｘ８ ｘ９ ｘ１０ ｘ１ １ ｘ１

２ ｘ１ ３ ｘ１

４ ｘ１ ５ ｘ１

６ ｘ１ ７ ｘ１

８ ｘ１ ９ ｘ２

０ ｘ２ １ ｘ２

２ ｘ２ ３ ｘ２

４ -1 制限

0～1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 ≧ 2

1～2 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 ≧ 2

2～3 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 ≧ 2

3～4 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 ≧ 2

4～5 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 ≧ 2

5～6 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 ≧ 2

6～7 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 ≧ 8

7～8 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 ≧ 8

8～9 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 8

9～10 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 8

10～11 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 4

11～12 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 4

12～13 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 ≧ 3

13～14 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 ≧ 3

14～15 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 ≧ 3

15～16 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 ≧ 3

16～17 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 ≧ 6

17～18 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 ≧ 6

18～19 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 ≧ 5

19～20 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 ≧ 5

20～21 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 ≧ 5

21～22 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 ≧ 5

22～23 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 ≧ 3 23～24 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 ≧ 3

Minimize 　 　 　　 Z=x

₁

+x

₂

+x

₃

+ ･･･ 　 +x

₂₄

Subject to x

₁

+x

₁₇

+x

₁₈

+x

₁₉

+x

₂₀

+x

₂₂

+x

₂₃

+x

₂₄

≧ 2

：

　 0

～

1

時は

2

人

　　　　　　　 　 　　　　　 x

₁

+x

₂

+x

₁₈

+x

₁₉

+x

₂₀

+x

₂₁

+x

₂₃

+x

₂₄

≧ 2

：

　 1

～

2

時は

2

人

　　　　　　　 ･･･ 　　　　　　 　 　　 x

₁₆

+x

₁₇

+x

₁₈

+x

₁₉

+x

₂₁

+x

₂₂

+x

₂₃

+x

₂₄

≧ 3

：

　 23

～

24

時は

3

人

And 　 　 　 　 x

₁ ～

x

₂₄

≧ 0

制約行 ｘ１ ｘ２ ｘ３ ｘ４ ｘ５ ｘ６ ｘ７ ｘ８ ｘ９ ｘ１０ ｘ１ １ ｘ１ ２ ｘ１ ３ ｘ１ ４ ｘ１ ５ ｘ１ ６ ｘ１ ７ ｘ１ ８ ｘ１ ９ ｘ２ ０ ｘ２ １ ｘ２ ２ ｘ２ ３ ｘ２ ４ -1 制限 0～1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 ≧ 2 1～2 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 ≧ 2 2～3 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 ≧ 2 3～4 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 ≧ 2 4～5 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 ≧ 2 5～6 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 ≧ 2 6～7 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 ≧ 8 7～8 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 ≧ 8 8～9 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 8

9～10 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 8

10～11 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 4

11～12 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 　 ≧ 4

12～13 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 　 ≧ 3

13～14 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 　 ≧ 3

14～15 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 　 ≧ 3

15～16 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 　 ≧ 3

16～17 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 　 ≧ 6

17～18 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 　 ≧ 6

18～19 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 　 ≧ 5

19～20 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 　 ≧ 5

20～21 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 　 ≧ 5

21～22 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 　 ≧ 5

22～23 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 　 ≧ 3

23～24 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 1 1 1 1 　 1 1 1 1 ≧ 3

プログラム結果

雇う人数の最少： Z=15.75 人

雇う人数の最少 ： 　 Z=16 人

x

₁

0 x

₂

4 x

₃

1 x

₄

1 x

₅

1 x

₆

1

x

₇

1 x

₈

0 x

₉

0 x

₁₀

0 x

₁₁

0 x

₁₂

0

x

₁₃

0.5 x

₁₄

0.75 x

₁₅

1.75 x

₁₆

1.75 x

₁₇

1.75 x

₁₈

0.25

x

₁₉

0 x

₂₀

0 x

₂₁

0 x

₂₂

0 x

₂₃

0 x

₂₄

0

x

₁

0 x

₂

4 x

₃

1 x

₄

1 x

₅

1 x

₆

1

x

₇

1 x

₈

0 x

₉

0 x

₁₀

0 x

₁₁

0 x

₁₂

0

x

₁₃

0 x

₁₄

1 x

₁₅

1 x

₁₆

2 x

₁₇

2 x

₁₈

1

x

₁₉

0 x

₂₀

0 x

₂₁

0 x

₂₂

0 x

₂₃

0 x

₂₄

0

Excel

表を用いて、

小数解を整数解に 処理すると

…

巡回問題の概要

概要

・最適解がある。（Bland の規則)

・巡回し、最適解に至らない。

　 　 　 提案 simplex法 (1) 最適解が得られる。

(2) 巡回する。

(3) 最適解・巡回現象が得られない。

　 　 　 提案 simplex法 の評価。

(1)→◎

(2)→○ 従来の解法の代替解法である

(3)→× 提案としてはダメである



巡回問題とは

?

　　　　　 　　

→ 定まった順序で永久に

　 　 　 　

回り続ける問題のことであ

る。



なぜ、巡回問題を検証するのか

　 　

？→ 多変数問題にも適用できる

　

のか

　

　 　 　 　 　

という指摘があったので

、多変数

　 　 　 　 　

問題の事例の１つとして

検証。



検証事例問題

　 　

・

H.W.Kuhn

の巡回問題

　 　

・

V.Chvatal

の巡回問題

H.W.kuhn の巡回問題 (7 変数， 3 つの等式 )

Minimize 　 　 z=-2X4-3X5+X6+12X7 Subject to 　 X1-2X4-9X5+X6+9X7=0

　 　 　 　 X2+(1.0/3.0)X4+X5-(1.0/3.0)X6-2 X7=0 　 　 　 　 X3+2X4+3X5-X6-12X7=2

And (X1, X2, X3, X4, X5, X6, X7) ≧ 0 　

7,3

0,0,0,0,-2,-3,1,12 0,1,0,0,-2,-9,1,9

0,0,1,0,0.333333,1,-0.333333,-2 2,0,0,1,2,3,-1,-12

0,0,0

プログラム入力データ

H.W.Kuhn の巡回問題の解析

_解析結果

H.W.Kuhn の巡回問題

　 　 　 提案 simplex法 (1)最適解が得られる。

(2)巡回する。

(3)最適解・巡回現象が得られない。

　 　 　 提案 simplex法の 評価。

(1)→◎

(2)→○ 従来の解法の代替解法である。

(3)→×提案としてはダメである

7 variables 3 constraints

0.000 0.000 0.000 0.000 -2.000 -3.000 1.000 12.000 0.000 1.000 0.000 0.000 -2.000 -9.000 1.000 9.000 0.000 0.000 1.000 0.000 0.333 1.000 -0.333 -2.000 2.000 0.000 0.000 1.000 2.000 3.000 -1.000 -12.000 Inequality sign

0 0 0

0.000 0.000 0.000 0.000 -2.000 -3.000 1.000 12.000 0.000 1.000 0.000 0.000 -2.000 -9.000 1.000 9.000 0.000 0.000 1.000 0.000 0.333 1.000 -0.333 -2.000 2.000 0.000 0.000 1.000 2.000 3.000 -1.000 -12.000 0.000 0.000 3.000 0.000 -1.000 0.000 0.000 6.000 0.000 1.000 9.000 0.000 1.000 0.000 -2.000 -9.000 0.000 0.000 1.000 0.000 0.333 1.000 -0.333 -2.000 2.000 0.000 -3.000 1.000 1.000 0.000 -0.000 -6.000 0.000 1.000 12.000 0.000 0.000 0.000 -2.000 -3.000 0.000 1.000 9.000 0.000 1.000 0.000 -2.000 -9.000 0.000 -0.333 -2.000 0.000 0.000 1.000 0.333 1.000 2.000 -1.000 -12.000 1.000 0.000 0.000 2.000 3.000 0.000 -0.000 6.000 0.000 0.000 3.000 -1.000 0.000 0.000 -2.000 -9.000 0.000 1.000 9.000 1.000 0.000 0.000 -0.333 -2.000 0.000 0.000 1.000 0.333 1.000 2.000 0.000 -6.000 1.000 0.000 -3.000 1.000 0.000 0.000 -2.000 -3.000 0.000 1.000 12.000 0.000 0.000 0.000 -2.000 -9.000 0.000 1.000 9.000 1.000 0.000 0.000 0.333 1.000 0.000 -0.333 -2.000 0.000 1.000 2.000 2.000 3.000 1.000 -1.000 -12.000 0.000 0.000 0.000 -1.000 0.000 0.000 -0.000 6.000 0.000 3.000 0.000 1.000 0.000 0.000 -2.000 -9.000 1.000 9.000 0.000 0.333 1.000 0.000 -0.333 -2.000 0.000 1.000 2.000 1.000 0.000 1.000 0.000 -6.000 0.000 -3.000 0.000 0.000 0.000 0.000 -2.000 -3.000 1.000 12.000 0.000 1.000 0.000 0.000 -2.000 -9.000 1.000 9.000 0.000 0.000 1.000 0.000 0.333 1.000 -0.333 -2.000 2.000 0.000 0.000 1.000 2.000 3.000 -1.000 -12.000 ????? Not Solved ?????

Minimize 　 　　 Z=-2X4-3X5+X6+12X7 Subject to 　 X1-2X4-9X5+X6+9X7=0

X2+(1.0/3.0)X4+X5-(1.0/3.0)X6-2X7=0 X3+2X4+3X5-X6-12X7=2

And (X1, X2, X3, X4, X5, X6, X7) 0 ≧

7,3

0,0,0,0,-2,-3,1,12

0.00001,1,0,0,-2,-9,1,9

0,0,1,0,0.333333,1,-0.333333,-2 2,0,0,1,2,3,-1,-12

0,0,0

プログラム入力デー タ

誤差値入力

7,3

0,0,0,0,-2,-3,1,12 0,1,0,0,-2,-9,1,9

0,0,1,0,0.333333,1,-0.333333,-2 2,0,0,1,2,3,-1,-12

0,0,0

プログラム入力デー タ

7 variables 3 constraints

0.000 0.000 0.000 0.000 -2.000 -3.000 1.000 12.000 0.000 1.000 0.000 0.000 -2.000 -9.000 1.000 9.000 0.000 0.000 1.000 0.000 0.333 1.000 -0.333 -2.000 2.000 0.000 0.000 1.000 2.000 3.000 -1.000 -12.000 Inequality sign

0 0 0

0.000 0.000 0.000 0.000 -2.000 -3.000 1.000 12.000 0.000 1.000 0.000 0.000 -2.000 -9.000 1.000 9.000 0.000 0.000 1.000 0.000 0.333 1.000 -0.333 -2.000 2.000 0.000 0.000 1.000 2.000 3.000 -1.000 -12.000 0.000 0.000 3.000 0.000 -1.000 0.000 0.000 6.000 0.000 1.000 9.000 0.000 1.000 0.000 -2.000 -9.000 0.000 0.000 1.000 0.000 0.333 1.000 -0.333 -2.000 2.000 0.000 -3.000 1.000 1.000 0.000 -0.000 -6.000 0.000 0.000 6.000 0.000 0.000 3.000 -1.000 -0.000 0.000 1.000 6.000 0.000 0.000 -3.000 -1.000 -3.000 0.000 0.000 3.000 0.000 1.000 3.000 -1.000 -6.000 2.000 0.000 -6.000 1.000 0.000 -3.000 1.000 0.000 2.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 2.000 1.000 0.000 1.000 0.000 -6.000 0.000 -3.000 2.000 0.000 -3.000 1.000 1.000 -0.000 0.000 -6.000 2.000 0.000 -6.000 1.000 0.000 -3.000 1.000 0.000 Calculation Feasible Result

X( 1)= 2.000 X( 2)= 0.000 X( 3)= 0.000 X( 4)= 2.000 X( 5)= 0.000 X( 6)= 2.000 X( 7)= 0.000 Z= 2.000

誤差値入力解析

解析結果

H.W.Kuhnの巡回問題

　 　 　 　 提案simplex法 (1)最適解が得られる。

(2)巡回する。

(3)最適解・巡回現象が得られない。

　 　 　 　 提案simplex法の評価

。

(1)→◎最適解が得られる解法である。

(2)→○従来の解法の代替解法である。

(3)→×提案としてはダメである

最適解

x1=2.0,x2=0,x3=0

x4=2.0,x5=0,x6=2.0,x7=0

Z=2.0

Chvatal の巡回問題の例 (4 変数， 3 つの順式 )

Minimize 　 　　 Z=-10x1+57x2+9x3+24x4 Subject to 　 -0.5x1-5.5x2-2.5x3-9x4 ≦ 0 　 　 　 　 0.5x1-1.5x2-0.5x3+x4

≦ 0

　 　 　 　 x1 ≦ 1 And (x1,x2,x3,x4) ≧ 0

4,3

0,-10,57,9,24 0,0.5,-5.5,-2.5,9 0,0.5,-1.5,-0.5,1 1,1,0,0,0

1,1,1

プログラム入力デー タ

Chvatal の巡回問題の解析

^解析結果

Chvatal の巡回問題

　 　 　 提案simplex 法 (1) 最適解が得られる。

(2) 巡回する。

(3) 最適解・巡回現象が得られない。

　 　

　 　 　 提案simplex 法の評価。

(1)→◎

(2)→○ 従来の解法の代替解法である。

(3)→× 提案としてはダメである

4 variables 3 constraints

0.000 -10.000 57.000 9.000 24.000 0.000 0.500 -5.500 -2.500 9.000 0.000 0.500 -1.500 -0.500 1.000 1.000 1.000 0.000 0.000 0.000 Inequality sign

1 1 1

0.000 -10.000 57.000 9.000 24.000 0.000 0.000 0.000 0.000 0.500 -5.500 -2.500 9.000 1.000 0.000 0.000 0.000 0.500 -1.500 -0.500 1.000 0.000 1.000 0.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 -53.000 -41.000 204.000 20.000 0.000 0.000 0.000 1.000 -11.000 -5.000 18.000 2.000 0.000 0.000 0.000 0.000 4.000 2.000 -8.000 -1.000 1.000 0.000 1.000 0.000 11.000 5.000 -18.000 -2.000 0.000 1.000 0.000 0.000 0.000 -14.500 98.000 6.750 13.250 0.000 0.000 1.000 0.000 0.500 -4.000 -0.750 2.750 0.000 0.000 0.000 1.000 0.500 -2.000 -0.250 0.250 0.000 1.000 0.000 0.000 -0.500 4.000 0.750 -2.750 1.000 0.000 29.000 0.000 0.000 -18.000 -15.000 93.000 0.000 0.000 2.000 0.000 1.000 -8.000 -1.500 5.500 0.000 0.000 -1.000 1.000 0.000 2.000 0.500 -2.500 0.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 20.000 9.000 0.000 0.000 -10.500 70.500 0.000 0.000 -2.000 4.000 1.000 0.000 0.500 -4.500 0.000 0.000 -0.500 0.500 0.000 1.000 0.250 -1.250 0.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 -22.000 93.000 21.000 0.000 0.000 -24.000 0.000 0.000 -4.000 8.000 2.000 0.000 1.000 -9.000 0.000 0.000 0.500 -1.500 -0.500 1.000 0.000 1.000 0.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 -10.000 57.000 9.000 24.000 0.000 0.000 0.000 0.000 0.500 -5.500 -2.500 9.000 1.000 0.000 0.000 0.000 0.500 -1.500 -0.500 1.000 0.000 1.000 0.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 1.000 　 　 ????? Not Solved ?????

誤差値入力

Minimize 　 　　 Z=-10x1+57x2+9x3+24x4 Subject to 　 -0.5x1-5.5x2-2.5x3-9x4 0 ≦ 0.5x1-1.5x2-0.5x3+x4 0 ≦ x1 1 ≦

And (x1,x2,x3,x4) 0 ≧

4,3

0,-10,57,9,24

0.00001,0.5,-5.5,-2.5,9 0,0.5,-1.5,-0.5,1

1,1,0,0,0 1,1,1

プログラム入力デー

4,3

タ

0,-10,57,9,24 0,0.5,-5.5,-2.5,9 0,0.5,-1.5,-0.5,1 1,1,0,0,0

1,1,1

プログラム入力デー タ

4 variables 3 constraints

0.000 -10.000 57.000 9.000 24.000 0.000 0.500 -5.500 -2.500 9.000 0.000 0.500 -1.500 -0.500 1.000 1.000 1.000 0.000 0.000 0.000 Inequality sign

1 1 1

0.000 -10.000 57.000 9.000 24.000 0.000 0.000 0.000 0.000 0.500 -5.500 -2.500 9.000 1.000 0.000 0.000 0.000 0.500 -1.500 -0.500 1.000 0.000 1.000 0.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 27.000 -1.000 44.000 0.000 20.000 0.000 0.000 0.000 -4.000 -2.000 8.000 1.000 -1.000 0.000 0.000 1.000 -3.000 -1.000 2.000 0.000 2.000 0.000 1.000 0.000 3.000 1.000 -2.000 0.000 -2.000 1.000 1.000 0.000 30.000 0.000 42.000 0.000 18.000 1.000 2.000 0.000 2.000 0.000 4.000 1.000 -5.000 2.000 1.000 1.000 0.000 0.000 0.000 0.000 0.000 1.000 1.000 0.000 3.000 1.000 -2.000 0.000 -2.000 1.000 Calculation Feasible Result

X( 1)= 1.000 X( 2)= 0.000 X( 3)= 1.000 X( 4)= 0.000 Z= 1.000

Chvatal の巡回問題の誤差値入力解析

解析結果 Chvatal の巡回問題

　 　 　 提案simplex法 (1)最適解が得られる。

(2)巡回する。

(3)最適解・巡回現象が得られない。

　 　 　 提案simplex法の評価。

(1)→◎最適解が得られる解法である

。

(2)→○従来の解法の代替解法である。

(3)→×提案としてはダメである

最適解

x1=1.0, x2=0,x3=1.0,x4=0

Z=1.0



提案

simplex

法の概要

まとめ

• 人為変数や二段階不要

• 等式、逆式、順式の順に解く

• 等式、逆式は、行・列の順でピボット選択するべき

• 逆式の段階で実行可能解の有無の判定可能



提案

simplex

法の検証

(

任意変数問題

)

• FORTRAN プログラムの作成　 OK

• 生産計画問題 (3 変数 ) 　 OK

• 輸送問題① ( 起点 2 、終点 3 、計6 変数問題 ) 　 OK

• 輸送問題② ( 起点 3 、終点 5 、計15 変数問題 ) 　 OK

• 人員配置問題 ( 全員 8h 常勤、0 ～23 時各勤務開始 24 変数問題 ) 　 OK

• 人員配置問題 (8h 常勤3 人および 4h 勤務アルバイト雇用 27 変数問題 ) 　 OK

• H.W.Kuhn （ハロルド・クーン）の巡回問題　 OK

• Chvatal( フバータル )の巡回問題　 OK

• 提案 simplex 法で、上記の 2 変数～ 27 変数問題の最適解が得られた。



本報告は、多変数問題に拡張し、提案

simplex

法の事例検証を行 った。• 今後は、その他の事例検証および事例検証以外の検証方法 ( プログラムの公開

による検証 ) が必要と考えている。

• 非・整数・線形計画法が得意とする組み合わせ最適化問題の社会現象は多いと 思われる。本報告が提案する単純な解き方が問題解決の一助となれば幸いであ る。

ご清聴ありがとうございました

。