CODEWITHSUNDEEP
pythonscipylinear-programming
Rusty Robot
Rusty Robot

Reputation: 1365

Linear programming, unexpected solution with equality constraint

I'm trying to figure out what is wrong with my implementation, I expect the result to be [5, 10], I don't understand how it gets [7.5, 7.5], x1 should be half of x2.

from scipy.optimize import linprog
import numpy as np

c = [-1, -1]

A_eq = np.array([
    [1, 0.5],
    [1, -0.5],
])

b_eq = [15, 0]

x0_bounds = (0, None)
x1_bounds = (0, None)

res = linprog(
    c,
    A_eq=A_eq.transpose(),
    b_eq=b_eq,
    bounds=(x0_bounds, x1_bounds),
    options={"disp": True})

print res.x
# =>                                                                                                                                                                                 
# Optimization terminated successfully.                                                                                                                                              
#          Current function value: -15.000000                                                                                                                                        
#          Iterations: 2                                                                                                                                                             
# [ 7.5  7.5]

Update from the author:

As it was said matrix transposition is not needed here. The problem was in the matrix itself, in order to get desired result, which is [5, 10], it has to be:

A_eq = np.array([
    [1, 1],
    [1, -0.5],
])

Upvotes: 1

Views: 422

Answers (2)

Nelewout
Nelewout

Reputation: 6574

Per the scipy linprog docs:

Minimize: c^T * x

Subject to:

A_ub * x <= b_ub

A_eq * x == b_eq

So, you are now solving the following equations:

Minimize -x1 -x2

Subject to,*

x1 + x2 = 15 (i)
0.5 * x1 - 0.5 * x2 = 0 (ii)

Now, (ii) implies x1 = x2 (so your desired solution is infeasable), and then (i) fixes x1 = x2 = 7.5. So, the solution returned by linprog() is indeed correct. Since you are expecting a different result, maybe you should look into the way you translated your problem into code, as I think that's where you will find both the issue and the solution.

*) Since you are taking the transpose.

Upvotes: 2

Holt
Holt

Reputation: 37686

Your problem is:

x1 + x2 == 15
0.5 * x1 - 0.5 * x2 == 0

minimize -x1 -x2

So obviously you have x1 == x2 (second constraint), and thus x1 = x2 = 7.5 (first constraint).

Looking at your question, you probably don't want to transpose A:

res = linprog(
    c,
    A_eq=A_eq,
    b_eq=b_eq,
    bounds=(x0_bounds, x1_bounds),
    options={"disp": True}
)

Why gives you the problem:

x1 + 0.5 * x2 == 15
x1 - 0.5 * x2 == 0

minimize -x1 -x2

And you get x1 = 7.5 and x2 = 15 (the only possible values).

Upvotes: 2

Related Questions