ヒビルテ(2013-04-09)

λ. 強双対性を使って線形計画を制約充足問題に還元する Linear and Discrete Optmization の双対性に関する部分(参考: 第五週目メモ)を復習していて気になったのだけど、強双対性の条件 cT x* = bT y* って線形式で書けてしまっているのよね。 ということは主問題と双対問題の制約条件と強双対性の連言をとっても線形(QF_LRA)の範囲に収まっていて、これの解(実行可能解)を求めれば、目的関数に関する最適化をしなくても最適解が求まることになるはず。 ということで試してみた。 主問題 簡単な問題として、Linear and Discrete Optmization で最初の例として使われていた、以下の例を考える。 MAXIMIZE 100 x1 + 125 x2 SUBJECT TO 3 x1 + 6 x2 <= 30 8 x1 + 4 x2 <= 44 B