linear optimization with scipy / simplex do not deliver optimum

Question

I am trying to solve the problem described by Saul Grass in his book "Illustrated Guide to Linear Programming", page 12ff The transportation problem.

Refrigerators have to be delivered to 3 stores (S1,S2,S3)
in the following quantities (10,8,7)
Transportation costs from factories F1,F2 to the stores are:
F1 (8,6,10) = 11 (total shipment from F1)
F2 (9,5,7) = 14 (total shipment from F2)

Saul Grass gives the objective function to minimize as:

8x_11 + 6x_12 + 10x_13 + 9x_21 + 5x_22 + 7x_23

and the constraints c as:
x_11 + x_12 + x_13 + 0x_21 + 0x_22 + 0x_23 = 11
0x_11 + 0x_12 + 0x_13 + x_21 + x_22 + x_23 = 14
x_11 + 0x_12 + 0x_13 + x_21 + 0x_22 + 0x_23 = 10
0x_11 + x_12 + 0x_13 + 0x_21 + x_22 + 0x_23 = 8
0x_11 + 0x_12 + x_13 + 0x_21 + 0x_22 + x_23 = 7

His best solution is [10,1,0,0,7,7] :

10 x 8x_11 + 1 x 6x_12 + 0 x 10x_13 + 0 x 9x_21 + 7 x 5x_22 + 7 x 7x_23 = 170

I have tried to solve this with scipy, but get a different result that is not as good as Saul Grass' solution (204 vs. 170). What is wrong in my solution?

My code:

import numpy as np
from scipy.optimize import linprog

c = [-8,-6,-10,-9,-5,-7] 
A = [[1,1,1,0,0,0],[0,0,0,1,1,1],[1,0,0,1,0,0],[0,1,0,0,1,0],[0,0,1,0,0,1]] 
b = [11,14,10,8,7]
x0_bounds = (0, None)
x1_bounds = (0, None)
x2_bounds = (0, None)
x3_bounds = (0, None)
x4_bounds = (0, None)
x5_bounds = (0, None)

res = linprog(c, A_ub=A, b_ub=b,  bounds=(x0_bounds, x1_bounds,x2_bounds,x3_bounds, x4_bounds,x5_bounds), method='simplex', options={"disp": True})
print(res)

My result:

Optimization terminated successfully.
         Current function value: -204.000000 
         Iterations: 4
     fun: -204.0
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([0., 0., 0., 0., 0.])
  status: 0
 success: True
       x: array([ 0.,  4.,  7., 10.,  4.,  0.])

Answer 1

Seeing the doc for scipy.optimize.linprog, A_eq and b_eq parameters should be used when equality constraints are given. And c should be [8, 6, 10, 9, 5, 7], not [-8, -6, -10, -9, -5, -7], since scipy.optimize.linprog minimize the objective function.

Therefore, you can do like the following:

from scipy.optimize import linprog

c = [8, 6, 10, 9, 5, 7]
A = [[1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1], [1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 0, 1]]
b = [11, 14, 10, 8, 7]
x0_bounds = (0, None)
x1_bounds = (0, None)
x2_bounds = (0, None)
x3_bounds = (0, None)
x4_bounds = (0, None)
x5_bounds = (0, None)

res = linprog(c, A_eq=A, b_eq=b, bounds=(x0_bounds, x1_bounds, x2_bounds, x3_bounds, x4_bounds, x5_bounds),
              method='simplex', options={"disp": True})
print(res)

which prints

Optimization terminated successfully.
         Current function value: 170.000000  
         Iterations: 6
     con: array([0., 0., 0., 0., 0.])
     fun: 170.0
 message: 'Optimization terminated successfully.'
     nit: 6
   slack: array([], dtype=float64)
  status: 0
 success: True
       x: array([10.,  1.,  0.,  0.,  7.,  7.])