第9回 超ロバスト計算原理講究
日時:平成18年6月21日(水) 14:45〜16:15
場所:工学部6号館2階62号講義室
講師:垣村 尚徳 (超ロバスト計算原理プロジェクト、RA)
タイトル:符号可解線形計画の組合せ的解法
概要
線形計画問題 max{cx | Ax=b, x≧0} が符号可解であるとは、与えられたA,b,cの要素の絶対値によらずに最適解のとりうる符号パターンが定まることを言う。
本講義では、A,b,c の符号パターンを表現する二部グラフを用いて、線形計画問題が符号可解であるための十分条件を与える。
そして、その十分条件を満たす線形計画問題に対して、A,b,cの符号パターンから最適解の符号パターンを得るための組合せ的解法を提案する。
この解法は、数値情報を用いないため入力誤差などの外乱に強いロバストな解法である。
|