企业官网建设流程全解析

简介：线性规划单纯形算法的完整 C++ 实现资源，面向运筹学课程学习者、算法竞赛入门者及需要做优化开发的程序员，重点解决线性规划模型的程序化求解与单纯形表的手工演算对照问题。压缩包共 17 个文件，包含 LinearProgram.cpp、StdAfx.h 等源码文件，编译生成的 exe 可执行程序，input.txt 示例输入与输出文本，以及 dsp/dsw/opt/plg 等 Visual C++ 6.0 工程配置文件和 pdb/ilk/obj 调试中间产物。工程按教科书经典流程实现标准形式建模、非基变量检验数计算、入基出基迭代、最优性判定，并支持不等式约束向等式约束的转换，涵盖 slack 变量与人工变量的处理逻辑。代码注释清晰，配合 ReadMe 与示例数据，可以边运行边观察目标函数变化，也能在此基础上扩展两阶段法或对偶单纯形法。目前已有 1051 人学习，适合希望弄懂算法细节并通过源码验证自身理解的读者。

1. 线性规划到底是什么：一张运货单背后的“最优解”问题

线性规划这个词，第一次听到的人往往会被“规划”两个字吓住，以为是要做很复杂的计划，或者是什么玄学方法。其实它干的事情非常朴实：在资源有限的前提下，算出怎么分配才能让某个目标最大或者最小。打个比方，你有一辆卡车要往几个超市送货，每家要的数量不一样，车子的载重有限，油耗也随路线变化。你该怎么安排每家送多少，才能既满足需求，又把运输成本压到最低？这个问题就是线性规划的典型场景。

这里的“线性”指的是目标函数和约束条件里，所有变量都只是一次方，不存在平方、相乘或者对数这种弯弯绕绕的关系。正因为关系简单，它才有了成熟高效的求解算法。搞懂线性规划，等于掌握了一把能处理大量现实资源分配问题的钥匙。

小到早餐店的面粉配比，大到几千个网点的物流调拨，背后都可能藏着一个线性规划模型。接下来我会从“为什么需要它”开始，一步步把这个概念讲透。

2. 为什么需要线性规划：手算已经崩了，数学还撑得住

2.1 约束条件：不是你想怎么做，而是你只能这么做

现实中做决策永远不是“想怎么来就怎么来”。做面包需要面粉、鸡蛋、黄油，还有烤箱时间；接项目需要人力、工时、预算；发货需要库存、运费、运力。这些限制在数学上叫做约束条件。线性规划的第一步，就是把它们写成不等式。比如你手头有 60 公斤面粉，做 A 面包每袋要用 1.2 公斤，做 B 面包每袋要用 0.8 公斤，那就有一条约束：1.2A + 0.8B ≤ 60。这里的 A 和 B 就是变量，代表两件事的投入数量。

也许你会说，这不过是初中数学的“列不等式”，有什么稀罕？但真实世界的约束不是一条，而是一堆。超市有需求下限，工厂有产能上限，物流有运力上限，资金有预算上限。几十条约束堆在一起，变量之间还互相牵制：你多做了 A，就需要更多面粉和黄油，烤箱时间也没了，B 就得少做。人脑分析两三条约束还能应付，五条以上就容易顾此失彼；等约束到了几十条、几百条，连“哪些组合合法”都判断不过来，更别说“哪个组合最好”。

这就是线性规划存在的第一个理由：它把现实中“这也不行、那也不行”的规则，用一组标准的不等式翻译成机器能理解的语言。机器不擅长“聪明”，但擅长“挨个检查”。只要约束写成数学形式，它就能一条一条核对，把所有可行方案筛出来。这样，决策就从一个靠感觉的“拍脑袋”问题，变成一个可计算、可复验的数学问题。

2.2 目标函数：在允许范围内找到更好的那个

有了约束，你只能在一个范围内做选择。可“都能满足”不等于“都好”。你要的是在一个明确的目标下找到最好的方案。比如面包房希望总利润最大，每卖出一袋 A 面包赚 5 元，每卖出一袋 B 面包赚 3 元，总利润就是 5A + 3B。这个总利润公式就是目标函数。

