线性规划（Linear Programming, LP）是一种数学优化方法，用于在给定约束条件下最大化或最小化目标函数。线性规划广泛应用于经济、工程、管理等领域，通过建立数学模型，帮助决策者找到最优解决方案。
一、线性规划数学模型
1.1 模型三要素
- 目标函数（Objective Function）
目标函数是线性规划中需要优化的函数，通常表示为线性形式。目标函数可以是需最大化的利润或最小化的成本。例如，在一个生产问题中，目标函数可以是某种商品的总利润，需要通过调整生产量来最大化这个值。目标函数的一般形式为：
其中：\(Z\)是目标值；\(c_1, c_2, \ldots, c_n\)是目标函数的系数；\(x_1, x_2, \ldots, x_n\) 是决策变量。
- 约束条件（Constraints）
约束条件是限制决策变量取值范围的线性不等式或等式。这些条件通常反映了资源的有限性、技术限制等。例如，在生产问题中，约束条件可能包括生产时间、原材料、资金等的限制。约束条件的一般形式为：
其中：\(a_{ij}\)是约束条件的系数；\(b_i\)是约束条件的右端常数；\(m\)是约束条件的数量。
- 非负性约束（Non-negativity Constraints）
在大多数实际问题中，决策变量通常需要非负，即每个变量必须大于或等于零。这反映了实际情况中物理量（如生产量、时间等）不能为负值。非负性约束的一般形式为：$$x_1 \geq 0, x_2 \geq 0, \ldots, x_n \geq 0$$
1.2 建模过程
问题描述：某公司生产两种产品A和B，每生产一单位A可获利3元，每生产一单位B可获利5元。生产A需要2小时工作时间和1单位原材料，生产B需要1小时工作时间和2单位原材料。现公司有100小时工作时间和80单位原材料。问公司应如何安排生产才能使利润最大化？
-
决策变量
- 设\(x_1\)为产品A的生产数量，
- 设\(x_2\)为产品B的生产数量。
-
目标函数
需要最大化利润，目标函数为：
-
约束条件
- \(2x_1 + x_2 \leq 100\)（工作时间约束）
- \(x_1 + 2x_2 \leq 80\) （原材料约束）
-
可行性约束
- \(x_1 \geq 0, x_2 \geq 0\)
通过上述步骤，建立了一个完整的线性规划数学模型。该模型可以通过图解法、单纯形法或其他优化算法求解，从而找到最优生产方案。线性规划不仅为决策者提供了一种系统化的决策工具，而且在资源优化配置方面具有重要意义。
1.3 图解法
\[\begin{align*} \max \quad & z = 2x_1 + 2x_2 \\ \text{s.t.} \quad & 5x_1 + 2x_2 \leq 15 \\ & 6x_1 + 2x_2 \leq 24 \\ & x_1 + x_2 \leq 5 \\ & x_1, x_2 \geq 0 \end{align*}\]import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import linprog
# 定义绘图的范围
x1 = np.linspace(0, 10, 400)
# 定义约束条件
y1 = 15 / 5
y2 = (24 - 6 * x1) / 2
y3 = 5 - x1
# 绘制可行域
plt.figure(figsize=(10, 8))
plt.plot(x1, y2, label=r'$6x_1 + 2x_2 \leq 24$')
plt.plot(x1, y3, label=r'$x_1 + x_2 \leq 5$')
plt.axhline(y=y1, color='r', linestyle='-', label=r'$5x_2 \leq 15$')
plt.xlim((0, 10))
plt.ylim((0, 10))
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
# 填充可行域
plt.fill_between(x1, 0, np.minimum(np.minimum(y1, y2), y3), where=(x1<=10), color='grey', alpha=0.5)
# 标记可行域
plt.legend()
# 求解线性规划问题
c = [-2, -1] # 因为linprog求解的是最小化问题，所以目标函数取反
A = [[6, 2], [1, 1], [0, 5]]
b = [24, 5, 15]
# 使用linprog求解
res = linprog(c, A_ub=A, b_ub=b, bounds=(0, None), method='highs')
if res.success:
# 绘制目标函数的最优解点
plt.plot(res.x[0], res.x[1], 'ro', label='Optimal Solution')
plt.legend()
plt.show()
print(f"Optimal value: {res.fun * -1:.2f}") # 最大化目标函数的最优值
print(f"Optimal solution: x1 = {res.x[0]:.2f}, x2 = {res.x[1]:.2f}")
else:
print("No solution found")
二、建模示例
1.1 例1
某公司在计划期内要安排生产A、B两种产品（假设市场销路很好）。生产单位产品的利润以及所需的劳动力、设备台时以及原材料的消耗资料如下表所示。
| 产品 | A | B | |
|---|---|---|---|
| 劳动力（工时） | 9 | 4 | 360 |
| 设备（台时） | 4 | 5 | 200 |
| 原材料（千克） | 3 | 10 | 300 |
| 单位产品利润 | 70 | 120 |
-
决策变量
- 设\(x_1\)为产品A的生产数量
- 设\(x_2\)为产品B的生产数量
-
目标函数
最大化利润，目标函数为：
- 约束条件
- 劳动力约束：\(9x_1 + 4x_2 \leq 360\)
- 设备台时约束：\(4x_1 + 5x_2 \leq 200\)
- 原材料约束：\(3x_1 + 10x_2 \leq 300\)
- 非负性约束：\(x_1 \geq 0, x_2 \geq 0\)
将上述内容整合，线性规划的数学模型为：
\[ \text{Maximize } Z = 70x_1 + 120x_2 \] \[ \text{subject to} \] \[ 9x_1 + 4x_2 \leq 360 \] \[ 4x_1 + 5x_2 \leq 200 \] \[ 3x_1 + 10x_2 \leq 300 \] \[ x_1 \geq 0, x_2 \geq 0\]这个数学模型可以通过图解法或使用线性规划求解器（如linprog）求解，从而找到最优的生产数量\(x_1\)和\(x_2\)以使得公司利润最大化。
1.2 例2
每种蓅菜含有的营养素成份是不同的, 从医学上知道每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时, 需要确定表中所列六种荒菜的供应量, 以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于 20 kg , 其它蔬菜的供应在一周内不多于 40 kg , 每周共需供应 140 kg 蔬菜, 为了使费用最小又满足营养素等其它方面的要求,问在下一周内应当供应每种疏菜各多少 kg ?
| 序号 | 蔬菜 | 铁 | 磷 | 维生素A | 维生素C | 烟酸 | 每千克费用 |
|---|---|---|---|---|---|---|---|
| 1 | 青豆 | 0.45 | 10 | 415 | 8 | 0.30 | 5 |
| 2 | 胡萝卜 | 0.45 | 28 | 9065 | 3 | 0.35 | 5 |
| 3 | 菜花 | 1.05 | 59 | 2550 | 53 | 0.60 | 8 |
| 4 | 白菜 | 0.40 | 25 | 75 | 27 | 0.15 | 2 |
| 5 | 甜菜 | 0.50 | 22 | 15 | 5 | 0.25 | 6 |
| 6 | 土豆 | 0.50 | 75 | 235 | 8 | 0.80 | 3 |
| 要求蔬菜提供的营养 | 铁 | 磷 | 维生素A | 维生素C | 烟酸 | 备注 |
|---|---|---|---|---|---|---|
| 要求值 | 6.00 | 25 | 17500 | 245 | 5.00 |
-
决策变量
设\(x_1, x_2, x_3, x_4, x_5, x_6\)分别为青豆、胡萝卜、菜花、白菜、甜菜、土豆的供应量（kg）。 -
目标函数
- 约束条件
满足营养需求，每种蔬菜的供应量上限，以及总供应量。- 铁的约束：
- 磷的约束：
- 维生素A的约束：
- 维生素C的约束：
- 烟酸的约束：
- 蔬菜供应量上限：
- 总供应量：
- 非负性约束：
- 数学模型
这个模型可以通过线性规划求解器（如 linprog）来求解，从而找到最小费用的蔬菜供应方案。