目的関数のない線形計画があります。だから私はその実現可能性をテストしたいだけです。それを行うために、シンプレックスにGLPK APIを使用しています。デフォルトの方法 (meth=GLP_PRIMAL) でシンプレックスを実行すると、ソルバーは 100000 回の反復 (設定した制限) で収束しません。ただし、メソッド GLP_DUALP を使用すると、数回繰り返した後、「警告: 二重縮退; 主シンプレックスへの切り替え」というメッセージが表示され、妥当な回数の繰り返しで収束します。
したがって、私の質問は、最終的に両方のケースで主シンプレックスを使用する場合、最初のケースで収束しないのはなぜですか。何が起こっているのでしょう。
前もって感謝します。
問題に関する詳細な情報がなければ、正確に何が起こっているのかを言うのは難しいですが、基本的に、二重縮退の場合の主シンプレックスは、ある種の「ウォームスタート」です。
双対アルゴリズムを使用している間、最適化プロセスは双対問題を生成します。これは、最適解から開始し、最適条件を含む実行可能な解を見つけようとします。代わりに、主単体は実行可能な解から開始し、次に最適な解を探します。
強い双対性定理が成り立つとき、最適解は同じはずです。あなたの問題では、「双対縮退」警告が表示されます。これは、双対問題に 0 になる方程式があることを意味します。したがって、この方程式内の変数は、目的関数に影響を与えません ( Xis100または just に関係なく1) 。 、目的関数がないため、これはもっともらしいです。GLPK は主シンプレックスに切り替えます。これは、双対問題には代替の最適解が存在するためです。すでに導出された情報を使用すると、主単体はより高速になる可能性があります。GLPK が正確に何をしているのかはわかりませんが、通常、主問題の下限として双対問題の実行可能な解を使用できます。
あなたの第一のアプローチを失速させているのは、おそらく同じ問題です。問題が縮退し、シンプレックス アルゴリズムが、目的に影響を与えない 1 つの変数で行き詰まります。そのため、この変数の最適値を見つけるのは困難です。