34

私は、目的関数がmaxそれぞれの係数を掛けた決定変数から余分な重みを追加する線形計画法を設定しようとしています。

これを念頭に置いて、線形計画法の目的関数内でminまたはmax演算子を使用する方法はありますか？

例：

Minimize
    (c1 * x1) + (c2 * x2) + (c3 * x3) + (c4 * max(c1*x1, c2*x2, c3*x3)) 
subject to
    #some arbitrary integer constraints:
    x1 >= ...
    x1 + 2*x2 <= ... 
    x3 >= ...
    x1 + x3 == ...

(c4 * max(c1*x1, c2*x2, c3*x3))それが私が懸念している「余分な重量」の用語であることに注意してください。「余分c4な重み」係数を示します。また、この特定の例では、、、およびは整数x1であることに注意してください。x2x3

上記は線形計画法が提供する範囲外かもしれないと思います。しかし、おそらくこれをハック/再フォーマットして有効な線形計画法にする方法はありますか？

この問題が完全に線形計画法の範囲外である場合、おそらく誰かがこのタイプの問題により適した最適化パラダイムを推奨できますか？（すべての可能な解決策を手動で列挙してチェックすることを回避できるものなら何でも役に立ちます。）

4

1 に答える 1

50

制約付きの補助変数、たとえばx4を追加します。

x4 >= c1*x1
x4 >= c2*x2
x4 >= c3*x3  
Objective += c4*x4
于 2012-05-29T04:23:40.367 に答える