多変数式の整数の組み合わせを見つけるモジュールを書きたいです。例えば
8x + 9y <= 124
モジュールは、x と y のすべての可能な正の整数を返します。x=2、y=12。正確に 124 である必要はなく、124 以下の任意の数にすることができます。正確な解が見つからない場合は、できるだけ 124 に近づける必要があります。
変数の数は任意である可能性があるため、力ずくで解決したくありません...（5、10、100、... n）
これを解決できるアルゴリズムはありますか？
1 に答える
1
問題を整数計画問題として作り直すことで、これを解決できます。
式を制約として書き直します。
8x + 9y < = 124 なので
8x + 9y + z = 124
スラック変数を導入したことに注意してくださいz。zできるだけ小さくしたいので、 を次のようにobjective functionします。Minimize z任意のソルバーは、z をインクリメントする前に、x と y のすべての可能な整数値を試します。
完全な IP は次のようになります。
最小 z 8x + 9y + z = 124 x、y、z >=0 および整数
商用またはオープンソースの LP/IP ソルバーを使用して解決します。(R の optim パッケージは 1 つの可能性です。Excel Solver も可能です。)
何らかの理由で、大きくしたり小さくしxたりしたい場合は、yobjective function co-efficients.
より一般的には、Min Cx x + Cy y + Cz z必要に応じてコスト パラメータ Cx Cy および Cz の重みを制御します。
それが役立つことを願っています。
于 2012-08-24T20:55:29.837 に答える