本文最后更新于5 天前，其中的信息可能已经过时，如有错误请留言
图解法求解线性规划问题 Solving LPs with the graphical method
线性规划的基本性质
- 若某一线性规划问题存在唯一最优解，则该最优解必在可行域的某个顶点处；
- 若某一线性规划问题存在多个最优解，则其中至少有一个最优解在可行域的顶点处；
- 若某一线性规划问题存在多个最优解，且已找到一个最优顶点，那么另一个最优解必为该顶点的相邻顶点，且两个最优顶点连线上的所有点均为最优解
例题
- 某工厂生产两种产品（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. 松弛变量：把“≤”约束改写成等式时，加上的非负变量
- 7. 剩余变量：把“≥”约束改写成等式时，减去的非负变量。
第 2 讲：单纯形算法 Simplex algorithm
- 单纯形表 (simple tableau) 是为单纯形算法而设计的一种计算表，其功能类似于方程组的增广矩阵，易于进行基变换运算
- 它不是连续优化里“梯度下降/最速下降”那种概念。因为线性规划的可行域是一个多面体，单纯形法是在顶点和顶点之间跳，不是在平滑曲面上顺着梯度滑
相关定义
- 标准型（所有约束为等式、所有变量非负）：
- 标准型中：
- 若有 n 个变量、m 个方程，且 n>m
- 则有 n−m 个自由度
- 可以令 n−m 个变量为 0，再解出剩下的 m 个变量。
- 非基本变量 (non-basic variables)：被设为 0 的变量
- 基本变量 (basic variables)：其他的变量（通过联立方程求出的变量）
- 基本可行解 (basic feasible solution, BFS)：求出的基本变量都满足非负
注意：
- 每个变量不是基本变量，就是非基本变量
- 基本变量个数 = 等式约束的数量
单纯形算法的几何与代数结合思路
- 单纯形算法的每一次迭代，都会得到一个基可行解
- 若模型存在可行解，单纯形算法通常以原点对应的顶点为初始迭代点，即令原决策变量为 0，松弛变量的取值等于约束条件的右端项
- 若当前基可行解并非最优解，算法会迭代至相邻顶点对应的另一个基可行解
- 迭代的本质是换基：一个非基变量转为基变量，同时一个基变量转为非基变量
初始化：初始基可行解为(0,0,80,120)，此时目标函数值Z=0。该解并非最优解，因为提高x1或x2的取值均可提升目标函数值。
核心要求：每个等式约束中，需有且仅有一个系数为 1 的基变量，后续所有基可行解的求解均需满足这一要求。
步骤
单纯形算法总结（一）
- 加入松弛变量，将所有不等式约束转化为等式约束，构建初始单纯形表(基本变量个数 = 等式约束的数量)
- 此时判断是否根据是否有 = / 大于号的约束是否使用2phase 方法
- 否则需要先构造辅助问题，再用非人工变量替换人工变量的优化问题
- 若目标函数行的所有系数均为正数，已得到最优解；若未满足，执行以下步骤；
- 选取目标函数行中系数最负的变量为入基变量（若多个变量系数同为最负，任选其一即可）；
- 将约束条件的RHS（右端项）与入基变量列对应的正系数做比值，选取比值最小的行确定主元，该行对应的基变量为出基变量。
- 正的意思是最小比值检验只在入基列正元素中做。负的、零的都不参与。而不是算后取绝对值
- 执行主元变换（初等行变换），使主元变为 1，且主元列的其余元素均为 0；
- 除目标函数行外，其余每一行需有且仅有一个系数为 1 的基变量；
- 目标函数行中，所有基变量的系数均为 0；
- 重复上述迭代步骤，直至满足最优性检验条件：目标函数行的所有系数（除RHS）均 ≥0。
- 结果：基变量的值即为RHS对应的值，非基变量的值为0，最有值为Z对应的RHS
- 选入变量时，表里选“最负的”的原理：本质上等价于原目标函数里选“正系数最大的”。
比例检验原理
谁最先被压到 0，谁就成为“卡住你”的那个约束，那个变量就必须出基。
示例1:
- 示例2
第三讲：单纯形法的特殊情况 special cases
退化现象 degenerate
- 两个（或以上）非基变量在最终行中拥有相同的最小负系数Two (or more) non-basic variables have the same “most negative” coefficient in the last row
- 可任选其中一个作为进基变量，最终仍能求得最优解
- 确定进基变量后，进行最小比值检验时，两个（或以上）基变量得出相同的最小比值
- 理论上可任选其一，但可能引发一些问题：退化现象（但一般不需要考虑）
原理解释
把单纯形法想成：你在一个房间的角点之间移动，每走一步都想让目标函数更优
- 进基变量：表示你准备沿着某个方向往前走
- 出基变量：表示谁先“顶到墙”，所以你最多只能走这么远
- 正常情况：只有一个变量先顶到墙。那你走了一步，到了一个新角点，事情很清楚
- 平局情况：有两个变量同时顶到墙。这说明你走到的位置，正好卡在一个“更尖的角”上，多个约束同时紧绷。这时如果你随便挑一个出基，数学上可以继续，但可能出现：基变了，但是你的人其实没挪地方，于是这一轮枢轴变换之后，目标函数值可能一点没改善，陷入死循环
无界问题
确定进基变量后，进行出基变量的最小比值检验时，进基变量所在列的所有系数均≤0
多重最优解
判定：最终行中有一个（或以上）非基变量的系数为 0
- 增大该非基变量的取值并将其选为进基变量时，目标函数值不会发生变化。
- 对该非基变量执行一次迭代操作，可得到另一个基本可行最优解。
- 若一个线性规划问题存在多重最优解，则至少存在两个基本可行最优解，其余所有最优解均可表示为这两个基本可行最优解的凸组合。
- 为什么 λ 必须在 [0, 1]? 因为这是 凸组合的定义。 对于两个点 \(A\) 和 \(B\)，凸组合是： \[ \lambda A + (1-\lambda) B \] 其中必须满足： \[ 0 \le \lambda \le 1 \] 这样生成的点才在 \(A\) 和 \(B\) 之间的线段上。
Simplex Two-Phase method
定义：两相法是在没有明显的初始基本可行解（BFS）时解决线性规划问题的系统技术
判断方法：出现 = 或 \ge 约束，通常就要考虑 two-phase
- 约束与≥不平等（没有自然松弛变量）
- 平等约束（完全没有松弛变量）
- 负右侧值
- 混合约束类型使初始化变得复杂
步骤：
Phase I（找初始 BFS）：
- 目的：不优化原目标函数，先判断原问题是否存在可行解。
- 方法：引入人工变量 w1,w2,…,wm（注意不是松弛/剩余变量)
构造辅助问题：minW=w1+w2+⋯+wm
- 结果判断：
- 若 Wmin=0：所有人造变量可消为 0，原问题存在可行解。
- 若 Wmin>0：至少一个人造变量无法消去，原问题无可行解。
Phase II：
- 步骤：删除人工变量，恢复原目标函数，继续用单纯形法求解。
- 目的：在已找到的可行起点上，优化原问题
- 例1：
同理第二题：
第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的系数）
写对偶问题的步骤：
- 对偶问题
- min – max对换
- 变量的个数 – 原约束的个数
- 变量的系数 – 原问题的RHS
- 对偶变量的正负性 – 原约束条件的正负性（正）
- 约束条件
- 约束条件的个数 = 原变量数量
- 约束条件的符号 – 原文题变量X的正负性（反）
- Xi大于0 – 第i个约束条件是小于
- Xi小于0 – 第i个约束条件是大于
- Xi没有约束（没写或者说明是free） – 第i个约束条件是等于
- 约束条件的系数
- LHS – 原约束条件的系数矩阵的列
- RHS – 原问题的各变量的系数
- 从原问题最优解得到对偶问题最优解：
定理（只是记录）
弱对偶性Weak duality 证明
互补松弛性 Complementary Slackness
- 直观含义：最优解处，约束的松弛 / 剩余变量与对应对偶变量的乘积为 0
- 由强对偶性可进一步得出：对偶变量的最优值就是原问题对应约束的影子价格
核心结论汇总
- 若原问题有最优解，则对偶问题也有最优解，且两者最优目标值相等；对偶变量最优值 = 原问题对应约束的影子价格。
- 最优解处，约束松弛 / 剩余与对应对偶变量乘积为 0（互补松弛）。
- 若原问题无界，则对偶问题不可行。
- 若原问题不可行(infeasible)，则对偶问题无界(unbounded)
例题
例1:
原问题无解，对偶问题无界
例2:
第五讲 – Branch-and-Bound (B&B) Algorithm 分支定界（B&B）算法
总结：Branch and Bound 的核心是：先解 LP relaxation 得到 bound；如果解不是整数，就对非整数变量分支；不断排除不可能更优、不可行、或已经整数的子问题，直到所有节点都被 fathomed，最后留下的最好整数解就是最优解。
- Q1. What is Branch and Bound used for?
- 用于求解整数规划问题，尤其是 ILP / MILP
- Q2. What is LP relaxation?
- 把整数限制去掉，把：\(x_j \in \mathbb{Z}\) 暂时放宽为：\(x_j \ge 0\)或连续变量。这样得到一个普通 LP，更容易解。
- Q3. Why do we branch?
- Q4. What is a branching variable?
- Q5. What does fathomed mean?
- 一个节点 / 子问题已经不需要继续分支。
- 常见原因：
- LP 解已经是整数解；
- LP 解不可行；
- LP relaxation 的 bound 已经不可能比当前最好整数解更好
- Q6. What are upper bound and lower bound in maximization B&B?
- Q8. When does the algorithm stop?
- 当所有子问题都被 fathomed，也就是没有任何还需要继续检查的节点时，算法停止。
- 此时当前最好的整数可行解就是最优整数解。
第六讲 – Sensitivity Analysis 敏感性分析
Shadow prices and reduced costs 影子价格与简约成本
约束的影子价格shadow price
- 每个约束都有影子价格，它等于对应松弛变量的简约成本
- 影子价格反映：约束右端项（RHS）变动对最优目标值的影响，其值是RHS增加1最优值的变化量
变量的简约成本reduced cost
- 每个变量都有简约成本，可在满足最优性条件的最终单纯形表最后一行中读出。
- 目标函数系数变动对最优目标值的影响。
下面说明如何用影子价格做敏感性分析：
影子价格和简约成本都是灵敏度分析中的重要内容。影子价格分析约束右端项变化对最优目标值的影响，简约成本分析目标函数系数变化对变量是否进入最优解的影响。
下面说明如何用影子价格做敏感性分析
simulation 仿真
必须区分预测forcasting与仿真：
- 预测：给出最可能的单一结果
- 仿真：生成大量可能结果 / 情景（也叫情景生成）
生成随机数
从正态分布生成样本
- 从正态分布中获取样本有多种方法。一种常见方法是：对一个随机均匀数应用累积分布函数的反函数（这正是NORM.INV 函数的做法）。我们之后会进一步学习这种方法，它适用于很大一类分布。
- 现在我们介绍另一种同样广泛接受的方法：它基于中心极限定理，并且只需要一个随机数发生器。
中心极限定理
- 回顾中心极限定理的一个表述：当大量相互独立且同分布（iid）的随机变量相加时，其和近似服从正态分布。
n 个随机变量的‘标准化’和（即先减去期望，再除以标准差）近似服从 N(0,1)：
连续型随机变量的逆变换法
运用接受 – 拒绝法从指定分布中生成样本Simulation – Acceptance-Rejection method
例1、2
解读Gams的输出文件（考试不考怎么写，但是考怎么看输出文件）
- Maximum achievable profit = 2500
- 决策变量 Decision Variables
- 生产50个product 1
- 不要生产产品2
- Reduced Cost: 简约价格
- 𝑥2 = 0and reduced cost = -10
- 产品 2 的利润必须增加 10 个单位，生产该产品才会变得有利可图
Needs +10 increase in profit coefficient . Only then enters solution
- 第一行 Labor：
- LHS（level） = RHS（Upper） → Binding constraint
- Shadow price（Marginal）：Increasing labor by 1 unit increases profit by 25
- 第二行 Machine：
- LHS < RHS → Non-binding constraint
Slack exists:Slack = 200 − 50 = 150 - Shadow Price = 0：Increasing machine capacity does not increase profit.
- LHS < RHS → Non-binding constraint
- ✔ Binding constraint → non-zero shadow price
- ✔ Non-binding constraint → zero shadow price
总结：
