松弛变量为何在 z = 36 时重回基变量

封面:松弛变量为什么在 z = 36 时重回单纯形基

三个枢轴步把教科书上的产品组合问题推到目标值 36。前两步看着都合理,第三步我反复读了几遍:进基变量是 s1,也就是第一个枢轴步里刚刚变紧的那条约束的松弛变量;x1 仍然是基变量,值从 4 掉到 2。目标值照样涨了 9。单纯形法并不往更好的坐标上爬,它走向更好的角点。

第三次枢轴抬高了目标值,x1 却在下降

把数字走一遍。最大化 3×1 + 5×2,约束为 x1 <= 4、2×2 <= 12、3×1 + 2×2 <= 18,两个变量非负。

产品组合问题上的四个基状态:随着紧约束集合变化,z 依次升到 0、12、27、36

第一个枢轴把 x1 换进来,把 s1 推出去:在 (4, 0) 处 z = 12。第二个枢轴把 x2 换进来,把 s3 推出去:在 (4, 3) 处 z = 27。两次移动都像贪心改进,都挑了「每单位下一个紧约束资源回报更高」的那个变量。比如第二个枢轴让目标值涨了 15,比第一个枢轴涨得多。

第三步不认这个故事。s1 重新进基,s2 离基,解滑到 (2, 6),z = 36。变量 x1 仍是基变量,值掉了一半,目标值却多了 9。

变的是紧约束的集合。在 (4, 3),紧的是 x1 <= 4 和 3×1 + 2×2 <= 18;在 (2, 6),紧的是 2×2 <= 12 和 3×1 + 2×2 <= 18。第一条约束现在带着 2 个单位的闲置容量,这份容量就是 s1 那一列回来的原因。还有一行值得再看一眼:3×1 + 2×2 <= 18 在两个角点上都紧。角点就是一串紧约束,那个看起来在后退的枢轴,恰恰是换掉集合的那一步。

单纯形表是记账,不是要你求逆的矩阵

单纯形表从不做任何求逆。每一行是一条约束,加上这条约束的各列,基记录哪一列在哪一行是基变量。这里基里每行正好一列,别的什么都不存。

列的布局按行类型定,一条规则一行。<= 行配一个 +1 的松弛列。>= 行配一个 -1 的剩余列,再加一个人工列。= 行配一个人工列。最右边一栏放右端项。

判定规则是检验数 z_j – c_j,这个求解器按索引顺序取第一个负值的列。每轮迭代都记下谁进基、谁离基、枢轴之后的目标值。日志才是值得留下的数据,答案是副产品。

任何枢轴开始之前,阶段 0 先改写问题

右端项为负会破坏初始基,求解器先把它们规范化:整行乘 -1,比较方向翻过来。<= 行变成 >=,>= 变成 <=。

这次改写是恒等变换,日志可以作证。我写了 min 2×1 + 3×2,约束 x1 + x2 >= 4 和 x1 + 3×2 >= 6,再把两行都改成翻符号、右端项取负的形式。阶段一两个枢轴,阶段二零个枢轴,x = (3, 1),z = 9,两次都一样。同一条路径,同一个答案,在同一个求解器上量了两遍。

阶段一只问一件事:人工变量能不能归零

人工变量的用处,是给第一个基一些能握住的东西。它们是挂着惩罚的假列:阶段一最大化人工变量之和的负值,所以目标值从零以下起步,朝零爬。

阶段一用人工变量证明可行性;阶段二优化原始目标

到零就是可行。还有东西留在零以下,说明原问题无解,求解器会直接这么说。把 x1 + x2 <= 2 和 x1 + x2 >= 5 一起交给它,阶段一迭代一次就停,w = -3,随后报告无可行解。

w 一到零,剩下的那些人工基变量被换出去;某一行如果不再有别的非零项,就作为冗余行删掉。一条等式约束加一条松弛约束能塌成一行而不报错,靠的就是这个路径。日志在这条路上留下三个目标值:-2,然后 0,然后没什么可修了。

最小化就是两端各带一个符号的最大化

这个引擎只解一类问题:最大化。最小化传进来时把目标系数取负,报出来的值再取负回去。

符号的往返很便宜,也值得盯一眼。对 min 2×1 + 3×2,内部跑的是最大化 -2×1 – 3×2,落在 (3, 1),内部值 -9,报告再翻成 z = 9。两个约束在那一点都取等号,所以最优点落在两条线的交点上,不在任何一条边上。

那次运行里有个细节比答案更有用。我观察到的运行,阶段二零个枢轴。阶段一在追着人工变量归零的路上,已经走到了最优顶点,目标值没有可改进的余地。可行性阶段的工作可以顺带落到答案上。

Bland 规则买的是确定性,不是速度

平局是朴素单纯形法的失效模式。两行给出同样的比值时,选谁决定这次运行是终止,还是循环下去。

这个求解器两边都用 Bland 规则:多个检验数为负时最小索引进基,比值打平时基里最小索引离基。换来的后果是终止性的硬保证,因为没有基会重复;外加一个有文档记录的兜底:200 次迭代上限,容忍度 1e-9,专门防数值麻烦。

这个取舍是实打实的。Bland 规则可能比商业求解器用的最大改进规则走更多顶点。你买到的是可复现:同一个问题每次跑都产出同一份枢轴日志,日志才因此值得一读。

无可行解与无界是证明,不是错误信息

两种状态都不是求解器出错。无可行解意味着阶段一没法把人工变量归零,没有任何一点能同时满足全部约束。无界意味着进基列里没有正项可以比比值,目标值沿一条射线逃向无穷。

引擎写下的最后一行标着「STATUS」,里面是三个词之一:OPTIMAL、UNBOUNDED 或 INFEASIBLE。比如试 max x1 + x2,约束 x1 – x2 <= 3。一次枢轴定下 x1 = 3,接着没有哪一行能限制 x2,运行以 UNBOUNDED 结束。三种状态都附带着产生该状态的迭代日志,这一点多数工具省掉了。

这个求解器到哪里为止

引擎处理 2 到 6 个变量、1 到 8 条约束。这个上限是有意设的:你能用手读的单纯形表,才是你能从中学到东西的表。

两阶段引擎的五项限制:2 到 6 个变量、1 到 8 行、不给对偶值、只做单纯形法、200 次迭代

要拿它做实际工作,两个缺口得留意。按它自己的输出,报告不带对偶值,所以既没有影子价格也没有灵敏度区间;duality 这个词只出现在关键词列表里,没出现在打印出来的结果里。引擎也没有内点法路径,一个尺度糟糕的六变量问题照样可能爬得很慢。

基准规模会改变这笔账。HiGHS 和 Gurobi 是为几千行建的,还自带这个引擎缺的热启动。你想看清某个枢轴为什么动的那一刻,打开 线性规划单纯形法求解器(两阶段),把约束粘进去,一行一行读日志。更多工具在 elysiatools.com。

一次求解前后的步骤还有两个邻居工具:约束式可能需要描述的动力系统,交给 二阶常系数线性微分方程求解器(特征方程法);把拟合结果对着实测值核一遍,用 残差计算器。

所以下次求解器递给你一份逐轮日志,先读最后一次枢轴,再读答案。问一问:变松的那条约束,是不是你原以为紧缺的那条;掉下去的那个变量,是不是你正在为它付钱的那个。日志存在的意义就是回答这个问题,而单个数字永远露不出答案。

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *