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

Presentation on theme: "人為変数や二段階を不要とする 実数型simplex法の解き方の 提案と検証"— Presentation transcript:

1 人為変数や二段階を不要とする 実数型simplex法の解き方の 提案と検証
　　　　　　　　　　　　　　　　　　　　　　　　環境都市デザイン工学科　　　６番　鎌倉勇輝 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　１５番　中平歩 　　　　　　　　　　　　　　　　　　　　　　　　　　　指導教員　　　　　　 竹内光生　　 人為変数や2段階を不要とする実数型simplex法の解き方の提案と検証について、竹内研究室１５番中平が発表します。

2 研究の背景と目的 背景 目的 本研究では、２段階単体法の人為変数や２段階なしの１段階の解法を提案している。
２段階単体法はピボット選択が常に列・行の順であるが、提案する解法では等式・逆式は行・列の順としている。 この方法は、２変数問題については提案済みであるが、多変数問題にも適用できるかの実証がないと指摘をうけている。 目的 昨年示した２変数問題について提案simplex法の再検証を行う。 多変数問題に対応するためのプログラミングの作成をする。 ２変数問題と同様に人為変数を追加しなくても解けることを、巡回問題や人員配置問題など多変数問題を用いて検証する。 本研究の背景として、 ・２段階単体法の人為変数や2段階なしの１段階の解法を提案しています。 ・一般的に、２段階単体法はピボット選択が常に列・行の順であるが、提案する解法では等式・逆式は行・列の順としています。 ・この方法は、２変数問題については提案済みであるが、多変数問題にも適用できるかの実証がないと指摘をうけています。 そこで、本研究の目的として、 ・昨年示した、２変数問題について提案simplex法の再検証を行います。 ・多変数問題に対応するためのプログラミングの作成および、２変数問題と同様に人為変数を追加しなくても解けることを巡回問題や人員配置問題のような多変数問題を用いて検証します。

3 プログラミングの特徴 特徴 従来の２段階単体法や図解法を用いることなく、巡回問題や多変数問題が簡単な操作で解ける
Fortranプログラムを用いる 最小化問題に対応している 等式、逆式、順式の順番で解く 逆式の段階で実行可能解の有無の判定可能 図1は、提案simplex法の流れ図です。 このプログラムの特徴は、 従来の2段階単体法や図解法を用いることなく、巡回問題や多変数問題が簡単な操作で解けます。 プログラムは、fortranプログラムを用いて作成し、最小化問題に対応しています。 流れ図からわかるように等式→逆式→順式の順番で解き、逆式の段階で実行可能解の有無の判定を行います。 図１.提案simplex法の流れ図

4 提案simplex法のfortranプログラム
プログラムの詳しい概要については論文に載せています。

5 生産計画問題(3変数) 問)ある工場で４種類の原料Ａ，Ｂ，Ｃ，Ｄを用いて、３種類の製品 Ⅰ,Ⅱ,Ⅲを生産する。利益が最大となる組み合わせを求めよ。 C 100kg A 80kg B 50kg D 70kg 原料の 使用可能量 製品Ⅰ(70万円) D:3kg C:7kg A:5kg 製品Ⅲ(30万円) B:8kg C:15kg A:6kg 製品Ⅱ(120万円) B:2kg D:11kg まず、プログラムの使い方について、生産計画の３変数問題を用いて説明します。 この問題は、ある工場で４種類の原料Ａ，Ｂ，Ｃ，Ｄを用いて、３種類の製品Ⅰ,Ⅱ,Ⅲを生産するときの利益が最大となる組み合わせを問われています。 この問題は利益の最大を求める問題なので、最大化問題といえます。 下図は、生産計画問題の条件をわかりやすくするために作成しました。 原料A~Dの使用可能量は各種このようになります。 例えば、製品Ⅰを生産する際には原料をA＝5kg、C=7kg、D＝3kgだけ必要とし、その製品1単位を生産したときの利益は70万円になります。

