线性规划期末题型操作手册

这份手册按”期末会怎么考”来整理。你可以把它当成考场流程卡：先识别题型，再套固定步骤，最后用一个小检查防止符号和方向出错。

如果你从来没学过线性规划，从”前置”部分开始读。如果你已经上过课，可以直接跳到”第 0 节考场总流程”。

前置：线性规划是什么？

如果你从来没听过”线性规划”四个字，这一节就是为你写的。读完你会知道：线性规划在干什么、为什么有用、长什么样。

从一个真实问题开始

小王开了一家木工坊，生产两种产品：桌子和椅子。

已知信息：

	桌子（每张）	椅子（每把）	库存上限
木材消耗	5 kg	2 kg	60 kg
工时消耗	4 小时	3 小时	48 小时
利润	50 元	30 元	—

小王的问题：这个月生产多少张桌子、多少把椅子，能赚最多钱？

你可能脱口而出：“全做桌子呗，桌子利润高！” 但算一算：

全做桌子：木材只够做 60÷5 = 12 张，工时只够做 48÷4 = 12 张。最多 12 张桌子，利润 = 12×50 = 600 元。
全做椅子：木材够做 60÷2 = 30 把，工时只够做 48÷3 = 16 把。最多 16 把椅子，利润 = 16×30 = 480 元。
混着做呢？比如 6 张桌子 + 8 把椅子：木材 5×6+2×8 = 46 ≤ 60 ✓，工时 4×6+3×8 = 48 ≤ 48 ✓，利润 = 300+240 = 540 元。

看到了吗？三种方案利润不同。“全做桌子”目前最好，但它真的是最好的吗？有没有更好的组合？

线性规划（Linear Programming，LP）就是帮你系统地找到最好方案的数学工具。

从问题里提炼六个概念

概念 1：决策变量（Decision Variable）

定义：你能自由调整的量，就是决策变量。

小王能控制的是”生产多少”：x₁ = 桌子数量，x₂ = 椅子数量。

概念 2：目标函数（Objective Function）

定义：你最终想让它变得最大（或最小）的那个表达式。

小王的目标是”总利润最大”：z = 50·x₁ + 30·x₂。

概念 3：约束条件（Constraint）

定义：你必须遵守的限制条件。

木材约束：5·x₁ + 2·x₂ ≤ 60
工时约束：4·x₁ + 3·x₂ ≤ 48
非负约束：x₁ ≥ 0，x₂ ≥ 0

概念 4：可行域（Feasible Region）

定义：所有同时满足全部约束条件的 (x₁, x₂) 组合，构成的区域。

可行域里的每个点都是一个”合法方案”。可行域外的点至少违反了一条约束。

概念 5：最优解（Optimal Solution）

定义：可行域中，使目标函数值最大（或最小）的那个点。

概念 6：线性（Linear）

定义：每个变量都只出现一次方（没有 x²、没有 x₁·x₂、没有 sin x），就是线性的。

线性规划 = 目标函数是线性的 + 约束条件全是线性的 + 求最优解。

完整建模

max z = 50·x₁ + 30·x₂

s.t.（subject to，"满足以下条件"的意思）
    5·x₁ + 2·x₂ ≤ 60    ... 木材
    4·x₁ + 3·x₂ ≤ 48    ... 工时
    x₁ ≥ 0, x₂ ≥ 0       ... 非负

一般形式

max (或 min)  z = c₁·x₁ + c₂·x₂ + ... + cₙ·xₙ

s.t.  a₁₁·x₁ + a₁₂·x₂ + ... + a₁ₙ·xₙ  ≤ (或 ≥ 或 =)  b₁
      a₂₁·x₁ + a₂₂·x₂ + ... + a₂ₙ·xₙ  ≤ (或 ≥ 或 =)  b₂
      ...
      x₁, x₂, ..., xₙ ≥ 0

变量多了以后画图就不行了（三维以上没法画），所以才需要单纯形法等算法来代替眼睛找最优解。

一句话总结：线性规划 = 在一堆线性约束围成的多面体里，找让线性目标函数最大（或最小）的角上的点。为什么是”角上的点”？因为线性函数在凸多面体上的最大/最小值一定在顶点取到。

前置：三种辅助变量

这三种变量是”化标准型”的核心工具。搞混它们是初学者最常犯的错误。

松弛变量（Slack Variable）

作用：把 ≤ 约束变成 = 等式。
物理含义：还剩多少余量（资源没用完的部分）。
加入方式：左边 +s，系数为 +1。

例子：木材约束 5x₁ + 2x₂ ≤ 60 → 加松弛变量 s₁：5x₁ + 2x₂ + s₁ = 60, s₁ ≥ 0。如果用了 46 kg 木材，s₁ = 14，表示还剩 14 kg。

