Koeffizienten Reduzierung in der linearen Programmierung führen zu inkohärenten Ergebnissen

Question

Ich bin ein wenig verwirrt über ein Ergebnis, dass ich nach einer Koeffizientenreduktion auf eine Einschränkung eines linearen Programmierproblems bekam.

Das Problem ist:

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 

Nach der Koeffizienten Reduktion der contraints wird:

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

wie im Applied Integer Programming Buch angegeben (Das-San Chen - Robert G.Batson - Yu Dang) auf Seite 96 (es gibt einen kleinen Fehler auf Seite 97. Der x1-Koeffizient ist 3 nicht 1).

Danach habe ich versucht, das Problem zu senden, mit und ohne die Koeffizientenreduzierung zu verstärken. Aber ich habe zwei verschiedene Ergebnisse:

[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 

warum? Kann die Lösung trotzdem als richtig angesehen werden, auch wenn das Ergebnis für x5 etwas anders ist? Ich habe drei verschiedene Solver (Minos, Gurobi, Cplex) verwendet, aber sie geben die gleichen Ergebnisse für das Problem.

Answer 1

Wenn Sie mit der Technik beziehen sich in 4.4.3, dann ist es klar, was ist das Problem hier.

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

Du diese Technik zu verwenden nicht erlaubt, als Koeffizienten kontinuierlich sind (in [1,2]) und nicht binär wie hier gebraucht!