做排产方案的时候线性规划是个绕不开的模型而单纯形法里的“大M法”又是最劝退新人的一关。前阵子我用Excel把一个小排产模型完整算了两遍第一遍是用单纯形法大M法纯公式直接求解手搭单纯形表逐步迭代第二遍是用Excel自带的“规划求解”功能一键出结果再回来校验手算的每一步。整个过程走下来我觉得这两种方式不是替代关系而是互补关系。这篇文章就把案例建模、表格布局、检验数公式、迭代消元、规划求解设置、结果对账、常见坑位一次说清楚适合运筹学刚入门、或者工作中偶尔要做优化决策但不想被黑箱工具糊弄的朋友。1. 大M法与Excel结合到底要解决什么1.1 大M法解决的核心痛点单纯形法需要一个初始可行基也就是一堆现成的单位列向量。但实际问题一旦出现“等式约束”或者“大于等于约束”情况就麻烦了。比方说某个约束是x1 x2 4你没法靠松弛变量“松出一个”变量来当初始基再比方说x1 3x2 6标准形化完之后是x1 3x2 - s1 6这里的-s1系数是-1也不是单位向量。这时候初始可行基从哪来大M法的办法很直接强行往这两个约束里塞人工变量让它们补成单位列向量。人工变量补出来的基本身不代表真实资源所以不能让它们留在最优解里“白占便宜”。办法是在目标函数里给它们设一个极大的惩罚系数求最大值时人工变量系数用-M求最小值时用M。这个M是一个远远大于其他系数的正数只要人工变量还在基里目标函数就会承受巨大损失迭代过程就会想方设法把它们换出去。等到最终表里人工变量全部出基或者即使还在基里但取值为0原问题就还原成真实的优化问题如果人工变量还在基里且取值大于0说明原问题根本无可行解。这一套逻辑清晰但手算容易错尤其是有多个M项混在一起的时候正负判断很容易翻车。1.2 为什么选Excel而不是写程序很多人觉得手算太麻烦写个Python用现成库不就行了但就我个人的体会Excel在这个场景下有一个不可替代的优点每一步迭代都看得见、摸得着。你改动一行公式整张单纯形表立刻刷新检验数、比值、目标值的变化全部可视化。写程序更像是一个黑箱你调用一个函数它给你一个结果中间过程如果不专门加日志基本是看不见的。而Excel的公式天然就是“日志”你完全可以把每一次迭代复制成一个新工作表保留完整的演算痕迹。另外Excel不用装额外环境几乎每台办公电脑都有。遇到急事没有规划求解加载项没有Python环境你靠一张空表也能把所有迭代步骤算出来。这正是“直接求解”路线的价值它不是效率最高的方案却是最透明的方案。等搞懂原理、验证过结果之后再用规划求解去处理更大规模的问题心里会踏实很多。2. 案例建模从排产问题到标准形2.1 一个适合演示的排产模型为了把大M法的细节完整展示出来我构造了一个两个变量、两个约束的小案例故意同时包含等式约束和大于等于约束。某车间要安排两种产品的产量产品A每件利润2万元产品B每件利润1万元。市场部门要求两种产品总产量恰好等于4件车间的瓶颈工序要求总加工时间至少达到6小时其中A每件耗1小时B每件耗3小时。两种产品产量都不能为负问怎么排产利润最大。设x1为A的产量x2为B的产量模型就是max z 2*x1 x2 约束 x1 x2 4 x1 3*x2 6 x1 0, x2 0这个模型很小但很有代表性。第一个约束是等式没有现成的松弛变量第二个约束是大于等于化成标准形后会出现-s1同样不能直接当基。两个约束凑在一起恰好就是需要大M法出场的情况。如果题目全是小于等于约束直接加松弛变量就能出初始基根本不需要人工变量也看不到大M法的妙处。2.2 变量改造的三步走把原问题转为标准形需要做三个动作。第一个动作给“大于等于”约束减去一个剩余变量s1让不等式变成等式x1 3*x2 - s1 6。这里的s1 0它的经济含义是实际加工时间超出最低要求的那部分。第二个动作给没有单位列向量的约束补人工变量。第一个等式约束x1 x2 4里没有任何松弛变量直接补一个人工变量A1变成x1 x2 A1 4。第二个约束已经减了s1但系数是-1无法作为初始基所以再补一个人工变量A2变成x1 3*x2 - s1 A2 6。人工变量的本质是“造假出来的初始基”后续必须被迭代出基。第三个动作改造目标函数。因为这是在求最大值人工变量每留在基里一个单位目标函数就要被扣掉Mmax z 2*x1 x2 - M*A1 - M*A2写到这里标准形就完整了。这里有个新手很容易忽略的点人工变量进入目标函数后它的系数会被计入单纯形表的检验数计算。如果目标函数里漏掉-M*A1 - M*A2后面算出来的检验数全都不对。2.3 M值的选取逻辑大M法里的M不是真的要写成无穷大在Excel里我们需要给它一个具体数值。取值太小惩罚不到位人工变量可能赖在基里不走最后给你一个“假最优解”取值太大Excel浮点运算在多次消元之后会积累微小误差有时候甚至出现-0.0000000001这种噪声影响最优性判断。我的习惯是把M放在一个独立单元格里比如命名成M数值设为目标函数系数的100到1000倍左右同时不要低于约束右端项的数量级。这个案例里目标系数最大是2右端项最大是6所以取M 10000完全够用。如果问题规模大一点右端项到几千、几万M就要相应放大到百万级别否则惩罚力度会不够。把M单独放单元格还有一个好处就是后续想对比不同M值的影响时只改一个单元格就能重新算完不用到处替换公式。3. 方案A直接求解——手把手搭单纯形表3.1 表格布局与通用公式我在Excel里把单纯形表按这样的结构排布算是比较标准的一种参考布局。第一行放各个变量的目标系数Cj第二行放变量名和基变量信息中间是约束系数矩阵右侧是右端项RHS最后一行放检验数。实际Excel布局会根据你的习惯微调但核心公式是一致的。以我的案例为例初始表可以理解成下面这样Cj210-M-MCB基变量x1x2s1A1A2RHS-MA1110104-MA213-1016检验数22M14M-M00注意这张表里Cj行中A1、A2对应的位置不是写一个字母M而是引用存放M的单元格。比如M放在某个单元格里A1的Cj就是-M单元格A2的Cj同样是-M单元格。Excel里怎么方便怎么来但不要直接在公式里写-MExcel不认识这种东西。检验数的计算是整套方案的核心。对每一列来说检验数公式是检验数 该列的Cj - SUMPRODUCT(当前基变量对应的CB列, 该列的系数列)用Excel函数表达就是Cj单元格 - SUMPRODUCT($CB列区域, 当前列区域)。SUMPRODUCT在这里做的是矩阵乘法把基变量各自的目标系数和当前变量列里对应行上的约束系数乘起来累加得到的就是“如果当前变量入基一单位目标函数会变化的量”。用原来的Cj减掉这个变化量就是检验数。我在实际搭建时会把“检验数”那一行所有列都用同一个公式拖出来这样既快又不容易错。因为SUMPRODUCT里的两个区域一个用绝对引用锁定一个随列变化拖拽填充后天然形成每一列各自的检验数。3.2 初始表检查与第一次迭代初始表的基变量是A1和A2对应的Cj都是-MRHS是4和6。初始基本身是单位矩阵所以初始解是A1 4, A2 6, x1 x2 s1 0此时目标函数值等于-M*(46) -100000显然是个“天价亏损”的起始点后续迭代就是要尽快逃离它。计算初始检验数x1列的检验数 2 - [(-M)*1 (-M)*1] 2 2M x2列的检验数 1 - [(-M)*1 (-M)*3] 1 4M s1列的检验数 0 - [(-M)*0 (-M)*(-1)] -MM取10000时22M 2000214M 40001都是正数说明目标函数还有提升空间。按最大检验数原则x2入基因为14M明显大于22M。入基变量定下来后用最小比值规则确定出基变量。计算每一行RHS与对应入基列系数的比值只考虑入基列系数大于0的行第1行4 / 1 4 第2行6 / 3 2最小比值是2所以第二行的基变量A2出基主元位置是第2行、x2列、系数3。这一步的逻辑是要让x2入基就必须把目前的三个基本可行解边界往回收最先挡路的是比值最小的那个约束它对应的基变量先降为0就需要出基腾位置。3.3 第一次迭代的实际消元操作在Excel里做高斯消元不需要完全靠手算用行公式就能完成。先把主元行整体除以主元系数3得到新主元行。然后对另一行做行变换新行等于旧行减去“新主元行乘以该行入基列系数”。消元之后第一轮迭代结束的单纯形表长这样Cj210-M-MCB基变量x1x2s1A1A2RHS-MA12/301/31-1/321x21/31-1/301/32检验数5/32M/301/3M/30-4M/3-1/3这轮迭代后的基变量是A1和x2函数值提高到(-M)*2 1*2 -19998比初始的-100000好多了但逼着人工变量出基的进程还在继续。重新算检验数x1列5/3 2M/3正数 s1列1/3 M/3正数 A2列-4M/3 - 1/3负数正的检验数还有两个继续迭代。x1列的检验数里M的系数是2M/3比s1列的M/3大所以x1入基。最小比值规则再算一遍第1行2 / (2/3) 3 第2行2 / (1/3) 6最小比值是3本轮第一行基变量A1出基主元位置是第一行、x1列、系数2/3。这一步非常关键因为人工变量A1终于要被换出基了。3.4 第二次迭代与最优性判定继续做行变换主元行整体除以2/3相当于乘以3/2然后对另一行做消元。第二次迭代后的最终表Cj210-M-MCB基变量x1x2s1A1A2RHS2x1101/23/2-1/231x201-1/2-1/21/21检验数00-1/2-2.5-M0.5-M此时基变量是x1和x2两个人造变量都离开了基。检验数行x1列0 x2列0 s1列-1/2 A1列-2.5 - M A2列0.5 - M因为M是10000A1和A2列的检验数都是很大的负数所有检验数全部小于等于0满足最优性条件。最优解是x1 3, x2 1最大利润z 2*3 1 7万元。把结果代回去验证x1 x2 3 1 4 x1 3*x2 3 3 6完全吻合。表中s1列检验数是负数也说明剩余变量继续增大无法改善目标A1、A2检验数被M压得死死的说明任何试图让人工变量重新入基的行为都会大幅拉低目标函数。这就是大M法“惩罚机制”在检验数层面的直观体现。3.5 手工消元时的几个实用习惯整个迭代过程下来我总结了几个非常实用的习惯。第一每一步迭代都复制到新的工作表再操作保留现场。不要在原表上直接覆盖否则算到第三步想回头核对第一步的公式和数值时你会非常痛苦。第二每次迭代前在表外单独注明本轮“入基变量”和“出基基变量”。这个备注看起来不起眼但当你隔几天回看这份表时它能帮你快速回忆起迭代路线。第三Excel默认显示小数但单纯形表中的分数其实更能看出模式。比如2/3、1/3你可以在Excel里把这些单元格设置成分数格式或者在旁边手动标注分数。我个人习惯保留原始小数在纸面上另写分数推导两边对照不容易乱。第四涉及M的检验数Excel里数值显示得很夸张比如20002、40001但你判断正负时要想一想这背后的代数结构哪些是真实系数哪些是M的倍数。如果只看数值不看结构遇到0.5-M这种负数会觉得莫名其妙其实它就是M项的惩罚在起作用。4. 方案B规划求解加载项4.1 加载与启用交换手算验证之后再用Excel自带的规划求解来对账。规划求解本质是一个优化求解器背后也可以选择线性规划的单纯形法引擎。第一次使用需要先加载加载项。不同版本的Office路径略有差异大体是点击“文件”菜单进入“选项”再找到“加载项”分类在底部“管理”下拉框里选择“Excel加载项”点“转到”在弹出的列表里勾选“规划求解加载项”确定。这一步完成后“数据”选项卡右侧就会出现“规划求解”按钮。如果你在列表里找不到这个加载项很可能当前Office安装不完整需要修复安装或者确认电脑是否安装了完整组件。Mac版Excel通常在“工具”菜单里能找到类似加载项管理入口。4.2 建模与参数设置规划求解使用前需要先把模型铺到工作表里。我习惯这样安排用几个单元格存放目标系数再用一片区域放约束系数矩阵右侧放RHS和符号最后留出一块可变单元格区域。本例的工作表可以这样组织单元格区域内容B2:C2目标函数系数分别输入2和1B4:C4第一个约束的系数分别输入1和1B5:C5第二个约束的系数分别输入1和3D4第一个约束右端值4D5第二个约束右端值6E4第一个约束符号 E5第二个约束符号 B7:C7可变单元格即x1和x2可先填1F2目标函数公式SUMPRODUCT($B$2:$C$2,$B$7:$C$7)F4第一个约束左端公式SUMPRODUCT($B$4:$C$4,$B$7:$C$7)F5第二个约束左端公式SUMPRODUCT($B$5:$C$5,$B$7:$C$7)然后打开规划求解对话框参数这样填设置目标F2 到最大值 通过更改可变单元格$B$7:$C$7 添加约束1F4 D4 添加约束2F5 D5 勾选使不受约束的变量为非负数 选择求解方法单纯线性规划这里有一件很重要的事必须在“选择求解方法”里选“单纯线性规划”否则Excel可能用非线性引擎去尝试速度慢不说结果也可能偏离真正的线性最优。勾选“使不受约束的变量为非负数”等于把x1, x2 0这个约束写进求解器漏掉这个勾选是最常见的建模错误之一。点“求解”之后Excel会弹出一个结果窗口通常显示找到一解。可变单元格变成x1 3, x2 1目标单元格F2显示7和手算结果完全一致。这说明直接求解和规划求解两套路线互相校验通过。4.3 结果验证与敏感性报告规划求解结果窗口里还有一个选项叫“敏感性报告”。对于线性规划模型这份报告能提供非常有价值的边际信息。敏感性报告分两块可变单元格部分和约束部分。可变单元格部分会列出每个变量的“终值”和“递减成本”。本例中x1和x2的递减成本都是0说明两个变量都已经进入最优基目标函数值没法通过微调它们单独变得更好。如果某个非基变量的递减成本是正数就代表在这个问题的当前最优解里强行让它入基一单位会让目标函数损失多少。约束部分会列出每个约束的“阴影价格”。所谓阴影价格就是约束右端项增加1个单位时目标函数最优值的变化量。本例第一个约束x1 x2 4是等式约束它的右端项每增加1最优目标利润大约会增加2.5万元第二个约束x1 3*x2 6是大于等于约束它的右端项每增加1最优目标利润会减少0.5万元因为最低工时要求提高会限制排产空间反映在阴影价格上就是负的。这个符号问题特别容易让新手懵建议结合具体业务场景去理解对最大化的生产问题来说提高最低资源消耗门槛本身就是坏事。5. 两条路线怎么选直接求解与规划求解的实战对比5.1 核心差异对比同一道题两种方式都能得到正确答案但它们的脾性完全不同。放一张对比表看一眼就明白对比项直接求解手工迭代表规划求解原理可见性每一步检验数、比值、出基入基都明明白白黑箱只给最终结果学习价值高适合理解单纯形法和大M法低适合使用工具解决问题操作门槛需要知道算法流程会行变换只需要会建模和设置参数处理规模变量约束一多就非常累几十个变量几百个约束也轻松受环境限制不需要加载项需要加载规划求解加载项出错点符号、比值、M值、消元计算模型区域引用错误、漏掉非负约束交付效率低高从这张表可以看出直接求解最大的价值是“看得见”规划求解最大的价值是“算得快”。如果你只是想要一个结果去交差规划求解一分钟搞定但如果你想知道为什么是这个结果或者你正在学运筹学的单纯形法那直接求解就是最好的老师。5.2 我推荐的组合用法我个人的路线一直很固定先拿一个简单案例自己在Excel里把大M法的迭代表完整走一遍确定理解了每一步的逻辑然后把同一个模型用规划求解再算一次跟手算结果对账。对不上就回去查表多半是公式区域引用或者符号方向写错了对得上就可以放心用规划求解处理更大规模的问题。工作中如果有业务方追问“这个最优解是怎么来的”我也不会只说“规划求解算出来的”而是会打开之前的手算表把一张张迭代表翻给他们看。非技术背景的人不一定看得懂单纯形表但看到检验数、比值、目标值一步步变化他们会更相信这个结果不是拍脑袋得出的。这也是“直接求解”路线在真实场景里的隐藏价值它不只是教学工具还是沟通工具。6. 常见问题与避坑速查6.1 大M法手工迭代的翻车点大M法手算最容易翻车的地方我概括成三类。第一类是目标函数里忘了给人工变量加M惩罚。人工变量在初始表和约束里都老老实实加了但目标函数漏了-M*A1 - M*A2那初始检验数就少算了对应项后续迭代的入基选择会全部乱掉最后经常得到一个人工变量还在基里的假解。第二类是把检验数正负判断反了。求最大值的时候检验数大于0说明目标还能改善要继续迭代检验数全部小于等于0才是最优。求最小值时方向相反。很多新手在max问题里看到负数检验数就以为可以停了结果得到一个明显不对的解。第三类是最小比值规则用得不严谨。算比值时只考虑入基列系数大于0的行系数小于等于0的行不能参与分母比较。如果所有入基列系数都小于等于0说明目标函数在这个方向上可以无限增大问题无界。实际排产场景里出现无界通常说明建模时少写了某个资源约束。6.2 规划求解的异常现象规划求解虽然方便但也不是永远顺风顺水。我遇到过几次比较典型的异常。第一求解结果出现负数。十有八九是“使不受约束的变量为非负数”没勾上或者勾上之后又被后续约束区域设置覆盖了。打开对话框重新检查一遍就好。第二弹窗提示“求解器找不到可行的解决方案”。这种情况多半是模型本身无解也就是约束条件相互矛盾。我曾经把等式约束右端项填错了一位小数导致模型怎么都无解。后来我会习惯性把模型先手动估算一遍粗算发现结果不对再回查单元格排查效率高很多。第三求解结果出来了但目标值和手算不一致。这时候优先怀疑SUMPRODUCT公式的区域是否错位其次检查约束符号里“”和“”“”是否都准确写入。单纯形法对等号非常敏感等于号和大于等于号在业务上含义可能相近但在数学模型里是完全不同的约束。6.3 一张速查表把常见现象、原因和解决办法整理成一张速查表排查起来会快很多现象常见原因处理办法最优表里人工变量还在基内且值大于0原问题无可行解回查约束方向和右端符号人工变量一直出不了基M取值太小惩罚不足把M放大1到2个数量级检验数符号判断错max和min方向搞混统一转成max问题或简化成负系数比值θ出现负数或不能选入基列系数可能小于等于0只取正系数行若全为非正问题无界目标值与其他工具对不上模型区域引用错位用SUMPRODUCT逐区域核对Solver结果有负值非负约束未勾选重新打开设置勾选非负Solver提示无可行解约束冲突或RHS错误手动粗算验证可解性这张表不一定要背下来但建议保存在你习惯的笔记工具里。做实际决策时遇到结果可疑从这张表里找对应现象往往能比重新推演算法更快定位问题。最后再分享一个小体会我现在做这类优化交付环节基本都用规划求解因为它快、准、稳。但每当我拿到一个不太熟悉的模型或者优化结果跟业务直觉差得很远时我还是会把这几张单纯形迭代表铺开老老实实算上一遍。这不是浪费时间而是让Excel帮你把算法“摊开看”的过程。对刚接触大M法的朋友我的建议是别急着背判据先把这个案例的表格亲手做出来感受一次从负十万到七万的迭代过程你对单纯形法的理解会扎实很多。