剩余变量（Surplus Variable）

作用：把 ≥ 约束变成 = 等式。
物理含义：超出下限多少。
加入方式：左边 −s，系数为 −1。

例子：2x₁ + x₂ ≥ 1 → 减剩余变量 s₁：2x₁ + x₂ − s₁ = 1, s₁ ≥ 0。如果实际值是 3，s₁ = 2，表示比最低要求多了 2。

人工变量（Artificial Variable）

作用：给单纯形法提供一个合法的起步点。
物理含义：没有。 纯粹的数学工具。
加入方式：左边 +a，系数为 +1。
关键规则：最终解中必须等于 0。不为 0 说明原问题无可行解。

什么时候需要？ 约束是 ≥ 或 = 类型时，没有松弛变量提供单位列，单纯形法启动不了。加人工变量人为造出单位列。

	松弛变量 s	剩余变量 s	人工变量 a
处理哪种约束	≤	≥	≥ 或 =
加入方式	左边 +s	左边 −s	左边 +a
有无物理含义	有（剩余资源）	有（超出下限）	无
最优解中的值	≥ 0 均可	≥ 0 均可	必须 = 0
目标函数中的系数	0	0	−M 或 +M

记忆口诀：小于加松弛，大于减剩余再加人工，等于直接加人工。人工变量是”临时工”，用完必须走人。

0. 考场总流程

拿到一道线性规划题，先不要急着算，先做 3 秒判断：

只有两个变量、让你”图解”或”画图”：走图解法。
让你”化标准型”：只做变量替换、加松弛/剩余/人工变量，不求最优解。
给了普通线性规划并要求”单纯形”：先化最大化、<=、非负，再列表。
约束里没有天然单位列，或者有 =、>=：大概率要大 M 法或两阶段法。
出现”对偶""判断正误”：先写清楚原问题是 max 还是 min，再用符号表。
给了最终单纯形表、问系数和右端项范围：这是灵敏度分析。
出现”取整数”：普通单纯形只能给松弛解，最后必须用分支定界或割平面。

1. 图解法：二维线性规划判断解的类型

题型信号

只有 x1, x2 两个变量。
题目说”用图解法”。
要你判断：唯一解、无穷多个最优解、无界解、无可行解。

操作步骤

把每个不等式边界先画成直线。
用一个测试点判断保留哪一侧半平面。
所有半平面的交集就是可行域。
画目标函数等值线，例如 6x1 + 4x2 = k。
平移目标线：最大化往目标值变大的方向推，最小化往目标值变小的方向推。
看最后碰到可行域的地方：
- 碰到一个顶点：唯一最优解。
- 沿着一条边同时碰到：无穷多个最优解。
- 可行域存在，但目标能一直变好：无界。
- 半平面没有交集：无可行解。

例题 1.1

（1）min z = 6x1 + 4x2

s.t.  2x1 +  x2 >= 1
      3x1 + 4x2 >= 1.5
      x1, x2 >= 0

关键点：

约束线 ①: 2x₁ + x₂ = 1 → 过 (0.5, 0) 和 (0, 1)
约束线 ②: 3x₁ + 4x₂ = 1.5 → 过 (0.5, 0) 和 (0, 0.375)
两线交于 (0.5, 0)

可行域示意图：

  x₂
  ^
  |
1 |·  P(0,1)
  | · 
  |  ·    约束线①: 2x₁+x₂=1
  |   ·        可行域 = ①和②的"上方"交集
  |    ·       ///////////////////////
  |  ②·· ·  /////////////////////////
  |  /  ·   ·  //////////////////////
  | / ····Q(0.5,0)=最优解  //////////
  |/        |   ///// 可行域向右上无限延伸
  +-------- |---+---+---+---+---+---> x₁
  0       0.5   1
 
  目标等值线: 6x₁+4x₂=k （一族平行线）
  最小化 → 等值线从右上往左下推
  最后碰到可行域的点 = Q(0.5, 0)

最优解：x1 = 1/2, x2 = 0，z_min = 3。唯一最优解。

（2）max z = 4x1 + 8x2

约束给出：

x1 + x2 <= 5
x2 >= x1 + 8
x1, x2 >= 0

因为 x2 >= x1 + 8 已经要求 x2 很大，而 x1 + x2 <= 5 又要求二者之和很小，两者冲突，所以无可行解。

最容易错的地方

不要看到可行域向外延伸就直接说”无界”。要看目标函数是不是能沿着延伸方向一直变好。
最小化和最大化的平移方向相反。
>= 的半平面经常画反，最好用 (0,0) 测一下。

2. 化标准型：把陌生变量变成熟悉变量

题型信号

题目只说”化成标准型”。
出现 x1 <= 0、变量”无约束”、<= 约束、等式约束混在一起。

