管理运筹学 - 课程体系介绍

课程概览#

运筹学（Operations Research）是一门以数学方法优化资源配置、实现科学决策的优化决策方法论。本课程的教学体系主要从系统分类、算法工具和实践应用三个维度展开：

问题体系：从线性性质、目标数量、变量性质与阶段特征四个维度理解运筹学问题的分类框架。
优化方法：掌握运筹学的核心求解方法与算法，包括图解法、单纯形法、表上作业法、逆推法等。
典型应用：学习运筹学在实际管理决策中的广泛应用，如生产计划、人力资源、设备更新、网络优化等。

本课程共包含 14 个核心知识点与 6 大核心求解方法，旨在通过理性分析和数学建模，实现决策的最优配置与效益最大化。

运筹学问题划分框架#

运筹学研究的优化问题极其丰富，可以通过以下四个核心维度进行系统性的分类和结构化，这为我们选择适当的求解方法提供了重要的理论依据。

1. 线性性质（Linearity）#

线性规划（Linear Programming）：目标函数与约束条件均为线性关系。
非线性规划（Non-linear Programming）：目标函数或约束条件中包含非线性项。

2. 目标数量（Objectives）#

单目标规划（Single-Objective Programming）：仅优化一个目标函数。
多目标规划（Multi-Objective Programming）：同时优化多个相互冲突的目标，旨在寻找 Pareto 最优解集（即无法在不使任何其他目标变差的情况下使某一目标变好的解）。

3. 变量性质（Variables）#

非整数规划（Continuous Programming）：决策变量可取连续实数值。
整数规划（Integer Programming）：决策变量必须取整数值（如包含用于表达“是/否”决策的 0-1 变量）。

4. 阶段特征（Stages）#

静态规划（Static Programming）：一次性决策，不考虑时间维度的序列影响。
动态规划（Dynamic Programming）：研究多阶段序贯决策，优化状态转移过程。

核心问题类型详解#

以下通过具体案例来详细剖析上述四类核心问题。

线性规划模型示例#

问题描述：某工厂在计划期内安排生产产品 Ⅰ 和 Ⅱ。已知生产单位产品所需的设备台时、原材料消耗及每件产品的利润如下表所示：

资源类型产品 Ⅰ 产品 Ⅱ 资源拥有量限制
设备 1 台时 2 台时 8 台时
原材料 A 4 kg 0 kg 16 kg
原材料 B 0 kg 4 kg 12 kg
单位利润 2 元 3 元
数学模型构建：设决策变量 $x_1$ 和 $x_2$ 分别为产品 Ⅰ 和 Ⅱ 的生产数量。为了实现总利润最大化，建立线性规划数学模型如下： $\max z = 2x_1 + 3x_2$ $\text{s.t. } \begin{cases} x_1 + 2x_2 \le 8 \\ 4x_1 \le 16 \\ 4x_2 \le 12 \\ x_1, x_2 \ge 0 \end{cases}$
核心特征：目标函数与约束条件均为变量的线性代数和，可行域呈凸多面体几何特征。
求解方法：常用 图解法（适用于二维变量）或 单纯形法（适用于多维变量）。

资源类型	产品 Ⅰ	产品 Ⅱ	资源拥有量限制
设备	1 台时	2 台时	8 台时
原材料 A	4 kg	0 kg	16 kg
原材料 B	0 kg	4 kg	12 kg
单位利润	2 元	3 元

多目标规划模型示例#

问题描述：一位投资商有 90,000 元资金，准备投资于股票 A 和 B（可同时投资）。股票的有关参数如下表：

股票名称单价（元）年收益（元/股·年）风险系数
股票 A 20 3 0.5
股票 B 50 4 0.2

股票 A 的年收益率为 $15\%$ ，股票 B 的年收益率为 $8\%$ 。高收益伴随着高风险。投资商希望设计一种投资方案，使得一年的总投资风险不高于 700，且投资收益不低于 10,000 元。
核心特征：需要同时兼顾收益最大化与风险最小化两个相互冲突的目标，解通常不是唯一的绝对最优解，而是 Pareto 最优解集。
求解方法：采用 加权法（给不同目标赋予权重）或 $\epsilon$-约束法（将次要目标转化为约束条件）。

股票名称	单价（元）	年收益（元/股·年）	风险系数
股票 A	20	3	0.5
股票 B	50	4	0.2

整数规划模型示例#

问题描述：某工厂面临三种生产方式决策（如选购不同自动化程度的设备）。高投资设备变动成本低、产能高；低投资设备变动成本高。令 $x_j$ 表示第 $j$ 种方式的产量， $c_j$ 表示变动成本， $k_j$ 表示固定成本。
核心特征：固定成本 $k_j$ 仅在选择该生产方式（即产量 $x_j > 0$ ）时才发生。因此，必须引入 0-1 变量 $y_j \in \{0, 1\}$ 表示是否采用第 $j$ 种生产方式，约束条件中会出现非连续的整数特征。
求解方法：分支定界法、割平面法。

