シンプレックスアルゴリズムと極値
この質問の速記は、LP =線形計画法、BFS =基本的な実行可能なソリューション、SEF =標準の等式形式です。
シンプレックスアルゴリズムは極値から極値まで反復するため（LPがSEFにある場合にシンプレックスがBFSからBFSに反復するという事実に対応）、実行可能領域が実現できない多面体である場合、シンプレックスアルゴリズムは幾何学的にどのように機能しますか？ SEF（例：ハーフスペース）？実行可能領域に極値がないLPがあるとします。次に、SEFにある「同等の」LPを記述し、代わりにシンプレックスアルゴリズムを実行できます。しかし、この新しい多面体には極端な点がありますが、元の多面体にはありません。私は当初、一方のLPの極値がもう一方の極値に全単射で対応していると思っていましたが、明らかにそうではありません。
では、LPのSEFバージョンの極値は、元の極値に全単射的に対応するのはいつですか？さらに、そのような全単射が成り立たない場合、元のLPに関してシンプレックスアルゴリズムが実行していることを幾何学的にどのように解釈する必要がありますか？
回答
シンプレックスアルゴリズムは極値から極値まで反復します
技術的にはありません。シンプレックスアルゴリズムは、基底から基底へと反復します。実行可能な基本的な解決策が極端な点に対応するのはたまたまです。（たとえば、デュアルシンプレックスは、プライマル実行可能領域の極値ではない、デュアル実行可能基本ソリューションを反復処理します）。
標準形式のLPを考えてみましょう。 \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}そのLPの実行可能領域は常に多面体です。極値がない場合は、空である（そして基本的な実行可能な解決策がない）か、またはのアフィン部分空間があります。$\mathbb{R}^{n}$。さて、後者の場合は起こり得ません。なぜなら、アフィン部分空間はのサブセットになることができないからです。$\mathbb{R}_{+}^{n}$。
さて、あなたの元の質問に戻りましょう：元の多面体とそのSEF表現が与えられた場合、その表現には極値があり、それらは元の多面体の極値に対応しますか？答えは次のとおりです。はい、SEFには極値があります。いいえ、元の多面体の極値に常に対応しているとは限りません。
簡単な例を次に示します。 $\mathcal{P} = \{x \in \mathbb{R}\}$、これは1次元の多面体です。その定式化には1つの自由変数があり、制約はありません。
SEF表現を作成するには、 $x$ 沿って $x^{+} - x^{-}$ と $x^{\pm} \geq 0$。さて、$(0, 0)$ そのSEFの極値であり、 $x=0$、これは極値ではありません $\mathcal{P}$。
私はあなたの質問を完全に理解しているとは言えませんが、あなたの混乱は、基本的な解決策が「極値」であるという仮定から生じていると思います。基本的な（必ずしもプライマリまたはデュアル実行可能である必要はありません）ソリューションは、行数の制約の交差です（その一部は境界である可能性があります）。結果として実行不可能または無制限のいずれかであるため、問題に主要なまたは二重の実行可能解がない可能性があります。教科書のシンプレックスアルゴリズムは、実際にアルゴリズムを開始するためにBFSを確立するために、何らかの形式のフェーズ1アプローチが必要であるという事実をスキップすることがあります。プライマリフェーズ1で問題のプライマルが実行不可能であることが判明する可能性があり、デュアルフェーズ1で問題が無制限に検出される可能性もあります。
更新：mtanneauによる答えは、おそらく、自由変数を持つ単一の制約についても同じことが当てはまるということです。シンプレックス実装は自由変数を直接処理し、それらを0で囲まれた2つの変数に変換しないことを追加したいだけです。しかし、同じことが当てはまり、アルゴリズムは基本解を反復し、非基本自由変数は値を取るという規則が作成されます0.また、有界多面体の場合、基本解は極値に対応することに注意してください。