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

如Applied Integer Programming书（Der-San Chen - Robert G.Batson - Yu Dang）第96页所述（第97页有一点错误。x1系数是3而不是1）。

之后，我尝试将问题提交给放大和不降低系数。但我得到了两个不同的结果：

[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 的结果略有不同，该解决方案是否仍然可以被认为是正确的？我使用了三种不同的求解器（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 回答