基于单纯形法最优表反向构建线性规划问题（LPP）的方法

嘿，我来给你拆解下这个反向推导的核心逻辑——当年我做这类作业题的时候也踩过坑，摸清楚步骤就顺得很：

第一步：先理清变量的基/非基结构 #

• 从给定的最优单纯形表里，先把**基变量（BV）和非基变量（NBV）**拎出来：基变量是那种在某一行系数为1、其他行系数为0的变量（说白了就是每个基变量对应唯一一行的“主元”）；剩下的全是非基变量，包括松弛变量$s_1,s_2...$、剩余变量$e_1,e_2...$（如果有的话）。
• 记清楚：原问题的决策变量是$x_1,x_2...$，松弛/剩余变量是后来加的，人工变量如果在最优表里是非基变量且值为0，一般可以忽略（因为两阶段法里第一阶段已经把它清掉了）。

第二步：还原目标函数 #

这一步就是你提到的“令z行中s1、s2等于0”的核心应用，具体操作：

• 首先把最优表的z行整理成标准形式：$z = z^* + \sum_{j∈NBV} σ_j x_j$，其中$z^*$是最优目标值，$σ_j$是z行里非基变量的检验数（注意符号！最大化问题里$σ_j≤0$，最小化则$σ_j≥0$）。
• 利用松弛变量的原目标系数为0这个特性：松弛变量$s_i$的原系数$c_{s_i}=0$，而根据单纯形法的z行更新公式，$σ_{s_i} = c_{s_i} - \sum_{k} y_k a_{k,s_i}$（$y_k$是对偶变量，也就是基变量的影子价格）。因为$c_{s_i}=0$，所以可以列方程算出$y_k$的值。
• 有了对偶变量$y_k$，再反推决策变量的原目标系数：$c_j = σ_j + \sum_{k} y_k a_{k,j}$（$a_{k,j}$是最优表中第k行第j列的系数）。
• 最后把所有变量的系数整合，就得到原目标函数（比如最大化的话就是$max z = c_1x_1 + c_2x_2 + ...$）。

第三步：还原约束条件 #

最优表的约束行其实是基变量用非基变量表示的式子，我们要把它转成原约束的标准型：

• 先看每一行的基变量：如果基变量是松弛变量$s_i$，那把$s_i$移到等式右边，剩下的部分就是原约束的标准型（比如$a_{i1}x_1 + a_{i2}x_2 + ... = b_i - s_i$，也就是原约束是$a_{i1}x_1 + a_{i2}x_2 + ... ≤ b_i$）。
• 如果基变量是决策变量$x_k$，那把所有非基变量移到等式左边，系数取反，就得到原约束的标准型（比如$x_k + a_{k1}s_1 + a_{k2}s_2 = b_k$ → $x_k = b_k - a_{k1}s_1 - a_{k2}s_2$ → 原约束是$x_k + a_{k1}s_1 + a_{k2}s_2 = b_k$，对应原问题的等式约束或者转换后的<=约束）。
• 要是遇到剩余变量，逻辑类似：原约束是>=类型，所以标准型里会有$-e_i$，移项后就能还原。

第四步：补充变量的非负约束 #

线性规划默认所有决策变量$x_j ≥ 0$，松弛/剩余变量也都是非负的；如果是自由变量（无正负约束），最优表里会有特殊表现（不过作业题里基本都是非负）。

第五步：验证推导结果 #

最保险的办法是把你推出来的LPP用单纯形法从头算一遍，看能不能得到给定的最优表和最优解——要是对得上，说明你推导没问题；要是对不上，回去检查z行的符号或者约束系数的正负。

内容的提问来源于stack exchange，提问作者Japkeerat Singh