动态规划模型示例#

问题描述（机器负荷分配问题）：某种机器可在高、低两种不同的负荷下生产。在高负荷下年产量函数为 $g(u_1) = 8u_1$ （ $u_1$ 为投入的完好机器数），年完好率 $a = 0.7$ ；在低负荷下年产量函数为 $h(y) = 5y$ ，年完好率 $b = 0.9$ 。初始完好机器数 $s_1 = 1000$ 台。问每年如何分配机器在高、低负荷下的生产，使 5 年内的总产量最高？
核心特征：决策过程与时间密切相关，整个过程可划分为前后衔接的 5 个阶段，当前阶段的决策将作为状态转移的输入影响下一阶段。
建模要素：需明确定义阶段、决策变量、状态变量与指标函数（递推方程），且必须满足最优性原理和无后效性。
求解方法：逆推法（动态规划的标准求解法，包括逆序解法和顺序解法）。

经典求解方法体系#

运筹学针对不同结构的问题，发展出了六大经典的求解方法：

1. 图解法（Graphical Method）#

适用场景：仅适用于二维决策变量的线性规划问题。
核心步骤：绘制约束条件边界直线 $\rightarrow$ 确定可行域凸多边形 $\rightarrow$ 绘制目标函数等值线并沿梯度方向平移 $\rightarrow$ 寻找与可行域边界最后的交点（最优顶点）。
优缺点：直观可视化，但无法处理高维问题。

2. 单纯形法（Simplex Method）#

适用场景：适用于任意维度的线性规划标准模型。
核心步骤：将模型标准化（引入松弛变量等） $\rightarrow$ 确定初始基可行解 $\rightarrow$ 计算检验数进行最优性检验 $\rightarrow$ 若未达最优，根据进基与出基规则进行基变换，更新单纯形表 $\rightarrow$ 迭代直至满足终止条件。
优缺点：计算效率高，便于计算机实现；但需要注意处理退化和循环现象。

3. 表上作业法（Transportation Method）#

适用场景：运输问题、指派问题等特殊结构的规划模型。
核心步骤：利用最小元素法（或西北角法）求初始基可行解 $\rightarrow$ 位势法（或闭回路法）检验 $\rightarrow$ 若非最优，通过闭回路调整法改进方案。

4. 逆推法（Backward Induction）#

适用场景：动态规划问题的标准求解算法。
核心思想：从最后一个阶段开始，逆向计算每个状态的最优决策，逐步推进至第一阶段，得出全局最优决策序列。

5. 标号法（Labeling Method）#

适用场景：图与网络优化问题（如最短路径问题、最大流问题）。
核心思想：通过在网络节点上进行动态标号（临时标号与永久标号），逐步搜寻并记录最优路径。

6. 决策树（Decision Tree）#

适用场景：风险型决策分析的可视化工具。
核心思想：绘制包含决策节点和状态（机会）节点的树状图，计算各方案的期望值，逆向选择最佳决策路径。

典型应用案例解析#

案例 1：生产计划问题（线性规划的应用）#

问题描述：公司面临外包协作或自行生产的决策。甲、乙、丙三种产品需要经过铸造、机械加工和装配三道工序。铸造工序中甲、乙可自产亦可外包，丙必须本厂自产。机加工和装配必须由本厂完成。
参数及工时限制：
- 本厂铸造工时限制 8000 小时，机加工限制 12000 小时，装配限制 10000 小时。
- 各项成本、售价、所需工时如下：
  - 甲：铸造工时 5 小时/件，自产铸造费 3 元/件，外包费 5 元/件；机加工工时 6 小时/件，机加工费 2 元/件；装配工时 3 小时/件，装配费 3 元/件；售价 23 元/件。
  - 乙：铸造工时 10 小时/件，自产铸造费 5 元/件，外包费 6 元/件；机加工工时 4 小时/件，机加工费 1 元/件；装配工时 2 小时/件，装配费 2 元/件；售价 18 元/件。
  - 丙：铸造工时 7 小时/件，自产铸造费 4 元/件，必须自产；机加工工时 8 小时/件，机加工费 3 元/件；装配工时 2 小时/件，装配费 2 元/件；售价 16 元/件。
