Chapter01.线性规划及单纯形法

线性规划及单纯形法运筹学核心优化方法·从建模到求解的完整体系Contents课程目录线性规划理论与求解方法的系统学习01线性规划问题及数学建模02图解法：二维问题的可视化求解03单纯形法：通用求解算法04大M法与对偶理论05线性规划应用实例与总结Chapter01线性规划问题及数学建模从实际问题出发，掌握线性规划的定义、要素与建模方法LinearProgramming什么是线性规划线性规划是运筹学中最经典的最优化方法，研究在有限资源约束下如何合理分配以实现目标函数最优（最大或最小）。其核心特征在于目标函数和约束条件均为决策变量的线性表达式，这使得问题具有凸性结构，保证了全局最优解的存在性。乔治·丹齐格（GeorgeB.Dantzig），线性规划之父，1947年提出单纯形法01线性规划（LinearProgramming,LP）特指目标函数和约束条件皆为线性的最优化问题，是作业研究（OperationsResearch）的核心工具。021947年美国数学家G.B.丹齐格提出单纯形法，开创了线性规划的系统求解理论，丹齐格因此被誉为"线性规划之父"。03应用极为广泛：生产计划、物流调度、资源分配、金融投资组合、网络流量优化等，大量用于降低成本与提升产值。04理论衍生出"对偶""分解""凸集"等核心概念，构成现代最优化理论的思维框架，许多复杂算法可分解为线性规划子问题逐一求解。LinearProgramming问题引入：工厂生产计划案例以工厂两种产品生产安排为典型案例，展示线性规划如何从实际决策问题中抽象出目标函数与约束条件。01利润目标：产品Ⅰ每件利润50元，产品Ⅱ每件100元，目标是使总利润最大02设备与原料A：设备台时≤300（x₁+x₂≤300），原料A≤400（2x₁+x₂≤400）03原料B与非负：x₂≤250，同时x₁≥0、x₂≥004最优解：在约束下找最优产量组合，使z=50x₁+100x₂最大产品生产资源消耗与限制资源类型产品Ⅰ产品Ⅱ资源限制设备台时11300原料A21400原料B01250单位利润（元）50100—资源消耗系数与限制构成约束方程组，单位利润构成目标函数系数LinearProgramming线性规划模型的三大组成要素线性规划模型由决策变量、目标函数和约束条件三大要素构成：决策变量代表可控因素的不同取值方案，目标函数以线性表达式量化优化方向（最大化或最小化），约束条件以线性等式或不等式界定可行范围。三者共同定义了线性规划问题的完整数学结构。01决策变量用x₁,x₂,…,xₙ表示可控制的因素，每一组取值对应一个具体方案决策变量通常要求非负（x₁,x₂,…,xₙ≥0），反映实际物理意义如产量、面积等不可为负x₁,x₂,…,xₙ≥002目标函数用决策变量的线性函数表达优化目标：Maxz或Minz=c₁x₁+c₂x₂+…+cₙxₙ系数c₁,c₂,…,cₙ称为价值系数，反映各决策变量对目标的单位贡献度Max/Minz03约束条件用一组线性等式或不等式表示必须遵循的限制：aᵢ₁x₁+aᵢ₂x₂+…+aᵢₙxₙ≤(=,≥)bᵢ右端常数bᵢ代表资源上限或最低需求量，系数aᵢⱼ称为技术系数或消耗系数≤=≥bᵢMODELINGMETHOD线性规划建模四步法线性规划建模遵循系统化的四步流程：理解问题→定义变量→构建目标→列出约束。每一步都有明确的操作规范和检验标准，确保从实际问题到数学模型的转化过程严谨完整，避免遗漏关键约束或误设目标方向。STEP01理解问题仔细分析实际场景，明确优化目标（是最大化利润还是最小化成本）以及所有限制条件和已知参数。这是建模的基础，直接影响后续步骤的正确性。STEP02定义决策变量设定x₁,x₂,…,xₙ代表可控因素的取值，每一组变量的值对应一个完整的决策方案。变量定义要清晰无歧义，便于后续数学表达。STEP03构建目标函数用决策变量的线性函数写出目标表达式，确定是求最大化（Max）还是最小化（Min）。目标函数是模型的核心，直接反映优化意图。STEP04列出约束条件用一组决策变量的线性等式或不等式表达所有必须遵循的限制，包括资源约束、技术约束和非负约束。完整的约束体系保证解的可行性。LinearProgramming线性规划的一般数学形式线性规划一般形式完整描述n个决策变量、m个约束的最优化结构，是标准化与求解算法的理论起点。Objmaxz=cTxs.t.Ax≤b,x≥001目标函数max(min)z=c₁x₁+c₂x₂+…+cₙxₙcⱼxⱼ02约束方程组共m个约束：aᵢ₁x₁+aᵢ₂x₂+…+aᵢₙxₙ≤(=,≥)bᵢm个03非负约束x₁,x₂,…,xₙ≥0，保证决策变量的物理意义合理性xⱼ≥004矩阵表达紧凑写为maxz=cTx，s.t.Ax≤b,x≥0，A为m×n系数矩阵m×nLINEARPROGRAMMING·CASESTUDY建模案例：农夫种植决策问题农夫种植决策问题是线性规划在农业资源分配中的经典应用。通过设定种植面积为决策变量，在土地、肥料、农药三重资源约束下追求收入最大化，展示了线性规划模型的广泛适用性。农田种植场景—资源约束下的面积分配决策MODELSUMMARYMaxz=p₁x₁+p₂x₂s.t.x₁+x₂≤A,f₁x₁+f₂x₂≤F,x₁,x₂≥001决策变量设定：设x₁为小麦种植面积、x₂为大麦种植面积，两者之和不得超过总农地面积Ax₁+x₂≤A02目标函数构建：Maxz=p₁x₁+p₂x₂，其中p₁和p₂分别为小麦和大麦的单位面积售出价格Maxz=p₁x₁+p₂x₂03资源约束条件：肥料约束f₁x₁+f₂x₂≤F（f₁、f₂为单位面积肥料消耗），农药约束p'₁x₁+p'₂x₂≤Pf₁x₁+f₂x₂≤F04非负约束：x₁≥0，x₂≥0，种植面积不可为负；此模型与工厂案例结构完全一致，仅参数含义不同x₁,x₂≥0CHAPTER02图解法：二维问题的可视化求解通过平面作图直观理解可行域、等值线与最优解的几何本质GRAPHICALMETHOD·STEP01图解法步骤一：绘制可行域图解法的第一步是在平面直角坐标系中逐条绘制约束边界直线并确定不等式满足的半平面，所有半平面的交集即为可行域。可行域是由约束条件围成的凸多边形区域，其顶点对应基本可行解，是后续寻找最优解的候选位置。01绘制约束边界对每个约束不等式，先画出等号成立时的边界直线（如x₁+x₂=300），再用测试点法确定不等式满足的半平面方向02非负约束限制非负约束x₁≥0,x₂≥0将可行域限制在第一象限，其他约束进一步切割缩小可行范围03半平面交集所有约束半平面的交集构成可行域——一个由若干直线段围成的凸多边形，本例中为五边形OABCD04凸集性质可行域一定是凸集（任意两点连线上的点仍在区域内），这意味着局部最优即全局最优线性规划可行域——约束半平面交集构成的凸多边形LinearProgramming·Step02图解法步骤二：等值线与最优解等值线是目标函数取固定值时形成的直线，同一条等值线上所有点的目标函数值相等。通过沿目标函数增大方向平行移动等值线，等值线与可行域最后接触的点（通常是顶点）即为最优解。本例中B点(50,250)为最优解，最大利润z=27500。01令目标函数z=50x₁+100x₂取固定值（如z=0,10000,20000），得到一组相互平行的等值线z=50x₁+100x₂02沿目标函数增大的方向平行移动等值线，z值逐步增大，等值线在可行域内扫过的区域目标值递增目标值递增方向03等值线即将离开可行域的最后接触点即为最优解，本例中为B点，坐标x₁=50,x₂=250B(50,250)04最优目标值z=50×50+100×250=27500，即在给定资源约束下工厂可获得的最大利润为27500元z=27,500元LINEARPROGRAMMING·CASESTUDY最小化问题的图解法：原料采购案例最小化问题与最大化问题的图解法逻辑一致，区别在于等值线沿目标函数减小方向移动。该案例中，在满足原料总量、最低采购量和加工能力三重约束下，最优采购方案为A原料250吨、B原料100吨，对应可行域顶点Q处取得最小购进成本。MODELING问题建模：Minf=2x₁+3x₂，约束为x₁+x₂≥350（总量）、x₁≥125（A最低量）、2x₁+x₂≤600（加工能力）、x₁,x₂≥0CONSTRAINTS约束分析：x₁+x₂≥350和x₁≥125为大于等于型，可行域在边界线上方；2x₁+x₂≤600为小于等于型，可行域在边界线下方ISO-LINE等值线移动：2x₁+3x₂=C沿C减小方向平移，与可行域最先接触的顶点Q(250,100)即为最优解OPTIMAL最优方案：购进A原料250吨、B原料100吨，满足所有约束且总成本最低约束系统与最优解可行域顶点Q处取得最小购进成本x₁+x₂≥350x₁≥1252x₁+x₂≤6002x₁+3x₂=C(iso-line)x₁x₂O125250C↓Q(250,100)(125,225)(125,350)可行域★最优解线性规划·图解法示意线性规划·解的分类线性规划解的四种情况与核心定理线性规划问题的解有四种可能：唯一最优解、无穷多最优解、无界解和无可行解。核心定理指出：若最优解存在，则至少有一个可行域顶点对应最优解。这一定理是单纯形法仅在基本可行解之间迭代搜索的根本理论依据。解的类型·A唯一最优解与无穷多最优解01唯一最优解：等值线与可行域仅在某一顶点相切，该顶点为唯一最优点02无穷多最优解：目标函数等值线与某条约束边界平行时，该边界线段上所有点都是最优解解的类型·B无界解与无可行解01无界解：可行域延伸到无穷远，目标函数值可无限增大或减小，通常说明模型遗漏了关键约束02无可行解：约束条件互相矛盾导致可行域为空集，新增约束与原有约束无法同时满足理论基础核心定理01若线性规划有最优解，则一定存在至少一个可行域的顶点（基本可行解）对应最优解02基本可行解的个数有限（不超过C(n,m)），理论上可通过遍历所有顶点找到最优解CHAPTER03单纯形法：通用求解算法从基本思想到完整计算流程，掌握线性规划的通用代数求解方法LinearProgramming单纯形法的基本思想与理论基础单纯形法基于"最优解在顶点取得"定理，在有限个基本可行解间逐步迭代，经有限步即达最优解或判定无界。01基本可行解与可行域可行域是n维空间中的多面凸集，其顶点对应"基本可行解"——满足所有约束且非零变量数不超过约束数m的解。02迭代搜索策略从初始基本可行解出发检验最优性；若非最优，按特定法则转换到相邻的改进基本可行解，重复迭代直至收敛。03有限步收敛保证每次转换使目标函数值严格改善（非退化情形下），基本可行解个数有限，经有限次迭代必达到最优解。04异常情形判别若问题无最优解（无界或无可行解），单纯形法同样能在迭代过程中做出判别，不会无限循环。LINEARPROGRAMMING标准型转化与松弛变量引入单纯形法要求线性规划为标准型：目标最大化、约束等式、变量非负。引入松弛或剩余变量将不等式转化为等式，其目标系数为零，不改变最优解。01标准型三要素●目标函数为Max型（若原问题为Minf，则转化为Max(−f)）●所有约束条件必须化为等式形式●所有决策变量满足非负约束（≥0）02≤约束：松弛变量→转化示例：x₁+x₂≤300化为x₁+x₂+x₃=300●x₃≥0为松弛变量，表示资源约束下未被使用的剩余资源量，其经济含义为闲置资源03≥约束：剩余变量→转化示例：x₁+x₂≥350化为x₁+x₂−x₄=350●x₄≥0为剩余变量，表示超出最低要求的富余量，用于满足"不低于"型约束的标准化需求04零系数与单位子矩阵●松弛/剩余变量在目标函数中的系数c=0，因此不改变原问题的最优目标值●引入后系数矩阵出现单位子矩阵，为单纯形法迭代提供明显的初始基本可行解LINEARPROGRAMMING标准型转化实例：例1的完整转化过程以工厂生产计划例1为对象，通过引入三个松弛变量将三个≤约束转化为等式约束，得到5个变量、3个等式的标准型。松弛变量对应的系数列向量恰好构成单位矩阵，令非基变量为零即可直接读出初始基本可行解(0,0,300,400,250)。01CONSTRAINTA&B原约束x₁+x₂≤300引入松弛变量x₃→x₁+x₂+x₃=300；2x₁+x₂≤400引入x₄→2x₁+x₂+x₄=400。松弛变量表示资源的未使用量，值为非负数。02CONSTRAINTC原约束x₂≤250引入松弛变量x₅→x₂+x₅=250；非负约束扩展为x₁,x₂,x₃,x₄,x₅≥0。所有变量必须满足非负条件，这是标准型的基本要求。03OBJECTIVEFUNCTION标准型目标函数：Maxz=50x₁+100x₂+0x₃+0x₄+0x₅，松弛变量系数为零不改变最优解。目标函数保持原问题的经济意义，仅增加零系数项以匹配变量维度。04INITIALSOLUTION令x₁=0,x₂=0（非基变量），得x₃=300,x₄=400,x₅=250（基变量），对应利润z=0。基变量由松弛变量自然构成单位矩阵，无需人工添加辅助变量。LinearProgramming·Foundations核心概念：基、基本解与基本可行解基是系数矩阵中线性无关列向量构成的可逆子矩阵，基本可行解对应可行域顶点，单纯形法在其间搜索最优解。Section01基与基变量①从m×n系数矩阵A中选出m个线性无关的列向量构成可逆子矩阵B，称为一个"基"②基B对应的m个变量为基变量，其余n−m个变量为非基变量Section02基本解①令非基变量为零，由BxB=b解出xB=B⁻¹b，得基本解x=(xB,0)②基本解个数不超过C(n,m)，即从n列中选m列的组合数Section03基本可行解①当基本解所有分量均≥0时称为基本可行解，几何上对应可行域的顶点②单纯形法仅在基本可行解之间迭代，无需遍历无穷多个可行解，大幅缩小搜索范围LINEARPROGRAMMING单纯形表的结构与检验数单纯形表是单纯形法手算的核心工具，检验数σⱼ反映非基变量边际贡献，是判断最优性和选择换入变量的关键。单纯形表结构：包含基变量列(CB)、变量列、系数矩阵各列(P₁,P₂,…,Pₙ)、右端列(b)及检验数行(σⱼ)和目标值TABLESTRUCTURE检验数计算公式：σⱼ=cⱼ−zⱼ=cⱼ−CBᵀ·Pⱼ，CB为基变量对应的价值系数向量，Pⱼ为第j列系数向量σⱼ=cⱼ−CBᵀ·Pⱼ最优性判定：若所有非基变量的σⱼ≤0，则当前基本可行解为最优解；若存在σⱼ>0，则问题尚可改进σⱼ≤0换入变量选择：取σⱼ>0中最大者对应的非基变量作为换入变量，使目标函数在每次迭代中获得最大改善MAX(σⱼ)SIMPLEXMETHOD·ITERATION单纯形法迭代步骤：换入、换出与基变换单纯形法每次迭代包含三步：选换入变量（检验数最大正值对应的非基变量）、选换出变量（最小比值法则确定）、执行基变换（高斯消元使换入变量列变为单位向量）。最小比值法则保证迭代后新解仍满足非负约束，确保始终在可行域顶点上移动。01确定换入变量：在所有σⱼ>0中选取最大者σₖ，对应非基变量xₖ进入基，使目标函数改善幅度最大MAXσⱼ02确定换出变量（最小比值法则）：计算θᵢ=bᵢ/aᵢₖ（仅对aᵢₖ>0），取θₗ=min{θᵢ}，第l行基变量离基MINθᵢ03基变换（主元运算）：以aₗₖ为主元，对单纯形表执行高斯行变换，使xₖ对应列变为第l个单位向量PIVOT04迭代终止判断：重新计算检验数行，若所有σⱼ≤0则达到最优；若某σₖ>0但对应列所有aᵢₖ≤0则问题无界σⱼ≤0SimplexMethod单纯形法求解演示：例1完整迭代过程以工厂生产计划例1为对象完整演示单纯形法迭代过程：从初始基本可行解(0,0,300,400,250)出发，经过两次基变换迭代，检验数全部非负后达到最优解x₁=50,x₂=250,z=27500，与图解法结论完全一致，验证了算法的正确性。单纯形法迭代过程关键数据迭代基变量解(x₁,x₂,x₃,x₄,x₅)目标值z说明初始x₃,x₄,x₅(0,0,300,400,250)0σ₁=50>0,σ₂=100>0，x₂换入第1次x₃,x₄,x₂(0,250,50,150,0)25,000σ₁=50>0，x₁换入第2次x₁,x₄,x₂(50,250,0,150,0)27,500σ₁≤0,σ₂≤0，达到最优TotalIterations2Optimalz27,500Decisionx₁=50,x₂=250经两次迭代，目标值从0提升至27,500，所有检验数非正，算法终止LinearProgramming退化现象与Bland法则退化是指基本可行解中存在值为零的基变量，可能导致单纯形法迭代时目标函数值不改善甚至产生循环。Bland法则通过规定换入变量和换出变量的选择优先级（取最小下标），从理论上严格保证单纯形法在退化情况下仍能有限终止。01退化定义当基本可行解中某个基变量取值为零时称为退化，对应最小比值θi=0的情况02退化影响迭代后目标函数值可能不改变（Δz=0），极端情况下可能导致基的循环——在不同基本可行解之间反复转换03Bland法则（防循环规则）①换入变量选σj>0中下标j最小者；②比值并列时换出变量选下标最小者04实际意义虽然循环在工程问题中极为罕见，但Bland法则从理论上保证了单纯形法的有限终止性，是算法完备性的重要补充ALGORITHMEFFICIENCY改进单纯形法与计算效率改进单纯形法通过维护基逆矩阵B⁻¹，每次迭代仅更新必要信息而非整个表格，大幅减少大规模问题的计算量与存储需求。01核心思想维护基逆矩阵B⁻¹，每次迭代只需计算换入列B⁻¹Pₖ、更新B⁻¹和检验数，无需完整行变换B⁻¹Pₖ02存储优势仅需存储B⁻¹（m×m矩阵）而非完整单纯形表（m×n矩阵），当n≫m时节省大量存储空间m×m≪m×n03计算复杂度单纯形法平均效率极高，但最坏情况为指数级时间复杂度（Klee-Minty反例可构造）O(2ⁿ)最坏04替代算法1984年Karmarkar提出内点法，具有多项式时间复杂度，适合超大规模线性规划问题1984Chapter04大M法与对偶理论解决初始基缺失问题，探索原问题与对偶问题的深层对称性LinearProgramming·线性规划大M法：处理无初始基的线性规划大M法通过引入人工变量构造初始单位基矩阵，并在目标函数中赋予人工变量极大的惩罚系数-M（Max问题），迫使单纯形法在迭代中将人工变量驱离基变量。若所有人工变量最终取零值则获得原问题最优解，否则判定原问题无可行解。01适用场景当约束包含等式（=）或大于等于（≥）型时，引入松弛/剩余变量后系数矩阵中无现成单位子矩阵。等式/≥约束·无现成单位矩阵02操作方法对每个缺少基变量的约束添加人工变量xᵢ′≥0，使系数矩阵出现单位矩阵，从而获得初始基本可行解。添加xᵢ′≥0·构造初始可行解03惩罚机制目标函数中人工变量系数设为−M（Max问题，M为充分大正数），迫使人工变量在迭代中趋向零值。系数−M·M→∞·驱离基变量04结果判定若最终解中所有人工变量=0，则得原问题最优解；若某人工变量>0仍在基中，则原问题无可行解。全部为零→最优解·否则无解LINEARPROGRAMMING·SIMPLEXMETHOD两阶段法：大M法的稳健替代两阶段法将大M法拆分为两个独立阶段，避免了选取惩罚系数M的困难。第一阶段以人工变量之和最小化为目标求解辅助问题，若最优值为零则获得原问题的初始基本可行解；第二阶段以此解为起点求解原目标函数，是商业求解器中处理初始基缺失的首选方法。PHASE1·OBJECTIVE第一阶段目标Minw=Σxᵢ'（人工变量之和），约束条件与原问题相同（含人工变量），用单纯形法求解辅助线性规划。Minw=Σxᵢ'PHASE1·JUDGMENT第一阶段判定若Minw=0，所有人工变量可为零，原问题有可行解；若Minw>0，原问题无可行解。w=0⟹可行PHASE2·OPERATION第二阶段操作去除人工变量列，以第一阶段终表中的基变量和基逆矩阵为初始状态，求解原目标函数。MaxzADVANTAGE相比大M法的优势无需选取M值，避免数值计算中因M过大导致的浮点精度问题和截断误差。无M值依赖LinearProgramming·Duality对偶理论：原问题与对偶问题的对称关系每个线性规划原问题都有对应的对偶问题，两者在目标方向、系数矩阵和约束结构上呈完美对称。弱对偶与强对偶定理为灵敏度分析提供数学基础。01对偶问题的构造规则原问题Maxz=cᵀx,s.t.Ax≤b,x≥0→对偶问题Minw=bᵀy,s.t.Aᵀy≥c,y≥0原问题的m个约束对应对偶问题的m个变量，原问题的n个变量对应对偶问题的n个约束02对偶定理弱对偶定理：对原问题任一可行解x和对偶问题任一可行解y，恒有cᵀx≤bᵀy强对偶定理：若原问题有最优解，则对偶问题也有最优解，且两者最优值相等z*=w*03经济解释对偶变量yᵢ的最优值称为第i种资源的影子价格，表示该资源每增加一单位对目标函数的边际贡献影子价格为零说明该资源有富余（约束非紧），影子价格越大说明该资源越稀缺LINEARPROGRAMMING·DUALITY对偶问题案例：资源定价的经济博弈以农夫种植问题为原问题，构造种植园主购买资源的对偶问题，生动展示对偶关系的经济直觉：原问题是资源所有者最大化利用收益，对偶问题是外部购买者最小化资源收购成本。对偶变量的最优解即为资源的影子价格，揭示了资源的真实经济价值。01·原问题农夫最大化种植收入Maxz=p₁x₁+p₂x₂，约束为肥料f₁x₁+f₂x₂≤F、农药p'₁x₁+p'₂x₂≤P、土地x₁+x₂≤A02·对偶问题种植园主最小化资源购买成本Minw=Fy₁+Py₂+Ay₃，约束为购买资源的支出不低于农夫种每种作物的收入03·对偶约束资源支出不低于作物收入f₁y₁+p'₁y₂+y₃≥p₁（买资源的钱≥种小麦收入），f₂y₁+p'₂y₂+y₃≥p₂（≥种大麦收入）04·经济含义影子价格揭示资源真实价值对偶最优解y₁*,y₂*,y₃*分别为肥料、农药、土地的影子价格，指导资源的合理定价与配置决策DUALSIMPLEXMETHOD对偶单纯形法：从对偶可行性恢复原始可行性对偶单纯形法始终保持检验数非正，通过选择负的右端常数对应的基变量换出、按最小比值确定换入变量，逐步恢复原始可行性。01核心思想：始终保持σⱼ≤0（对偶可行），迭代消除b列中的负元素以恢复原始可行，与标准单纯形法方向相反σⱼ≤002换出变量选择：取b列中最负元素对应的基变量换出，使可行性违反最严重的变量优先得到修正minbᵢ03换入变量选择：在换出行负元素对应的非基变量中，按最小比值min{|σⱼ/aₗⱼ|}确定换入变量min比值04典型应用场景：灵敏度分析中增加约束后重新求解、整数规划割平面法中添加Gomory割后继续迭代割平面SENSITIVITYANALYSIS灵敏度分析：参数变化对最优解的影响参数变化对最优解的影响可用最优单纯形表直接计算允许区间，影子价格为资源决策提供量化依据。价值系数cⱼ的灵敏度确定cⱼ在什么范围内变化时当前最优基不变，仅目标值改变。cⱼ右端常数bᵢ的灵敏度确定资源量bᵢ的允许变化范围，在此范围内影子价格有效且最优基结构不变。bᵢ影子价格应用若某资源的影子价格为10元/单位，则企业愿以不超过10元的单价购入该资源以扩大产能。10元/单位参数超限处理当参数变化超出允许范围时，用对偶单纯形法或标准单纯形法从当前表继续迭代求新最优解。对偶单纯形法CHAPTER05线性规划应用实例与总结从理论到实践，展示线性规划在多场景中的决策优化价值LINEARPROGRAMMING·APPLICATION应用案例一：运输问题与物流优化运输问题是线性规划在物流领域的经典应用，以最小化总运输成本为目标，在产地供应量与销地需求量的双重约束下确定最优运输方案。其特殊的系数矩阵结构（全幺模矩阵）保证基本可行解为整数解，在实际物流调度中有广泛应用。01问题结构：m个产地（供应量aᵢ）、n个销地（需求量bⱼ），单位运费cᵢⱼ，决策变量xᵢⱼ为产地i到销地j的运量02目标函数：Minz=ΣᵢΣⱼcᵢⱼxᵢⱼ，求所有运输路径的总成本最小化03约束条件：供应约束Σⱼxᵢⱼ≤aᵢ（每个产地运出量不超供应），需求约束Σᵢxᵢⱼ≥bⱼ（每个销地运入量满足需求）04特殊性质：系数矩阵为全幺模矩阵，当供应量和需求量为整数时，最优解自动为整数，无需整数规划即可得到整数运输方案物流仓储与货物分拣场景·运输问题的实际应用背景LINEARPROGRAMMING·APPLICATION应用案例二：配料问题与配方优化配料问题是线性规划在化工、食品和饲料行业的典型应用，在满足多种营养成分含量要求的前提下最小化原料配比成本。建模关键在于将行业标准和质量规范准确转化为线性约束条件，决策变量为各原料的配比用量，可通过灵敏度分析指导原料采购策略。01问题场景用n种原料配制产品，每种原料含不同比例的营养成分，需满足m种成分的含量上下限要求02决策变量与目标xⱼ为第j种原料的用量，Minz=Σcⱼxⱼ（总配料成本最小化），cⱼ为各原料单价03营养约束Σaᵢⱼxⱼ≥Lᵢ（第i种成分不低于下限），Σaᵢⱼxⱼ≤Uᵢ（不高于上限），aᵢⱼ为第j种原料中第i种成分的含量比04扩展应用灵敏度分析可揭示哪种原料价格变化会影响配方结构，指导企业的长期采购合同谈判策略LINEARPROGRAMMING·APPLICATION应用案例三：投资组合优化线性规划以预期收益最大化为目标，在多重约束下确定最优资产配置；虽精确风险建模需二次规划，但线性近似因计算高效、约束灵活而被广泛采用。01决策变量：xⱼ为投资于第j种资产的资金比例，目标Maxz=Σrⱼxⱼ实现预期收益最大化02资金约束：Σxⱼ=Total总投资额固定，xⱼ≥0不允许卖空的简化情形03风险分散约束：单一资产不超α%，行业集中度不超β%，控制敞口风