「同次自己双対内点法」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
線形計画問題の最適性の条件に新たに<math>2\, </math>つのパラメータを導入することによって, 定数ベクトルが<math>0\, </math> (同次), 主問題と双対問題が同形(自己双対), かつ最適解をもつ 人工的な線形計画問題を生成し, これに主双対内点法を適用する多項式時間解法である. 人工問題の最適解から, 元の問題の最適解の有無や最適解が得られる. 大きな値の初期点を必要としない点で, 非許容初期点内点法 より数値的に安定しているといわれている. | 線形計画問題の最適性の条件に新たに<math>2\, </math>つのパラメータを導入することによって, 定数ベクトルが<math>0\, </math> (同次), 主問題と双対問題が同形(自己双対), かつ最適解をもつ 人工的な線形計画問題を生成し, これに主双対内点法を適用する多項式時間解法である. 人工問題の最適解から, 元の問題の最適解の有無や最適解が得られる. 大きな値の初期点を必要としない点で, 非許容初期点内点法 より数値的に安定しているといわれている. | ||
| + | |||
| + | [[Category:線形計画|どうじじこそうついないてんほう]] | ||
2008年11月13日 (木) 12:49時点における最新版
【どうじじこそうついないてんほう (homogeneous self-dual interior point method)】
線形計画問題の最適性の条件に新たにつのパラメータを導入することによって, 定数ベクトルが (同次), 主問題と双対問題が同形(自己双対), かつ最適解をもつ 人工的な線形計画問題を生成し, これに主双対内点法を適用する多項式時間解法である. 人工問題の最適解から, 元の問題の最適解の有無や最適解が得られる. 大きな値の初期点を必要としない点で, 非許容初期点内点法 より数値的に安定しているといわれている.
