1 基本概念
线性规划是研究在线性约束条件下，对线性目标函数进行最优化的一类数学模型。它的核心特征在于“线性”二字：变量之间的关系以加法与比例关系为主，不涉及高阶非线性项。由于结构清晰、可解释性强，线性规划成为运筹学和优化理论中的基础模型之一。
1.1 定义与问题形式
在线性规划中，通常需要在若干决策变量的条件下，使某个线性目标达到最大或最小，同时满足一组线性等式或不等式约束。常见形式可写为：在给定系数矩阵、目标向量和约束向量的情况下，寻找一个满足全部约束的变量取值，使目标函数最优。
这类问题既可以表示为最大化收益，也可以表示为最小化成本。实际应用中，变量往往对应产量、运输量、投资额、流量等可分配资源。
1.2 线性规划的组成要素
线性规划模型通常由三部分构成：决策变量、目标函数与约束条件。三者共同决定了问题的可行范围和优化方向。
1.2.1 决策变量
决策变量是待求的未知量，表示需要由模型决定的对象。它们可以是连续数量，也可以是某些离散决策的近似表示，但在经典线性规划中通常取连续值。
1.2.2 目标函数
目标函数用于刻画优化目标，一般是若干决策变量的线性组合。它可以表示利润、成本、时间、能耗等指标。通过调整变量取值，目标函数的值随之变化，求解过程就是寻找其最优值。
1.2.3 约束条件
约束条件描述资源、能力、平衡关系或规则限制，通常以线性等式或不等式表示。它们限定了变量可以取值的范围，使得模型更贴近实际情境。
1.3 可行解与最优解
满足全部约束条件的解称为可行解。所有可行解构成的集合称为可行域。在线性规划中，若某个可行解使目标函数达到最佳值，则称为最优解。
需要注意的是，线性规划并不总是存在最优解。若可行域为空，则问题无可行解；若可行域存在但目标值可以无限改善，则问题可能无界。
1.4 标准型与一般型
一般型线性规划允许出现不同形式的约束，如“≤”“≥”和“=”混合存在，变量也可能没有统一的符号限制。标准型则通常将问题整理为统一形式，例如以“最大化目标函数、约束为等式、变量非负”为代表。
将一般型化为标准型是许多算法的预处理步骤。这样做有助于统一处理方式，并便于引入松弛变量或人工变量。
2 数学基础
线性规划建立在向量空间、矩阵运算、凸几何和线性代数等基础之上。其数学表达紧凑，便于用统一记号描述大规模问题。
2.1 向量与矩阵表示
在线性规划中，决策变量常可组织成向量，目标函数与约束系数则构成向量或矩阵。采用矩阵表示后，模型可简洁写为“优化一个线性函数，满足矩阵形式的约束”。
这种表示方式不仅节省书写空间，也有利于算法设计与程序实现。现代求解器几乎都以矩阵形式处理问题数据。
2.2 凸集与凸优化背景
线性规划的可行域是凸集，这是其理论性质的重要来源。凸集的特点是：集合中任意两点连线上的点仍然属于该集合。线性约束定义的半空间、超平面及其交集都具有凸性。
由于目标函数也是线性的，线性规划属于凸优化的一种特殊情形。凸性保证了局部最优即全局最优，这使得求解理论更加完善。
2.3 几何解释
从几何角度看，线性规划相当于在一个由若干直线、平面或超平面围成的区域中，寻找目标函数值最优的点。这种解释直观而清晰，尤其适合低维情形。
2.3.1 可行域的结构
可行域通常是若干半空间的交集，因此往往呈现多面体结构。若问题有界，可行域可能是一个凸多边形或凸多面体；若约束不足，则可行域可能延伸到无穷远。
2.3.2 超平面与半空间
线性等式约束对应超平面，线性不等式约束对应半空间。多个约束叠加后，形成一个受限区域。目标函数的等值线或等值超平面沿着某个方向移动，最优解通常出现在边界的顶点或极点处。
2.4 线性代数基础
线性规划的理解与求解离不开线性代数知识，如秩、线性相关、基、矩阵可逆性等。特别是在单纯形法中，基矩阵及其逆矩阵扮演关键角色。
此外，约束方程组的解空间结构、变量的自由度以及冗余约束的识别，也都依赖线性代数工具。
3 典型模型
线性规划擅长描述“在有限资源下进行最优分配”的问题，因此在管理、工程和经济分析中非常常见。
3.1 资源分配问题
资源分配问题研究如何把有限资源分给多个活动，使总体收益最大或成本最小。资源可能是资金、原料、时间或人力，约束体现资源总量限制，目标函数则反映分配效果。
3.2 生产计划问题
生产计划模型关注不同产品的产量安排。企业往往需要在设备能力、原料供应和市场需求等条件下确定最优生产组合，以平衡利润、库存和交付要求。
3.3 运输问题
运输问题研究从多个供给点向多个需求点配送货物的最优方案。模型通常以运输成本最小为目标，并满足各地供给与需求平衡条件，是线性规划的经典应用之一。
3.4 指派问题
指派问题用于把若干任务分配给若干执行者，使总成本最低或总效益最高。典型场景包括人员排班、机器作业分配和岗位匹配。该问题具有高度结构化特征，常可借助专门算法高效求解。
3.5 网络流问题
网络流问题将系统表示为由节点和边构成的网络，在边容量和节点守恒约束下优化流量配置。它广泛用于交通、通信、物流和管道系统分析，是线性规划的重要分支。
4 求解方法
线性规划的求解方法较为成熟，既包括适合低维直观分析的图解法，也包括适合大规模问题的单纯形法、内点法等。
4.1 图解法
图解法主要用于二维问题或变量较少的情形。通过画出约束对应的半平面，得到可行域，再沿目标函数改善方向移动，找到最优点。它直观易懂，常用于教学与初步分析，但不适合高维问题。
4.2 单纯形法
单纯形法是线性规划中最著名的经典算法之一，长期以来在工程与管理应用中占据核心地位。它沿着可行域的顶点之间逐步移动，每一步都保持可行，并不断改善目标值。
4.2.1 基本思想
该方法利用线性规划最优解往往出现在极点这一性质，从一个基本可行解出发，通过枢轴变换进入相邻更优的基本可行解，直到无法继续改进为止。
4.2.2 基本可行解
基本可行解是由一组线性约束选取若干变量作为基变量后得到的可行解。它通常对应可行域的一个顶点。单纯形法正是在基本可行解之间跳转，以搜索最优点。
4.2.3 迭代过程
单纯形法的迭代大致包括选择进入变量、确定离开变量、进行枢轴运算、更新基。每次迭代都使目标值朝最优方向变化，同时保持约束满足。
4.3 对偶单纯形法
对偶单纯形法从“对偶可行”但“原问题不可行”的状态出发，通过迭代逐步恢复原问题可行性并保持对偶条件。它在某些重新优化场景中十分高效，尤其适合约束改变后的快速更新。
4.4 内点法
内点法不沿边界顶点移动，而是在可行域内部沿路径逐步逼近最优解。与单纯形法相比，它在大规模稀疏问题上具有良好表现，且理论上具有多项式时间复杂度特征。
4.5 分支定界法中的线性松弛
在线性规划常作为整数规划的松弛子问题出现。分支定界法通过把整数约束暂时放宽为连续约束，先求线性松弛问题的解，再根据结果对变量取值范围进行分支和剪枝，从而搜索整数最优解。
5 对偶理论
对偶理论是线性规划的重要理论框架，它揭示了一个原问题与另一个对应问题之间的深层联系。
5.1 原问题与对偶问题
每个线性规划通常都能构造出一个与之对应的对偶问题。原问题和对偶问题在变量、约束和目标方向上呈现镜像关系。二者的解并不一定相同，但最优值之间存在紧密联系。
5.2 对偶构造规则
对偶问题的构造遵循一定规则：原问题的约束会影响对偶变量的数量，原问题的变量会转化为对偶约束。目标最大化与最小化之间往往相互对应，约束方向与变量符号也有固定映射关系。
5.3 弱对偶与强对偶
弱对偶指出，任意原问题可行解与任意对偶问题可行解之间，目标值满足一定不等关系。强对偶则说明，在适当条件下，原问题与对偶问题的最优值相等。这一结论是线性规划理论的核心成果之一。
5.4 互补松弛条件
互补松弛条件给出了原问题与对偶问题最优解之间的精确关系。直观上说，某个约束若没有“卡紧”，对应的对偶变量往往为零；反之，若对偶变量非零，则对应约束通常达到紧约束状态。
5.5 对偶变量的经济解释
对偶变量常被解释为资源的边际价值或影子价格。它表示在其他条件不变时，某项资源增加一个单位对最优目标值的影响。这个解释使对偶理论在经济和管理分析中具有很强的实用性。
6 灵敏度分析
灵敏度分析研究模型参数发生变化时，最优解和最优值如何随之改变。由于实际数据往往存在误差或波动，这一分析对决策应用尤为重要。
6.1 目标系数变化
当目标函数中的系数发生变化时，最优方案可能保持不变，也可能转向新的解。灵敏度分析可以判断在多大范围内原最优基仍然有效，以及目标值会如何调整。
6.2 约束右端项变化
约束右端项变化通常对应资源总量、需求水平或容量限制的变动。分析这类变化可以帮助判断系统对外部条件波动的承受能力，以及原有方案是否需要重新优化。
6.3 影子价格
影子价格反映了约束资源的边际贡献，常与对偶变量相对应。它告诉决策者某项资源是否稀缺，以及增加该资源是否值得投入额外成本。
6.4 最优基稳定性
最优基稳定性关注在参数扰动下，当前基是否仍保持最优。若参数变化仍落在允许范围内，则可直接利用原解进行快速更新；否则需要重新求解或调整模型结构。
7 特殊类型与扩展
在线性规划的基础上，还形成了若干重要扩展模型，用于处理更复杂的实际决策问题。
7.1 整数线性规划
整数线性规划要求部分或全部决策变量只能取整数值。它常用于离散选择、排程和组合优化，模型更贴近实际，但求解难度通常高于连续线性规划。
7.2 混合整数线性规划
混合整数线性规划同时包含整数变量与连续变量，适合描述既有离散决策又有连续调配的场景，例如选址与流量分配结合的问题。它在工业优化中非常常见。
7.3 参数线性规划
参数线性规划研究模型参数变化对最优解结构的影响，常用于分析一类问题在不同条件下的解族。它强调模型随参数演化时的连续性和分段特征。
7.4 随机线性规划
随机线性规划用于处理参数存在不确定性的情形，如需求波动、成本随机变化等。它通过概率分布、情景分析或鲁棒思想，将不确定性纳入优化框架。
7.5 大规模稀疏线性规划
当变量和约束数量很大，但矩阵中非零元素相对较少时，就形成大规模稀疏线性规划。这类问题需要专门的数据结构和数值算法，以减少存储开销并提高计算效率。
8 应用领域
线性规划的应用范围极广，凡是涉及资源优化配置的问题，往往都能找到其建模思路。
8.1 物流与供应链
在线物流系统中，线性规划可用于仓储分配、运输路径安排、库存控制和多级配送优化。它帮助企业在成本、时效和服务水平之间寻找平衡。
8.2 金融与投资
在金融领域，线性规划可用于资产配置、风险约束下的投资组合设计以及资金流规划。其模型可将收益、成本和限制条件清晰表达，便于量化决策。
8.3 生产制造
生产制造环节中，线性规划常用于产能安排、原料配比、班次计划和设备利用优化。它有助于提高资源利用率并降低单位成本。
8.4 通信网络
通信网络中的带宽分配、路由选择和流量调度，都可以借助线性规划建模。网络结构天然适合用节点和边的形式表示，因此相关问题常具备良好的线性结构。
8.5 能源管理
在能源管理中，线性规划可用于发电计划、负荷分配、储能调度以及燃料使用优化。通过建立约束与成本关系，能够辅助实现更高效的能源配置。
9 相关算法与软件
随着计算技术的发展，线性规划已经形成较为成熟的软件生态和建模工具链。
9.1 商用求解器
商用求解器通常具备较强的数值稳定性、较快的求解速度和完善的工程支持，适用于工业级大规模模型。它们往往集成了单纯形法、内点法及混合策略。
9.2 开源求解器
开源求解器为研究和教学提供了便利，也便于二次开发与算法实验。它们常用于原型验证、中小规模问题求解以及嵌入式优化系统。
9.3 建模语言
建模语言用于以接近数学表达的方式描述优化问题，再由求解器自动处理。它降低了模型编写难度，提高了问题表达的清晰度，也便于模型维护与扩展。
9.4 计算复杂度与实现特点
线性规划在理论上有较成熟的复杂度分析框架，但实际性能更多取决于矩阵稀疏性、数值条件、预处理方式和算法选择。实现中常需兼顾速度、精度与稳定性。
10 历史与发展
线性规划的发展经历了从理论萌芽到算法成熟、再到大规模工业应用的过程。
10.1 早期数学背景
线性规划的思想可追溯到资源分配、极值问题和线性不等式研究的早期工作。相关数学基础在分析学、几何和线性代数的发展中逐渐形成。
10.2 单纯形法的提出
单纯形法的出现使线性规划具备了可操作、可推广的系统算法。它的提出极大推动了运筹学的发展，也让线性规划从理论模型转变为广泛应用的实用工具。
10.3 现代优化技术的发展
随着计算机和数值分析技术进步，内点法、稀疏矩阵技术、启发式预处理和并行计算逐步成熟，线性规划的求解能力和适用范围显著扩大。
10.4 线性规划在计算机时代的演进
进入计算机时代后，线性规划从手工运算转向自动化求解，逐渐嵌入工业软件、管理系统与科学计算平台。如今，它不仅是独立的优化工具，也常作为更复杂模型的基础组件。