6 定式化(数式を使って表現) 変数の決定 →各製品Ⅰ,Ⅱ,Ⅲの生産量をx1,x2,x3とおく 目的関数
　　 総利益はZ=70x1+120x2+30x3(万円) 制約条件式(原料の使用可能量を超えない) 　　 原料Ａ：5x1　　　+6x3≦80 原料Ｂ：　　　2x2+8x3≦ 　　 　　　 　　　原料Ｃ：7x1　　　+15x3≦100　　　　　　　　　　 　　　原料Ｄ：3x1+11x2　　　≦70 生産量は0以上 　　　x1≧0,x2≧0,x3≧0 次に定式化を行う前に、前のページの図を表に変えたものを表１～３に示します。 この表を用いて、定式化を行います。 定式化は、はじめに、変数の決定を行います。 ここでは、各製品Ⅰ,Ⅱ,Ⅲの生産量をx1,x2,x3と決定します。 次に、目的関数は最大の利益を求める式を表１を用いてたてます。 そして、制約条件式は各原料A~Dの利用可能量を超えない式を表２と３を用いてたてます。 最後に、生産量は０以上で正の値のみとします。

7 テキストにデータ入力 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 ファイル名：seisan_in.txt 　変数の数と ←制約条件式の数 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 ←目的関数 ←制約条件式 この問題は最大の利益を求める最大化問題です。 目的関数は、このプログラムに適した最小化問題にするためにZに-１をかけます。 入力データのファイル名は、「seisan_in.txt」とします。 入力データは初めに、変数の数“３”と制約条件式の数“４”を入力します。 次に、目的関数をZ=0とし、それぞれの変数の前につく値を順番に入力します。 同様に、制約条件式は右辺を先に入力し、左辺の変数の前につく値を入力します。 最後に、各制約条件式の順式、等式、逆式の判断を数字に置き換えて入力します。 ここでは、４つの制約条件式が順式であるので１を４つ入力します。 入力する順式、等式、逆式に対する数字は以下のように決めています。 ≦(順式)：１ ,＝(等式)： 0 , ≧(逆式)：－１ ←制約条件式の順式、 　等式、逆式の判断 ≦(順式)：１ ,＝(等式)：0 , ≧(逆式)：－１

8 プログラムでの処理 ②上書き保存 ③コンパイル ④実行 ①プログラムのファイル名を変える
入力データ作成後、次にプログラムで処理を行います。 プログラムの３行目と４行目は、入出力ファイル名を入力する欄です。 入力データのファイル名は‘seisan_in.txt‘とし、出力結果のファイル名は‘seisan_out.txt‘とします。 ファイル名を変更後は、上書き保存し、コンパイルをして完了すれば、実行を押してプログラムでの処理は終了です。 ①プログラムのファイル名を変える 入力データ：seisan_in.txt 　出力結果：seisan_out.txt

9 出力結果 データ入力した値→ 制約条件式のMUKIを示す→ ピボット選択・操作２回→ 答え． ←問題の答え
ファイル名： seisan_out.txt 3 variables constraints Inequality sign Calculation Feasible Result X( 1)= X( 2)= X( 3)= Z= データ入力した値→ 制約条件式のMUKIを示す→ ≦(順式) → １ ピボット選択・操作２回→ 答え． ＜各製品の生産量＞ 製品Ⅰ：X( 1)= ≒14.3kg 製品Ⅱ：X( 2)= 2.468≒2.5g 製品Ⅲ：X( 3)= 0kg ＜最大の利益＞ Z= ≒1296万円 次に、出力結果について説明します。 先程の作業を行うと「seisan_in.txt」と同じフォルダに「seisan_out.txt」というファイルがでます。 これが、この問題の出力結果です。 出力結果には、データ入力した値、制約条件式の向きを表す数字、ピボット選択・操作の流れ、問題の答えが示されています。 出力結果より、答えは各製品の生産量は以下のようになり、最大の利益は1296万円という結果が得られました。 ←問題の答え

10 人員配置問題(24変数) 問1)シカゴ校外の北東有料道路の料金所は、24時間に以下の 人員を必要とする。料金所の人間は４時間働き、1時間休み、又4 時間働く。何時から働いてもよい。雇う人数の最少を求めたい。 表４．各時間内での必要とする人員 変数の決定 　X1 = 真夜中から働く人の数 　X2 = 午前１時から働く人の数 　X3 = 午前2時から働く人の数 　　　　　　　・ 　X23 = 午後10時から働く人の数 　X24 = 午後11時から働く人の数 時間 必要とする人員 0時から午前6時 2 午前6時から10時 8 午前10時から正午 4 正午から午後16時 3 午後16時から18時 6 午後18時から22時 5 午後22時から24時 次に、3変数よりも変数の多い24変数を用いて、このプログラムが適応できるのかを検証してみました。 LINDO Japanで提案されている人員配置問題を用います。 シカゴ校外の北東有料道路の料金所は、24時間に以下の人員を必要とします。 料金所の人間は４時間働き、1時間休み、又4時間働き、何時から働いてもよいとします。 このときの雇う人数の最少となる組合せを問われています。 表４は、各時間内での必要とする人員を示しています。 はじめに、変数の決定として、０時～24時を１時間ごとにX1～X24として分けます。

