선형 프로그래밍의 계수 감소로 인코 히어 런트 결과로 이어짐

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 

- 로버트 G.Batson - Yu Dang) (96 페이지에서 약간의 오류가 있습니다. x1 계수는 3이 아님).

그 후 나는 계수 감소가있는 경우와없는 경우에 문제를 제출하려고했습니다. 하지만 두 가지 결과가 나타납니다.

[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의 기술을 말하는 경우 문제가 무엇인지 분명히합니다. 당신의 계수가 연속 (의 [1,2]) 여기에 필요에 따라 바이너리 아니기 때문에

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

당신은 은이 기술을 사용할 수 없습니다!