视频字幕
运筹学中的两阶段法是一种用于解决线性规划问题的算法，特别适用于那些初始基本可行解不易直接找到的问题。例如，包含大于等于或等于约束的问题。两阶段法通过引入人工变量，将原问题分解为两个阶段来求解。第一阶段的目标是寻找原问题的一个基本可行解，通过引入人工变量并最小化这些人工变量之和。第二阶段则在找到基本可行解的基础上，恢复原问题的目标函数，求解原问题的最优解。
第一阶段的目标是寻找原问题的一个基本可行解。首先，我们需要将所有约束条件转化为标准形式，即等式约束，且变量非负。对于小于等于约束，我们加入松弛变量；对于大于等于约束，我们减去剩余变量并引入人工变量；对于等于约束，直接引入人工变量。以这个例子为例，原问题有一个小于等于约束和一个大于等于约束。转化后，我们构造一个辅助问题，其目标函数是最小化所有人工变量之和，在这个例子中就是最小化a1。通过求解这个辅助问题，如果最优值为0，说明原问题有可行解，且所有人工变量的值都为0。此时，我们得到了原问题的一个基本可行解，可以进入第二阶段。
在第一阶段，我们使用单纯形法求解辅助问题。首先，构造初始单纯形表，其中基变量包括松弛变量s1和人工变量a1。目标函数W行的系数是通过将人工变量的系数设为0，其他变量的系数设为它们在目标函数中的负系数得到的。接下来，我们选择入基变量和出基变量，进行基变换。在这个例子中，第一次迭代选择x2作为入基变量，a1作为出基变量。经过迭代后，我们得到最终的单纯形表，此时W的值为0，说明原问题有可行解。最终单纯形表中，基变量是x1和x2，它们的值分别为3和1，这就是我们找到的原问题的一个基本可行解。注意，此时所有人工变量的值都为0，这是我们进入第二阶段的条件。
进入第二阶段，我们从第一阶段的最优单纯形表开始，首先移除所有人工变量列。然后，恢复原问题的目标函数。在这个例子中，原目标函数是最大化z = 3x₁ + 2x₂。我们需要将z行的系数更新为仅包含非基本变量。具体做法是，将原目标函数中基本变量的系数乘以它们在单纯形表中对应的行，然后从原目标函数中减去，得到新的z行。在这个例子中，基本变量是x₁和x₂，它们在原目标函数中的系数分别是3和2。更新后，z行的系数变为[-3/2, -1/2]，对应s₁和s₂，而z的值为-11。由于所有非基变量的检验数都是负数，表明当前解已经是最优解。因此，原问题的最优解是x₁=3，x₂=1，最大值z=11。
总结一下，两阶段法是解决线性规划问题的有效算法，特别适用于那些初始基本可行解不易直接找到的情况。第一阶段通过引入人工变量，构造辅助问题来寻找原问题的一个基本可行解。如果第一阶段的最优值为零，说明原问题有可行解，我们可以进入第二阶段；如果大于零，则原问题无可行解。第二阶段在找到基本可行解的基础上，恢复原问题的目标函数，继续使用单纯形法求解原问题的最优解。两阶段法的优势在于它可以处理各种类型的约束条件，包括小于等于、大于等于和等于约束。在实际应用中，两阶段法是单纯形法的重要扩展，广泛应用于资源分配、生产计划、交通运输等领域的优化问题。