™…

Size: px

Start display at page:

Download "™…"

せとかあくや
7 years ago
Views:

1 Man is a Thinking Reed. No.16 March, 29 K A N S A I UNIVERSITY NEWSLETTER

2 Tops Interview KANSAI UNIVERSITY NEWS LETTER No.16 March,29 March,29 No.16 KANSAI UNIVERSITY NEWS LETTER 2

3 KANSAI UNIVERSITY NEWS LETTER No.16 March,29 3 March,29 No.16 KANSAI UNIVERSITY NEWS LETTER 4 Tops Interview JR a

4 LEADER S NOW! ( 62) 3 2 O KANSAI UNIVERSITY NEWS LETTER No.16 March,29 March,29 No.16 KANSAI UNIVERSITY NEWS LETTER 6

5 Research Front Line POS 2 SPA NYK 2 KANSAI UNIVERSITY NEWS LETTER No.16 March,29 March,29 No.16 KANSAI UNIVERSITY NEWS LETTER 8

6 最適化問題の具体例輸送問題工場から納品先に商品を輸送する工場の輸送量生産量以下納品先への輸送量注文量輸送にはコストが発生するコストを最小にするにはどのように輸送すればよい研究最前線工場 1 納品先 1 生産量 :15(t) 注文量 :1(t) 工場 2 実社会に通じる最適化法の研究納品先 2 生産量 :2(t) 最適化法を用いた注文量 :2(t) 工場 3 納品先 3 生産量 :25(t) 問題解決策の追求注文量 :18(t) 輸送コスト万円 /t 工場 1 工場 2 工場 3 数学とコンピュータの力で最適な状態を求める納品先 1 納品先 2 納品先環境都市工学部工場をときその制約を満たしながら目的関数の値を最小あるいは納品先を変数最大にするというものであり数学とコンピュータの力により工場最適化法の適用プロセスる檀助教に話を聞いた納品先 1.モデル開発考える対象を定式化するわかりやすく言うと数学とコンピュータを利用して制約を考慮しながら最もよい状態を探し出すという学問分野です例えば工場が原料を調達して配送するまでの物流合理化問題を考えると価格も違い何か所もある原料の購入元各工場の作る製品の種別や出荷可能量などが制約これらを組み合わせ最もよい解この場合はどこで原料を購入しどの工場でどれだけの量を生産すれば最もコストが安くなるかあるいは利益が多くなるかという最適解を求めます現実問題への適用のプロセスは最適化法の適用プロセスには ①問題のモデル化 ②求解 ③ 解の検証という 3 つの段階がありますまず①では実際の問題を抽象的に捉え数学的に表現します数学とコンピュータは抽象的にものを扱うことができるため汎用性があります上の例でいう工場の生産量など決定すべき量は変数 X などとしますその際 X は制約と目的を数学的に表現できるものであれば何でもよいのです制約として等しくなければならない場合は多い少ないはで表します次に② では定式化した問題を解きますソルバというソフトウエアで解くのが一般的であり問題に適したアルゴリズム解法を選択し解を求めますまたは新しくアルゴリズムを作って解を求める場合もあります最後に③では ②の解が正しいかどうかを検証します ①の時点での間違いや入力データのケアレスミスもあり得ます実際の状況に合致しているかを調べ間違っていれば①②に戻ってモデルを修正し解を求めますそれを繰り返すことで満足のいく解を求めます仕事と同じで最終的には現場の人間の判断が重要です多様なジャンルで応用されている最適化法輸送問題のほかどのような場面で応用されているのですか 9 KANSAI UNIVERSITY NEWS LETTER No.16 March,29 set I; # 工場の集合 set J; # 納品先の集合 var x{i, J} >= ; param s{i}; param d{j}; param c{i, J}; set I : = 1 2 3; set J : = 1 2 3; # 輸送量以上 # 各工場の生産量 # 納品先の注文量 # 輸送コスト param s : = [1] 15 [2] 2 [3] 25; param d : = [1] 1 [2] 2 [3] 18; param c : = [1, 1] 1 [1, 2] 8 [1, 3] 8 [2, 1] 2 [2, 2] 1 [2, 3] 9 [3, 1] 15 [3, 2] 12 [3, 3] 18 ; minimize f: sum {i in I, j in J} (c[i, j] * x[i, j]); # 輸送コストの和を最小に s.t. C1{i in I}: sum {j in J} x[i, j] <= s[i]; # 制約１: 各工場からの輸送量が生産量を超えない s.t. C2{j in J}: sum {i in I} x[i, j] == d[j]; # 制約２: 各納品先には注文量を輸送するソルバに入力で表すソルバの出力最適解に関する情報が記載されている工場から納品先への輸送量量を表すので０以上 Problem: Rows: Columns: Non-zeros: Status: Objective: パラメータデータ解を求めるでは最適化法は社会のどのような場面に応用さどのような学問なのですかデータ各工場の生産量各納品先の注文量工場納品先間の輸送コスト輸送問題の定式化最適化とは数学的に表現される目的関数と制約条件がある問題を定式化し解決する問題をソルバがわかるように記述したもの檀寛成助教れているのだろうか最適化法の実問題への適用を研究してい Research Front Line 3.解の検証求めた解を検証する 2.求解モデルを解き解を求める工場の生産量の注文量から納品先への輸送コスト定式化した最適化問題目的関数最小輸送コストの合計を最小にするこのプロセスを繰り返し適用することで解の精度を高める工場制約条件 1 面白いものでは最長片道切符があります JR の片道切符で乗れる最も距離の長い路線ルートを最適化により導き出し募金を集めて実際に最長片道切符を購入し電車に乗って話題となりましたまた J リーグの対戦順を決める際なるべく均等な条件でスケジュールを組むために利用されていますほかにも身近なところでは最短ルートを求める必要のあるカーナビなどにも応用されています最適化という言葉の認知度は低いですが実は日常に深く繋がっているのですご自身ではどのような研究をされているのですかまだ運用されていませんが大学における時間割作成問題を整数計画問題として定式化する研究などを手掛けています現状時間割は担当者が時間をかけて手作業で作成していますがそれを定式化し問題を設定しますそこさえ作ってしまえばあとはコンピュータが作成してくれるため実際の運用に至れば作業時間は短縮され負担もかなり軽減できるはずです人間が作る場合は毎年一からの作業ですが定式化した問題には汎用性があるので一旦定式化してしまえば条件が変わらない限り毎年同じものが使え手間は一回でよくなります最適化法を運用する会社での社員経験もあるそうですがソフトウエアベンダーで実際にお客様から持ち込まれた問題を定式化し解を求め問題解決してソリューションを提供するという最適化に関する仕事をしていましたまたソルバの実装もしていましたより研究にシフトするため在社中に学位を取得し縁あって関西大学に着任しましたが本学に着任してからも総合ビル管理会社との共同研究でエレベータの保守点検作業の効率化という共同研究を行いましたこれは安全性が求められるエレから各納品先への輸送量の合計が生産量を上回らない各工場制約条件 2 から納品先への輸送量の合計が注文量と一致する sample 9 2 OPTIMAL f = 58 (MINimum) No Row name f C1[1] C1[2] C1[3] C2[1] C2[2] C2[3] St -- NU NU NS NS NS Activity Lower bound Upper bound Marginal = = = -5-2 No Column name x[1,1] x[1,2] x[1,3] x[2,1] x[2,2] x[2,3] x[3,1] x[3,2] x[3,3] St -- NL NL NL NL Activity Lower bound Upper bound Marginal Karush-Kuhn-Tucker optimality conditions: 求解結果最適解最小輸送コスト 58 万円最適輸送量 t 納品先 1 納品先 2 工場 1 15 工場 2 2 工場 KKT.PE: max.abs.err. =.e+ on row max.rel.err. =.e+ on row High quality 納品先 3 18 各工場からの輸送量工場の生産量を超えていない各納品先への輸送量注文量と一致工場 / 納品先の数が 1 程度になっても普通のコンピュータで数秒程度で解を求めることが可能ベータの保守作業において人間が考えた従来の手順が本当に最適かどうかを検証することが目的ですエレベータのピット地下に入り作業するためには安全性を確保するための一連の手順がありますこの作業手順が最適であるかを調べるためルールを定式化し実際のデータと合わせてソルバで解き最適な手順を求めたのです結論としては従来の手順が最適でしたまた作業手順が漏れた際その後の作業のどこかに安全な状態で挟みこめるタイミングを見つけるなるべく手戻りの少ない状況を見つけて作業するなど方法も提案しましたそのほか消防力の最適配置システムの開発などにも携わったこともあります KKT.P: max.abs.err. =.e+ on row max.rel.err. =.e+ on row High quality KKT.DE: max.abs.err. =.e+ on column max.rel.err. =.e+ on column High quality KKT.D: max.abs.err. =.e+ on row max.rel.err. =.e+ on row High quality End of output 一般ユーザー向けソフトウエアの開発今後の課題をお聞かせ下さい現在最適化法における 3 つのプロセスの運用全体を効率化するソフトウエアを作成中です具体的にはモデルの定式化をサポートしソルバを用いて解を求め解の検証にも役立つソフトウエアであり大学院生卒業研究生たちと一緒に作成しています汎用性を持たせることを目指してはいますがユーザーの使いやすさを考えるとその分野に特化した仕組みが入っていた方がよいためカスタマイズもできるようになればと考えています March,29 No.16 KANSAI UNIVERSITY NEWS LETTER 1

