pythonscipyscipy-optimizetraveling-salesmansimplex

Using Scipy's linprog and the simplex method, how do I solve a simple tableau and get the expected results?


I am trying to solve a simple simplex tableau using the python library scipy.

c = [7, 9, 18, 17]
A = [
    [2, 4, 5, 7],
    [ 1, 1, 2, 2],
    [ 1, 2, 3, 3]
]
b = [42, 17, 24]

from scipy.optimize import linprog

print(linprog(c, A, b, method='simplex'))

According to this course from the University Le Havre where this example tableau was used to introduce the simplex method, I should be getting [3,0,7,0] for the variables and 147 for the minimized function.

Instead, I get [0,0,0,0] and 0.


Solution

  • The optimisation sense of your problem setup is incorrect. linprog assumes minimisation but the textbook asks for maximization. Invert the sign of c and the problem succeeds:

    import numpy as np
    from scipy.optimize import linprog
    
    c = -np.array((7, 9, 18, 17))
    A = [
        [2, 4, 5, 7],
        [1, 1, 2, 2],
        [1, 2, 3, 3]
    ]
    b = [42, 17, 24]
    
    
    result = linprog(c=c, A_ub=A, b_ub=b, method='highs')
    print(result)
    
            message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
            success: True
             status: 0
                fun: -147.00000000000006
                  x: [ 3.000e+00  0.000e+00  7.000e+00  0.000e+00]
                nit: 4
              lower:  residual: [ 3.000e+00  0.000e+00  7.000e+00  0.000e+00]
                     marginals: [ 0.000e+00  2.000e+00  0.000e+00  1.000e+00]
              upper:  residual: [       inf        inf        inf        inf]
                     marginals: [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00]
              eqlin:  residual: []
                     marginals: []
            ineqlin:  residual: [ 1.000e+00  0.000e+00  0.000e+00]
                     marginals: [-0.000e+00 -3.000e+00 -4.000e+00]
     mip_node_count: 0
     mip_dual_bound: 0.0
            mip_gap: 0.0