Interactivelinearprogramming gives the wrong answer

asked 2020-10-19 23:12:53 -0600

Cyrille gravatar image

updated 2020-10-20 07:28:50 -0600

slelievre gravatar image

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.

edit retag flag offensive close merge delete