Wang Haihua
🍈 🍉🍊 🍋 🍌
在数学中，线性规划是一种具有一定约束条件的优化操作的方法。它是将我们关心的目标函数最大化或最小化。
术语“线性规划”由两个词组成:线性和规划。线性一词定义了多个变量之间的一阶关系。规划一词定义了从各种备选方案中选择最佳解决方案的过程
线性规划模型由线性函数组成，这些函数以线性方程的形式或不等式的形式受到约束。线性规划是一种重要的技术，可以用来寻找最优的资源利用。
线性规划广泛应用于数学和其他一些领域，如经济、商业、电信和制造领域。
LP的基本组成如下:
决策变量 决策变量是指问题中可以改变的量，例如生产多少货物，选择哪条路径等；线性规划的目标就是找到最优的决策变量。在线性规划中决策变量包括实数变量，整数变量，0-1变量等。
目标函数 目标函数就是把问题中的决策目标量化，一般分为最大化目标函数$\max$和最小化目标函数$\min$ 在线性规划中，目标函数为一个包含决策变量的线性函数，例如$\max x_1 + x_2$
约束条件 约束条件是指问题中各种时间，空间，人力，物力等限制。 在线性规划中约束条件一般表示为一组包含决策变量的不等式，例如$x_1 + 2x_2 \leq 10 $或者$4x_1 + 3x_2 \leq 24$。此外，决策变量的取值范围称为符号约束，例如$x_1 \geq 0, x_2 \geq 0$。
假设一家巧克力生产公司只生产两种类型的巧克力——A和B。这两种巧克力只需要牛奶和巧克力。制造A和B的每一个单位，需要以下数量:
公司厨房里有5个单位的牛奶和12个单位的巧克力。每卖出一笔，公司就赚一笔
现在，该公司希望实现利润最大化。它应该分别生产多少单位的A和B ?
公司将尽可能多地生产A和B以使利润最大化。但是牛奶和巧克力资源是有限的。 根据上上述信息，每单位A和B需要1单位牛奶。可供应的牛奶总量是5个单位。数学形式为 $$X + Y \le 5$$ 每单位的A和B需要3单位和2单位的巧克力。可供使用的巧克力总数量为12个单位。数学形式为： $$3 X + 2 Y \le 12$$ 而且，A和B的单位只能是整数。
我们还需要保证产量不能为负数，所以 $$X\ge 0,Y \ge 0$$ 为了使公司获得最大的利润，上述的不等式必须得到满足。 这样我们就将一个现实世界的问题转化为了一个数学模型。
将上述模型进行整理即为： $$ \begin{aligned} &\min \quad Z = 6X+5Y \\ &\text { s.t. }\left\{\begin{array}{l} {X + Y \le 5} \\ {3 X + 2 Y \le 12} \\ { X\ge 0,Y \ge 0} \\ { X,Y \in \mathbb{Z}} \end{array}\right. \end{aligned} $$
这里的目标函数和约束条件是使用矩阵乘积表示的，标准形式下为取目标函数最小值，约束条件取小于等于。但这都不影响线性规划的实质，将形式标准化也有助于编程求解。
对于只有两个自变量的线性规划问题，我们可以采用图解法进行求解；更多数量自变量的情况会有诸如内点法等方法，不过在数学建模问题求解中我们会借助软件进行求解，反而困难小了很多。重要的是将模型建立起来。
我们首先根据约束条件画出可行域（feasible fieled），如下图阴影部分
接下来将目标函数转换为$Y=\frac{6}{5}X+\frac{Z}{5}$的形式，这样要求$Z$最大，只要找到$Y=\frac{6}{5}X+\frac{Z}{5}$与可行域的交点中使函数截距最大的点即可。我们将直线$Y=\frac{6}{5}X$向左上方平移，最终找到点(2,3)既能保证点符合可行域要求，又能保证使目标函数值最大，这就是我们要求求得的最优点。
import matplotlib.pyplot as plt
%matplotlib inline
import numpy as np
plt.rcParams['font.family']=['SimHei']
plt.rcParams['axes.unicode_minus']=False
def area(x):
if x<2:
return 5-x
else:
return (12-3*x)/2
x = np.linspace(0,5,20)
y1 = (12-3*x)/2
y2 = 5-x
y3 = [area(i) for i in x]
z2 = -6/5*x+4
z4 = -6/5*x+8
z0 = -6/5*x+27/5
plt.figure(figsize=(5,6))
plt.plot(x,y1,linewidth=3,label=r'$X+Y=5$')
plt.plot(x,y2,linewidth=3,label=r'$3X+2Y=12$')
#plt.plot(x,z2,linestyle='--',label=r'$-\frac{6}{5}x+4$')
#plt.plot(x,z4,linestyle='--',label=r'$-\frac{6}{5}x+8$')
#plt.plot(x,z0,linestyle='--',label=r'$-\frac{6}{5}x+\frac{27}{5}$')
#plt.scatter([2],[3],marker='*',color='r',s=500)
plt.fill_between(x,y3,alpha=0.1,color='red')
plt.text(0.5,2,'可行域(feasible field)')
plt.ylim(0,6)
plt.xlim(0,5)
plt.xlabel('X')
plt.ylabel('Y')
plt.legend()
plt.grid()
plt.savefig('images/lp01.png')
def area(x):
if x<2:
return 5-x
else:
return (12-3*x)/2
x = np.linspace(0,5,20)
y1 = (12-3*x)/2
y2 = 5-x
y3 = [area(i) for i in x]
z2 = -6/5*x+4
z4 = -6/5*x+8
z0 = -6/5*x+27/5
plt.figure(figsize=(5,6))
plt.plot(x,y1,linewidth=3,label=r'$X+Y=5$')
plt.plot(x,y2,linewidth=3,label=r'$3X+2Y=12$')
plt.plot(x,z2,linestyle=':',label=r'$-\frac{6}{5}x+4$')
plt.plot(x,z4,linestyle=':',label=r'$-\frac{6}{5}x+8$')
plt.plot(x,z0,linestyle='--',label=r'$-\frac{6}{5}x+\frac{27}{5}$')
plt.scatter([2],[3],marker='*',color='r',s=500)
plt.fill_between(x,y3,alpha=0.1,color='red')
plt.text(0.5,2,'可行域(feasible field)')
plt.ylim(0,6)
plt.xlim(0,5)
plt.xlabel('X')
plt.ylabel('Y')
plt.legend()
plt.grid()
plt.savefig('images/lp02.png')
加工一种食用油需要精炼若干种原料油并把它们混合起来。原料油的来源有两类共5种：植物油VEG1，植物油VEG2，非植物油OIL1，非植物油OIL2，非植物油OIL3。购买每种原料油的价格（英镑/吨）如表5.1所示，最终产品以150英镑/吨的价格出售。
植物油和非植物油需要在不同的生产线上进行精炼。每月能够精炼的植物油不超过200吨，非植物油不超过250吨；在精炼过程中，重量没有损失，精炼费用可忽略不计。最终产品要符合硬度的技术条件。按照硬度计量单位，它必须在3~6之间。假定硬度的混合是线性的，而原材料的硬度如表5.2所示。 为使利润最大，应该怎样指定它的月采购和加工计划。
from model_insight.load_datasets import load_oil
df_oil = load_oil()
df_oil
| 价格 | 硬度 | |
|---|---|---|
| VEG1 | 110.0 | 8.8 |
| VEG2 | 120.0 | 6.1 |
| OIL1 | 130.0 | 2.0 |
| OIL2 | 110.0 | 4.2 |
| OIL3 | 115.0 | 5.0 |