Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Interactivelinearprogramming gives the wrong answer

Here are two version of the same linear programming problem :

$min\ -1.8x-y +600|x\leq30;y\leq32;2x+3y\leq90;10x+6y\leq230$ $min\ 4.2x+5y +6z|x\leq30;y\leq32;2x+3y\leq90;10x+6y\leq230;x+y+z = 100;$

The first one, is simply the second after elimination of the $z$ variable. Here is one Sagemath code to solve the first

%display latex
A=matrix([[1,0],[0,1],[2,3],[10,6]])
b=vector([30,32,90,230])
c=vector([-1.8,-12])
inc=InteractiveLPProblem(A,b,c,["I_A","I_B"],problem_type="min",objective_constant_term=600)#la forme du problem_type est obligatoire pour InteractiveLPProblemStandardForm
show(inc)
inc.plot()
inc=inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

But the answer is obviously false. I have use the same type of code to solve the second.

%display latex
A=matrix([[1,0,0],[0,1,0],[2,3,0],[10,6,0],[1,1,1]])
b=vector([30,32,90,230,100])
c=vector([4.2,5,6])
inc=InteractiveLPProblem(A,b,c,["x","y","z"],problem_type="min",constraint_type=['<=','<=','<=','<=','=='],objective_constant_term=600)
show(inc)
inc=inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

Here the answer is infeasibility.

But with the following code I reach the good answer (verified by Lips <- Sourceforge, which gives the same answer for both problems):

n=5 #nombre de contraintes
m=3 #nombre de variables
A= matrix(n,m,[1,0,0,0,1,0,2,3,0,10,6,0,1,1,1]) #les coefficients
bmin=[0,0,0,0,100] #les bornes inférieures pour les contraintes
bmax=[30,32,90,230,100] #les bornes supérieures pour les contraintes (oo=infini)
show(LatexExpr("A="),A)
show(LatexExpr("bmin="),bmin)
show(LatexExpr("bmax="),bmax)
sol=MixedIntegerLinearProgram(maximization=False, solver="GLPK") #on crée le programme
x= sol.new_variable(integer=False, indices=[0..m-1]) #les nouvelles variables sont x_0...x_11
B=A*x #la fonction linéaire pour les contraintes
sol.set_objective(4.2*x[0]+5*x[1]+6*x[2]+600) # fixe l'objectif
#on construit les contraintes avec leurs bornes
for i in range(n):
    sol.add_constraint(B[i], min=bmin[i], max=bmax[i])
sol.show()
sol.solve()
xx=sol.get_values(x)
show(LatexExpr(r"I_A^\star ="),xx[0],LatexExpr(r", I_B^\star ="),xx[1],LatexExpr(r", E^\star ="),xx[2], LatexExpr(r" \text{ et } C^\star ="),sol.get_objective_value())

So I wonder if I have made a mistake or if there is an error in the code. I am perfectly aware that the interactivelinearprogramming package is construct for pedagogical reason. But some things are not very obvious. For instance it is sensitive to the order of the options.

Interactivelinearprogramming gives the wrong answer

Here are two version versions of the same linear programming problem :

$min\ -1.8x-y +600|x\leq30;y\leq32;2x+3y\leq90;10x+6y\leq230$ $min\ 4.2x+5y +6z|x\leq30;y\leq32;2x+3y\leq90;10x+6y\leq230;x+y+z = 100;$

problem:

  • $\min$ { $-1.8 x - y + 600 \; | \; x \leq 30; \; y \leq 32 ; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230$ }

  • $\min$ { $4.2 x + 5 y + 6 z \; | \; x \leq 30; \; y \leq 32; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230; \; x + y + z = 100$ }

The first one, one is simply the second one after elimination of the $z$ variable. variable.

Here is one Sagemath some SageMath code to solve the firstfirst one

%display latex
A=matrix([[1,0],[0,1],[2,3],[10,6]])
b=vector([30,32,90,230])
c=vector([-1.8,-12])
inc=InteractiveLPProblem(A,b,c,["I_A","I_B"],problem_type="min",objective_constant_term=600)#la A = matrix([[1, 0], [0, 1], [2, 3], [10, 6]])
b = vector([30, 32, 90, 230])
c = vector([-1.8, -12])
# La forme du problem_type `problem_type` est obligatoire pour InteractiveLPProblemStandardForm
`InteractiveLPProblemStandardForm`
inc = InteractiveLPProblem(A, b, c, ["I_A", "I_B"], problem_type="min", objective_constant_term=600)
show(inc)
inc.plot()
inc=inc.standard_form()
inc = inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

But the answer is obviously false. I have use used the same type of code to solve the second. second one.

%display latex
A=matrix([[1,0,0],[0,1,0],[2,3,0],[10,6,0],[1,1,1]])
b=vector([30,32,90,230,100])
c=vector([4.2,5,6])
inc=InteractiveLPProblem(A,b,c,["x","y","z"],problem_type="min",constraint_type=['<=','<=','<=','<=','=='],objective_constant_term=600)
A = matrix([[1,0,0],[0,1,0],[2,3,0],[10,6,0],[1,1,1]])
b = vector([30,32,90,230,100])
c = vector([4.2,5,6])
inc = InteractiveLPProblem(A, b, c, ["x", "y", "z"], problem_type="min", constraint_type=['<=', '<=', '<=', '<=', '=='], objective_constant_term=600)
show(inc)
inc=inc.standard_form()
inc = inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