决策变量设计：
- 设 $x_1, x_2, x_3$ 分别为自行铸造的甲、乙、丙产品件数。
- 设 $y_1, y_2$ 分别为外包铸造的甲、乙产品件数。
数学模型： $\max z = (23 - 3 - 2 - 3)x_1 + (23 - 5 - 2 - 3)y_1 + (18 - 5 - 1 - 2)x_2 + (18 - 6 - 1 - 2)y_2 + (16 - 4 - 3 - 2)x_3$ 即简化为： $\max z = 15x_1 + 13y_1 + 10x_2 + 9y_2 + 7x_3$ $\text{s.t. } \begin{cases} 5x_1 + 10x_2 + 7x_3 \le 8000 & \text{（铸造工时约束）} \\ 6(x_1 + y_1) + 4(x_2 + y_2) + 8x_3 \le 12000 & \text{（机加工工时约束）} \\ 3(x_1 + y_1) + 2(x_2 + y_2) + 2x_3 \le 10000 & \text{（装配工时约束）} \\ x_1, x_2, x_3, y_1, y_2 \ge 0 \end{cases}$

案例 2：人力资源分配问题（线性规划的应用）#

问题描述：公交线路每日 6 个时间段所需人员如下：6:00-10<00>（60 人）、10:00-14<00>（70 人）、14:00-18<00>（60 人）、18:00-22<00>（50 人）、22:00-2<00>（20 人）、2:00-6<00>（30 人）。每位司机和乘务人员连续工作 8 小时。
数学模型：设 $x_i$ ( $i=1,2,\dots,6$ ) 表示在第 $i$ 个时间段开始上班的人数。 $\min w = \sum_{i=1}^6 x_i$ $\text{s.t. } \begin{cases} x_6 + x_1 \ge 60 \\ x_1 + x_2 \ge 70 \\ x_2 + x_3 \ge 60 \\ x_3 + x_4 \ge 50 \\ x_4 + x_5 \ge 20 \\ x_5 + x_6 \ge 30 \\ x_i \ge 0, \text{且为整数} \end{cases}$

案例 3：套裁下料问题（整数规划的应用）#

问题描述：做 100 套钢架，每套需要 2.9m、2.1m、1.5m 的圆钢各一根。原材料每根长 7.4m，如何下料最省原料？

下料方案分析：经计算，有以下 8 种可能方案（单根原料切分方式）：

切分方案	2.9m 件数	2.1m 件数	1.5m 件数	总长度	废料头
方案 1	1	0	3	7.4m	0m
方案 2	2	0	1	7.3m	0.1m
方案 3	0	2	2	7.2m	0.2m
方案 4	1	2	0	7.1m	0.3m
方案 5	0	1	3	6.6m	0.8m
方案 6	1	1	1	6.5m	0.9m
方案 7	0	3	0	6.3m	1.1m
方案 8	0	0	4	6.0m	1.4m

模型设计：设 $z_k$ 为采用方案 $k$ 的原材料根数。目标是使用最少的原材料总根数： $\min N = \sum_{k=1}^8 z_k$ $\text{s.t. } \begin{cases} 1z_1 + 2z_2 + 0z_3 + 1z_4 + 0z_5 + 1z_6 + 0z_7 + 0z_8 \ge 100 & \text{（2.9m 需求限制）} \\ 0z_1 + 0z_2 + 2z_3 + 2z_4 + 1z_5 + 1z_6 + 3z_7 + 0z_8 \ge 100 & \text{（2.1m 需求限制）} \\ 3z_1 + 1z_2 + 2z_3 + 0z_4 + 3z_5 + 1z_6 + 0z_7 + 4z_8 \ge 100 & \text{（1.5m 需求限制）} \\ z_k \ge 0, \text{且为整数} \quad (k=1,2,\dots,8) \end{cases}$

案例 4：最大流问题（网络优化的应用）#

问题描述：运送石油从采地 $v_1$ 到销售点 $v_7$ 。网络中各段管道容量 $c_{ij}$ 不等。要求在不超过管道最大容量限制的前提下，求出每小时能运送的最大石油量。
基本原理：满足发点净流出量等于收点净流入量，中间节点的流入量等于流出量（流守恒定律）。

案例 5：经济订购批量 EOQ 模型（库存控制的应用）#

问题描述：益民食品批发部为 200 多家零售店供货。在 12 周的需求数据基础上（每周平均需求 3000 箱，总需求 36000 箱），通过权衡订货成本（每次订货固定支出）与存储成本（仓储变动支出），确定最佳订货批量 $Q$ ，以实现总库存管理成本最小化。

复习思考题#

简述运筹学问题划分的四个核心维度，并分别举例说明各个维度下的具体优化问题类型。
对比分析图解法与单纯形法的异同，说明二者各自的适用场景、优缺点以及它们之间的内在联系。
在套裁下料问题中，如何系统性地生成所有可能的切分方案？ 如果切分方案列举不全，会对最终模型的优化结果产生什么影响？

一罐可乐