标准动作

变量必须非负：
- x <= 0：令 x = -u，其中 u >= 0。
- x 无约束：令 x = v - w，其中 v, w >= 0。
约束必须等式：
- <=：加松弛变量 +s。
- >=：减剩余变量 -s，如果要单纯形起步，通常还要加人工变量。
- =：保持等式，但可能需要人工变量。
右端项最好为非负；如果右端项为负，整行乘以 -1，不等号方向反向。
如果教材要求统一最大化，就令 Z = -z。

例题 1.2

原题：

min z = 2x1 - x2 + 2x3
 
s.t.
-x1 + x2 + x3 = 4
-x1 + x2 - x3 <= 6
x1 <= 0, x2 >= 0, x3 无约束

变量替换：

u = -x1 >= 0
x3 = v - w, v >= 0, w >= 0
s >= 0

标准型：

min z = -2u - x2 + 2v - 2w
 
s.t.
u + x2 + v - w = 4
u + x2 - v + w + s = 6
u, x2, v, w, s >= 0

速记

<= 加松弛，>= 减剩余；变量不听话，就拆成非负变量。

3. 单纯形法：表格题的主线

这一章只讲一件事：怎么用单纯形法，手算求解线性规划最大化问题。读之前你不需要会任何矩阵运算，只要会加减乘除就够了。

先把术语搞清楚

1. 基（Basis）：从所有变量里选出 m 个”主角”。标准型有 m 个等式约束，选 m 个线性无关的列组成矩阵 B，就是”基”。

2. 基变量（Basic Variable）/ 非基变量（Non-basic Variable）：被选中的 m 个是基变量（有值的主角），没被选中的是非基变量（暂时令它们 = 0）。

3. 基本可行解（Basic Feasible Solution，BFS）：非基变量全部 = 0，解出基变量的值，且基变量全部 ≥ 0。几何上对应可行域的一个顶点。单纯形法就是从一个顶点跳到相邻顶点，每跳一步目标函数都变好。

4. 检验数（Reduced Cost，σⱼ）：衡量”如果让非基变量 xⱼ 从 0 开始变大，目标函数能改善多少”。公式 σⱼ = cⱼ − c_B · B⁻¹ · aⱼ。初始表时基是松弛变量（c_B 全是 0），所以检验数直接等于目标函数系数 cⱼ。最大化问题：有正检验数就继续，全 ≤ 0 就最优。

5. 主元（Pivot Element）：进基列和出基行交叉的那个数。

6. 主元变换（Pivot Operation）：高斯消元的一轮——主元行 ÷ 主元，其他行用行运算把主元列消成 0。

题型信号

题目要求”用单纯形法求解”。
变量多于两个，不适合图解。
约束容易变成 <= 加松弛变量。

单纯形表格式

  基变量 |  x1   x2  ...  s1   s2  ...  |  b（右端项）
  -------+-------------------------------+-----------
   s1    |                               |
   s2    |                               |
   ...   |                               |
  -------+-------------------------------+-----------
  检验数σ |                               |  z 值

最大化问题的五步流程

第 0 步：化标准型。 ≤ 约束加松弛变量变等式。初始基 = 全部松弛变量。

第 1 步：看检验数行。 有正数？选最大正数的列 → 进基变量。全部 ≤ 0 → 最优，停！

第 2 步：最小比值法找出基行。 进基列中只看正元素，算 b_i ÷ 该元素。比值最小的行 → 出基行。（零和负数跳过）

第 3 步：做主元变换。 主元行 ÷ 主元；其他行 = 该行 − (该行在进基列的元素) × 新主元行。

第 4 步：更新基变量列。 出基换进基，回到第 1 步。

例题 1.5 完整演示（每一步都有表格）

max z = 3x1 + 5x2
s.t.
x1 <= 4
2x2 <= 12
3x1 + 2x2 <= 18
x1, x2 >= 0

化标准型：加 s1, s2, s3。

max z = 3x1 + 5x2 + 0s1 + 0s2 + 0s3
s.t.
x1 + s1 = 4
2x2 + s2 = 12
3x1 + 2x2 + s3 = 18
所有变量 >= 0

初始表（基：s1, s2, s3）：

  基   |  x1    x2    s1    s2    s3   |   b
  -----+-------------------------------+------
  s1   |   1     0     1     0     0   |   4
  s2   |   0     2     0     1     0   |  12
  s3   |   3     2     0     0     1   |  18
  -----+-------------------------------+------
   σ   |   3     5     0     0     0   |   0

检验数有正数（3 和 5），还不是最优。

第一次迭代：

选进基：σ(x2) = 5 最大 → x2 进基。

最小比值法：

