第 1 章：运筹学与线性规划概述¶

场景： 你是一家奶茶店的老板。每天你要决定：卖出多少杯奶茶？每杯用多少原料？员工排班怎么安排？目标是让利润最大，同时不超过原料和员工时间的限制。这就是一个典型的运筹学问题——而当所有关系都是线性的，就变成了 线性规划 。

1.1 运筹学的起源与发展¶

运筹学的定义¶

运筹学是一门 应用数学 学科，研究如何在 有限的资源 下做出 最优决策 。

运筹学的学科体系¶

运筹学是一个大家族，包含多个分支：

1.2 线性规划的核心思想¶

什么是线性规划？¶

线性规划是一种优化方法，其中：

• 目标函数 是线性的（一次函数）
• 约束条件 也是线性的（一次不等式）
• 我们在约束条件划定的可行域中，寻找目标函数的最优值

设每天卖 \(x_1\) 杯 A 奶茶，\(x_2\) 杯 B 奶茶。则：

目标函数： \(\max \quad z = 5x_1 + 3x_2\)

约束条件： \(2x_1 + x_2 \le 10\) （牛奶约束）

\(x_1 + 2x_2 \le 8\) （茶叶约束）

\(x_1 \ge 0, \ x_2 \ge 0\) （非负约束）

这就是一个 线性规划问题 。

1.3 线性规划的发展历程¶

1.4 线性规划的典型应用场景¶

应用 1：生产计划（利润最大化）¶

某工厂生产两种产品 P1 和 P2：

           P1      P2      资源上限
原料 A     2       1          10
原料 B     1       2           8
单位利润   5       3           —

求：最大利润及生产方案

应用 2：成本最小化¶

某饲料厂需要配制饲料，要求：
  - 至少含 10 单位蛋白质
  - 至少含 8 单位维生素

原料 A：每 kg 含 1 单位蛋白质、1 单位维生素，价格 2 元
原料 B：每 kg 含 2 单位蛋白质、1 单位维生素，价格 3 元

求：满足营养需求时的最小成本

应用 3：运输调度¶

某公司从两个仓库向三个门店送货：

仓库 1 容量 200，仓库 2 容量 300
门店需求：甲 150，乙 200，丙 150
单位运费：

      甲   乙   丙
仓库1  3    5    4
仓库2  4    2    6

求：最小总运费及调度方案

1.5 线性规划的分类¶

根据解的情况，线性规划问题可分为四类：

要点总结¶

• 运筹学起源于二战军事研究，目标是优化资源配置和决策
• 线性规划 = 目标函数线性 + 约束条件线性
• 线性规划问题分为四类：唯一解、无穷多解、无界解、无可行解
• 典型应用：生产计划（利润最大化）、成本最小化、运输调度

课后练习¶

1. 建模练习 ：根据以下描述，建立线性规划模型： 某工厂生产两种产品 A 和 B。A 产品每件利润 4 元，B 产品每件利润 6 元。每件 A 需要 3 单位原材料和 1 单位工时，每件 B 需要 2 单位原材料和 2 单位工时。原材料每天供应 12 单位，工时每天供应 8 单位。

2. 判断练习 ：根据以下特征，判断线性规划问题的类型：

3. 某问题的可行域向一个方向无限延伸

4. 某问题的目标函数等值线与可行域的一条边完全重合

5. 思考题 ：线性规划和之后会学到的"整数规划"有什么区别？为什么有些问题必须要求变量是整数？

下一章预告： 第 1 章我们建立了线性规划的直觉。第 2 章将复习学习线性规划所需的数学基础——向量范数、矩阵运算、梯度和海森矩阵。这些工具将在后续章节中反复使用。

继续第 2 章：数学基础回顾 →