知能ロボット設計論 担当：平田 健太郎 第2回 （4/21） １．グラフとネットワークにおける数理 ・ シンプレックス法 (1) 1 Schedule 4/14 １．グラフとネットワークにおける数理 ・ 輸送問題とLP 4/21 ・ シンプレックス法（１） 4/28 ・ シンプレックス法（２）, 最大流/最小費用流問題 5/8 ・ 多項式時間アルゴリズム, 双対問題 5/12 ・ 内点法 5/19 5/26 6/2 ・ 最短経路問題とダイクストラ法 ・ 組合せ最適化（１） ・ 組合せ最適化（２） Design of Intelligent Robot 2 本日の話題に関連する英単語 simplex method basic/non-basic variables feasible region convex/convexity polyhedra edge/vertex iteration optimality primal/dual problem Design of Intelligent Robot 3 輸送問題 C1 F1 C2 F2 C3 線形計画問題 (LP) Design of Intelligent Robot 4 cT x = γ 等式条件のときの変数の数 制約条件の数 不等式条件のときの変数の数 m l m′ m′ = m + l Ax ≤ b, x ≥ 0 制約条件を満たす の領域 m′ > l ⇒ 実行可能領域 (feasible region) 凸多面体 (convex polyhedra) ⇒ 多面体であって, その内部の任意の2点を結ぶ線分上 の点がすべて, もとの多面体内部に含まれるもの Design of Intelligent Robot 5 一般に実行可能領域は凸多面体であり, 等高線は平面で与 えられる．したがって最適値は必ずその頂点で達成される. 多面体の頂点は有限個だから，原理的に有限回の探索を実 行すればよい. 例題 x2 x1 Design of Intelligent Robot 6 図形的解法 x2 x1 系統的な探索方法 ⇒ シンプレックス法 Design of Intelligent Robot 7 [基本的な考え方] 4変数に対して制約式は2つなので, 変数のうち2つを0とおくと残 りの変数の値が一意に定まる. 目的関数値が効果的に減少する ように0とする変数のとり方を変えていけばよい. 変数の一部を0とすることによって一意的に定まる解 x を基底解 という. 基底解がx ≧0 を満たすとき実行可能基底解という. 0 とおいた変数を非基底変数， それ以外を基底変数という. Design of Intelligent Robot 8 x2 5 4 1 2 6 3 x1 評価関数の値を減少させな がら，基底を更新していくア ルゴリズムがあればよい Design of Intelligent Robot 9 行列Aを分割 Design of Intelligent Robot 10 x2 5 4 1 2 6 3 Design of Intelligent Robot x1 11 最適解の判定条件 まず最適解の判定条件を考える． [理由] • 解法アルゴリズムの停止条件が得られる • 「最適でない」証拠の中にどうすればよりよくなるかの情報が含 まれていればうれしい 最適解か？ No Yes 終了 Design of Intelligent Robot 12 最適解の判定 基本となる式: Design of Intelligent Robot 13 シンプレックス法（単体法）のアルゴリズム 絶対値の大きいものを選ぶのが有力 Design of Intelligent Robot 14 最適条件が満たされるまで繰り返す 例： 最小化したい目的関数 制約条件 現在の解 (4, 0)T Design of Intelligent Robot 15 例外 Design of Intelligent Robot 16 例題 [第1反復] Design of Intelligent Robot 17 DIYのページ <１> Design of Intelligent Robot 18 DIYのページ <２> Design of Intelligent Robot 19 DIYのページ <3> Design of Intelligent Robot 20 線形計画問題の標準形 系統的な解法を考えるにあたって, 問題毎の定式化に 差異があると不都合 （例: 最大化 or 最小化, 制約条件の与え方) 標準形を定めて，その解法を与える （1） 最小化 標準形 （3） 全ての変数に 非負条件 (2) 等号制約 Design of Intelligent Robot 21 標準形でない例 最大化 x2 に符号制約なし 2,3番目が不等号制約 係数cの符号反転 ２つの正数の差で表現 両辺のギャップをある正数を導 入して表現（スラック変数） ⇒ 標準形に変換できる Design of Intelligent Robot 22 標準形でない ⇒標準形 Design of Intelligent Robot 23
© Copyright 2024 ExpyDoc
