数理計画

質問

今、自分でモデルを作り数理計画法を用いて解くということをしています。自分の作ったモデルが

min ax1+bx2
s.t. x1+x2<c or x1+x2=0

上のように制約条件の中に「or（もしくは）」が入るものになってしまった（実際に作ったものはもっと複雑ですが簡単にすると上のような感じです）のですがこういったものは線形計画と呼べるのでしょうか？また解くことは可能でしょうか？

回答No.2

pori_boy

こんにちは

このような問題は線形計画と呼べません。
解くことが可能かというと、No.1さんのようにすれば
（この例だと）2つの問題を解けばOKです。

ただし、注意すべき点として、orが複数入ると
とかなければならない問題の数が指数的に増えます。
ので、もっと複雑なものというのが解けるかどうかは
問題の構造によるという答えになると思います。

例えば、難しい問題として有名な0-1整数計画問題は
x1=0 or x1=1,
x2=0 or x2=1,
...
xk=0 or xk=1
という制約が入ってくると思いますが、この場合
2^k個の問題を解いて、その中で一番良いものを
採用する、という必要がでてきますね。

回答No.1

ElectricGamo

制約条件のどちらかを満たせばいいので

>min ax1+bx2
>s.t. x1+x2<c or x1+x2=0

を

min ax1+bx2
s.t. x1+x2<c

と

min ax1+bx2
s.t. x1+x2=0

の2つの数理計画問題にして、それぞれの解のうち ax1+bx2 の小さい方を取ればいいので、線形計画問題に出来ます。問題が複雑になっても同様です。