1

私の問題の一部は、特定の数値の加重合計の絶対値を最小化することです。重みを見つけなければなりません。

(a1, a2 > 0), (a3, a4 < 0) となる数値 A、a1、a2、a3、a4 のセットがあるとします。

たとえば、最小の重みは 0.1 (10%)、最大は 0.4 (40%) です。加重合計がゼロになるような加重wを探しています。ゼロが不可能な場合は、可能な限りゼロに近い値。これを実現するために、単純な線形モデルを使用できます。

Minimise E

E >= SUM w * a
E >= -(SUM w * a)
SUM w = 1
w >= 0.1 for all w
w <= 0.4 for all w

解を非常に高速に見つけるには、単純な線形計画で十分です。ただし、この問題の多項式アルゴリズムまたは式を見つけたいと思います。何か案は？この問題はよく知られていますか?

ありがとう！

4

2 に答える 2

1

最小化 (または最大化)SUM w * aは簡単です。すべての重みを最小に設定し、最小から最大 (または最大から最小) の順に重みを増やし、全体的な最大値が達成されるまで、局所的な最大値を尊重します。

[min, max] 区間に 0 が含まれる場合、最適解はこれら 2 つの解の凸結合として実現できます。それ以外の場合は、解を 0 に近づけます。

于 2012-04-18T02:27:55.163 に答える
1

楕円体アルゴリズムは、線形計画法の最初のワースト ケース多項式時間アルゴリズムでした。

ただし、問題をすばやく解決したいのではないかと思います。そのため、多項式時間アルゴリズムに関心があります。

その場合は、シンプレックス法を使用したほうがよいでしょう。シンプレックスは最悪の場合指数関数的ですが、ほとんどの実用的なアプリケーションでは最良の選択と思われます。驚くべきことではありませんが、私が知っているすべての高品質のソルバーに実装されています。

于 2012-04-18T08:50:12.827 に答える