线性规划中的系数减少导致不连贯的结果

Question

我对线性规划问题的约束系数减少后得到的结果有点困惑。

问题是：

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页所述（第96页有一点错误97.x1系数是3不是1).

在那之后，我尝试将问题提交给 ampl，有和没有系数减少。但是我得到了两个不同的结果：

[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），但它们在问题上输出的结果相同。

Answer 1

如果你指的是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] 中）而不是这里需要的二进制！

线性规划中的系数减少导致不连贯的结果

Coefficients Reduction in Linear Programming lead to incoherent results

linear-programming

reduction

ampl

coefficients

operations-research