11 問題の定式化 Minimize Z=x1+x2+x3+ ･･･ +x24
Subject to x1+x17+x18+x19+x20+x22+x23+x24≧2 ： 0～1時は2人 　 x1+x2+x18+x19+x20+x21+x23+x24≧2 ： 1～2時は2人 ･･･ 　 x16+x17+x18+x19+x21+x22+x23+x24≧3 ： 23～24時は3人 And　　　　　　x1～x24≧0 制約行 ｘ１ ｘ２ ｘ３ ｘ４ ｘ５ ｘ６ ｘ７ ｘ８ ｘ９ ｘ１０ ｘ１１ ｘ１２ ｘ１３ ｘ１４ ｘ１５ ｘ１６ ｘ１７ ｘ１８ ｘ１９ ｘ２０ ｘ２１ ｘ２２ ｘ２３ ｘ２４ -1 制限 0～1 1 ≧ 2 1～2 2～3 3～4 4～5 5～6 6～7 8 7～8 8～9 9～10 10～11 4 11～12 12～13 3 13～14 14～15 15～16 16～17 6 17～18 18～19 5 19～20 20～21 21～22 22～23 23～24 制約行 ｘ１ ｘ２ ｘ３ ｘ４ ｘ５ ｘ６ ｘ７ ｘ８ ｘ９ ｘ１０ ｘ１１ ｘ１２ ｘ１３ ｘ１４ ｘ１５ ｘ１６ ｘ１７ ｘ１８ ｘ１９ ｘ２０ ｘ２１ ｘ２２ ｘ２３ ｘ２４ -1 制限 0～1 1 ≧ 2 1～2 2～3 3～4 4～5 5～6 6～7 8 7～8 8～9 9～10 10～11 4 11～12 12～13 3 13～14 14～15 15～16 16～17 6 17～18 18～19 5 19～20 20～21 21～22 22～23 23～24 この問題は、雇う人数の最少を求める最小化問題です。 目的関数は、雇う人数の合計を求めたいので、働く人数X１～X24をすべて足します。 制約条件式は下記の表を用いて導きます。 この表は、問題の条件に沿ってExcelでシフト表を作成しました。 赤で塗られている部分に人が配置されています。 この表の見方は時間ごとに横に見て、赤に塗られているところの変数を用いて24個の制約条件式をたてます。 変数は０以上で正の値とします。 ３変数と同様に入力データを作成し、プログラム処理を行うと、出力結果が得られました。

12 プログラム結果 雇う人数の最少：Z=15.75人 雇う人数の最少： Z=16人 Excel表を用いて、 小数解を整数解に 処理すると… x1
x2 4 x3 1 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 0.5 x14 0.75 x15 1.75 x16 x17 x18 0.25 x19 x20 x21 x22 x23 x24 雇う人数の最少：Z=15.75人 Excel表を用いて、 小数解を整数解に 処理すると… x1 x2 4 x3 1 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 2 x17 x18 x19 x20 x21 x22 x23 x24 プログラム結果はこのようになりました。 人員配置問題は雇う人数を求める問題なので、解として少数値は適さないと考えます。 そこで、Excel表を用いて、小数解を整数解に直す処理を行いました。 Excel表の処理手順は、スライドに載せきれないので、ここでは省略します。 処理手順については、論文に載せています。 Excel表で処理を行った結果、以下のようになります。 各時間には、このように人員が割り当てられ、雇う人数の最少は16人となりました。 ここで説明した問題以外に、輸送問題や人員配置問題の27変数についても検証を行いました。 今回は発表時間の都合上、検証内容の説明は省略します。 雇う人数の最少： Z=16人

