视频教程链接：
https://www.bilibili.com/video/BV13tHfzREnV/?p=2&spm_id_from=333.976.top_right_bar_window_history.content.click&vd_source=98031030bb7928a33e1b19aa75c4a7aa

图解法求解线性规划问题 Solving LPs with the graphical method

线性规划的基本性质

1. 若某一线性规划问题存在唯一最优解，则该最优解必在可行域的某个顶点处；
2. 若某一线性规划问题存在多个最优解，则其中至少有一个最优解在可行域的顶点处；
3. 若某一线性规划问题存在多个最优解，且已找到一个最优顶点，那么另一个最优解必为该顶点的相邻顶点，且两个最优顶点连线上的所有点均为最优解

例题

• 某工厂生产两种产品（A 和 B），单位产品的利润贡献分别为 9 英镑（产品 A）和 12 英镑（产品 B），即 \(c_1 = 9\)，\(c_2 = 12\)。
• 每种单位产品的生产均需消耗一定的机器工时和钻孔工时，具体工时消耗如下表所示：

产品	机器工时	钻孔工时
A	4	2
B	2	5

每周机器工时的最大可用量为 80 小时，钻孔工时的最大可用量为 120 小时。
决策问题：下周应生产两种产品各多少单位，才能实现利润最大化？

若有多个点的取值都为最大值，则存在多个最优解

数学规划（最优化）相关专业术语补充 terminology for mathematical programming (optimisation)

• 1. 不可行问题Infeasible problem： 不存在可行解，即约束条件之间相互矛盾。
• 2. 无界问题Unbounded problem： 目标函数在可行域内可以无限优化（最大化问题的最优值为 \(+\infty\)，最小化问题的最优值为 \(-\infty\)），即约束条件的限制作用不足。
• 3. 可解问题Solvable problem： 既非不可行问题，也非无界问题的规划问题。
• 4. 有效约束/无效约束 Active/inactive constraint： 这个约束对可行域的边界真的起作用，删掉它会改变可行域
  • 形式化定义：对于第 \(i\) 个约束 \(a_{i1}x_1 + \dots + a_{in}x_n \le b_i\)，设 \((x_1^*,\dots,x_n^*)\) 为问题的最优解。若 \[ a_{i1}x_1^* + \dots + a_{in}x_n^* = b_i \] 则该约束为**有效约束**；若 \[ a_{i1}x_1^* + \dots + a_{in}x_n^* < b_i \] 则该约束为无效约束。
• 5. 紧约束Binding constraint: 设约束是\(g(x) \le b\) 如果在某个点上刚好取等号： \(g(x) = b\) 那这个约束就叫紧约束
  • 通俗来说：这个约束在当前点“绷紧了”，没有松弛量了
  • 紧约束一定是有效约束，如果一个约束在你关心的点上已经取等号了，说明这个点正好压在它的边界上。那它显然不是完全没用的约束，至少在这个点它确实起了限制作用。
  • 多数情况下（非全部），有效约束也是紧约束，一个约束可能对整个可行域是有用的，但在你当前这个点上并没有刚好取等号

• 6. 松弛量Slack 针对“\(\le\)”型约束， \[ \text{松弛量} = \text{约束右端项} – \text{最优解处的约束左端项} \] 有效约束的松弛量为 \(0\)，无效约束的松弛量大于 \(0\)。
• 7. 剩余量Surplus: 针对“\(\ge\)”型约束， \[ \text{剩余量} = \text{最优解处的约束左端项} – \text{约束右端项} \]

第 2 讲：单纯形算法 Simplex algorithm

• 单纯形表 (simple tableau) 是为单纯形算法而设计的一种计算表，其功能类似于方程组的增广矩阵，易于进行基变换运算
• 它不是连续优化里“梯度下降/最速下降”那种概念。因为线性规划的可行域是一个多面体，单纯形法是在顶点和顶点之间跳，不是在平滑曲面上顺着梯度滑。

Slack and Surplus Variables 松弛变量与剩余变量

• 松弛变量：把“≤”约束改写成等式时，加上的非负变量
  • 表示“还剩多少容量”。非负很重要，后续判断是否使用2 phase method
• 剩余变量：把“≥”约束改写成等式时，减去的非负变量。
  • 表示“超过最低要求多少”。