s1 行：x2 列 = 0 → 跳过
s2 行：12 ÷ 2 = 6 ← 最小
s3 行：18 ÷ 2 = 9

s2 出基。主元 = s2 行 x2 列 = 2。

主元变换：

新 x2 行 = 旧 s2 行 ÷ 2：       [0, 1, 0, 1/2, 0 | 6]
s1 行不变（x2 列 = 0）：         [1, 0, 1, 0,   0 | 4]
新 s3 行 = 旧 s3 − 2×新 x2 行：  [3, 0, 0, -1,  1 | 6]
新 σ = 旧 σ − 5×新 x2 行：       [3, 0, 0, -5/2, 0]   z = 0 + 5×6 = 30

迭代 1 后的表：

  基   |  x1    x2    s1    s2    s3   |   b
  -----+-------------------------------+------
  s1   |   1     0     1     0     0   |   4
  x2   |   0     1     0   1/2     0   |   6
  s3   |   3     0     0    -1     1   |   6
  -----+-------------------------------+------
   σ   |   3     0     0  -5/2     0   |  30

σ(x1) = 3 > 0，继续。

第二次迭代：

选进基：σ(x1) = 3 唯一正数 → x1 进基。

最小比值法：

s1 行：4 ÷ 1 = 4
x2 行：x1 列 = 0 → 跳过
s3 行：6 ÷ 3 = 2 ← 最小

s3 出基。主元 = s3 行 x1 列 = 3。

主元变换：

新 x1 行 = 旧 s3 行 ÷ 3：        [1, 0, 0, -1/3, 1/3 | 2]
新 s1 行 = 旧 s1 − 1×新 x1 行：   [0, 0, 1,  1/3, -1/3 | 2]
x2 行不变（x1 列 = 0）：          [0, 1, 0,  1/2,    0 | 6]
新 σ = 旧 σ − 3×新 x1 行：        [0, 0, 0, -3/2,   -1]   z = 30 + 3×2 = 36

最终表：

  基   |  x1    x2    s1     s2      s3   |   b
  -----+-----------------------------------+------
  s1   |   0     0     1    1/3    -1/3   |   2
  x2   |   0     1     0    1/2      0    |   6
  x1   |   1     0     0   -1/3     1/3   |   2
  -----+-----------------------------------+------
   σ   |   0     0     0   -3/2     -1    |  36

所有检验数 ≤ 0，最优！

最优解：x1 = 2, x2 = 6, z = 36。s1 = 2（第一个约束还有余量）。

验证：x1 ≤ 4 → 2 ≤ 4 ✓，2x2 ≤ 12 → 12 ≤ 12 ✓，3x1+2x2 ≤ 18 → 18 ≤ 18 ✓。

迭代路径：

迭代    进基    出基    z 值    当前解
 0       —       —       0     (0, 0)      ← 原点
 1       x2      s2     30     (0, 6)      ← 沿边跳到顶点
 2       x1      s3     36     (2, 6)      ← 最优顶点

怎么判断解的类型

最优表中非基变量检验数都严格满足停止条件：唯一最优解。
有非基变量检验数等于 0：可能有无穷多个最优解。
选中进基列后，该列没有正元素：无界。
人工变量最后仍然为正：原问题无可行解。

4. 大 M 法与两阶段法：处理”没有现成起点”的题

题型信号

约束中有 = 或 >=。
加松弛/剩余变量后，没有明显的单位列作为初始基。
题目直接写”大 M 法”或”两阶段法”。

为什么要人工变量

单纯形法要从一个”基本可行解”出发。松弛变量有时能直接提供单位列；但等式约束或 >= 约束经常没有这个起点。人工变量就是临时搭的台阶，帮你先起步，最后必须把它赶出基。

大 M 法步骤

给没有单位列的约束加人工变量 a_i。
最大化问题中，目标函数减去 M a_i；最小化问题中，目标函数加上 M a_i。M 是一个人为设定的极大正数（想象成 10 亿）。
修正目标行：因为人工变量是基变量，必须通过行运算让它在目标行的检验数变 0。
正常做单纯形。
如果最优时人工变量仍大于 0，原问题无可行解。

大 M 法完整计算例题

max z = 3x1 + 2x2
 
s.t.
  x1 + x2 = 5          ... (1) 等式约束，没有松弛变量
  2x1 + x2 <= 8         ... (2)
  x1, x2 >= 0

化标准型：约束 (2) 加松弛 s1，约束 (1) 加人工变量 a1：

max z = 3x1 + 2x2 + 0·s1 − M·a1
 
s.t.
  x1 +  x2 + a1      = 5
  2x1 + x2      + s1 = 8
  所有变量 >= 0

修正目标行：a1 是基变量（c = −M），目标行加上 M×(约束 1)：