Here the answer is infeasibility.

But with the following code I reach the good answer (verified by Lips <- Sourceforge, Sourceforge, which gives the same answer for both problems):

n=5 #nombre n = 5  # nombre de contraintes
m=3 #nombre m = 3  # nombre de variables
A= matrix(n,m,[1,0,0,0,1,0,2,3,0,10,6,0,1,1,1]) #les A = matrix(n, m, [1, 0, 0, 0, 1, 0, 2, 3, 0, 10, 6, 0, 1, 1, 1])  # les coefficients
bmin=[0,0,0,0,100] #les bmin = [0, 0, 0, 0, 100]  # bornes inférieures pour les contraintes
bmax=[30,32,90,230,100] #les bmax = [30, 32, 90, 230, 100]  # bornes supérieures pour les contraintes (oo=infini)
show(LatexExpr("A="),A)
show(LatexExpr("bmin="),bmin)
show(LatexExpr("bmax="),bmax)
sol=MixedIntegerLinearProgram(maximization=False, (oo = infini)
show(LatexExpr("A="), A)
show(LatexExpr("bmin="), bmin)
show(LatexExpr("bmax="), bmax)
sol = MixedIntegerLinearProgram(maximization=False, solver="GLPK") #on  # on crée le programme
x= x = sol.new_variable(integer=False, indices=[0..m-1]) #les indices=[0 .. m - 1])  # les nouvelles variables sont x_0...x_11
B=A*x #la x_0 à x_11
B = A*x  # la fonction linéaire pour les contraintes
sol.set_objective(4.2*x[0]+5*x[1]+6*x[2]+600) # fixe l'objectif
#on # on construit les contraintes avec leurs bornes
for i in range(n):
    sol.add_constraint(B[i], min=bmin[i], max=bmax[i])
sol.show()
sol.solve()
xx=sol.get_values(x)
xx = sol.get_values(x)
show(LatexExpr(r"I_A^\star ="),xx[0],LatexExpr(r", ="), xx[0], LatexExpr(r", I_B^\star ="),xx[1],LatexExpr(r", ="), xx[1], LatexExpr(r", E^\star ="),xx[2], ="), xx[2], LatexExpr(r" \text{ et } C^\star ="),sol.get_objective_value())
="), sol.get_objective_value())

So I wonder if I have made a mistake or if there is an error in the code. code. I am perfectly aware that the interactivelinearprogramming package is construct interactivelinearprogramming package is built for pedagogical reason. reasons. But some things are not very obvious. obvious. For instance it is sensitive to the order of the options.

Interactivelinearprogramming gives the wrong answer

Here are two versions of the same linear programming problem:

  • $\min$ { $-1.8 x - y + 600 \; | \; x \leq 30; \; y \leq 32 ; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230$ }

  • $\min$ { $4.2 x + 5 y + 6 z \; | \; x \leq 30; \; y \leq 32; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230; \; x + y + z = 100$ }

problem.

The first one is simply the second one after elimination of the $z$ variable.

eliminating the variable $z$.

  • $\min$ { $-1.8 x - y + 600 \; | \; x \leq 30; \; y \leq 32 ; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230$ }

  • $\min$ { $4.2 x + 5 y + 6 z \; | \; x \leq 30; \; y \leq 32; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230; \; x + y + z = 100$ }

Here is some SageMath code to solve the first one

%display latex
A = matrix([[1, 0], [0, 1], [2, 3], [10, 6]])
b = vector([30, 32, 90, 230])
c = vector([-1.8, -12])
# La forme du `problem_type` est obligatoire pour `InteractiveLPProblemStandardForm`
inc = InteractiveLPProblem(A, b, c, ["I_A", "I_B"], problem_type="min", "I_B"],
                           problem_type="min",
                           objective_constant_term=600)
show(inc)
inc.plot()
inc = inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

But the answer is obviously false. I have used the same type of code to solve the second one.

%display latex
A = matrix([[1,0,0],[0,1,0],[2,3,0],[10,6,0],[1,1,1]])
matrix([[1, 0, 0], [0, 1, 0], [2, 3, 0], [10, 6, 0], [1, 1, 1]])
b = vector([30,32,90,230,100])
vector([30, 32, 90, 230, 100])
c = vector([4.2,5,6])
vector([4.2, 5, 6])
inc = InteractiveLPProblem(A, b, c, ["x", "y", "z"], problem_type="min", "z"],
                           problem_type="min",
                           constraint_type=['<=', '<=', '<=', '<=', '=='], '=='],
                           objective_constant_term=600)
show(inc)
inc = inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

Here the answer is infeasibility.

But with the following code I reach the good answer (verified by Lips <- Sourceforge, which gives the same answer for both problems):

