带有松弛变量的 Scipy 线性规划

Question

我想最小化一个目标函数，我根据来自 4Centers 的变量A, B1, B2, B3, B4计算该函数。

我的(简化)数据集如下所示：

Center1  Center2  Center3  Center4
A   10.0000  10.0000  10.0000  10.0000
B1   0.8415   0.9547   0.9460   0.9512
B2   0.9895   0.9443   0.9042   0.9634
B3   0.9460   0.9443   0.8101   0.9199
B4   0.9878   0.8362   0.9233   0.7909

我知道如何找到权重向量x，只需使用 scipy.optimize.linprog 即可最小化此目标函数

import numpy as np
from scipy.optimize import linprog
from numpy.linalg import multi_dot as dot
import pandas as pd
# minimise the costs across A and B variables in the 4 centres.
df = pd.DataFrame(np.array([[10, 10, 10, 10],
[0.8415, 0.9547, 0.9460, 0.9512],
[0.9895, 0.9443, 0.9042, 0.9634],
[0.9460, 0.9443, 0.8101, 0.9199],
[0.9878, 0.8362, 0.9233, 0.7909]]),
columns=['Center1', 'Center2', 'Center3', 'Center4'],
index=['A', 'B1', 'B2', 'B3', 'B4'])
# to reduce df (2-D array) to a 1-D array
lamb = np.array([0.1, 1, 1, 1, 1])
bounds = list(zip([-3, -3, -3, -3], [3, 3, 3, 3]))
A= None
b=None
c = dot([lamb,df.values]).squeeze()
res3 = linprog(c=c, A_ub=A, b_ub=b, bounds=bounds,
options={"disp": True})
# Solution vector of weights x
x = res3.x

我的问题是，我想惩罚B1.x, B2.x, B3.x, B4.x之间的最大差异。换句话说，在优化结束时，我希望解决方案集x，导致集合B1.x, B2.x, B3.x, B4.x中的绝对偏差最小。

>>df.loc[['B1', 'B2', 'B3', 'B4'],:].dot(x)
Out[24]: 
B1   -11.0802
B2   -11.4042
B3   -10.8609
B4   -10.6146
dtype: float64

我可以按如下方式计算所有Bi,Bj对之间的成对差异，因为我想要每对的最大差异，我同时查看Bi-Bj和Bj-Bi。

# pairwise differences
constraints = {'b1_b2' : df.loc['B1']-df.loc['B2'],
'b1_b3' : df.loc['B1']-df.loc['B3'],
'b1_b4' : df.loc['B1']-df.loc['B4'],
'b2_b3' : df.loc['B2']-df.loc['B3'],
'b2_b4' : df.loc['B2']-df.loc['B4'],
'b3_b4' : df.loc['B3']-df.loc['B4']}
const_df = pd.DataFrame(constraints)
A = pd.concat([const_df, -1*const_df], axis=1).T
b = np.array([1]*12) # the 1's here are arbitrary place holders.
res4 = linprog(c=c, A_ub=A, b_ub=b, bounds=bounds,
options={"disp": True})

上面的代码运行，但我不太明白如何包含松弛变量来惩罚A中这些成对差异的max()，这些差异目前只是Ax<=b约束形式。我知道线性规划可以用来解决绝对偏差问题。如果有人可以提供一些方向/简单的代码，我将不胜感激。

Answer 1

最小化一组变量的范围并不太困难：

minimize sum(j, c(j)*x(j)) + P*(maxx - minx)
B(i) = sum(j, b(i,j)*x(j))
minx ≤ B(i)
maxx ≥ B(i)

其中minx和maxx是附加变量，p是一些惩罚。这是线性和连续的，因此可以直接在 LP 模型中使用。