原目标行：      z = 3x1 + 2x2 − M·a1
加 M×(约束1)：  + M·x1 + M·x2 + M·a1 = 5M
修正后：        z = (3+M)x1 + (2+M)x2 + 0·s1 + 0·a1 − 5M

初始表（基：a1, s1）：

         | x1    x2    s1    a1  | b
---------|------------------------|-------
  a1     |  1     1     0     1  |  5
  s1     |  2     1     1     0  |  8
---------|------------------------|-------
  σ      | 3+M   2+M    0     0  | z=−5M

第一次迭代：

进基：x1（σ = 3+M 最大）。比值：a1 行 5/1 = 5，s1 行 8/2 = 4。s1 出基。主元 = 2。

新 x1 行 = 旧 s1 ÷ 2：             [1, 1/2, 1/2, 0 | 4]
新 a1 行 = 旧 a1 − 1×新 x1 行：     [0, 1/2, -1/2, 1 | 1]

         | x1    x2      s1       a1  | b
---------|----------------------------|-------
  a1     |  0    1/2    −1/2       1  |  1
  x1     |  1    1/2     1/2       0  |  4
---------|----------------------------|-------
  σ      |  0   1/2+M/2  −3/2−M/2  0  | z=12−M

a1 还在基中（= 1），z = 12−M（仍很差），σ(x2) = 1/2+M/2 > 0，继续。

第二次迭代：

进基：x2。比值：a1 行 1/(1/2) = 2，x1 行 4/(1/2) = 8。a1 出基！（人工变量被赶走了）主元 = 1/2。

新 x2 行 = 旧 a1 ÷ (1/2)：         [0, 1, -1, 2 | 2]
新 x1 行 = 旧 x1 − (1/2)×新 x2 行： [1, 0, 1, -1 | 3]

最终表：

         | x1    x2    s1    a1  | b
---------|------------------------|-------
  x2     |  0     1    −1     2  |  2
  x1     |  1     0     1    −1  |  3
---------|------------------------|-------
  σ      |  0     0    −1  −M−1  | z=13

所有检验数 ≤ 0，a1 不在基中 → 原问题有可行解。

最优解：x1 = 3, x2 = 2, z = 13。验证：x1+x2 = 5 ✓，2x1+x2 = 8 ✓。

如果迭代结束时人工变量仍在基中且 > 0，说明原问题无可行解。

两阶段法步骤

第一阶段：只关心人工变量，令目标为”让人工变量总和变成 0”。
若第一阶段最优值不为 0，原问题无可行解。
若第一阶段最优值为 0，删掉人工变量，带回原目标函数。
第二阶段：从第一阶段得到的可行基继续做普通单纯形。

例题 1.6 与 1.7

1.6（1）最终结果：

x* = (5/2, 5/2, 5/2, 0)
z_max = 15

用两阶段法求 1.6（1）时，最终结果相同。

最容易错的地方

人工变量不是原问题变量，最后不能留在答案里。
大 M 法里 M 的惩罚方向要和目标方向匹配：最大化写 -M a_i。
两阶段法第一阶段不是求原目标，而是先求可行起点。
初始表必须做”修正目标行”——不修正的话基变量的检验数不是 0，整个计算全错。

5. 对偶问题：符号表比硬背更可靠

题型信号

题目说”写出对偶问题”。
原问题里有混合的 <=、>=、= 和变量符号限制。

原问题为 min 时的对偶规则

原问题元素	对偶里对应什么
第 i 个约束是 `>=`	`yi >= 0`
第 i 个约束是 `<=`	`yi <= 0`
第 i 个约束是 `=`	`yi` 无约束
变量 `xj >= 0`	第 j 个对偶约束是 `<=`
变量 `xj <= 0`	第 j 个对偶约束是 `>=`
变量 `xj` 无约束	第 j 个对偶约束是 `=`

如果原问题是 max，上表方向对称反过来：常见标准形式 max, <=, x>=0 的对偶就是 min, >=, y>=0。

例题 1.15

对偶问题：

max w = 15y1 + 20y2 - 5y3
 
s.t.
-y1 - 5y2 + y3 >= -5
 5y1 - 6y2 - y3 <= -6
-3y1 + 10y2 - y3 = -7
 
y1 >= 0, y2 <= 0, y3 无约束

对偶判断题 2.2

答案：

（1）错
（2）错
（3）错
（4）对

应试理解：

原问题可行，不代表对偶一定可行；原问题可能是无界的。
对偶无可行解，不代表原问题一定无可行解；原问题也可能无界。
弱对偶要分方向：max 原问题的可行目标值 <= min 对偶的可行目标值；min 原问题则反过来。
在同一个原问题形式固定后，对偶问题是唯一的；换等价写法可能长得不一样，但本质等价。

