做生产计划、物流调度这类工作久了你会发现很多决策问题最后都归结成一个老面孔线性规划。Excel里的规划求解能一键给出答案但碰上带“大于等于”约束的模型直接求解出来的东西往往和教材例题对不上这时候把单纯形法大M法在Excel里手动搭一遍反而能帮你把整个求解过程看穿。这篇就聊聊怎么在Excel里用单纯形法的大M法求解线性规划包括手工搭建表格的“直接求解”路线以及用“规划求解”功能一步到位的路线最后比较两条路线分别适合什么场景。我尽量把表头、迭代步骤和常见坑都写清楚推荐给正在学运筹学、做课程设计或者想验证手算结果的同学。1. 先别急着打开Excel把模型写成标准形单纯形法不是拿到什么题都能直接算的它要求线性规划模型先转成标准形。我见过太多同学上来就把表格往Excel里一摆结果卡在负系数、剩余变量这类细节上。这一节我们先花几分钟把模型整理干净后面不管是手算还是用工具都会顺很多。1.1 一个带“”约束的典型题目为了后面好演示我假设一个小车间要安排两种产品A和B的生产。产品A每件利润1万元产品B每件利润2万元。设备工时有限制约束条件是2x1 x2 ≤ 10同时销售合同要求两种产品加起来至少要生产4件也就是x1 x2 ≥ 4这里 x1 和 x2 分别表示A、B产品的产量都是非负变量。目标函数就是最大化利润max z x1 2x2这个例子很小但很典型因为它同时包含“小于等于”和“大于等于”约束恰好是为大M法量身定做的题。如果你只想求解不大于约束的问题只需要松弛变量根本用不到大M法一旦出现“≥”或者“”约束初始基变量不好找人工变量就必须登场。1.2 松弛变量、剩余变量、人工变量到底往哪放先把两个约束改写成等式。第一个约束“≤”可以加一个松弛变量s1代表没用完的设备工时2x1 x2 s1 10第二个约束“≥”要先减去一个剩余变量s2因为左边比右边多出来的部分需要扣掉才能相等x1 x2 - s2 4问题是减掉s2之后如果想把s2当成基变量它的系数是-1不是单位向量没法直接作为初始基。所以还要再加一个人工变量a1x1 x2 - s2 a1 4a1本身没有任何实际经济含义纯粹是凑初始基用的。这样处理后s1的系数列是(1,0)a1的系数列是(0,1)它们构成单位矩阵可以直接当基变量。目标函数也要跟着改。因为我们在最大化问题里引入了一个“假变量”必须让它付出代价所以目标函数写成max z x1 2x2 - M·a1这里的M是一个非常大的正数代表对人工变量的“惩罚”。如果最优解里a1还留在基变量里并且大于0就说明原问题不可行这个后面会再细说。1.3 大M法的核心思想用惩罚把“假变量”赶走大M法听起来神秘其实本质上就是给人工变量标一个极高的“违禁价”。最大化问题里只要模型中还有可行解让人工变量留在基里就会把目标函数往下拉单纯形法会自动优先把它们换出基。你可以把这个过程理解成一个奖惩机制人工变量就像一个不应出现的临时工你给它开一个极高的“工资成本”优化器为了把利润做到最大会想方设法把它辞退。只要最终最优解中人工变量等于0说明“临时工”已经被完全清退剩下的解就是原问题的真实最优解。反过来如果迭代到最后人工变量仍然是正的基变量说明模型本身可能是矛盾的或者约束条件之间冲突导致无可行解。这是大M法自带的一种“报警机制”非常有用。2. 手算一遍单纯形表把每一步看透很多同学用Excel规划求解直接出结果但完全不知道数字怎么来的。我建议至少在练习阶段手算一遍单纯形表这样后面在Excel里搭公式才不会瞎填。下面我用刚才那个模型完整走一遍大M法迭代。2.1 建初始单纯形表模型整理之后变量顺序为x1、x2、s1、s2、a1。目标函数系数分别是c [1, 2, 0, 0, -M]基变量先取s1和a1对应的基系数是0和-M。初始单纯形表如下基变量基系数x1x2s1s2a1RHS比值s10211001010a1-M110-1144检验数M1M20-M0-4M这里的检验数行按 cj - zj 计算。以x1列为例zj 2×0 1×(-M) -M所以 cj - zj 1 - (-M) M1。检验数行的右端值是当前目标函数值等于 -M×4也就是 -4M。在最大化问题里入基变量选检验数最大正值那一列。M看作一个足够大的数显然M2比M1更大所以x2入基。2.2 第一次迭代确定主元接着看比值。比值的意义是把某个基变量换成入基变量后约束能撑住多少。x2列对应的比值第一行10 / 1 10 第二行4 / 1 4选最小正比值也就是第二行出基a1离开基变量。主元位置就在第二行、x2列交叉处主元值是1。现在做行变换。主元行整体除以主元值也就是不变第一行要消去x2列的第一个元素1。具体操作第一行新值 第一行旧值 - 1×主元行新值因为主元行第二行和第一行在x2列都是1直接用减法就能消元。更新后的单纯形表如下基变量基系数x1x2s1s2a1RHS比值s101011-166x22110-114-4舍去检验数-1002-M-28注意这一轮人工变量a1已经顺利出基接下来的表格里它的作用已经完成了。检验数行里s2列出现正值2说明还有改进空间继续进行下一轮迭代。2.3 第二次迭代收敛到最优s2入基。看s2列的比值第一行6 / 1 6 第二行4 / (-1) -4负比值必须舍去因为如果采用负比值会让基变量变成负数违背非负约束。所以第一行出基s1离开主元位置在第一行、s2列主元值为1。行变换后得到最终表基变量基系数x1x2s1s2a1RHS比值s201011-16x222110010检验数-30-20-M20检验数行全部小于等于0达到最优。最优解是 x210x10目标函数最大值 z20。带回原约束验证一下2×01010满足设备工时01010≥4满足合同约束。结果正确。这里有个小技巧最优解中直接看基变量那一列对应的RHS就是变量取值非基变量x1、s1等取0。在这个例子中s26意味着剩余变量等于6也就是产量超出了最低合同要求6件。2.4 最优解的经济含义单纯从数值看这个车间应该把全部产能放在产品B上生产10件B不生产A利润20万元。这看起来有点“极端”但线性规划的最优解往往落在可行域的顶点上顶点通常就是某些变量取0的角点。如果业务上不允许出现零产量那就需要额外加下界约束比如x1≥1然后重新求解。这个属于模型调整的范畴不在单纯形法的核心流程里但值得你在实际应用中留意。3. Excel直接求解把单纯形表做成可复用的模板现在进入正题怎么在Excel里直接搭建大M法的单纯形表。手动在纸上迭代没问题但在Excel里做的好处是修改系数后能快速重算还能用公式防止手误。3.1 工作表怎么布局最顺手我试过好几种布局最后觉得“一行一个基变量、列按变量排开”最直观。在Sheet中按照下面的结构准备行内容第1行变量名x1、x2、s1、s2、a1、RHS第2行目标函数系数1、2、0、0、-M第3行第一条约束2、1、1、0、0、10第4行第二条约束1、1、0、-1、1、4第5行基变量名s1、a1第6行基系数0、-M第二步再往下留两行放检验数行和比值列。检验数行用公式计算不要手填这样才能保证每次修改系数后自动更新。检验数公式可以这样写。假设C列开始放变量系数基系数放在B6:B7区域约束矩阵在C3:H4区域那么某个变量列的检验数可以表示成目标系数 - SUMPRODUCT(基系数, 该列约束系数)例如x1列检验数就是C2 - SUMPRODUCT($B$6:$B$7, C3:C4)拖拽填充整行即可。比值计算就更容易RHS除以入基变量列对应系数只取正数。3.2 行变换公式只记住两条规则每次迭代的核心就是主元运算。新手最容易在这里写错公式其实规则只有两条。第一条新的主元行等于旧的主元行除以主元值。假设主元在第4行第D列那么新主元行的任意一个单元格C8可以用C4/$D$4复制时需要把主元单元格固定用$D$4锁住行和列。第二条其他行的新值等于旧值减去“旧主元列对应元素”乘以“新主元行对应值”。假设第3行是其他行主元列是第4行的D列那么新的第3行任意单元格可以写C3 - $D$3 * C8这里的$D$3表示第3行在主元列上的旧值C8表示新主元行在变量列上的值。实际操作时我会在表格右侧并排放两三个表的区域每个区域代表一轮迭代。第一轮表在主区域第二轮表复制到旁边修改主元行和公式第三轮继续复制。这样每一轮都能对照不容易乱。3.3 迭代到什么时候停手单纯形迭代的停止条件就一句话检验数行全部小于等于0。对最大化问题来说只要还有正检验数就说明目标还能继续增大。在Excel里可以用IF函数做一个自动判断。比如在检验数行末尾加一个状态单元格IF(MAX(检验数区域)0, 已最优, 继续迭代)如果写着“继续迭代”就去检查最大的正检验数对应哪一列然后计算比值确定出基行再做行变换。熟练后一轮操作大概两三分钟小规模问题不会超过三五个表就能出结果。3.4 别忘了最后验证一组约束迭代结束后我强烈建议你别只看目标函数。把最优解代回原来的约束条件在Excel里单独开一个验证区。比如x210x10那么设备工时约束就是2×01×1010正好等于10合同约束是01010大于等于4。两个约束都成立目标值等于20。如果有任何一条不满足先回头检查标准形转换尤其是剩余变量和人工变量的符号这个环节最容易被符号带沟里。4. 用规划求解功能一条龙搞定如果不想一张表一张表地迭代Excel自带的规划求解功能可以直接帮你完成任务。它的底层算法也包含单纯形法但对用户隐藏了迭代过程只需要把模型单元格摆好。4.1 先把加载项打开很多版本默认不显示规划求解按钮需要手动加载。操作路径是文件 → 选项 → 加载项 → 转到Excel加载项 → 勾选“规划求解加载项” → 确定。加载完成后“数据”选项卡右侧会出现“规划求解”按钮。如果找不到这个加载项可能是办公软件版本太精简需要安装完整的Excel组件。我遇到过有人卡在这里很久其实重新安装Office就能解决。4.2 建立变量、目标、约束单元格规划求解需要一个清晰的模型区。我习惯这样布置D2和E2放决策变量x1、x2F2放目标函数公式D2*B2 E2*C2这里B2、C2分别存放目标函数中x1和x2的系数也就是1和2。再往下建两条约束对应的左侧公式D2*B4 E2*C4表示设备工时D2*B5 E2*C5表示合同产量B4:C4位置写第一条约束的系数2和1右边约束值是10B5:C5位置写第二条约束的系数1和1约束值是4。4.3 设置规划求解参数打开规划求解对话框参数设置如下“设置目标”填F2方向选最大值 “通过更改可变单元格”填D2:E2 “添加约束”中加入F4 10F5 4D2:E2 0这里最关键的一步是选择求解方法。在“选择求解引擎”下拉菜单里必须选“单纯线性规划”不能默认用GRG非线性。线性规划模型用单纯形法才能保证找到全局最优解GRG非线性虽然也能算线性问题但容易在边界上出现问题。点击“求解”Excel会很快给出结果x10x210目标值20和手算完全一致。4.4 保存方案与敏感性报告规划求解出结果之后不只有一个数字就完了。在“规划求解结果”对话框里Excel允许你保存方案也能生成报告。常见的报告有三种运算结果报告、敏感性报告、极限值报告。敏感性报告对实际决策很有用它会告诉你每个约束的影子价格以及目标系数在哪个范围内变化不会影响最优解结构。比如设备工时约束的影子价格可以理解为每增加1个单位设备工时能带来多少利润提升。这比单纯看一个最优产量更贴近管理决策。我建议你每次都勾选生成报告放到单独工作表里这样后续答辩、汇报时可以直接引用。5. 直接求解与规划求解怎么选有哪些坑既然两条路都能求出答案那到底该用哪种说实话我的经验是确认答案用规划求解学习原理用直接求解手算一遍再用规划求解验证两边都能对得上这个结果才敢放心用。5.1 两条路线的合适场景对比维度直接求解手动迭代规划求解教学理解极高每一步都透明较低黑箱出结果操作速度慢尤其变量多时快几秒完成可变规模小规模一般50×50以内勉强中大规模也能处理出错风险符号和公式容易错参数设置容易错是否需要人工变量需要大M法核心不需要工具内部处理报表与敏感性分析无靠自己整理自带报告非常方便如果你的目标是搞懂单纯形法的来龙去脉直接求解必须做一遍。如果你是做项目、赶报告优先用规划求解节约时间。最理想的组合是先用规划求解得到答案再用手动表验证一两步关键迭代这样既有速度又有说服力。5.2 我用着最难受的几个大M坑我在Excel里手算大M法踩过不少坑挑几个最典型的分享。第一个坑是M值取太大。很多人觉得M越大越保险直接填-1000000000结果Excel浮点运算出现精度问题检验数全是乱码。我的做法是让M比模型最大系数大100到1000倍就够了比如这个例子最大系数是2M取1000都绰绰有余没必要用天文数字。第二个坑是负比值当成出基行。比值检验只看正数负数说明该约束在当前迭代下不支持入基变量增加强行选取会让基变量为负。这个错误手算时容易犯Excel里也容易选错行。第三个坑是人工作变量提前出基后还继续盯着看。人工变量一旦离开基变量就相当于被“开除”了后续迭代可以直接忽略那一列省很多事。你继续算也不会错但会增加不必要的计算量。第四个坑是忽略退化现象。当两个比值相等时叫退化可能出现基变量为0的情况。如果遇到退化和循环单纯形法可能来回绕。Excel直接求解时我建议如果连续三轮检验数、目标值都没变化就检查一下是不是遇到循环了必要时换成规划求解或者两阶段法。5.3 常见问题快速排查表现象可能原因处理办法最优解中人工变量大于0原问题无可行解检查约束之间是否矛盾检验数一直有正数但迭代不进去比值均为负或无正主元重新检查变量符号和模型标准形M太大导致数值异常浮点精度不足减小M或换用两阶段法规划求解提示线性条件不满足目标或约束里用了非线性函数检查公式中的乘除和嵌套函数手算结果与规划求解不一致手算主元行选错或符号写错用规划求解结果反推逐步验证每一轮表格变量出现负数漏了非负约束在规划求解中添加D2:E20最后分享一个我常用的验证技巧把最优解代回原约束检查剩余量和松弛量是否合理。比如这个例子中s26说明实际产量超过合同要求6件。你在Excel里单独设一列自动算剩余变量和松弛变量一眼就能看出模型是否可靠。按这个流程走即使以后遇到几十个变量的生产计划问题也不容易被数字骗过去。