2

線形計画問題の制約で係数を削減した後に得た結果について、少し混乱しています。

問題は：

maximize z = x1 + x2 + x3 + x4 + x5 + x6
subject to: 6*x1 + 3*x2 - 5*x3 + 2*x4 + 7*x5 - 4*x6 <= 15
where:
      1<=x1<=2 continuos
      1<=x2<=2 continuos
      1<=x3<=2 continuos
      1<=x4<=2 continuos
      1<=x5<=2 continuos
      1<=x6<=2 continuos

係数削減後、制約は次のようになります。

subject to: 3*x1 + 3*x2 - 3*x3 + 2*x4 + 3*x5 - 3*x6 <= 8

応用整数プログラミングの本 (Der-San Chen - Robert G.Batson - Yu Dang)の 96 ページに記載されているように(97 ページに少し誤りがあります。x1 係数は 1 ではなく 3 です)。

その後、係数削減の有無にかかわらず、問題をamplに送信しようとしました。しかし、2 つの異なる結果が得られました。

[without coefficients reduction]
CPLEX 12.6.1.0: optimal integer solution; objective 11.57142857
display x;
x1  2
x2  2
x3  2
x4  2
x5  1.57
x6  2

[with coefficients reduction]
CPLEX 12.6.1.0: optimal integer solution; objective 11.33333333
display x;
x1  2
x2  2
x3  2
x4  2
x5  1.33
x6  2

なぜ？x5の結果が少し異なっていても、解決策は正しいと見なすことができますか? 私は 3 つの異なるソルバー (minos、gurobi、cplex) を使用しましたが、問題に対して同じ結果を出力します。

4

1 に答える 1

2

4.4.3のテクニックを参照している場合、ここで何が問題なのかは明らかです。

Suppose we are given a constraint of the form
    a1*y1+ a2*y2 + ... + ai*yi < b
    where yi = 0 or 1

係数は連続 ([1,2]) であり、必要に応じてバイナリではないため、この手法を使用することはできません!

于 2016-10-16T14:28:24.323 に答える