7 Topics RISS6 5 1 RISS RCSS PG Lab 4 DM Lab 3 RCSS RISS RISS A A RISS RISS Web RISS RISS 6 Springer The Review of Socionetwork Strategies6 Vol. 3, No DOI DOI RISS KANDAI NEWS RISS 1 2 RISS RISS 511 RISS RISS 1 RISS 4 3 Master of Professional Clinical Psychology 11 KANSAI UNIVERSITY NEWS LETTER No.16 March,29 March,29 No.16 KANSAI UNIVERSITY NEWS LETTER 12

8 OINT ROGRAM Organization for Research and Development of Innovative Science and Technology N I E NEDO 4 32 NEDO NEDO m 1.5m KANSAI UNIVERSITY NEWS LETTER No.16 March,29 March,29 No.16 KANSAI UNIVERSITY NEWS LETTER 14

9 KANDAI N E W S NHK , O 3 1WC No. March, IT IG KANSAI UNIVERSITY NEWS LETTER No.16 March,29

Reed_No26_修正0905.indd

Reed_No26_修正0905.indd Man is a Thinking Reed. No.26 September, 2011 K A N S A I UNIVERSITY NEWSLETTER 1 5 4 7 9 11 21 13 1 Hop Step Jump!! 4 15 Tops Interview 1 1030 1OSAKA MARATHON 2011 40 125 3 50 405 1,500452 18 201041 4