线性规划实战

# 基本概念

线性规划可用来解决在约束条件下的最优解。

# 三要素

在利用线性规划解决问题之前，需要明确三个要素。

借用维基百科的农药例子，假设一个农夫有一块面积为A的农地、F肥料、P农药，打算种植小麦和大麦，每单位小麦/大麦的投入产出见表格，问如何种植才能卖出最高的价格。

	小麦	大麦
所需肥料	F1	F2
所需农药	P1	P2
售卖价格	S1	S2

决策变量: 需要通过计算得出的值。如例子中小麦的种植面积、大麦的种植面积
目标函数: 需要达成的目标。如例子中小麦和大麦的卖出价格之和
约束条件: 计算过程中受到的限制。如例子中的农地面积、肥料数量、农药数量、小麦/大麦最低种植面积(不为负)

# scipy.optimize.linprog

线性规划在标准形式上，发展出很多不同的形式，由于用的是scipy提供的包，所以以scipy.optimize.linprog所提供的形式来解决解析来的问题。

目标函数 $$ \min C^TX \tag{1} $$
约束条件 $$ A_{ub} X \leq b_{ub} \tag{2} $$ $$ A_{eq} X = b_{eq} \tag{3} $$ $$ l \leq X \leq u \tag{4} $$ 其中式$(2)$为不等式约束，式$(3)$为等式约束，式$(4)$为边界约束，

# demo上手

仍然以维基百科的农药例子为例，假设一个农夫有一块面积为$A=100$的农地、$F=200$肥料、$P=40$农药，打算种植小麦和大麦，每单位小麦/大麦的投入产出见表格，问如何种植才能卖出最高的价格。

	小麦	大麦
所需肥料	F1=20	F2=15
所需农药	P1=0.5	P2=0.2
售卖价格	S1=20	S2=10

# 决策变量

设种植小麦$x_1$，种植大麦$x_2$，矩阵表达为: $$ X = \left[ \begin{matrix} x_1 \cr x_2 \end{matrix} \right] \tag{5} $$

# 目标函数

由于linprog是最小化目标，而我们目标是最大化，所以需要对原始的目标函数乘-1
目标函数为: $$ \begin{align} target &= -(S1 \times x_1 + S2 \times x_2) \cr & = -(20\times x_1+10 \times x_2) \end{align} \tag{6} $$
转成矩阵形式为: $$ C^T = \left[ \begin{matrix} -20\ -10 \end{matrix} \right] \tag{7} $$

# 约束条件-不等式约束

面积 $$ \begin{align} x_1 + x_2 &\leq A \cr x_1 + x_2 &\leq 100 \end{align} \tag{8} $$
肥料 $$ \begin{align} F1 \times x_1 + F2 \times x_2 &\leq F \cr 20 \times x_1 + 15 \times x_2 &\leq 200 \end{align} \tag{9} $$
农药 $$ \begin{align} P1 \times x_1 + P2 \times x_2 &\leq P \cr 0.5 \times x_1 + 0.2 \times x_2 &\leq 40 \end{align} \tag{10} $$
整合成成矩阵形式为: $$ A_{ub} = \left[ \begin{matrix} 1 \ 1 \cr 20 \ 15 \cr 0.5 \ 0.2 \end{matrix} \right] \tag{11} $$

$$ b_{ub} = \left[ \begin{matrix} 100 \cr 200 \cr 40 \end{matrix} \right] \tag{12} $$

# 约束条件-等式约束

这个例子中没有等式约束。

如果问题改为一定要种满，那么就有等式约束$x_1+x_2 = 100$。

# 约束条件-边界约束

种植面积约束 $$ 0 \leq x_1, x_2 \leq \infty \tag{13} $$
整合成成矩阵形式为: $$ l = \left[ \begin{matrix} 0 \cr 0 \end{matrix} \right] \tag{14} $$

$$ u = \left[ \begin{matrix} \infty \cr \infty \end{matrix} \right] \tag{15} $$

# 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


from scipy.optimize import linprog

C = [[-20], [-10]]
A_ub = [[1, 1], [20, 15], [0.5, 0.2]]
b_ub = [[100], [200], [40]]
bounds = [(0, None), (0, None)]

# 计算
res = linprog(C, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

# 结果
print("是否有最优解: ", res.success)
print("最优解所能卖出价格: ", -1 * res.fun)
print("最优解所需种植小麦、大麦数量: ", res.x)

结果为:

1
2
3


是否有最优解:  True
最优解所能卖出价格:  200.0
最优解所需种植小麦、大麦数量:  [10.  0.]