最优化方法简述
什么是最优化方法？
最优化方法是一种应用数学方法，旨在特定限制条件下，从所有可能的决策方案中寻找出一个最优方案，以达成预设的最优化目标（例如成本最低、利润最高、效率最快等）。
最优化问题的本质：在约束下求极值。
最优化方法的基本模型
任何一个最优化问题都可以抽象成一个标准的数学模型。
模型定义：
min (或 max) 目标函数 s.t. 约束条件min/max：指明目标是最小化还是最大化。s.t.：是 "subject to" 的缩写，意为“受限于...”。
核心术语：
可行解: 满足模型中所有约束条件的解。
不可行解: 未满足至少一个约束条件的解。
最优解: 在所有可行解中，能使目标函数达到最佳值（最大或最小）的那个解。
解决最优化问题的基本步骤
1. 问题定义
任务： 找出最优化问题的三大核心要素：
(a) 所有可能的决策方案是什么？
(b) 系统存在哪些限制条件？
(c) 评价方案好坏的标准（最优化目标）是什么？
2. 模型构造
任务： 建立数学模型，包括确定决策变量、写出目标函数和约束条件的数学表达式。力求将模型归类为某种标准数学模型，如：
线性规划
整数规划、动态规划等
非线性规划
3. 模型求解
任务： 利用成熟的最优化算法（如后续要学的单纯形法）或软件工具找到数学模型的最优解。
延伸： 常常伴随灵敏度分析，即分析当模型中的参数（如成本、资源量）发生变化时，最优解会如何变化。
4. 模型验证
目标： 检验模型的正确性和实用性。
任务： 将模型的输出结果与实际情况（如历史数据）进行比较。一个好的模型，其给出的方案应该优于历史上的实际做法。如果不符，则可能需要回到第一步或第二步重新审视问题定义和模型假设。
线性规划
什么是线性规划？
线性规划是最优化方法中的一个重要分支，也是应用最广泛的一种。它的“线性”特征体现在两个方面：
目标函数 是决策变量的线性表达式。
约束条件 也是决策变量的线性等式或不等式。
一个线性规划模型，同样由三个基本部分构成：
决策变量: 需要确定的未知数，如生产数量、资源分配等。
目标函数: 一个需要最大化（如利润、收入）或最小化（如成本、损耗）的线性函数。
约束条件: 决策变量必须满足的一组线性限制，代表了资源、时间、需求等方面的局限。
线性规划求解：图解法
下面通过一个案例，来演示建模和求解一个只有两个决策变量的线性规划问题。
问题描述: 某集成商生产闸机和售票机，受设备A、设备B和调试时间三种资源的限制，目标是安排生产计划，使每日利润最大。
建模步骤：
确定决策变量: 这是建模的第一步，也是最关键的一步。
x= 每日生产闸机的数量y= 每日生产售票机的数量
构造目标函数: 根据问题目标（利润最大化）来构建。
每台闸机利润2万，每台售票机利润1万。
总利润
z = 2x + y目标是最大化，所以目标函数为：
max z = 2x + y
构造约束条件: 将所有资源限制转化为数学不等式。
设备A时间约束: 闸机不占用，售票机占用5小时，每日可用15小时。
5y <= 15设备B时间约束: 闸机占用6小时，售票机2小时，每日可用24小时。
6x + 2y <= 24调试时间约束: 各占用1小时，每日可用5小时。
x + y <= 5隐含约束 (非负约束): 生产数量不能为负。
x >= 0,y >= 0
完整的线性规划模型:
max z = 2x + y s.t. 5y <= 15 6x + 2y <= 24 x + y <= 5 x, y >= 0
对于只有两个决策变量的线性规划问题，可以使用图解法直观地找到最优解。（初中知识）
求解步骤:
确定可行解空间: 在坐标系中画出所有约束条件代表的区域，它们的交集就是可行解空间。
从可行点中确定最优解: 在可行解空间内找到使目标函数达到最优值的点（一定为顶点）。
线性规划求解：单纯形算法
为什么需要单纯形算法？
图解法非常直观，但仅适用于2个决策变量。当变量增多时，图解法就失效了。单纯形算法 是一种用于求解 任意多变量的线性规划问题 的代数方法。
线性规划的标准型
单纯形算法的计算过程要求模型具有统一的格式，即标准型。
标准型的两个要求:
所有约束都是等式，且右端项非负。
所有决策变量都非负。
如何将普通模型转化为标准型？
处理不等式约束 (
<=或>=):对于
≤约束: 在左侧加上一个非负的松弛变量，使其变为等式。松弛变量代表未被用尽的资源量。例如：
6x₁ + 4x₂ <= 24变为6x₁ + 4x₂ + s₁ = 24，其中s₁ >= 0。
对于
≥约束: 从左侧减去一个非负的剩余变量，使其变为等式。剩余变量代表超出最低要求的量。例如：
3x₁ + 2x₂ >= 14变为3x₁ + 2x₂ - s₁ = 14，其中s₁ >= 0。
注：严格不等式（ < 或 > ）会从根本上破坏模型的可解性。线性规划中的变量通常是连续的，可以直接将 < 视为 ≤，> 视为为 ≥
处理右端项为负数:
将整个约束等式或不等式两边同乘以 -1，使右端项转为非负。
示例：
原模型：
max z = 5x₁ + 4x₂ s.t. 6x₁ + 4x₂ <= 24 x₁ + 2x₂ <= 6 -x₁ + x₂ <= 1 x₂ <= 2 x₁, x₂ >= 0标准型 (引入4个松弛变量 s₁, s₂, s₃, s₄):
max z = 5x₁ + 4x₂ + 0s₁ + 0s₂ + 0s₃ + 0s₄ s.t. 6x₁ + 4x₂ + s₁ = 24 x₁ + 2x₂ + s₂ = 6 -x₁ + x₂ + s₃ = 1 x₂ + s₄ = 2 x₁, x₂, s₁, s₂, s₃, s₄ >= 0注意：松弛/剩余变量在目标函数中的系数通常为0。
标准型的可行域：
标准型与普通模型的最大区别在于，除了非负约束，其他约束条件都是等式约束。
对于由普通模型转换而来的标准型，先只考虑 m 个等式约束，可看作一个由 m 个方程 n 个变量组成的方程组，且通常 n > m 。这个方程组的解空间为一个 n - m 维的子空间 （比如一个由 1 个方程 2 个变量组成的方程组，其解空间为一条直线）。
现在考虑 n 个非负约束，等式约束形成的解空间会被非负约束条件裁剪，得到标准型的可行域（还是刚刚那个例子，比如只取代表解空间的那条直线的第一象限以及与坐标轴正半轴的交点）。
可以证明，最优解一定位于可行域的顶点上。在标准型中，可行域的顶点对应的可行解叫基本可行解。
“可行域的顶点”是一种几何层面的描述，如何将其转换为代数层面的描述，从而进行代数求解呢？事实上，对于一个点为标准型的可行域的顶点的充要条件为：
在等式约束形成的解空间上 （满足所有等式约束）
恰好位于
n - m个非负约束的边界上（即有n-m个变量的值恰好为 0）所有变量的值均非负 （满足所有非负约束）
因此，可以得到如下定义：
基本可行解:
在一个包含
n个变量和m个方程的标准型中 (n > m):任意选择
n-m个变量，令它们的值为 0，这些变量称为非基变量 (Non-basic Variables)。使用
m个方程求解剩下的m个变量，这些变量称为基变量 (Basic Variables)。得到的这组解
(x₁, x₂, ..., xn)称为一个基本解。如果这个基本解中所有变量的值都非负，则称其为基本可行解。
暴力枚举的局限性: 我们可以通过枚举所有
n-m个非基变量的组合来找出所有顶点，但这在变量数量很多的时候计算量很大 (C(n,m))。单纯形法提供了一种更优越的搜索方式。
单纯形算法
单纯形算法是一个迭代过程，从一个基本可行解（顶点）开始，系统地移动到另一个能使目标函数值更优的相邻顶点，直到找到最优解。
算法步骤 (以上面给出的模型为例):
1. 初始化：建立初始单纯形表
将标准型模型（包括
z - 5x₁ - 4x₂ = 0）填入一个表格，除了基以外的列代表系数。初始的基本可行解通常是原点 (
x₁=0, x₂=0)，此时基变量为所有松弛变量 (s₁, s₂, s₃, s₄)。
初始单纯形表:
当前解为
x₁=0, x₂=0, s₁=24, s₂=6, s₃=1, s₄=2，目标函数值z=0。注意观察，对于基变量的每一列，都是一个单位向量。所以在选择进基变量时，只会选择到非基变量（值为0，只能增大）。同时，由于非基变量一定为 0，则解的值就是当前基变量的值。
2. 迭代过程
重复以下步骤，直到满足终止条件：
a. 判断是否最优:
检查
z所在行。对于最大化问题，如果所有变量的系数都非负，则当前解为最优解，算法终止。（对于最小化问题，本质上等价于最大化它的相反数）当前
z行中x₁的系数为-5，x₂的系数为-4，不是最优，继续。
b. 确定进基变量:
从
z行中选择最负的系数。它对应的变量就是进基变量，（该变量为非基变量且系数为负，说明增加该变量，z就会增大，而且增大得最快）这里-5是最小的，所以
x₁是进基变量。x₁所在的列是枢轴列。
c. 确定离基变量:
计算最小比率:
比率 = 解 / 枢轴列中对应的正系数。（计算持续增大进基变量时，哪个基变量会首先变为0）s₁ 行:
24 / 6 = 4(最小值)s₂ 行:
6 / 1 = 6s₃ 行: 系数为-1，不考虑
s₄ 行: 系数为0，不考虑
选择最小非负比率对应的行。该行的基变量就是离基变量。
这里比率最小的是4，所以
s₁是离基变量。s₁所在的行是枢轴行。
d. 执行行变换 - 高斯-若尔当消元法:
枢轴元素: 枢轴行和枢轴列交叉处的元素 (这里是 6)。
目标: 将枢轴列变换为单位向量（枢轴元素变为1，其他元素变为0）。
新枢轴行 = 当前枢轴行 / 枢轴元素
New s₁ Row->New x₁ Row=(0 6 4 1 0 0 0 | 24) / 6=(0 1 2/3 1/6 0 0 0 | 4)新其他行 = 当前行 - (当前行在枢轴列的系数) * (新枢轴行)
New z Row=(1 -5 ... | 0) - (-5) * (0 1 ... | 4)=(1 0 -2/3 5/6 0 0 0 | 20)...对其他所有行执行此操作。
理解：把进基元素纳入基变量（不再为0），把离基元素纳入非基变量（为0），并标准化。
3. 得到新的单纯形表，重复迭代
第一次迭代后的表:
z值为20。z行仍有负数(-2/3)，继续迭代。x₂成为新的进基变量，s₂成为新的离基变量。
第二次迭代后的表:
最终判断:
z行所有变量系数（3/4, 1/2）均为非负，达到最优。
4. 读取最优解
最优解: 看基变量列和解列。
x₁ = 3,x₂ = 3/2。非基变量 (s₁, s₂) 值为0。最优目标值: 看
z行的解列。z = 21。
改进单纯形法
为什么需要改进单纯形法？
在标准的单纯形法中，最理想的情况是约束条件全部为 ≤ (小于等于) 且右端常数项非负。这时，我们引入的松弛变量（系数为+1）天然构成了一个单位矩阵，让我们无需任何计算就能直接获得一个初始基本可行解。
但在实际建模中，经常遇到 = (等式) 或 ≥ (大于等于) 的约束。这带来了两个无法通过简单代数变换解决的棘手问题：
对于 = 约束：
首先，单纯形法需要一个现成的解来启动迭代，我们往往选择原点（决策变量都为零）作为这个现成的解，因为这个解唾手可得，非常方便。但是，如果存在等式约束，原点显然无法作为现成的解了。
如果强行不使用原点，就需要先进行高斯消元解方程组，把某些决策变量的系数化为单位向量。而单纯形法的过程本身就是在做高斯消元，在算法开始前先解一遍方程很麻烦。
对于
≥约束，直接把剩余变量乘负号变正不行吗？对于 x_1 + x_2 \ge 5，引入剩余变量 s_1 后变为 x_1 + x_2 - s_1 = 5。
此时 s_1 系数为 -1，无法做基。如果方程两边同乘 -1，变为 -x_1 - x_2 + s_1 = -5。
虽然 s_1 系数变为了 1，但右端项（RHS）变成了 -5。这意味着初始解为 s_1 = -5。
冲突： 单纯型要求所有变量必须 非负 (\ge 0)。从负数起点出发，算法会直接失效。
解决方案： 为了解决上述问题，我们不得不引入人工变量 (Artificial Variables, 记为 R)。这些变量是人为添加的假变量，仅用于通过第一步的非负性检查，我们需要在迭代过程中把它们赶出基底。
方法一：大M法 (Big M Method)
什么是大M法？
大M法是一种通过给人工变量施加巨额惩罚来迫使它们退出基底的方法。既然 R 是假变量，我们就不希望它出现在最终结果中。
如何构造模型？
我们在目标函数中，给人工变量赋予一个极大的系数 M (Big M)：
对于最小化问题 (min): 惩罚系数为 +M（为了让总目标最小，算法会自动把 R 变成 0）。
对于最大化问题 (max): 惩罚系数为 -M。
变量添加规则：
≤约束: 加松弛变量 (+s)。=约束: 加人工变量 (+R)。≥约束: 减剩余变量 (-e)，并加人工变量 (+R)。
求解步骤
先化为标准型
修正标准型： 将原目标函数 \min z = \sum c_j x_j 修改为 \min z = \sum c_j x_j + \sum M R_i。
初始化单纯形表：
填入系数后，我们会发现基变量是 R，但目标函数行（z行）中 R 的系数是 M（非0）。
违规： 单纯形表要求基变量在 z 行的系数必须为 0。
操作： 进行初等行变换，
新z行 = 旧z行 - M * (R所在的约束行)，将 M 消去。
迭代与判别：
按照标准单纯形法进行迭代。M 作为一个符号大数参与运算。
成功： 最终表中所有检验数满足最优条件，且人工变量 R 全部为 0。
失败（无解）： 最终表满足最优条件，但基变量中仍有人工变量且值 > 0。说明原问题约束冲突，不可行。
方法二：两阶段法 (Two-Phase Method)
为什么需要两阶段法？
大M法在计算机数值计算中存在隐患：如果 M 选得太大，可能会因为计算机浮点数精度限制，导致“大数吃小数”，产生严重的舍入误差。两阶段法通过分步求解，避免了使用 M。
怎么做？
阶段 I：找可行解
目标： 不考虑原目标函数，只致力于把人工变量 R 消除掉。
模型：
目标函数： \min r = \sum R_i （最小化所有人工变量之和）。
约束： 同原问题。
求解： 运行单纯形法。
结论：
如果最优值 \min r > 0：说明人工变量无法清零，原问题无解，停止。
如果最优值 \min r = 0：说明找到了一组不含人工变量的可行解，进入阶段 II。
如何在阶段Ⅰ寻找初始可行解？
在阶段 I，我们构造一个了辅助问题 \min r = \sum R_i。为了启动单纯形法，我们需要一个初始可行解。
步骤 1：列出约束方程
假设标准化后的约束如下（R 为基变量）：
a_{11}x_1 + \dots + R_1 = b_1
a_{21}x_1 + \dots + R_2 = b_2
a_{31}x_1 + \dots + s_3 = b_3 (这是个 \le 约束，用松弛变量 s_3 做基)
步骤 2：写出原始目标函数
r = R_1 + R_2 或者是：r - R_1 - R_2 = 0
步骤 3：代入消元（关键的一步）
单纯形表要求 r 行中 R_1, R_2 的系数为 0。我们需要用约束方程把 R_1, R_2 替换掉。
直接将所有含有 R 的约束方程相加： (R_1 + R_2) + \sum (\text{其他项}) = b_1 + b_2
移项得到： R_1 + R_2 = (b_1 + b_2) - \sum (\text{其他项})
将这个代入目标函数 r = R_1 + R_2： r = (b_1 + b_2) - \sum (\text{其他项})
整理成单纯形表的一行 (r + \dots = \text{常数}): r + \sum (\text{非基变量的系数}) = (b_1 + b_2)
此时把 r 行内的其他变量看作决策变量，选原点作为初始可行解就行了。在单纯形表的 r 行中可以选择初始的只包含人工变量的形式，也可以选择人工变量代换后的形式，结果是一样的。
阶段 II：找最优解
目标： 在可行解的基础上，优化真正的目标函数。
操作：
删列： 去掉阶段 I 最终表中所有的人工变量列。
换行： 将 z 行换回原问题的目标函数系数。
平账： 此时 z 行中基变量系数可能不为0，需要像大M法第一步那样，做行变换将基变量系数消为0。
迭代： 继续运行单纯形法直至求出最优解。
单纯形法的特殊情况
1. 退化
现象：
在确定最小比率（确定离基变量）时，出现两个或多个相同的最小比率。
这意味着选谁离基都可以，但下一次迭代时，剩下的那个基变量的值会变成 0。
几何意义：
多余的约束。在几何空间中，表现为超过 n 个超平面交于同一个顶点（例如二维平面上3条直线交于一点，其实2条线就确定这个点了，第3条是多余的）。
影响：
可能导致算法在同一个顶点处原地踏步（基变量变了，但解的值不变）。理论上可能导致死循环，但实际应用中极少发生。
2. 可选择最优解
现象：
当单纯形表已经达到最优状态（z 行所有检验数合格），此时观察非基变量：
发现某个非基变量在 z 行的系数恰好为 0。
含义：
如果让这个非基变量进基，目标函数值 z 不会发生变化。说明存在另一个顶点也是最优解。
几何意义：
目标函数平面与某一个有效约束平面平行。
此时，两个最优顶点连线上的所有点都是最优解（无穷多解）。
3. 无界解
现象：
在确定进基变量（例如 x_k）后，想要计算最小比率来确定离基变量。
发现该列（x_k列）中，所有的约束系数都 \le 0。
含义：
无论 x_k 增加多少，都不会触碰到任何约束边界。目标函数值可以无限优化下去。
几何意义：
可行域在某个方向上是开口无限延伸的。通常意味着建模时漏掉了某些限制条件。
4. 不可行解
现象：
单纯形法迭代正常终止（满足最优性条件，找不到可以让目标更好的进基变量了）。
但是： 最终的基变量中，仍然包含人工变量 (R)，且其值 > 0。
含义：
我们尽力了，但无法摆脱人工变量。说明无法找到一组满足所有真实约束的解。
几何意义：
约束条件相互矛盾（例如要求“既要大于5，又要小于2”），可行域为空集。