n = 5  # nombre de contraintes
m = 3  # nombre de variables
A = matrix(n, m, [1, 0, 0, 0, 1, 0, 2, 3, 0, 10, 6, 0, 1, 1, 1])  # les coefficients
bmin = [0, 0, 0, 0, 100]  # bornes inférieures pour les contraintes
bmax = [30, 32, 90, 230, 100]  # bornes supérieures pour les contraintes (oo = infini)
show(LatexExpr("A="), A)
show(LatexExpr("bmin="), bmin)
show(LatexExpr("bmax="), bmax)
sol = MixedIntegerLinearProgram(maximization=False, solver="GLPK")  # on crée le programme
x = sol.new_variable(integer=False, indices=[0 .. m - 1])  # les nouvelles variables sont x_0 à x_11
B = A*x  # la fonction linéaire pour les contraintes
sol.set_objective(4.2*x[0]+5*x[1]+6*x[2]+600) # fixe l'objectif
# on construit les contraintes avec leurs bornes
for i in range(n):
    sol.add_constraint(B[i], min=bmin[i], max=bmax[i])
sol.show()
sol.solve()
xx = sol.get_values(x)
show(LatexExpr(r"I_A^\star ="), xx[0], LatexExpr(r", I_B^\star ="), xx[1], LatexExpr(r", E^\star ="), xx[2], LatexExpr(r" \text{ et } C^\star ="), sol.get_objective_value())

So I wonder if I made a mistake or if there is an error in the code. I am perfectly aware that the interactivelinearprogramming package is built for pedagogical reasons. But some things are not very obvious. For instance it is sensitive to the order of the options.

Interactivelinearprogramming gives the wrong answer

Here are two versions of the same linear programming problem.

The first one is simply the second one after eliminating the variable $z$.

  • $\min$ { $-1.8 x - y + 600 \; | \; x \leq 30; \; y \leq 32 ; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230$ }

  • $\min$ { $4.2 x + 5 y + 6 z \; | \; x \leq 30; \; y \leq 32; \; 2 x + 3 y \leq 90; \; 10 x + 6 y \leq 230; \; x + y + z = 100$ }

Here is some SageMath code to solve the first one

%display latex
A = matrix([[1, 0], [0, 1], [2, 3], [10, 6]])
b = vector([30, 32, 90, 230])
c = vector([-1.8, -12])
# La forme du `problem_type` est obligatoire pour `InteractiveLPProblemStandardForm`
inc = InteractiveLPProblem(A, b, c, ["I_A", "I_B"],
                           problem_type="min",
                           objective_constant_term=600)
show(inc)
inc.plot()
inc = inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

But the answer is obviously false. I have used the same type of code to solve the second one.

%display latex
A = matrix([[1, 0, 0], [0, 1, 0], [2, 3, 0], [10, 6, 0], [1, 1, 1]])
b = vector([30, 32, 90, 230, 100])
c = vector([4.2, 5, 6])
inc = InteractiveLPProblem(A, b, c, ["x", "y", "z"],
                           problem_type="min",
                           constraint_type=['<=', '<=', '<=', '<=', '=='],
                           objective_constant_term=600)
show(inc)
inc = inc.standard_form()
inc = inc.run_simplex_method()
show(inc)

Here the answer is infeasibility.

But with the following code I reach the good answer (verified by Lips <- Sourceforge, which gives the same answer for both problems):

n = 5  # nombre de contraintes
m = 3  # nombre de variables
A = matrix(n, m, [1, 0, 0, 0, 1, 0, 2, 3, 0, 10, 6, 0, 1, 1, 1])  # les coefficients
bmin = [0, 0, 0, 0, 100]  # bornes inférieures pour les contraintes
bmax = [30, 32, 90, 230, 100]  # bornes supérieures pour les contraintes (oo = infini)
show(LatexExpr("A="), A)
show(LatexExpr("bmin="), bmin)
show(LatexExpr("bmax="), bmax)
sol = MixedIntegerLinearProgram(maximization=False, solver="GLPK")  # on crée le programme
x = sol.new_variable(integer=False, indices=[0 .. m - 1])  # les nouvelles variables sont x_0 à x_11
B = A*x  # la fonction linéaire pour les contraintes
sol.set_objective(4.2*x[0]+5*x[1]+6*x[2]+600) # fixe l'objectif
# on construit les contraintes avec leurs bornes
for i in range(n):
    sol.add_constraint(B[i], min=bmin[i], max=bmax[i])
sol.show()
sol.solve()
xx = sol.get_values(x)
show(LatexExpr(r"I_A^\star ="), ="),
     xx[0], LatexExpr(r", I_B^\star ="), ="),
     xx[1], LatexExpr(r", E^\star ="),  xx[2], LatexExpr(r" \text{ et } C^\star ="), ="),
     sol.get_objective_value())

So I wonder if I made a mistake or if there is an error in the code. I am perfectly aware that the interactivelinearprogramming package is built for pedagogical reasons. But some things are not very obvious. For instance it is sensitive to the order of the options.