6. 对偶单纯形法：先”最优性对”，再修”可行性”

题型信号

题目明确说”用对偶单纯形法”。
初始表中检验数已经满足最优性条件，但右端项 b 有负数。

操作步骤

看右端项 b。如果有负数，说明当前解不可行。
选最负的 b_i 所在行作为出基行。
进基列选择（对偶版最小比值法）：在出基行中只看负元素（因为 b_r < 0，主元必须是负数才能让 b_r 变正）。对每个负元素 a_{rj}，计算 |σ_j / a_{rj}|（检验数绝对值 ÷ 该元素绝对值），选使这个比值最小的列作为进基列。
做主元变换。
重复直到所有 b_i >= 0，此时若检验数仍满足最优性条件，就得到最优解。

如果出基行没有负元素，说明原问题无可行解。

例题 2.11

min z = 4x1 + 12x2 + 18x3
 
s.t.
x1 + 3x3 >= 3
2x2 + 2x3 >= 5
x1, x2, x3 >= 0

化标准型（减剩余变量，取负让 s1,s2 做初始基）：

-x1 - 3x3 + s1 = -3      (b1 = -3)
-2x2 - 2x3 + s2 = -5     (b2 = -5)

初始检验数 σ(x1)=4, σ(x2)=12, σ(x3)=18，全 ≥ 0（min 问题最优性满足），但 b 有负数 → 用对偶单纯形法。

第一次迭代：b2 = −5 最负，第 2 行出基。出基行负元素：x2 列(−2)、x3 列(−2)。比值：|12/(−2)| = 6，|18/(−2)| = 9。x2 进基（比值 6 最小）。

最终答案：

x* = (0, 3/2, 1)
z_min = 36

小白理解

普通单纯形像是”从可行点出发，慢慢变得更优”。对偶单纯形反过来：它一开始可能不是可行点，但方向已经对了；它要做的是把右端项修到非负。

7. 灵敏度分析：看最终表，不要重算全题

题型信号

题目给了最终单纯形表。
问 c1, c2 在什么范围内变化，最优解不变。
问右端项 b1, b2 在什么范围内变化，最优基不变。

大白话：灵敏度分析到底在问什么？

你已经算出了最优解。老板突然说”原材料涨价了”或”仓库容量变了”——你需要从头再算吗？

不需要。 灵敏度分析帮你回答：参数变化多少以内，当前最优方案还是最优的？

两类核心问题：

目标函数系数变了 → 看检验数还是不是都 ≤ 0
右端项变了 → 看基变量值还是不是都 ≥ 0

前置知识：B⁻¹ 怎么从最终表里直接读出来

B（基矩阵，Basis Matrix）：最终表中基变量在原始问题中对应的系数列组成的矩阵。

B⁻¹ 不需要手算矩阵求逆！ 它就藏在最终单纯形表的松弛变量列里。

为什么？初始表中松弛变量列是单位矩阵 I。经过行变换后变成 B⁻¹·I = B⁻¹。

一句话：最终表里 s1、s2、s3 那几列的数字（不含 σ 行），就是 B⁻¹。直接抄。

用例题 1.5 的最终表做完整演示

最终表：

  基   |  x1    x2    s1     s2      s3   |   b
  -----+-----------------------------------+------
  s1   |   0     0     1    1/3    -1/3   |   2
  x2   |   0     1     0    1/2      0    |   6
  x1   |   1     0     0   -1/3     1/3   |   2
  -----+-----------------------------------+------
   σ   |   0     0     0   -3/2     -1    |  36

基变量：s1, x2, x1。c_B = [0, 5, 3]。

B⁻¹ = s1、s2、s3 三列：

B⁻¹ = | 1     1/3    -1/3 |
       | 0     1/2     0   |
       | 0    -1/3     1/3 |

目标函数系数变化：c1（x1 的系数）在什么范围内最优基不变？

原 c1 = 3，设变成 3+Δ，c_B 变成 [0, 5, 3+Δ]。

重算非基变量（s2、s3）的检验数：

σ(s2) = 0 − [0, 5, 3+Δ]·[1/3, 1/2, −1/3]ᵀ
      = −(5/2 − (3+Δ)/3) = −3/2 + Δ/3
      要求 ≤ 0 → Δ ≤ 9/2 → c1 ≤ 15/2
 
σ(s3) = 0 − [0, 5, 3+Δ]·[−1/3, 0, 1/3]ᵀ
      = −(3+Δ)/3 = −1 − Δ/3
      要求 ≤ 0 → Δ ≥ −3 → c1 ≥ 0

结论：c1 ∈ [0, 15/2]。x1 的利润在 0 到 7.5 之间变化，当前方案不用调整。