为上述线性规划模型引入松弛变量x3​和x4​，将模型转化为标准型（所有约束为等式、所有变量非负）：

基本变量、非基本变量、基本可行解BFS(Basic Feasible Solution)

标准型中：

• 若有 n 个变量、m 个方程，且 n>m
• 则有 n−m 个自由度
• 可以令 n−m 个变量为 0，再解出剩下的 m 个变量。

定义：

• 非基本变量 (non-basic variables)：被设为 0 的变量
• 基本变量 (basic variables)：其他的变量（通过联立方程求出的变量）
• 如果求出的基本变量都满足非负，则得到一个基本可行解 (basic feasible solution, BFS)。

总结：

• 每个变量不是基本变量，就是非基本变量
• 基本变量个数 = 等式约束的数量
• 非基变量被令为 0，基变量为联立方程组的解
• 若基本变量都非负，则该解可行。

单纯形算法的几何与代数结合思路

• 单纯形算法的每一次迭代，都会得到一个基可行解
• 若模型存在可行解，单纯形算法通常以原点对应的顶点为初始迭代点，即令原决策变量为 0，松弛变量的取值等于约束条件的右端项
• 若当前基可行解并非最优解，算法会迭代至相邻顶点对应的另一个基可行解
• 迭代的本质是换基：一个非基变量转为基变量，同时一个基变量转为非基变量

初始化：初始基可行解为(0,0,80,120)，此时目标函数值Z=0。该解并非最优解，因为提高x1​或x2​的取值均可提升目标函数值。

核心要求：每个等式约束中，需有且仅有一个系数为 1 的基变量，后续所有基可行解的求解均需满足这一要求。

步骤

单纯形算法总结（一）

1. 加入松弛变量，将所有不等式约束转化为等式约束，构建初始单纯形表(基本变量个数 = 等式约束的数量)
2. 若目标函数行的所有系数均为正数，已得到最优解；若未满足，执行以下步骤；
3. 选取目标函数行中系数最负的变量为入基变量（若多个变量系数同为最负，任选其一即可）；
4. 将约束条件的RHS（右端项）与入基变量列对应的正系数做比值，选取比值最小的行确定主元，该行对应的基变量为出基变量。
   • 正的意思是最小比值检验只在入基列正元素中做。负的、零的都不参与。而不是算后取绝对值
5. 执行主元变换（初等行变换），使主元变为 1，且主元列的其余元素均为 0；
6. 除目标函数行外，其余每一行需有且仅有一个系数为 1 的基变量；
7. 目标函数行中，所有基变量的系数均为 0；
8. 重复上述迭代步骤，直至满足最优性检验条件：目标函数行的所有系数（除RHS）均 ≥0。

• 选入变量时，表里选“最负的”的原理：本质上等价于原目标函数里选“正系数最大的”。

比例检验原理

谁最先被压到 0，谁就成为“卡住你”的那个约束，那个变量就必须出基。

第三讲：单纯形法的特殊情况 special cases

退化现象

• 两个（或以上）非基变量在最终行中拥有相同的最小负系数Two (or more) non-basic variables have the same “most negative” coefficient in the last row
  • 可任选其中一个作为进基变量，最终仍能求得最优解
• 确定进基变量后，进行最小比值检验时，两个（或以上）基变量得出相同的最小比值
  • 理论上可任选其一，但可能引发一些问题：退化现象（但一般不需要考虑）

把单纯形法想成：你在一个房间的角点之间移动，每走一步都想让目标函数更优

• 进基变量：表示你准备沿着某个方向往前走
• 出基变量：表示谁先“顶到墙”，所以你最多只能走这么远
• 正常情况：只有一个变量先顶到墙。那你走了一步，到了一个新角点，事情很清楚
• 平局情况：有两个变量同时顶到墙。这说明你走到的位置，正好卡在一个“更尖的角”上，多个约束同时紧绷。这时如果你随便挑一个出基，数学上可以继续，但可能出现：基变了，但是你的人其实没挪地方，于是这一轮枢轴变换之后，目标函数值可能一点没改善，陷入死循环

无界问题

单纯形法中的判定特征：确定进基变量后，进行出基变量的最小比值检验时，进基变量所在列的所有系数均≤0。

底层逻辑回顾：

结合上一讲的可解模型，回顾最小比值检验的意义：

