使用scipy / simplex的线性优化不能提供最优

Question

我正在尝试解决索尔·格拉斯在他的书“线性规划的图解指南”中描述的问题，第12ff页交通问题。

冰箱必须送到3家商店(S1、S2、S3)

以下列数量(10,8,7)

从工厂F1、F2到商店的运输成本是：

F1 (8,6,10) = 11 (来自F1的总发货量)

F2 (9,5,7) = 14 (来自F2的总发货量)

索尔·格拉斯给出了最小化的目标函数为：

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

约束条件c为：

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

他的最佳解决方案是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

我试着用scipy解决这个问题，但是得到了一个不同的结果，没有Saul Grass的解决方案(204比170)好。我的解决方案出了什么问题？

我的代码：

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)

我的结果是：

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

在给定等式约束时，应使用the doc for scipy.optimize.linprog、A_eq和b_eq参数。c应该是[8, 6, 10, 9, 5, 7]，而不是[-8, -6, -10, -9, -5, -7]，因为scipy.optimize.linprog最小化了目标函数。

因此，您可以执行以下操作：

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)

哪种打印

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.])