右端项变化：b2（第二个约束 2x2 ≤ 12 的右端，原值 = 12）在什么范围内最优基不变？

设 b2 = 12+Δ。新基变量值 = B⁻¹ · [4, 12+Δ, 18]ᵀ：

s1 值 = 1×4 + (1/3)(12+Δ) + (−1/3)×18 = 2 + Δ/3    ≥ 0 → Δ ≥ −6
x2 值 = (1/2)(12+Δ) = 6 + Δ/2                        ≥ 0 → Δ ≥ −12
x1 值 = (−1/3)(12+Δ) + (1/3)×18 = 2 − Δ/3            ≥ 0 → Δ ≤ 6

取交集：Δ ∈ [−6, 6]，即 b2 ∈ [6, 18]。

方法总结

分析什么	什么会变	保持什么不变	怎么算
目标系数	检验数	所有非基变量 σ ≤ 0	σⱼ = cⱼ − c_B^{new} · [最终表 xⱼ 列]
右端项	基变量值	所有基变量 ≥ 0	x_B^{new} = B⁻¹ · b^{new}

口诀：改系数→重算检验数→解 σ ≤ 0。改右端→重算 B⁻¹b→解 x_B ≥ 0。B⁻¹ 从松弛变量列直接读。

例题 1.21 答案

例题 1.21 的原问题与例题 1.5 不同，但方法完全一样：

（1）目标函数系数变化范围：c1 ∈ [15/4, 25/2]，c2 ∈ [4, 40/3]。

（2）右端项变化范围：b1 ∈ [24/5, 16]，b2 ∈ [9/2, 15]。

（3）当目标函数变为 max z = 12x1 + 4x2 时：x* = (8/5, 0)，z_max = 96/5。

（4）当右端项由 [9, 8]^T 变为 [11, 19]^T 时：x* = (11/3, 0)，z_max = 110/3。

最容易错的地方

“最优解不变”和”最优基不变”不是完全同一句话。灵敏度分析通常先判断最优基是否不变。
单独改变 c1、单独改变 c2 的范围，不能直接当作二者同时改变的充分条件。
右端项变化只先看可行性；目标系数变化只先看检验数。

8. 整数规划：先放松，再把小数赶走

题型信号

题目写了 x1, x2 取整数。
目标和约束仍然是线性的。

普通线性规划的最优解可能是小数，但整数规划答案必须是整数点。

8.1 分支定界法

操作步骤

先去掉整数限制，求 LP（Linear Programming，线性规划）松弛问题。
如果松弛解已经全是整数，直接结束。
如果某个变量是小数，例如 x1 = 3.5，就分两支：
- x1 <= 3
- x1 >= 4
每个分支再求松弛问题。
如果某支的上界不可能超过当前最好整数解，就剪枝。
直到所有分支都被剪掉或得到整数解。

例题：整数规划 2.2

最终最优整数值：

z_max = 5

最优整数解有三个：

(x1, x2) = (3, 2), (4, 1), (5, 0)

考场写法建议

分支定界题不要只写最后一个点。要写清楚：

松弛问题最优值是多少。
从哪个小数变量分支。
哪些分支被剪枝，剪枝理由是什么。
最终整数最优解和最优值。

8.2 割平面法（Gomory 割）

大白话

割平面法不分支，而是加一条新约束（一刀切），把当前的小数最优点切掉，但不切掉任何整数可行点。然后在新的更小可行域上重新求最优。

操作步骤

先求 LP 松弛问题的最优单纯形表。
找一个右端项 b_i 不是整数的基变量行。
对该行的每个系数和右端值，计算小数部分。
用小数部分构造 Gomory 割约束。
加入原问题，用对偶单纯形法继续迭代。
直到最优解全为整数。

“小数部分”的定义（最容易搞错的地方）

小数部分 f(a) = a − ⌊a⌋，其中 ⌊a⌋ 是下取整（不超过 a 的最大整数）。

对正数很好理解：f(3.75) = 3.75 − 3 = 0.75

对负数要特别小心：

⌊−0.25⌋ = −1（不是 0！因为 −1 是不超过 −0.25 的最大整数）
所以 f(−0.25) = −0.25 − (−1) = 0.75
再看一个：⌊−1.5⌋ = −2，所以 f(−1.5) = −1.5 − (−2) = 0.5

小数部分永远在 [0, 1) 范围内，不管原数正负。

Gomory 割公式

设选中行的方程为（j 只遍历非基变量）：

x_i + Σ_j a_{ij}·x_j = b_i

Gomory 割为：

Σ_j f(a_{ij})·x_j ≥ f(b_i)

引入松弛变量后：−Σ_j f(a_{ij})·x_j + s_new = −f(b_i)。右端项为负，用对偶单纯形法继续。

完整小例子

