システム最適化特論担当：平田健太郎第5回（5/11）１．グラフとネットワークにおける数理・内点法（2） 1 講義日程（予定） 4/13 １．グラフとネットワークにおける数理・輸送問題とLP 4/20 ・シンプレックス法（１） 4/27 ・シンプレックス法（２）, 双対問題 5/7 ・多項式時間アルゴリズム, 内点法（１） 5/11 ・内点法（２） 5/18 ・最短経路問題とダイクストラ法（１） 5/25 ・最短経路問題とダイクストラ法（２） 6/1 ・組合せ最適化（１） 6/8 ・組合せ最適化（２） 2 (D) min min max , s.t. s.t. , s.t. , 0 , ′′′ 0 (P’) ′ ′′ ′′′ min 0 ′ ′′ ′′′ s.t. ′ ′′ ′′′ 0 min ̃ , s.t. 0 , ̃ 0 , , , 3 (D’) (P’) min ̃ min max 0 , ̃ s.t. 0 , 0 ̃ s.t. s.t. , , ̅≔ よって, min s.t. ̅ ̅ min ̅ ̅ 0, , ̅ ̅ s.t. ̅ (D’) に最適解が存在 , 0 (P) に最適解が存在 4 Who are you? 5 フリーな数値解析ソフトウェア Octave を使って数値計算してみる（利用できる環境があればMatlabでもよい） 6 7 8 あとは, 指示に従って, 適切にインストールする 9 標準でGUIが起動する 10 エディタで新規ファイル作成 (Script) 11 ここにプログラムを書く 12  これをやってみよう 2の数値 1.41421356 … を求める 2 を満たす 0 を求める二分法 (Bisection Method) f (x) 0 であるような2点 , とし, 2 を入れ替える. をとる. と同符号のまたはと所望の近似値が得られるまで繰り返す. x1 xM x2 x 13 編集後, bisect.m として適当な場所に保存. で実行. （初回はパスを通す設定ダイアログあり）結果は Command Window に表示される（画面下タブ切り替え）. 14 繰り返し回数の値誤差 15 ニュートン法 (Newton’s Method) 初期値に対して接線を引く. 接線と軸の交点をにおけるの f (x) f ( x1 ) とする. x2 x1 x 所望の近似値が得られるまで繰り返す. これもやってみよう. 初期値は例えば 2. 繰返しは5回ぐらいで十分. 16  パス追跡・主双対内点法主問題 primal problem (P) 双対問題 dual problem (D) 双対問題 (D’) 17 双対定理よりスカラ量少なくとも一方は0：相補性条件 18 線形相補性問題非線形パス追跡法 19 (Newton法) 20 1984年11月米国OR学会(ダラス）にて発表. 「自分の解法の出現によって新しい時代の幕が開いた」と述べるが, 専門家からの技術的質問には一切答えないというルール破りの行動に出た. 21 カーマーカー特許とソフトウェア ―数学は特許になるか中公新書今野浩 (著) 22 23 24 1984年アメリカ, ベル研究所の研究者ナレンドラ・カーマーカー（Narendra Karmarkar）によって世界初のアルゴリズム特許が出願され, 88年に特許申請が認められた．数式（算法）は、特許にならないという常識をくつがえした．日本にもAT&T社から「最適資源割当て方法」として出願され成立．（特許第2033073号） 1989年 AT&T LPソルバKORBXと専用コンピュータ(890万ドル)の抱き合わせ販売を開始. 【KORBX購入先】デルタ航空: 全米166都市間を運行する400機の飛行機と7000名の乗務員に関するスケジューリング問題を解いた. (年間10M$の経費節減) 米空軍: 70000制約式, 500000変数の問題が解けるようになった. Karmarkar法: 対数障壁関数を用いたポテンシャル関数の値で最適解からの誤差を測り, 射影変換を用いて探索方向を決定. 25 バリア関数（ペナルティ）法制約条件： log バリア関数：  log( f i ( x)) 制約領域の境界  f i (x) 制約領域の内側 26 バリア関数と（線形）評価関数を合成バリア関数の値合成した値バリア関数の等高線 27 バリア関数（ペナルティ）法原問題 (制約つき）制約なし問題（等価）バリア関数対数バリア関数（微分可能）制約なし問題（近似）制約なし非線形最適化 28 Karmarkar法射影変換法 60年代に先行研究(ディキン(ロシア)) アフィン変換法主双対内点法 AT&Tの特許戦略: 制約領域の内部を通るものならどんなものであれ特許侵害とみなす対抗ソフト OB1 (5万ドル) 登場 29 ネットワークに関する他の線形計画問題宅配便会社が各都市で荷物の積み替えなどをしながらA市からF市へ品物を運ぶ. 各道路の輸送量制約下でA市からF市へ配送できる量の最大値を求めよ. 90 B 120 20 30 A 60 10 100 30 50 F 130 80 70 A～F：都市 D C 80 100 E 40 各枝における１日当たりの輸送量上限値 30  最大流問題各枝の流量制約下でソースからシンクへ流すことのできるフローの最大値を求めよ. 90 各枝における流量上限値 1 60 3 100 120 Source 30 s 10 20 30 80 t Sink 130 2 70 50 80 100 4 40 ：節点の集合, ：枝の集合, ：ソース, ：シンク, ：枝 , 上の流れの大きさ, ：枝 , の容量, ：ソースからシンクへの総流量 31  定式化 1 s Source 3 1 32  最大流問題 33  最小費用流問題最大流問題の条件に加えて, 各枝における単位流量あたりのコストが与えられている. 90 s 1 60 3 s 100 120 30 s 10 20 30 80 t 2 2 4 1 5 2 3 2 4 1 … 1 3 130 2 70 50 1 80 100 4 40 ソースからシンクへのフローは与えられているとする. 各枝の輸送量制約下で定められた量の品物をソースからシンクへ流すとき，費用が最小となる配送法を求めよ. 34 35