13 巡回問題の概要 巡回問題とは? なぜ、巡回問題を検証するのか？ 検証事例問題 概要 → 定まった順序で永久に 回り続ける問題のことである。
→ 定まった順序で永久に 　　　　回り続ける問題のことである。 なぜ、巡回問題を検証するのか？ 　　→　多変数問題にも適用できるのか　 　　　　　という指摘があったので、多変数 　　　　　問題の事例の１つとして検証。 検証事例問題 　　・H.W.Kuhnの巡回問題 　　・V.Chvatalの巡回問題 概要 ・最適解がある。（Blandの規則) ・巡回し、最適解に至らない。 　　　　　　　　　　提案simplex法 (1)最適解が得られる。 (2)巡回する。 (3)最適解・巡回現象が得られない。 　　　　　　　　　　提案simplex法の評価。 (1)→◎ (2)→○従来の解法の代替解法である (3)→×提案としてはダメである

14 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-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,1,0,0,-2,-9,1,9 0,0,1,0, ,1, ,-2 2,0,0,1,2,3,-1,-12 0,0,0

15 H.W.Kuhnの巡回問題の解析 解析結果 H.W.Kuhnの巡回問題 提案simplex法 (1)最適解が得られる。 (2)巡回する。
7 variables constraints Inequality sign ????? Not Solved ????? H.W.Kuhnの巡回問題 　　　　　　　　　提案simplex法 (1)最適解が得られる。 (2)巡回する。 (3)最適解・巡回現象が得られない。 　　　　　　　　　提案simplex法の評価。 (1)→◎ (2)→○従来の解法の代替解法である。 (3)→×提案としてはダメである

16 誤差値入力 Minimize Z=-2X4-3X5+X6+12X7 Subject to X1-2X4-9X5+X6+9X7=0
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, ,1, ,-2 2,0,0,1,2,3,-1,-12 0,0,0 7,3 0,0,0,0,-2,-3,1,12 ,1,0,0,-2,-9,1,9 0,0,1,0, ,1, ,-2 2,0,0,1,2,3,-1,-12 0,0,0

17 誤差値入力解析 最適解 x1=2.0,x2=0,x3=0 x4=2.0,x5=0,x6=2.0,x7=0 Z=2.0 解析結果
H.W.Kuhnの巡回問題 　　　　　　　　提案simplex法 (1)最適解が得られる。 (2)巡回する。 (3)最適解・巡回現象が得られない。 　　　　　　　　提案simplex法の評価。 (1)→◎最適解が得られる解法である。 (2)→○従来の解法の代替解法である。 (3)→×提案としてはダメである 7 variables constraints Inequality sign Calculation Feasible Result X( 1)= X( 2)= X( 3)= X( 4)= X( 5)= X( 6)= X( 7)= Z= 最適解 x1=2.0,x2=0,x3=0 x4=2.0,x5=0,x6=2.0,x7=0 Z=2.0

18 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

19 Chvatalの巡回問題の解析 解析結果 Chvatalの巡回問題 提案simplex法 (1)最適解が得られる。 (2)巡回する。
4 variables constraints Inequality sign 　????? Not Solved ????? Chvatalの巡回問題 　　　　　　提案simplex法 (1)最適解が得られる。 (2)巡回する。 (3)最適解・巡回現象が得られない。　　 　　　　　　提案simplex法の評価。 (1)→◎ (2)→○従来の解法の代替解法である。 (3)→×提案としてはダメである

20 誤差値入力 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 4,3 0,-10,57,9,24 ,0.5,-5.5,-2.5,9 0,0.5,-1.5,-0.5,1 1,1,0,0,0 1,1,1

21 Chvatalの巡回問題の誤差値入力解析
　　　　　　提案simplex法 (1)最適解が得られる。 (2)巡回する。 (3)最適解・巡回現象が得られない。 　　　　　　提案simplex法の評価。 (1)→◎最適解が得られる解法である。 (2)→○従来の解法の代替解法である。 (3)→×提案としてはダメである 解析結果 4 variables constraints Inequality sign Calculation Feasible Result X( 1)= X( 2)= X( 3)= X( 4)= Z= 最適解 x1=1.0, x2=0,x3=1.0,x4=0 Z=1.0

22 まとめ 提案simplex法の概要 提案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法の事例検証を行った。 今後は、その他の事例検証および事例検証以外の検証方法(プログラムの公開による検証)が必要と考えている。 非・整数・線形計画法が得意とする組み合わせ最適化問題の社会現象は多いと思われる。本報告が提案する単純な解き方が問題解決の一助となれば幸いである。

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