假设最终表某行是：x1 + 0.5·x3 − 0.25·s1 = 3.75

量	原值	⌊ ⌋	小数部分 f
b	3.75	3	0.75
a(x3)	0.5	0	0.5
a(s1)	−0.25	−1	0.75

割约束：0.5·x3 + 0.75·s1 ≥ 0.75

加入表后：−0.5·x3 − 0.75·s1 + s_new = −0.75，然后用对偶单纯形法迭代。

例题：整数规划 2.3

最终答案：

x* = (4, 3)
z_max = 55

小白理解

割平面不是随便加一条线，而是加一条”不会切掉任何整数可行点，但会切掉当前小数最优点”的线。这样每加一次，松弛问题就更接近真正的整数规划。

9. 考前速查表

题型	一眼识别	先做什么	最后写什么
图解法	两个变量、让画图	画可行域	解类型 + 最优点 + 最优值
标准型	变量符号混乱、只让化标准	变量替换	等式约束 + 非负变量
单纯形	普通 LP 求最优	加松弛变量建初表	最优解、最优值、解类型
大 M / 两阶段	有 `=`, `>=`, 人工变量	加人工变量 + 修正目标行	人工变量为 0 后的原变量答案
写对偶	出现”对偶”	先定 max/min	对偶目标、约束、变量符号
判断题	理论判断	用弱对偶/强对偶/可行无界关系	对/错 + 一句话理由
对偶单纯形	RHS 有负、要求对偶单纯形	选最负 RHS 行	RHS 全非负时读答案
灵敏度	给最终表	读 B⁻¹（松弛变量列）	范围或新最优解
分支定界	取整数	先求松弛问题	分支、剪枝、整数最优解
割平面	取整数、要求割平面	取小数部分构造 Gomory 割	整数最优解

10. 最后一页检查清单

交卷前按这个顺序扫一遍：

目标方向有没有写错：max/min。
不等号方向有没有因为乘以 -1 而反过来。
自由变量有没有拆成两个非负变量。
x <= 0 有没有写成 x = -u, u >= 0。
人工变量最后是否为 0。
对偶变量符号是否和原约束方向匹配。
灵敏度范围端点是否用分数保留。
整数规划最后的解是否真的满足整数和全部约束。
如果有多个最优整数解，是否全部列出。
最后答案有没有写清楚 x* 和 z*。

zero2hero 学习笔记

探索

线性规划期末题型操作手册

线性规划期末题型操作手册

前置：线性规划是什么？

从一个真实问题开始

从问题里提炼六个概念

概念 1：决策变量（Decision Variable）

概念 2：目标函数（Objective Function）

概念 3：约束条件（Constraint）

概念 4：可行域（Feasible Region）

概念 5：最优解（Optimal Solution）

概念 6：线性（Linear）

完整建模

一般形式

前置：三种辅助变量

松弛变量（Slack Variable）

剩余变量（Surplus Variable）

人工变量（Artificial Variable）

0. 考场总流程

1. 图解法：二维线性规划判断解的类型

题型信号

操作步骤

例题 1.1

最容易错的地方

2. 化标准型：把陌生变量变成熟悉变量

题型信号

标准动作

例题 1.2

速记

3. 单纯形法：表格题的主线

先把术语搞清楚

题型信号

单纯形表格式

最大化问题的五步流程

例题 1.5 完整演示（每一步都有表格）

怎么判断解的类型

4. 大 M 法与两阶段法：处理”没有现成起点”的题

题型信号

为什么要人工变量

大 M 法步骤

大 M 法完整计算例题

两阶段法步骤

例题 1.6 与 1.7

最容易错的地方

5. 对偶问题：符号表比硬背更可靠

题型信号

原问题为 min 时的对偶规则

例题 1.15

对偶判断题 2.2

6. 对偶单纯形法：先”最优性对”，再修”可行性”

题型信号

操作步骤

例题 2.11

小白理解

7. 灵敏度分析：看最终表，不要重算全题

题型信号

大白话：灵敏度分析到底在问什么？

前置知识：B⁻¹ 怎么从最终表里直接读出来

用例题 1.5 的最终表做完整演示

目标函数系数变化：c1（x1 的系数）在什么范围内最优基不变？

右端项变化：b2（第二个约束 2x2 ≤ 12 的右端，原值 = 12）在什么范围内最优基不变？

方法总结

例题 1.21 答案

最容易错的地方

8. 整数规划：先放松，再把小数赶走

题型信号

8.1 分支定界法

操作步骤

例题：整数规划 2.2

考场写法建议

8.2 割平面法（Gomory 割）

大白话

操作步骤

“小数部分”的定义（最容易搞错的地方）

Gomory 割公式

完整小例子

例题：整数规划 2.3

小白理解

9. 考前速查表