为什么一定要有个目标函数？因为没有目标，规划就没有方向。你可能会说：“我全做利润最高的 A 不就行了？”但别忘了约束条件不是摆设。面粉虽然是够的，但黄油和烤箱时间很可能不够。于是问题变成了：在 A 和 B 之间找到一个配比，让总利润最高。这有点像你把一笔钱分成两份投资，A 收益高但风险大，B 收益低但更稳，究竟怎么分，取决于你要在“风险不超过某个值”的前提下追求收益。

线性规划里的目标函数可以求最大，也可以求最小。最大常见于利润、产量、满意度；最小常见于成本、运输距离、等待时间。不管哪种，它都刻画了你想把什么指标做到极致。而约束条件和目标函数合在一起，才构成一个完整的优化问题。缺了约束，答案是“无限大”或“全做 A”这类空话；缺了目标，你是“有方案但不知道选哪个”。两个放在一起，才叫“规划”。

还要注意，目标函数里的变量必须都是一次方。如果写成“每多生产一个产品，单位利润反而下降”，那变量之间就不是单纯的线性关系，这种问题已经超出线性规划的适用范围，得用别的工具。这个区分非常关键，后面会有专门章节讨论。

2.3 一个小例子：面包房的配比难题

拿面包房来具体感受一下。假设每天可用面粉 60 公斤、黄油 20 公斤、烤箱工时 18 小时。A 面包每袋要面粉 1.2 公斤、黄油 0.4 公斤、烤箱 0.3 小时，利润 5 元；B 面包每袋要面粉 0.8 公斤、黄油 0.2 公斤、烤箱 0.4 小时，利润 3 元。算一算两种面包各做多少袋利润最高。

先把约束写出来：

• 面粉：1.2A + 0.8B ≤ 60
• 黄油：0.4A + 0.2B ≤ 20
• 烤箱：0.3A + 0.4B ≤ 18
• 产量非负：A ≥ 0, B ≥ 0

目标函数是 max 5A + 3B。如果不开机计算，纯靠脑子试，可能先想到“全做 A”，但黄油限量 20 公斤，A 每袋要 0.4 公斤黄油，最多做 50 袋；而此时烤箱时间要 15 小时，面粉要 60 公斤，刚好都在边缘。总利润是 250 元。可你回头一看，B 每袋只费面粉和黄油的一半量，烤箱却要 0.4 小时，是不是可以做一点 B 来释放面粉，同时提高利润？再试“全做 B”，B 最多受烤箱限制：18 ÷ 0.4 = 45 袋，利润只有 135 元，明显更低。那最佳答案一定在 A 和 B 混搭中间。

这类“试几个极端值”的方法，在变量少时管用，可一旦变量变多，你连“极端值”都数不清有多少个。线性规划的求解算法，会系统地去检查所有可能的配比。回到这个例子，最优解大约是把 A 和 B 调整到一个让总利润超过 250 元的组合。具体是多少，下章用可视化方法算清楚。这里想让你记住的是：线性规划把“怎么搭配”的问题变成一个可以提交给计算机的标准命题，你只需要告诉它“约束是什么，目标是什么”，它就能给你一个明确答案。

3. 线性规划怎么算：从可行域的顶点一步步“走到”最优解

3.1 可行域：所有可能答案围成的一片区域

上一章的面包房问题，只有 A 和 B 两个变量。把 A 画成横轴、B 画成纵轴，每个约束都对应一条直线，并在直线的一侧是合法区域。比如面粉约束 1.2A + 0.8B ≤ 60，把所有满足它的点标出来，会落在一条直线的右下侧。同样，黄油、烤箱、非负约束各自切掉一块区域。这些区域叠在一起，最后剩下的共用部分，就是一个多边形。这个多边形叫做可行域。

可行域里的每个点都给出一套方案：横纵坐标代表 A 和 B 的产量。只要这个点在多边形内部或边上，就代表面粉、黄油、烤箱都够用，产量也都是非负的。而多边形外面的点，至少违反某一条约束，是不可行的。你可以把可行域理解成一片“安全区”，所有正经可行的方案都在里面，外面全是坑。

如果有三个变量，可行域变成一个三维的多面体；变量更多，就是高维空间里的一个“超多面体”，眼睛看不见，但数学上依然存在。不管维度多高，可行域都有一个共同特征：它是一个凸的几何体。所谓凸，就是区域内任意两点连一条线，整条线都在区域内部。这个“凸”不是随意出现的，它是因为所有约束都是线性的。也正是因为凸，后面寻找最优解的方法才变得又简单又可靠。

3.2 最优解为什么总在顶点上

现在假设你想最大化总利润 5A + 3B。在 A-B 图上，令 5A + 3B = 某个常数 c，会得到一条直线。同一个 c 上所有方案的利润都相同，所以它叫等值线。c 越大，这条线就越往右上方向移动；c 越小，越靠近左下。你需要做的是：从远处慢慢把这条等值线往可行域方向推，第一次碰上可行域的那个点，就是能取得最大 c 的可行方案。

如果等值线扫过可行域的内部，说明还能继续推；只有等值线就要离开可行域、与它相擦而过的瞬间，c 才最大。而这个“相擦”的位置，在绝大多数情况下是可行域的一个顶点，也就是两条约束直线的交点。比如多边形的一个角，正好是产量 A 和 B 的临界组合。为什么不会是边上的其他点？因为如果你在一个边的中间停下来，等值线还可以顺着边再往前走一点，让 c 增大，除非目标函数恰好和这条边平行，那整条边都是最优解。但即便有这种特殊情况，端点也仍然是最优解之一。

这个结论很重要：求解线性规划，本质上是检查可行域的所有顶点，而不是检查无限多个点。顶点是有限的，因为它是约束直线的交点。两个变量时，顶点就是两条线的交点，数一数就知道有多少；100 个变量时，顶点数量可能会爆炸式增长，但至少“有限”给了算法一个收敛的方向。这也解释了为什么线性规划的计算可以机械化：与其漫无目的地搜索，不如从一个顶点跳到另一个顶点，直到最优。

3.3 单纯形法：从一个顶点跳跃到另一个顶点的爬山法

单纯形法就是利用“最优解在顶点”这个性质设计的。它的思路非常简单：先从可行域随便找一个顶点作为起点，然后沿着可行域的边，看向相邻的顶点，有没有哪个能让目标函数变得更好？如果有，就移动过去；再重复这个过程，直到没有任何相邻顶点能进一步改善目标函数，当前顶点就是最优解。

你可以把它想象成在一个多面体的表面爬山。你站在某个角上，向四周看看，哪个角更高，就跳过去；跳到新角后，再向四周看，直到周围没有更高的角。因为多面体是凸的，所以不用担心爬到半山腰的假峰，也不需要回头路。整个过程就像“走一步看一步，但每一步都是向上的”，所以它非常直观。

下面用一段简短的代码来表示单纯形法的主循环，它对理解核心逻辑很有帮助：

# 假设已经得到了初始顶点和对应的目标函数值 current_vertex = get_initial_vertex() current_value = objective(current_vertex) while True: neighbors = get_adjacent_vertices(current_vertex) # 找出所有相邻顶点 best_neighbor = None best_value = current_value # 在所有相邻顶点中找一个能让目标函数值提升的 for neighbor in neighbors: candidate = objective(neighbor) if candidate > best_value: best_value = candidate best_neighbor = neighbor # 找不到更好的邻居，说明已经站在最优解的顶点上 if best_neighbor is None: break current_vertex = best_neighbor current_value = best_value

这段代码省略了“怎么找初始顶点”“怎么列出相邻顶点”这些底层细节，它们需要矩阵运算和专门的判定逻辑，但主循环就是上面这个“不断跳到更好的邻居”的过程。实际工程中，你不会手写这段代码，而是直接用成熟的求解器。但理解了主循环，你就知道求解器在“黑匣子”里干什么了。

单纯形法是线性规划最早也最著名的算法。后来还出现了内点法，它不从顶点之间跳，而是从可行域内部“笔直”地逼近最优解，适合变量特别多、约束矩阵特别稀疏的大规模问题。不管用哪种算法，它们都依赖同一个事实：可行域是凸的，最优解存在于顶点或边界。这也是为什么线性规划被研究得这么透彻，因为它的“地形”太规整了，算法几乎不会迷路。

4. 线性规划常见的误区：它和整数规划、非线性规划的区别不是一点点

学习线性规划的人，最容易在概念边界上翻车。很多看起来“差不多”的词，实际运用起来差得十万八千里。下面这几个误区，是初学者最常踩的坑。

4.1 误区一：把“线性”当成“一条线”

易混点：线性规划的名字里有“线性”两个字，很多人以为它只能处理画出来是一条直线的问题，甚至以为解出来的答案是一条线。

为什么混：因为“线性”在数学上指变量都是一次方，而“线”这个字很容易让人联想到几何里的直线，于是想当然地以为“线性规划 = 沿着一条直线规划”。

怎么区分：线性规划里的“线性”说的是目标函数和约束条件中，变量之间没有平方、立方、乘积、三角函数这类非一次关系。但它所描述的可行域，在二维时是一个多边形，在三维时是一个多面体，不是一条线。最优解通常是一个点，也就是一组变量的取值，而不是一条线段。你可以把“线性”理解成“所有效果按比例叠加”，而不是“画出来是直的”。

举个例子，目标函数 3x₁ + 4x₂ 是线性的，但 3(x₁)² + 4x₂ 就不是；约束里出现 x₁·x₂ ≤ 10 也不再是线性。把这些“非线性”混入后，可行域不再凸，最优解不一定在顶点，单纯形法也就失效了。所以判断是不是线性规划，标准不是“图像直不直”，而是“变量次数是不是都是一次方”。

4.2 误区二：以为所有带“规划”的问题都能用线性规划硬套

易混点：很多新手遇到任何优化问题，第一反应就是“我设一堆变量，写上目标函数和约束，然后用线性规划求解”。结果发现解出来的东西根本没法用。

为什么混：因为线性规划是优化领域里最成熟、最容易入门的工具，大家学了一个上手工具后就容易把它当成万能锤子，看到什么问题都想敲一下。

怎么区分：线性规划要求变量是实数、可任意分割，还要求目标函数和约束都是线性表达式。如果变量必须是整数，比如“派几辆车”“建不建仓库”，那是整数规划；如果目标函数里出现 x²、x·y、log(x) 这类项，那是非线性规划；如果参数本身不确定，那还需要随机规划或鲁棒优化。这些问题都有专门的方法，乱用线性规划算出的结果往往在现实中根本无法执行。判断的起点是：能不能把你的问题写成“变量的一次方组合 + 小于等于某个常数”这种形式，能才考虑用线性规划。

比如“派车问题”，变量是车辆数量，必须整数。线性规划可能算出 3.7 辆车，这在实际派车时就是笑话。这类问题应该用整数规划，它会在整数集合里搜索最优解，虽然计算更慢，但结果可以直接执行。

4.3 误区三：混淆“问题”和“求解算法”

易混点：把单纯形法、内点法这些算法直接称为线性规划，或者反过来把线性规划当成某种具体算法。

为什么混：因为教材和教程经常用“线性规划求解”来指代“用单纯形法求解”，讲多了，就以为它们是同一个东西。

怎么区分：线性规划是一个数学问题，它定义了“目标函数 + 约束条件”这种结构；单纯形法、内点法、椭球法都是求解这个问题的算法。就好比“去北京”是一个旅行目标，“坐高铁”“坐飞机”是到达目标的方法。你可以说“用单纯形法解线性规划”，但不能说“单纯形法就是线性规划”。这层区分在工程中很重要：当你换一个求解器时，问题模型没有变，变的只是算法和实现。原本用单纯形法求解不了的大规模问题，换成内点法可能就很快，但你要写的模型还是那套目标函数和约束。

4.4 误区四：以为最优解永远只有一组固定数字

易混点：看到求解器输出一个 x₁=3, x₂=5 的结果，就认为这是唯一答案，没有其他可能。

为什么混：因为在大多数教学例题中，等值线和可行域顶点是错开的，确实只有一个顶点是最优解，于是大家形成了“最优解=唯一解”的刻板印象。

怎么区分：当目标函数的等值线恰好和可行域的某一条边平行时，这条边上的所有点都能取得相同的目标函数值，这时存在无穷多个最优解。这种情况下，求解器可能只返回其中一个顶点，但它并不是唯一的答案。实际做决策时，知道“有多组同优方案”很有用，因为除了目标函数，你还可以在这些方案里挑一个对执行更友好的，比如消耗原料更少的那个。所以在用求解器时，可以额外查看是否存在多个最优解，别把返回的第一个解当成唯一真理。

5. 线性规划能用在哪些地方：排产、物流、投资，以及更多

5.1 资源分配：多个项目抢同一批人

一家外包公司接了好几个项目，每个项目都需要前端、后端、测试的人力投入。假设公司只有固定的 20 名开发、8 名测试，每个项目需要的各角色工时不同，项目利润也不同。问题是怎么把这批人分配到各项目，让总利润最大，同时每个项目的人员投入必须在一个范围内。这就是资源分配问题。

它的模型和面包房问题本质一样，只是“面粉”换成了“人天”，“面包”换成了“项目”。变量是每个项目投入多少人天，约束是每个角色的总投入不能超过现有规模，目标函数是所有项目利润的总和。这类问题在软件公司排期、工厂排产、医院排班中很常见。线性规划的好处是它能同时处理“资源有限”和“优先级不同”两个要求，而且在需求变化时，可以快速重新计算一套新方案。

建模的时候有个小技巧：先把决策变量列出来，再写约束，最后写目标函数。这个顺序能避免你漏掉某条重要限制。比如现实中“项目 A 和项目 B 不能同时做”这种互斥要求，如果写成 x_A + x_B ≤ 1 但变量又被定义成连续实数，那模型就会允许 0.5 个 A 和 0.5 个 B 同时存在，显然不对。这种时候你就得提醒自己，该上整数变量，而不是硬用线性规划。

5.2 运输调度：多个仓库送多个门店

经典的运输问题：你有 3 个仓库，5 家门店，每个仓库有库存上限，每家门店有需求量，从每个仓库到每家门店的单位运费不同。问怎么安排运输量，让总运费最低。变量就是“从仓库 i 到门店 j 送多少货”，约束是每个仓库运出的总量不超过库存，每家门店收到的总量满足需求，目标函数是所有运输路线运费之和。

这类问题的规模往往很大。比如 100 个仓库、1000 个门店，变量就有 10 万个，约束也有上千条。线性规划在这种规模下依然能求解，因为约束矩阵的结构是稀疏的，很多位置上是 0。农业、电商、快递行业都在用类似模型做每日调拨。你不需要记住具体的算法，只需要知道：只要运费和运输量成正比（即“线性”），这个问题就是线性规划，可以用标准解法来处理。

5.3 投资组合：风险和收益的线性权衡

再来看一个金融场景。假设有几种理财产品，每种产品每投资 1 万元的预期收益和风险值已知。你的总资金只有 200 万，并且希望整个组合的风险不超过某个上限。目标是最大化总预期收益。每份投资的收益和风险都按比例线性累加，所以这也是一个线性规划。

当然，真实的投资组合优化经常用更复杂的模型，因为风险度量可能是“方差”这种平方项，那就变成二次规划了。但当你用“风险打分”这种线性指标时，线性规划依然能给出不错的参考。这也提醒我们：同一个场景，不同假设会得到不同数学模型，先搞清楚关系到底是不是线性的，再决定用什么工具。

5.4 一个直观实现：用一段代码求解一个小模型

有了上面的场景，我们看一个最简单的代码实现。下面用一个抽象求解器接口，求解一个两变量的线性规划模型。假设现在有两种产品，变量为 x 和 y，目标函数是最大化 3x + 2y，约束是 x + y ≤ 4，2x + y ≤ 5，且两个变量非负。

# 用列表表示变量系数，直接构造一个线性规划模型 from some_solver import solve_lp # 目标函数：max 3*x + 2*y model = { "objective": [3, 2], "constraints": [ {"coeff": [1, 1], "rhs": 4, "type": "<="}, {"coeff": [2, 1], "rhs": 5, "type": "<="}, ], "bounds": [(0, None), (0, None)], # x, y 下界为 0，上界不限 } # 调用求解器，maximize=True 表示求最大值 result = solve_lp(model, maximize=True) print("x =", result.x[0], "y =", result.x[1]) print("最优目标值 =", result.value)

这段代码里，objective是目标函数系数列表，对应 3x + 2y；constraints是约束列表，每一项都用coeff表示不等号左边的系数，rhs表示右边的常数，type表示符号；bounds规定了每个变量的取值范围。实际使用中，你只需要把真实的约束系数填进去，求解器会返回最优的取值和对应的目标值。这个模型换成“人天分配”“仓库运输”，只是变量个数和系数不同，结构完全一样。

看到这里你应该能感受到，线性规划的建模有很强的“套路”感：先找到决策变量，再把限制翻译成不等式，最后把目标写成一次方表达式。掌握这个套路之后，很多看起来完全不同的领域问题，其实都在同一套数学框架下。

6. 什么时候该用线性规划，什么时候别用：一个老开发者的踩坑教训

6.1 该用的场景：变量连续、关系线性、约束明确

线性规划适合处理这样的问题：变量可以取小数（比如时间、重量、金额），所有资源消耗按比例累加，目标只有一个且想最大化或最小化。典型信号是“每增加一个单位，效益和成本都固定增加”。比如排产、运输、库存管理、广告预算分配，只要你能写出一次方的目标函数和不等式约束，大概率属于线性规划。

6.2 不该用的场景：整数决策、非线性、不确定性

这几种情况不要硬套线性规划：

• 变量必须是整数，比如“是否建仓库”“派几辆车”，这时候要用整数规划。如果你强行解线性规划，可能会得到“0.7 个仓库”这种荒唐答案。
• 目标或约束里带平方、乘积、指数、对数，比如总成本里有固定费用和可变费用相乘，这时候要用非线性规划。
• 参数本身是随机的，比如明天需求量不确定，这时候要用随机规划或鲁棒优化，而不是把参数拍死成一个平均数。

三种情况对比如下：

| 问题特征 | 合适的规划类型 | | 变量连续，约束和目标都是线性 | 线性规划 | | 变量必须取整数 | 整数规划 | | 目标或约束存在非线性项 | 非线性规划 | | 参数不确定，需要控制风险 | 鲁棒优化/随机规划 |

6.3 先画图，再建模，最后写代码

我有过一次翻车经历。某个项目要决策“是否启用某个备选仓库”，我图省事，直接把它设成一个 0-1 变量，但用的却是线性规划求解器。结果返回的是 0.7，意思是要启用 70% 的仓库？这个方案根本没法执行。后来我意识到，我犯的正是误区二和三：把整数变量当成连续变量，又把问题当成了线性规划。

从那以后，我每次建模都强制走一遍检查清单：先画一画可行域和等值线，确认变量是连续还是整数，再用笔把目标函数和每条约束写出来，最后才写代码调求解器。这个习惯救了我好几次，也让我在团队里少被骂几次。我把这类问题的建模套路和边界检查清单整理到了一起，需要时翻一翻，能少踩点坑。希望帮到你。

本文还有配套的精品资源，点击获取