在利润最大化问题的初始单纯形表中，确定x2​为进基变量时，为保证解的可行性，x2​的取值最大只能增至 24，此时x4​的取值降至 0。

若进基变量x2​所在列的所有系数均≤0，意味着x2​的取值可无限增大，且始终满足约束条件，不会有任何非基变量被压成0

多重最优解

判定：最终行中有一个（或以上）非基变量的系数为 0。

核心逻辑

增大该非基变量的取值并将其选为进基变量时，目标函数值不会发生变化。

求解结果

对该非基变量执行一次迭代操作，可得到另一个基本可行最优解。

若一个线性规划问题存在多重最优解，则至少存在两个基本可行最优解，其余所有最优解均可表示为这两个基本可行最优解的凸组合。

Simplex Two-Phase method

定义：两相法是在没有明显的初始基本可行解（BFS）时解决线性规划问题的系统技术

两个阶段：

• 第一阶段：通过解决辅助问题找到任何可行的基本解决方案
• 第二阶段：从第一阶段发现的BFS开始优化原始目标功能

什么时候需要两阶段的方法？

同理第二题：

第3讲 – Optimisation modelling – QP and IP

• 到目前为止，我们只处理过线性规划模型(LP)。这类模型通常是利润最大化或成本最小化问题
• 它们是最容易求解的优化模型
• 单纯形法是首个被提出的优化模型求解方法 ——仅适用于线性规划 Simplex algorithm was the first proposed method for solving optimisation models – applicable only to LP’s
• 它并非线性规划的唯一求解方法；后续发展的内点法在软件包中同样（甚至更）常用
  It is not the only solution method for LP’s; the Interior Point Method, developed later on, is also (or more!) popular / implemented in software packages

Beyond LP’s 超越线性规划

• 凸优化问题可被标准求解器精确且较快求解。
• 凸优化问题：最小化目标为凸函数，可行域为凸集；此时局部最小值即为全局最小值（最优解）A convex optimization problem is one in which the objective function (to minimise) is a convex function of decision variables and the set of feasible solutions is convex That makes any local mimimum to be also a global minimum(and hence, an optimal solution)

重要的非线性优化模型类别

本节课聚焦优化建模（而非求解方法），重点讲解：

• 二次规划（QP）Quadratic Programming
  • 主要应用于金融领域；多数求解器可精确求解大规模 QP 问题。
• 整数规划（IP）Integer Programming
  • 主要用于逻辑约束建模；计算难度高，大规模模型需启发式算法。

二次规划（QP）

二次目标函数 + 线性约束 The objective function is quadratic of decision
variables; linear constraints

General form: Min \( x^T \cdot Q \cdot x + x^T \cdot c \)
subject to:
\( Ax = b \)
\( x \ge 0 \)

其中：

• \( x^T = (x_1, \dots, x_n) \)：决策变量向量
• \( Q \)：\( n \times n \) 对称矩阵
• \( c \)：\( n \) 维列向量
• \( A \)：\( m \times n \) 矩阵
• \( b \)：\( m \) 维列向量

• 未来股价 / 收益未知，属于随机变量。投资组合收益为随机变量，围绕期望值的波动被视为风险
• 常用方法：通过优化找到收益方差 / 风险最小的组合
• 目标函数（最小化）代表方差，约束包含可行性要求。将方差表示为组合权重的函数，需估计参数：
  • 各股票收益的方差
  • 每对股票收益间的协方差

整数规划（IP）

• 许多应用中，（部分）决策变量被约束为整数。
  • 全变量为整数：整数规划（IP）
  • 部分变量为整数：混合整数规划（MIP）
• 整数约束会极大增加求解难度。仅适用于中小规模（常近似求解）
• 优化软件（含 Excel 规划求解）可求解 IP/MIP，但仅适用于小规模问题
• 二进制变量Binary Variable，取值仅为 0 或 1，用于建模逻辑约束，代表 “是 / 否” 决策
  本节以金融资本预算为例

• 资本预算问题（IP）

可投资金：19000 英镑，共 4 个投资项目，全投或不投。
项目成本与净现值（NPV）如下：

	项目 1	项目 2	项目 3	项目 4
成本	6700	10000	5500	3400
NPV	8000	11000	6000	4000

目标：最大化净现值

二进制变量建模逻辑约束

