线性规划建模的核心要素与适用条件# 建立线性规划（LP）模型需要满足以下基本条件：
目标函数 ：问题的目标能够用单一的数值指标来表示，且是决策变量的线性组合。备选方案 ：存在多种可行的决策方案，并且有充足的相关技术数据。资源约束 ：实现目标的路径受到一定客观条件的限制，且这些限制条件可用线性等式或不等式来描述。 建模的三大核心要素为：决策变量（D.V.） 、目标函数（O.F.） 、约束条件（s.t.） 。建模时切记不能遗漏非负约束 。
典型应用领域与案例剖析# 1. 套裁下料问题（合理利用线材）#
问题描述 ：工厂要制作 100 套钢架，每套需要 2.9 m 2.9\text{ m} 2.9 m 2.1 m 2.1\text{ m} 2.1 m 1.5 m 1.5\text{ m} 1.5 m 7.4 m 7.4\text{ m} 7.4 m
方案穷举分析 ：
首先需列出所有单根原材料可行的切分方案。设切分后废料长度小于 1.5 m 1.5\text{ m} 1.5 m ≥ 1.5 m \ge 1.5\text{ m} ≥ 1.5 m
方案编号 2.9 m 2.9\text{ m} 2.9 m 2.1 m 2.1\text{ m} 2.1 m 1.5 m 1.5\text{ m} 1.5 m 方案总长 (m \text{m} m 废料头长 (m \text{m} m 方案 1 2 0 1 7.3 0.1 方案 2 1 2 0 7.1 0.3 方案 3 1 1 1 6.5 0.9 方案 4 1 0 3 7.4 0.0 方案 5 0 3 0 6.3 1.1 方案 6 0 2 2 7.2 0.2 方案 7 0 1 3 6.6 0.8 方案 8 0 0 4 6.0 1.4
模型构建 ：
设 x k x_k x k k k k k = 1 , … , 8 k=1,\dots,8 k = 1 , … , 8 min z = ∑ k = 1 8 x k \min z = \sum_{k=1}^8 x_k min z = ∑ k = 1 8 x k s.t. { 2 x 1 + x 2 + x 3 + x 4 ≥ 100 （满足 2.9 m 需求） 2 x 2 + x 3 + 3 x 5 + 2 x 6 + x 7 ≥ 100 （满足 2.1 m 需求，注意：方案6切2根，方案7切1根） x 1 + x 3 + 3 x 4 + 2 x 6 + 3 x 7 + 4 x 8 ≥ 100 （满足 1.5 m 需求） x k ≥ 0 , 且为整数 ( k = 1 , 2 , … , 8 ) \text{s.t. } \begin{cases} 2x_1 + x_2 + x_3 + x_4 \ge 100 & \text{（满足 2.9 m 需求）} \\ 2x_2 + x_3 + 3x_5 + 2x_6 + x_7 \ge 100 & \text{（满足 2.1 m 需求，注意：方案6切2根，方案7切1根）} \\ x_1 + x_3 + 3x_4 + 2x_6 + 3x_7 + 4x_8 \ge 100 & \text{（满足 1.5 m 需求）} \\ x_k \ge 0, \text{且为整数} \quad (k=1,2,\dots,8) \end{cases} s.t. ⎩ ⎨ ⎧ 2 x 1 + x 2 + x 3 + x 4 ≥ 100 2 x 2 + x 3 + 3 x 5 + 2 x 6 + x 7 ≥ 100 x 1 + x 3 + 3 x 4 + 2 x 6 + 3 x 7 + 4 x 8 ≥ 100 x k ≥ 0 , 且为整数 ( k = 1 , 2 , … , 8 ) （满足 2.9 m 需求） （满足 2.1 m 需求，注意：方案 6 切 2 根，方案 7 切 1 根） （满足 1.5 m 需求）
计算结果 ：经单纯形法（或分支定界法）计算，最优解为：x 1 = 30 , x 2 = 10 , x 4 = 50 x_1=30, x_2=10, x_4=50 x 1 = 30 , x 2 = 10 , x 4 = 50 x k = 0 x_k=0 x k = 0
关键洞察 ：在建立此类模型时，约束条件采用“≥ \ge ≥ = = =
2. 配料问题（原材料混合优化）#
问题描述 ：某厂要用三种原材料 C、P、H 调配出三种不同规格的产品 A、B、D。已知产品规格要求、销售单价、每天原料供应限制及原料单价如下表所示：
产品 规格要求 销售单价（元） A 原材料 C 比例不低于 50 % 50\% 50% 25 % 25\% 25% 50 B 原材料 C 比例不低于 25 % 25\% 25% 50 % 50\% 50% 35 D 无特殊要求 25
原材料 每日供应量限制 成本单价（元） C 100 65 P 100 25 H 60 35
模型构建 ：
由于原料和产品有交叉混合关系，使用双下标变量 x i j x_{ij} x ij i i i i ∈ { A , B , D } i \in \{A, B, D\} i ∈ { A , B , D } j j j j ∈ { C , P , H } j \in \{C, P, H\} j ∈ { C , P , H } 极大化总利润 max z = 总销售收入 − 总原材料成本 \text{极大化总利润 } \max z = \text{总销售收入} - \text{总原材料成本} 极大化总利润 max z = 总销售收入 − 总原材料成本 max z = 50 ∑ j x A j + 35 ∑ j x B j + 25 ∑ j x D j − 65 ∑ i x i C − 25 ∑ i x i P − 35 ∑ i x i H \max z = 50 \sum_{j} x_{Aj} + 35 \sum_{j} x_{Bj} + 25 \sum_{j} x_{Dj} - 65 \sum_{i} x_{iC} - 25 \sum_{i} x_{iP} - 35 \sum_{i} x_{iH} max z = 50 ∑ j x A j + 35 ∑ j x B j + 25 ∑ j x D j − 65 ∑ i x i C − 25 ∑ i x i P − 35 ∑ i x i H s.t. { x A C ≥ 0.5 ( x A C + x A P + x A H ) （产品 A 中 C 的比例限制） x A P ≤ 0.25 ( x A C + x A P + x A H ) （产品 A 中 P 的比例限制） x B C ≥ 0.25 ( x B C + x B P + x B H ) （产品 B 中 C 的比例限制） x B P ≤ 0.50 ( x B C + x B P + x B H ) （产品 B 中 P 的比例限制） x A C + x B C + x D C ≤ 100 （原材料 C 供应量约束） x A P + x B P + x D P ≤ 100 （原材料 P 供应量约束） x A H + x B H + x D H ≤ 60 （原材料 H 供应量约束） x i j ≥ 0 ( ∀ i , j ) \text{s.t. } \begin{cases} x_{AC} \ge 0.5(x_{AC} + x_{AP} + x_{AH}) & \text{（产品 A 中 C 的比例限制）} \\ x_{AP} \le 0.25(x_{AC} + x_{AP} + x_{AH}) & \text{（产品 A 中 P 的比例限制）} \\ x_{BC} \ge 0.25(x_{BC} + x_{BP} + x_{BH}) & \text{（产品 B 中 C 的比例限制）} \\ x_{BP} \le 0.50(x_{BC} + x_{BP} + x_{BH}) & \text{（产品 B 中 P 的比例限制）} \\ x_{AC} + x_{BC} + x_{DC} \le 100 & \text{（原材料 C 供应量约束）} \\ x_{AP} + x_{BP} + x_{DP} \le 100 & \text{（原材料 P 供应量约束）} \\ x_{AH} + x_{BH} + x_{DH} \le 60 & \text{（原材料 H 供应量约束）} \\ x_{ij} \ge 0 \quad (\forall i, j) \end{cases} s.t. ⎩ ⎨ ⎧ x A C ≥ 0.5 ( x A C + x A P + x A H ) x A P ≤ 0.25 ( x A C + x A P + x A H ) x B C ≥ 0.25 ( x B C + x B P + x B H ) x B P ≤ 0.50 ( x B C + x B P + x B H ) x A C + x B C + x D C ≤ 100 x A P + x B P + x D P ≤ 100 x A H + x B H + x D H ≤ 60 x ij ≥ 0 ( ∀ i , j ) （产品 A 中 C 的比例限制） （产品 A 中 P 的比例限制） （产品 B 中 C 的比例限制） （产品 B 中 P 的比例限制） （原材料 C 供应量约束） （原材料 P 供应量约束） （原材料 H 供应量约束）
3. 人力资源规划（快递分拣排班问题）#
问题描述 ：分拣部共有 11 台分拣机，分拣效率为 500 件/h 500\text{ 件/h} 500 件 /h
全日制职工 ：工作 8 小时，班次可选：10:00-18<00>, 11:00-19<00>, 12:00-20<00>，日薪 150 元。非全日制职工 ：工作 5 小时，班次可选：13:00-18<00>, 14:00-19<00>, 15:00-20<00>，日薪 80 元。快件时限 ：12<00> 前到达的必须在 14<00> 前处理完；15<00> 前到达的必须在 17<00> 前处理完；所有快件必须在当天 20<00> 前处理完。
模型构建 ：
设 x 1 , x 2 , x 3 x_1, x_2, x_3 x 1 , x 2 , x 3 y 1 , y 2 , y 3 y_1, y_2, y_3 y 1 , y 2 , y 3 15<00> - 18<00> 时段内，所有 6 个班次的员工均处于在岗状态。因此，最大在岗人数之和受限于分拣机总量：
x 1 + x 2 + x 3 + y 1 + y 2 + y 3 ≤ 11 x_1 + x_2 + x_3 + y_1 + y_2 + y_3 \le 11 x 1 + x 2 + x 3 + y 1 + y 2 + y 3 ≤ 11 500 件 500\text{ 件} 500 件 总工资支出最少 的 LP 模型。
目标函数：
min z = 150 ( x 1 + x 2 + x 3 ) + 80 ( y 1 + y 2 + y 3 ) \min z = 150(x_1 + x_2 + x_3) + 80(y_1 + y_2 + y_3) min z = 150 ( x 1 + x 2 + x 3 ) + 80 ( y 1 + y 2 + y 3 ) 4. 连续投资问题#
问题描述 ：某部门有 10 万元初始资金，考虑在今后五年内为 A、B、C、D 四个项目投资，期末本利总额最大。
项目 A ：1-4 年每年初可投，次年末回收本利 115 % 115\% 115% 项目 B ：第 3 年初可投，5 年末回收本利 125 % 125\% 125% 项目 C ：第 2 年初可投，5 年末回收本利 140 % 140\% 140% 项目 D ：1-5 年每年初可购买公债，当年末还本息 106 % 106\% 106%
决策变量设计 ：
设 x i A , x i B , x i C , x i D x_{iA}, x_{iB}, x_{iC}, x_{iD} x i A , x i B , x i C , x i D i i i 资金动态平衡方程构建 （每年初投资额等于手中可支配资金）：
第 1 年 ：x 1 A + x 1 D = 100 , 000 x_{1A} + x_{1D} = 100,000 x 1 A + x 1 D = 100 , 000 第 2 年 ：x 2 A + x 2 C + x 2 D = 1.06 x 1 D x_{2A} + x_{2C} + x_{2D} = 1.06 x_{1D} x 2 A + x 2 C + x 2 D = 1.06 x 1 D 第 3 年 ：x 3 A + x 3 B + x 3 D = 1.15 x 1 A + 1.06 x 2 D x_{3A} + x_{3B} + x_{3D} = 1.15 x_{1A} + 1.06 x_{2D} x 3 A + x 3 B + x 3 D = 1.15 x 1 A + 1.06 x 2 D 第 4 年 ：x 4 A + x 4 D = 1.15 x 2 A + 1.06 x 3 D x_{4A} + x_{4D} = 1.15 x_{2A} + 1.06 x_{3D} x 4 A + x 4 D = 1.15 x 2 A + 1.06 x 3 D 第 5 年 ：x 5 D = 1.15 x 3 A + 1.06 x 4 D x_{5D} = 1.15 x_{3A} + 1.06 x_{4D} x 5 D = 1.15 x 3 A + 1.06 x 4 D 额度限制 ：x 3 B ≤ 40 , 000 x_{3B} \le 40,000 x 3 B ≤ 40 , 000 x 2 C ≤ 30 , 000 x_{2C} \le 30,000 x 2 C ≤ 30 , 000
目标函数 （第五年末拥有的资金总额最大）：
max z = 1.15 x 4 A + 1.25 x 3 B + 1.40 x 2 C + 1.06 x 5 D \max z = 1.15 x_{4A} + 1.25 x_{3B} + 1.40 x_{2C} + 1.06 x_{5D} max z = 1.15 x 4 A + 1.25 x 3 B + 1.40 x 2 C + 1.06 x 5 D 复习思考题#
在配料优化问题中，如何使用双下标决策变量 x i j x_{ij} x ij 请以产品 A 中原材料 C 的比例限制为例，写出转换后的线性约束形式。分析连续投资问题中的资金流动态平衡特征 。如果第一年投项目 A，这笔资金在第二年和第三年初的状态分别是什么？为什么不需要在第四年和第五年设置项目 A 的投资变量？在人力资源规划中， overlapping shifts（重叠班次）会对资源总量约束（如本案中的设备台数限制）产生什么影响？ 如何用数学约束表达这种重叠性限制？ 
