第 3 周作业：图解法、基本解与单纯形法

Views: --
#作业

源文件是同学的第 3 周手写作业，未附题面。因此本篇是根据作答过程还原题意：扫描可辨认出三组内容——七个二维 LP 的图解结果、基本解/基本可行解枚举，以及若干单纯形表。无法从作答唯一恢复的约束系数不补写，重点整理可复用的计算过程。

一、二维线性规划图解

手写作答给出的七个结果依次包括：

小题作答中的结论
1最优点 (0,5)(0,5)，最优值 −30-30
2最优点 (5,0)(5,0)，最优值 −5-5
3无解
4最优点 (5,25/2)(5,25/2)，最大值 2525
5最优点 (7/4,3/8)(7/4,3/8)，最小值 −6-6
6最优点 (12/7,15/7)(12/7,15/7)，最大值 120/7120/7
7最优点 (7/2,0)(7/2,0)，最大值 21/221/2

这些数值只能视为源作答记录；因为题面缺失，无法独立复核是否有抄写误差。

图解法的规范流程：

  1. 每条不等式先画边界直线；
  2. 用测试点确定半平面；
  3. 取交集得到可行域，并判断是否为空或无界；
  4. 找全部顶点；
  5. 在顶点代入目标，或平移目标等值线。

若可行域无界，不代表目标无界；要看目标改善方向是否能沿可行射线无限前进。

二、基本解枚举

源作答对形如

Ax=b,x≥0Ax=b,\qquad x\ge0

的问题枚举所有可能的基列组合。以 m=2m=2 为例，每次从 AA 中选两列 BB，若 det⁡B≠0\det B\ne0，计算

xB=B−1b,xN=0.x_B=B^{-1}b,\qquad x_N=0.
  • 所有可逆基给出基本解；
  • 只有 xB≥0x_B\ge0 的才是基本可行解；
  • 不同基可能给出同一退化点。

扫描中一题最终记录的最优解为

xˉ=(0,8,0,4)T,fmax⁡=40;\bar x=(0,8,0,4)^T,\qquad f_{\max}=40;

另一题记录

xˉ=(0,5,0,0,1)T,fmin⁡=−6.\bar x=(0,5,0,0,1)^T,\qquad f_{\min}=-6.

由于题面缺失，这里不反推矩阵之外的题意。

三、单纯形表

作答中通过圈主元、行归一化和消元推进单纯形表。标准书写应包含：

  1. 标出正检验数对应的进基变量（按本课最小化约定）；
  2. 只对主元列正元素做最小比值；
  3. 标出出基变量；
  4. 主元行除以主元，其他行消成零；
  5. 读最终基解并代回核验。

扫描中若干最终结果包括 fmin⁡=−440f_{\min}=-440、fmax⁡=583/50f_{\max}=583/50、fmin⁡=−68/3f_{\min}=-68/3 与 fmin⁡=−26f_{\min}=-26。这些结果依赖原表系数，不在缺题面的情况下重新包装成完整题目。

四、关于基更新公式

最后一页推导了换基后的检验数更新。若第 rr 个基变量被第 kk 列替换，Gauss–Jordan 行变换作用于所有列，新的检验数也按同样主元操作更新。这个结论解释了为什么无需每轮重新算 B−1B^{-1}：单纯形表本身就在维护 B−1AB^{-1}A、B−1bB^{-1}b 与检验数。

作业自检

  • 图解结果要区分“可行域无界”和“目标无界”。
  • 枚举基时先检查列独立，再检查基本变量非负。
  • 单纯形表的目标符号必须全文一致。
  • 本篇表中数值是源作答记录，不是缺失题面的重新命题。

评论