简介线性规划单纯形算法实现资源面向运筹学、计算机科学等领域学习者和开发者用于解决资源分配、生产计划、网络流量优化等线性约束问题。包内提供C工程源码覆盖标准形式建模、单纯形表构建、基变量与非基变量迭代替换、检验数判断及终止条件等核心环节同时附带输入文本样例和可直接运行的程序便于对照代码理解算法流程。资源共17个文件以cpp源文件、头文件、txt数据文件及exe可执行文件为主并包含调试信息文件压缩包仅623KB结构简洁适合快速部署实验。已有1051人学习下载对于正在学习运筹学课程、准备算法实验报告或希望掌握单纯形法工程实现的读者可作为可运行的参考代码与学习模板。1. 线性规划到底解决什么问题从一杯奶茶的备货难题说起线性规划这个词听起来像高数课堂里的纸面模型。我第一次真正理解它是在一家奶茶店的备货问题上每天要决定进多少红茶、多少牛奶预算有限、冷柜空间有限还得保证不断货。多进哪样、少进哪样月底利润差一截。这个“在限制里找最优”的日常难题正是线性规划的典型样子。一句话定义线性规划是在资源有限的条件下用一组一次方程描述目标和限制求出让目标最大或最小的那套可行方案。它诞生于百年前的生产调度如今藏在排班、物流、投资配比的背后。搞懂它你就看懂了“凡事有约束、选择有最优”这句大实话是怎么被数学写下来的。2. 线性规划的三大积木变量、目标、约束怎么搭线性规划的模型说到底就三样东西有哪些数可以调、想达到什么目的、有什么条件不能破。这三样分别对应决策变量、目标函数和约束条件。第一次接触的人总被数学符号吓退其实它就像装修房子你可以决定刷什么颜色、买什么家具但不能超过预算也不能破坏承重墙。这三块积木缺一块模型就立不起来。没有变量你不知道该算什么没有目标算出来也不知道好坏没有约束答案往往是“无穷大”或“无穷小”毫无意义。下面逐个拆开看。2.1 决策变量你到底在定哪些“数”决策变量就是你可以拍板决定的数字。奶茶店的进货量、工厂的产量、货车的运量、员工的值班时长这些都是变量。它们的特点是每种选择都有一个取值范围而且变量之间会互相牵制。设置变量时最容易犯的错是把不该当成变量的东西当成变量。比如奶茶店决定“进 300 杯红茶”如果杯子数量不由你定而是总部配送、每单固定 300 杯那 300 就不是变量是常量。把常量当变量会让模型算出跟你实际权限不符的方案这种差距在落地时会导致“看着最优实际根本没权执行”。变量的数量直接决定问题复杂度。两三个变量画个图就能比划几十上百个变量就得靠算法在背后扫。建模时有个朴素的习惯能用一个变量说清的事别拆成两个。变量越少模型越好检查求解也越快。2.2 目标函数把“想求什么”写成一道算式目标函数是你心里那杆秤。做生意想利润最大做调度想成本最小做仓储想空间占用最少。把它写成数学算式就是给每个变量乘一个系数再相加。比如奶茶店的利润假设每杯红茶赚 6 元每杯牛奶赚 4 元进货量是 x1 和 x2那么总利润就是 6x1 4x2。目标是让这个算式尽可能大。注意这里有个“线性”的关键每个变量都只乘常数、只做加减不会出现 x1 乘以 x2也不会出现 x1 的平方。只要出现乘积、平方、开根号这类操作问题就从线性滑向了非线性难度和求解方式都会大变。写目标函数时最怕的是把“想优化的事”和“能算的数”搞混。比如你想“让顾客满意”但满意度不是一个能用函数直接算的数。这时得把满意度拆成“缺货次数”“平均等待时间”这类可量化指标。数学优化里流行一句话你不能优化一个说不清楚的东西。2.3 约束条件资源的边界一条都不能漏约束条件写的是所有不能越过的红线。预算不能超、库存不能爆、工时不能超、配额不能低于某个下限。每条红线都是一个等式或不等式。回到奶茶店进货总价不能超过 2000 元冷柜最多放 80 箱奶这两种限制都写成不等式。有的约束看起来多余但它恰恰是现实里“不得不”的那条腿。比如“至少进 30 箱红茶”不仅因为吧台要用还因为签了供货协议这是法律意义上的下限。漏掉这种约束模型给出的最优方案就是办公室里的空想。约束之间还会互相打架。预算想压到最低库存却要求足够大调来调去最终结果往往落在某条边界的交点上。这就是线性规划里最反直觉的一点最优解往往不是“平均一下”而是“顶在边界上”。后面讲误区时这一点还会回来。3. 线性规划能解决什么从排班、物流到把钱花在哪有人觉得线性规划只是课本习题实际上它是运筹学里应用最广的工具之一。只要资源有限、目标可量化、关系近似线性它就能上场。这一章看几个真实场景再聊聊为什么“线性”这件事本身非常有价值。3.1 生产计划在有限工序里排最优产量小工厂最常见的难题一台机器、两种产品、有限的工时和原料怎么排产量利润才最高这是教科书级的生产计划问题。木工车间做桌子和椅子桌子利润高但费木材椅子利润低但走量快到底做几桌几椅这类问题几十年前靠老师傅经验拍脑袋现在直接用线性规划设产量为变量把设备工时、原料库存写成约束把利润写进目标函数。答案给出后厂长还能看清每个约束的“影子价格”——机器每多开一小时利润能多多少。这直接指导了“要不要买新设备”这种投资决策价值远超算一次产量。生产计划里最常见的翻车点是把“生产准备时间”这种固定成本忘了。线性规划默认每个变量可以单独取任意正数但现实里开机、换模具都有一次性成本。这时需要引入整数变量或固定成本项模型就从纯线性变成混合整数线性规划求解难度上升但结果更接近真实操作。3.2 运输与排程路线、运量和时刻一起算物流调度员每天面对的问题是几个仓库、几十辆车、几百个订单怎么送才能总里程最短、油费最低。纯靠司机的感觉跑一趟可能绕路十公里。把每个订单送到哪个客户、由哪辆车送、装货多少写成变量把车辆容量、时间窗、司机最长工时写成约束线性规划能一次性给出一整套派车方案。地铁和公交的班组排班也一样。司机的班次必须覆盖早高峰每班不能超过规定时长空窗期不能太长。这些限制条件列出来以后“哪天安排哪位司机跑哪几趟”就是一串整数变量的问题。看起来和运输完全不搭边底层数学结构却几乎相同这也是线性规划最迷人的地方五花八门的行业场景抽象出来是同一类模型。排班问题里有个深坑叫“硬约束过多”。每个司机都要求周末休息每辆车都必须回原库约束堆到一定程度模型会直接无解。聪明的做法是给一部分约束设成“软约束”——允许违反但违反要扣分。这样模型总有解只是解在“尽量满足所有条件”的意义上最优。3.3 投资与人员把有限资源分配到回报最大处投资组合是一个经典的线性规划问题手里有一笔钱买哪几只资产、各买多少才能在风险不超过上限的情况下让预期收益最大。把每只资产的投资比例设为变量风险上限写成约束收益写成目标函数。老一辈讲“鸡蛋别放在一个篮子里”线性规划就是把这句经验变成精确的百分比。人员分配也一样。项目经理要做季度的人力规划几个项目同时在抢后端工程师每个项目需要不同人天每个人手上最多承担多少任务如何分配让所有项目的总延误最小。把人天当成可分配的“资源包”这就是一个典型的线性规划。调优结果出来后你会发现瓶颈不在某个工程师能力不够——这类问题常常会揭示“资源总量不足”和“分配结构不合理”是两个完全不同的问题。这些场景的共性是目标函数和约束关系都是加法式的。收益、成本、时长、人天这些数在现实里通常满足“加总”逻辑所以线性规划能给出好答案。如果哪天出现“两个人配合能产生三倍效果”这种非线性协同线性规划就会失灵那得换更重的工具。3.4 为什么“线性”反而是件好事可解、快速、好验证很多人一听“线性”就嫌太简单实际上“线性”是数学优化的金矿。因为线性函数没有拐弯抹角的行为可行区域是一个多面体最优解一定出现在某个顶点上。算法只需要在这些顶点里找不需要翻遍所有可能方案。这意味着三点。第一线性规划有成熟的求解算法几十年打磨下来几万变量的问题几秒钟就能算出结果。第二结果可以验证把求出的变量代回每个约束逐条检查是否满足比黑匣子神经网络可靠得多。第三求解器还会附带对偶信息和敏感性分析你能知道哪个约束最紧张、哪个系数涨跌会改变最优方案。这些“售后信息”在决策里的价值常常超过最优解本身。同样正因为线性模型里所有系数都必须可解释。利润是 6 元就是 6 元不随销量改变。现实里批发价越买越便宜那是非线性折扣这时你得把价格拆成几段分段线性拟合再放进模型。理解“线性假设”的边界比会调用求解器更重要这件事放到最后一章详细展开。4. 常见误区线性规划不是线性回归也不是越复杂越好很多人第一次看到“线性规划”四个字第一反应是“这跟线性回归是不是亲戚”。实际上它们一个管优化一个管拟合方向完全相反。这个部分整理了四个最常见的混淆和踩坑点每条按“为什么混、怎么区分”来讲。4.1 误区一线性规划等于线性回归线性回归做的是“根据一堆历史数据画一条线让所有点到线的距离之和最小”。它求的是“拟合已知数据”的参数。线性规划做的是“在约束下给出一组新方案”让目标函数最大或最小。一个是解释过去一个是决定未来。一个输入是数据样本输出是系数一个输入是约束和目标输出是决策变量值。之所以混是因为两者都出现“线性”“目标最小”这些词。回归里的“最小二乘”是让误差平方和最小规划里的“最小化”是让成本函数最小。连方法都不同回归常常用梯度下降或矩阵求逆规划用单纯形法或内点法。区分方法也简单你手上有过去 100 天的销售数据想了解价格和销量的关系那是回归你知道价格、成本和各产品的资源消耗想决定明天生产多少那是规划。一个是“看懂”一个是“决定”。如果目标变量有 y 的下标“预测值”八成是回归如果求的是“怎么分配”的方案数那就是规划。4.2 误区二约束越多越准其实可能直接无解新手建模有个通病觉得约束越多越严谨把能想到的限制全部塞进去。结果求解器一跑提示不可行。比如又要求总利润不低于 5 万又要求某个原料使用量不超过 1 吨可这两个条件在现有产能下根本不可能同时满足。可行域被约束挤没了模型自然无解。约束是把双刃剑每条约束都缩小可行域约束越多可行域越小最优解的选择范围越小。约束加到某个临界点可行域会变成空集再好的算法也救不回来。这时候求解器给不出方案只能靠你去“违约”——放开某条约束看结果那恰恰是敏感性分析派上用场的时刻。区分合理约束和多余约束有个办法逐条问自己如果去掉这条现实里真的允许吗比如“红茶进货量必须为正”几乎是废话因为进货量天然非负但“红茶不低于 30 箱”是合同要求就得保留。建模时少的不是约束是“对现实边界的理解”。好的模型不是约束多而是每条约束都精确描述了一条真实边界。4.3 误区三最优解一定藏在“中间”其实常常在顶点凭生活经验很多人以为最优方案是“平衡”的比如两个产品各做一半或者预算平均分配。线性规划给出的答案往往不是这样它倾向于把某个资源用满把某项指标压到极限其他项适当牺牲。拿两个变量的模型来说在二维坐标里可行域是一个多边形目标函数是一根可以平移的等值线。越往外平移利润越高但一旦离开可行域就违法。所以最优位置一定是“等值线与多边形边界相切”的地方而这个切点几乎总在两条边界的交点也就是多边形的顶点上。打个比方你背着一公斤行李去爬山想带最值钱的组合但你只有一公斤容量。最优解一定正好装到一公斤而不是留一段余量。这个特点在真实场景里很有用检查求解结果时看看哪些约束处于“刚好满足”的状态那些就是卡住收益的瓶颈。如果某个约束松松垮垮说明它根本没起作用可以考虑删掉。4.4 误区四建模完成等于求解完成模型跑不出结果就换算法“模型建好了”和“问题解决了”之间还隔着求解这一大步。常见的失败不是算法太慢而是模型本身有问题变量无界、约束冲突、浮点数值差异过大、甚至两个约束本来就是重复的。见过某开发者的模拟项目 X模型有 800 个变量求解器跑了一分钟没出结果后来发现有一条约束效率写反了导致可行域极其狭长数值上几乎退化。这时换算法通常没用要回头检查模型。一看变量是否有上下界二看约束是否语义矛盾三看系数尺度比如一个系数是 0.001另一个是 100000求解器在数值上容易出问题四看是否该用整数规划却用了连续变量。区分“模型错”和“算法不行”也简单先用小规模样例试跑如果小样例都解不对一定是模型问题小样例秒出结果换成大数据就崩才轮到讨论算法效率。记住一句话求解器不会骗你但它只会回答你写出来的问题不会回答你脑补的问题。5. 一个最小线性规划样例从建模到看懂结果前面讲了那么多这里用一个特别小的例子把流程串起来。目标不是教会你写代码而是让你看见“现实问题→数学公式→求解器答案”这条链上每一步发生了什么。这个流程你可以当成模板套到任何线性规划问题上。5.1 给一个做桌椅的小厂建模假设某木工作坊生产桌子和椅子。桌子利润 20 元一张椅子利润 15 元一把。每张桌子需 2 单位木材和 1.5 单位工时每把椅子需 1 单位木材和 2 单位工时。木材每天最多 120 单位工时每天最多 100 单位。问各生产多少利润最高设桌子产量为 x1椅子产量为 x2。目标函数利润 20x1 15x2要求最大。约束木材使用 2x1 1x2 ≤ 120工时使用 1.5x1 2x2 ≤ 100产量非负。这一个不等式组就是完整的线性规划模型。每个数字都能对应回车间的真实参数这是建模最要紧的检查方式。到这里你会发现“建模”本质上就是翻译把生产语言翻译成数学语言。翻译得越准确求解器给你的方案越可执行。很多初学者跳过翻译直接套模板改数据等到结果荒谬时才回头检查反而浪费时间。5.2 用代码把模型交给求解器模型一旦写清楚求解就交给程序。以 Python 里最常用的求解接口为例模型可以直接写成下面这段形式。注意这里的 c 表示目标系数linprog 默认求最小值所以求最大利润时要给系数取负号。from scipy.optimize import linprog # 目标最大化 20*x1 15*x2 # linprog 默认求最小值所以目标系数取相反数 c [-20, -15] # 约束条件A_ub * x b_ub # 木材约束2*x1 1*x2 120 # 工时约束1.5*x1 2*x2 100 A_ub [[2, 1], [1.5, 2]] b_ub [120, 100] # 变量边界x1, x2 都不为负数 bounds [(0, None), (0, None)] # 求解 res linprog(c, A_ubA_ub, b_ubb_ub, boundsbounds, methodhighs) # res.x 是最优产量-res.fun 是最大利润因为前面取了负号 print(res.x, -res.fun)这段代码每一步都有明确含义c 是你的店铺毛利A_ub 是每件产品消耗的资源b_ub 是手上每天的资源上限bounds 告诉求解器产量不能为负。跑出来的结果大约是 x1 50x2 20最大利润为 1300 元。这意味着多生产桌子更划算因为桌子单位利润高代价是它占用更多木材。模型写完后强烈建议做一个“人工冒烟测试”把 x1 和 x2 手动代入每个约束算一遍确认没违反任何条件。求解器给出的解一旦有数值误差靠这个步骤能立刻发现是资源超了还是利润算错。5.3 怎么读懂输出以及为什么最优往往是“贴着边界”求解器返回的不只是一组数字还有状态信息。res.status 如果是 0说明找到最优解如果是 2说明模型不可行如果是 3说明目标函数无界通常是漏了约束。这些状态码就是你的排查指南。更值得看的是哪条约束被“用满了”。这个例子里木材约束 250 120 120刚好等于上限工时约束 1.550 220 115还剩 5 单位。说明木材是当前瓶颈如果能买到更多木材利润还有上升空间而工时有余量说明工时不是当前卡脖子因素。“最优解贴着边界”在这里体现得特别直观木材量一点不剩全部转化为产品。这不是巧合而是线性规划在指定条件下必然的表现——如果某个资源还有富余就意味着还有加到满为止的增产空间。读结果时先看哪条约束紧、哪条松比看具体数值更能帮你理解业务的瓶颈在哪。6. 什么时候该用、什么时候别硬用线性规划的边界判断要不要用线性规划不是看问题里有没有“优化”两个字而是看三个前提是否同时成立变量可连续取值目标函数和约束都是线性的数据相对可靠。三个都满足就用缺一个就得想别的办法。第一个反例是整数决策。你不可能生产 0.4 台设备和招 0.7 个人变量一旦必须取整数就不是纯线性规划而是整数规划。求解难度会指数级上升需要用分支定界等更重的方法。常见错误是先把整数问题当线性规划解再把结果四舍五入。小规模问题四舍五入还能接受规模一大四舍五入可能带来约束违反或严重次优。第二个反例是非线性关系。采购量越大单价越低员工加班越久效率越低两产品共用生产线会产生交叉干扰这些都让目标或约束不再是简单的加减乘。此时强行线性化会得到漂亮但错误的答案。可以考虑分段线性近似或者直接上非线性优化工具别硬用线性规划装。第三个反例是数据波动太大。线性规划给出的方案是“基于你输入的准确数字”的最优解如果成本系数今天是 20、明天是 300输出结果根本没有稳定性。这种场景下与其追求一次最优不如用鲁棒优化或在模型里人为加安全余量。我自己在做过一个模拟项目 X 的时候就栽过跟头把人员排班当线性规划写忘了几位关键员工必须连休两天结果方案把所有休息堆在同一周经理看到计划直接拒绝。从那以后我每次建模前都强制走一遍检查变量能取小数吗约束是线性吗系数有依据吗确认完再调算法踩坑率低了一大半。线性规划是个好工具但它的边界练就的恰恰是你判断“值不值得用”的眼光。希望这篇文章能帮你看清这件事。本文还有配套的精品资源点击获取
