scipy 复杂目标线性规划问题的计算机实现

x759pob2  于 2022-11-09  发布在  其他
关注(0)|答案(1)|浏览(123)

您好,我正在尝试解决以下问题:
我有多个食物类别集A、B、......,每个类别集的营养信息编码在向量x_a1、x_a2、......、x_b1、x_b2、......中。我还有一个向量y,它编码目标营养值。我想从食物集合中选择一种食物组合,使目标营养值y与所选食物营养向量之和之间的差异最小化:

min_x ||x−y||_2

其中x是所有选定食物的元素总和

x = ∑_i(x_{ij})

当i∈{A,B,C,...}且j∈{1,2,3,...}时,可以得到一个很好的结果.
为了用线性规划来解决这个问题,我用下面的方法来表达它:设Z是一个m × n的矩阵,包含n种食物和m种营养素,w_j是一个二进制值的向量,我试图最小化L1范数:

sum_i | sum_j(Z_{ij}w_j) - y |

通过分别引入松弛变量t_i和非负剩余变量s_i,线性地得到:

min sum_i(s_i + t_i)
s.t. sum_j(Z_{ij}w_j) - s_i + t_i = y for all i
     sum_j(w_j) >= 1 for j∈{A,B,C,...}

有人能给我指出方向,我将如何制定这在scipy?

2g32fytz

2g32fytz1#

scipy用作接口:

min c'x
     Ax=b
     Dx<=e
     l <= x <= u

你必须把你的问题硬塞进这个格式中。这一步并不总是容易的(但是,对你的问题来说并不太难)。如果你想使用更接近你的方程的东西,可以使用像PuLP或Pyomo这样的工具。CVXPY也是一种可能。
使用SCIPY时,最好找一张纸,画出矩阵的布局。列是变量,行是方程。类似于:

w(j)     s(i)     t(i)     rhs

 obj     0        1        1

 A       Z       -I        +I       y

 D      -1        0        0       -1 

 lo     -inf      0        0
 up     inf       inf      inf

相关问题