• 恰好投资 2 个项目？
• 至多投资 2 个项目？
• 投资项目 2 则必须投资项目 4？
• 项目 2 和 4 至多投一个？
• 项目 2 和 4 至少投一个？
• 项目 2、3、4 中至多投 2 个？

阈值与基数约束（MIP）

某工厂可生产 3 种新型洗涤剂 A、B、C：

• 单位利润（英镑 / 千克）：13、10、15
• 单位成本（英镑 / 千克）：5、4、6
• 总预算：10000 英镑

另有生产线启动固定成本，要求：

• A：产量≥80kg，否则不生产
• B：产量≥70kg，否则不生产
• C：产量≥75kg，否则不生产

目标：最大化利润。

• 设x1​,x2​,x3​为 A、B、C 产量（千克），阈值约束：
• x1​≥80 或 x1​=0
• x2​≥70 或 x2​=0
• x3​≥75 或 x3​=0

建模方法：为每个连续变量添加二进制变量dj​

• dj​=1：生产产品j（xj​>0）
• dj​=0：不生产（xj​=0）

模型含 3 个连续变量 + 3 个整数 / 二进制变量，为混合整数规划（MIP）
阈值约束建模：

模型： 最大化：\( 13x_1 + 10x_2 + 15x_3 \)
约束：
\( 5x_1 + 4x_2 + 6x_3 \leq 10000 \)
\( 80d_1 \leq x_1 \leq 2000d_1 \)
\( 70d_2 \leq x_2 \leq 2500d_2 \)
\( 75d_3 \leq x_3 \leq 1668d_3 \)
\( d_1, d_2, d_3 \) 为二进制变量

QP+MIP 组合阈值约束

最低风险投资组合（QP）中，常加入阈值约束：

第4讲 – Duality Theory 对偶理论

• 对偶理论的基础在于每一个线性规划问题（原问题）都可以关联一个对偶问题，这两个问题的最优解之间存在紧密的联系。
• 对于最小化问题，我们先不急着直接求最优解，而是先从另一个角度构造一些“肯定不超过最优值”的数；这些数都是下界，而对偶问题就是在这些下界里找最大的那个。

对带约束的最优化问题，每个约束都引入一个乘子 \( y_i \)，称为Lagrange multipliers or dual variables
构造拉格朗日函数

• 如果 \( x^* \) 是原问题最优解，那么通常存在某个 \( y^* \)，使得 \( (x^*, y^*) \) 是拉格朗日函数的驻点（驻点stationary point即所有一阶偏导数均为 0 的点）。这给后面对偶变量的解释打了基础。
• 这只是最优性的必要条件（非充分条件）—— 但在部分情形下，该条件可直接确定最优解，如下例所示：

线性规划（LP）情形

同理可推得一般约束与变量的对偶规则：

对偶模型构造规则总结

• 原问题的每个约束对应对偶问题的一个变量
• 原问题的每个变量对应对偶问题的一个约束
• 若原问题为最大化，则对偶问题为最小化
• 对偶问题目标函数系数 = 原问题约束右端项（RHS）
• 对偶问题约束右端项（RHS） = 原问题目标函数系数
• 约束系数矩阵转置（如对偶第一个约束系数 = 原问题x1​的系数）

补充符号规则

• 最小化问题中：
  • ≥ 约束 ⇨ 对偶变量 ≥ 0
  • ≤ 约束 ⇨ 对偶变量 ≤ 0
  • 等式约束 ⇨ 对偶变量自由
• 最大化问题中：
  • ≤ 约束 ⇨ 对偶变量 ≥ 0
  • ≥ 约束 ⇨ 对偶变量 ≤ 0
  • 等式约束 ⇨ 对偶变量自由

定理（只是记录）

弱对偶性Weak duality 证明

互补松弛性 Complementary Slackness

• 直观含义：最优解处，约束的松弛 / 剩余变量与对应对偶变量的乘积为 0。
• 由强对偶性可进一步得出：对偶变量的最优值就是原问题对应约束的影子价格

核心结论汇总

1. 若原问题有最优解，则对偶问题也有最优解，且两者最优目标值相等；对偶变量最优值 = 原问题对应约束的影子价格。
2. 最优解处，约束松弛 / 剩余与对应对偶变量乘积为 0（互补松弛）。
3. 若原问题无界，则对偶问题不可行。

例题

写对偶问题的步骤：

例2: