algorithm - 最小最大制約を線形化する方法

Question

現在、私はこの線形計画法モデルを持っています:

マックスX

そのような：

Max_a(Min_b(F(a,b,X))) <= 何らかの定数

* Max_aは次式を a だけ変えて最大化するという意味で、Min_bも同様

さて、問題は拘束部分をどう線形化するかです。現在の Minmax 線形化に関する論文のほとんどは、目的としての Minmax について述べています。しかし、それが制約である場合、どのように線形化するのですか??

ありがとう

Answer 1

予備的な発言:あなたが説明する問題は「線形プログラミングモデル」ではなく、直接線形モデルに変換する方法はありません(解決できないという意味ではありません)。

まず、Max制約の は必要ないことに注意してください。つまり、問題は次のように再定式化できます。

 Max X
 subject to: Min_b F(a, b, X) <= K  forall a

さて、あなたは「線形モデル」について話しているので、少なくともF線形であると仮定します。

 F(a, b, X) = Fa.a + Fb.b + FX.X

そして、制約は明らかに次のように書くことができます:

 Fa.a + Min_b Fb.b + FX.X <= k forall a

興味深い点は、 の最小値がとbの値に依存しないことです。したがって、事前に解決できます。最初に find を見つけてから解決しますaXu = Min_b Fb.b

 Max X
 subject to Fa.a + FX.X <= k - u   forall a

もちろん、これは と のドメインが独立していることを前提としていますa(bフォームの):とをAxB結合する他の制約がある場合、それは別の問題です (その場合、質問に完全な問題を書いてください)。ab