線形計画問題について教えてください。

この線形計画問題で、条件を１）と２）で変えたときに
最適解がどう違うのでしょうか？教えてください。
最大化：X1+2X2-X3+3X4+X5+2X6
条件：2X1+X2+3X3+X4+4X5+3X6≦7

１）0≦Xj≦1,j=1,2,3,4,5,6

２）Xj∈{0,1},j=1,2,3,4,5,6

No.3 ベストアンサー 回答者： pori_boy 回答日時： 2007/01/19 12:17

こんにちは

この問題に関しては条件を1としても2としても
まったく同じ最適解がでてきそうですね。

まず、条件1と条件2を比べると、条件2で実行可能となる解は
全て条件1でも実行可能となるので、
1)の最適値 ≧ 2)の最適値　となりますよね。

次に、条件1のもとで線形計画問題を解くと
X1=X2=X4=X6=1, X3=X5=0 という最適解が得られます。
（線形計画問題の一般的な解法を使っても良いですし、
　この問題は、ナップサック問題とよばれる問題形式
　となっていることから、専用の解法を使っても良いです）
ここで得られた解を見ると、条件1を満たすのは当然ですが
幸運にも条件2を満たしているので、この解が条件2での
最適解ということがわかると思います。

この回答へのお礼

かなり詳しく教えてくださってありがとうございます。
わかりやすかったです。
最適解まで解いてもらっちゃって・・・(^_^;)
すごく助かりました！！

お礼日時：2007/01/20 03:04

No.2 回答者： Willyt 回答日時： 2007/01/18 09:53

１では一般的な線形計画法を適用して解を得ることができますが、１の場合は取れる独立変数の値が連続ではないので、通常の線形計画法を適用できなくなります。

無理矢理に適用するには例えば解が０または１にできるだけ近くなるような懲罰函数を目的関数に加えることで近似的に達成することができます。しかしこれは線形ではなくなりますよね。

この回答へのお礼

詳しく教えてくださってありがとうございます。
参考になりました(^^♪

お礼日時：2007/01/19 02:56

No.1 回答者： rabbit_cat 回答日時： 2007/01/18 04:25

１）と２）では、難しさが段違いに違います。

２）のほうが圧倒的に面倒です。まあ、線形なんでできますけど。

最適解は、多分、１）２）で違うでしょうけど実際に計算してないのでわかりません。
ただ、必ず
　1)の最適値 ≧ 2)の最適値
は成り立ちます。

この回答へのお礼

教えてくださってありがとうございました。
参考になりました。(^^♪

お礼日時：2007/01/19 02:53