对偶理论及灵敏度分析

对偶理论及灵敏度分析运筹学·线性规划理论深化与决策应用Contents课程目录对偶理论的系统性学习路径，从基础概念到前沿算法应用。01对偶问题的提出与基本概念02对偶理论的核心定理03对偶单纯形法04灵敏度分析05原始对偶内点算法与应用06总结与展望CHAPTER01对偶问题的提出与基本概念从资源最优配置到资源估价——对偶思想的起源LINEARPROGRAMMING·DUALITY对偶问题的经济背景对偶理论源于资源配置的双重决策视角：原问题求解有限资源的最优生产配置以获得最大产值，对偶问题则在相同资源条件下正确估计资源的使用价值以达到最少支付，两者从不同角度出发却内在统一。原问题：资源最优配置在有限原材料、工时等约束下安排生产计划，使总产值最大化，属于生产者的利润最大化视角最大化对偶问题：资源估价为每种资源设定影子价格，使得出售资源的总收入不低于用于生产所能获得的利润，属于资源定价者视角影子价格理论奠基冯·诺伊曼1947年首次提出对偶概念，后由丹齐格和塔克在20世纪40年代末系统研究，奠定线性规划对偶理论基础1947理论扩展对偶思想从线性规划扩展到非线性规划，衍生出拉格朗日对偶、共轭对偶等多种形式，其中拉格朗日对偶恒为凸规划凸规划线性规划·对偶理论对称形式的对偶问题对称形式的对偶问题展现了原问题与对偶问题之间完美的结构对称性：目标函数方向相反，系数矩阵互为转置，变量个数与约束个数互换，体现了数学形式的优美统一。标准形式原问题maxZ=CX,AX≤b,X≥0；对偶问题minW=Yb,YA≥C,Y≥0，构成对称对偶对。这种标准形式是研究对偶理论的基础框架。max↔min数量互换原问题n个变量对应n个对偶约束，m个约束对应m个对偶变量。变量与约束的数量关系在对偶问题中发生互换，这是对称形式的核心特征之一。n↔m系数对应目标函数系数C成为对偶约束右端项，约束右端b成为对偶目标函数系数。这种系数的对偶转移保证了两个问题在最优解处的目标值相等。C↔b矩阵转置约束条件系数矩阵A在对偶问题中变为其转置矩阵Aᵀ。矩阵的转置关系使得原问题的行约束转化为对偶问题的列约束，保持结构的对称性。A→AᵀDUALITYTHEORY原问题与对偶问题的结构对应原问题与对偶问题之间存在六条严格的对称对应规则，涵盖目标函数方向、约束不等号方向、变量与约束的互换关系、系数与常数的对调关系以及矩阵转置关系，构成了对偶理论的形式基础。01约束方向反转极大化问题的约束条件为≤，对应极小化问题的约束条件为≥，不等号方向始终相反。≤↔≥02常数→系数原问题m个约束右端常数b₁…bₘ对应变为对偶问题中m个对偶变量y₁…yₘ的系数。b→y03系数→常数原问题目标函数中n个变量系数c₁…cₙ对应变为对偶问题n个约束条件的右端常数。c→RHS04矩阵转置约束矩阵A的第i行第j列元素aᵢⱼ，在对偶问题中出现在第j行第i列位置，即整个矩阵转置。A→Aᵀ05非负约束原问题与对偶问题中所有变量均受非负约束，这是对称形式的重要特征。x,y≥006唯一确定任何一个对称形式的线性规划问题都可以通过上述六条规则唯一确定其对偶问题。6RULESDUALTHEORY非对称形式对偶问题的转换非对称形式的线性规划问题通过引入等式约束与自由变量的对应规则，可以统一转换为对偶问题。原问题中的等式约束对应无约束的对偶变量，自由变量对应等式约束，这些规则使得任意线性规划都能写出对偶形式。01等式约束对应于对偶问题中该约束的对偶变量为自由变量（无非负限制），反之亦然，体现了约束类型与变量类型的对偶关系。02原问题中自由变量（无符号限制）对应于对偶问题中该位置的约束取等号形式，保证对偶关系的完整性。03将等式约束拆为两个不等式、将自由变量表示为两个非负变量之差，可以从对称形式推导出非对称形式的转换规则。04无论对称或非对称形式，目标函数系数、约束右端常数和系数矩阵的对应关系保持不变，区别仅在于约束形式与变量取值。05掌握非对称转换规则后可应对任意形式的线性规划问题，是进行对偶分析和灵敏度分析的必要基础。DUALPROBLEM·EXAMPLE对偶问题写出实例通过具体生产问题实例，可以直观掌握从原问题到对偶问题的转换过程：将每种资源的限量转化为对偶目标函数系数，将每种产品的利润转化为对偶约束的右端常数，将消耗系数矩阵转置为对偶约束系数。maxZ=3x₁+5x₂工厂生产产品A（利润3元/件）和B（利润5元/件），受原料1（日限12kg）和原料2（日限8kg）约束x₁+2x₂≤12x₁+x₂≤8原料约束条件构成标准对称形式的原问题，x₁,x₂≥0minW=12y₁+8y₂对偶变量y₁、y₂分别代表原料1和原料2的影子价格，目标系数取自原问题约束右端常数y₁+y₂≥32y₁+y₂≥5对偶约束分别对应产品A和B，系数矩阵为原问题系数矩阵的转置，y₁,y₂≥0y₁=y₂=1.5元/kg求解对偶问题得到每种原料的合理估价，说明两种原料在当前最优方案下具有相同的边际价值Chapter02对偶理论的核心定理弱对偶、强对偶与互补松弛性——连接原问题与对偶问题的数学桥梁DUALITYTHEORY弱对偶性定理弱对偶性定理建立了原问题与对偶问题目标函数值之间的基本不等式关系：原问题任意可行解的目标值不超过对偶问题任意可行解的目标值，为求解最优性提供了上下界估计。01核心定理若X₀和Y₀分别是原问题（max）和对偶问题（min）的可行解，则CX₀≤Y₀b恒成立，无需最优性假设即可证明02推论一：上下界估计原问题（max）的任一可行解目标值都是对偶问题目标值的下界，对偶问题任一可行解目标值是原问题目标值的上界03推论二：无界性传递若原问题目标函数无界（可趋于正无穷），则对偶问题一定无可行解；反之若对偶问题无界，原问题一定无可行解04推论三：最优性判定若原问题可行解X₀与对偶问题可行解Y₀满足CX₀=Y₀b，则X₀和Y₀分别是各自问题的最优解05理论基础地位弱对偶性是强对偶性和互补松弛性的基础，也是对偶单纯形法和灵敏度分析的理论出发点FoundationDUALITYTHEORY强对偶性定理（对偶定理）若原问题与对偶问题均有可行解，则两者均存在最优解且最优目标函数值严格相等，求解一个问题的同时自动获得了另一个问题的最优解。定理表述原问题与对偶问题均可行时，两者均具最优解且目标函数值相等maxCX*=minY*b证明思路最优基B的单纯形乘子即为对偶问题最优解Y*=CBB⁻¹实用意义松弛变量检验数即为对偶变量最优值，无需单独求解DUALFROMPRIMAL反证应用一侧最优而另一侧无可行解，说明建模存在错误MODELCHECK完整体系弱对偶保证不等式，强对偶保证最优处取等号CX≤Yb→=DUALITYTHEORY互补松弛性定理互补松弛性定理揭示了原问题与对偶问题最优解之间的精确对应关系：某个约束松弛为正时对应的对偶变量必为零，某个对偶变量为正时对应的原约束必取紧约束，这为已知一个问题的最优解推导另一个问题的最优解提供了直接方法。互补松弛性表述设X₀、Y₀分别是原问题和对偶问题的最优解，U₀为原问题松弛变量值，V₀为对偶问题剩余变量值，则Y₀U₀=0且V₀X₀=0经济解释若某种资源在最优方案下未被完全利用（松弛变量>0），则该资源的影子价格为零；若影子价格>0，该资源一定被完全利用直接求解对偶已知原问题最优解时，利用互补松弛性可建立方程组直接求解对偶问题最优解，避免重新运行单纯形法充分必要条件互补松弛条件Y₀U₀=0是原问题和对偶问题最优解的充分必要条件，与强对偶性定理等价灵敏度分析基础在灵敏度分析中，互补松弛性用于判断参数变化后原最优解是否仍然有效，是灵敏度分析的理论基础之一LinearProgramming·Duality影子价格的经济含义对偶问题最优解即为各资源的影子价格，反映每增加一单位资源对目标函数最优值的边际贡献，是管理决策中资源定价、购入与出售判断的核心依据。影子价格定义—对偶问题最优解y*ᵢ表示第i种资源每增加一个单位时原问题目标函数最优值的增量，即∂Z*/∂bᵢ=y*ᵢ资源购入决策—当某资源的市场价格低于其影子价格时，购入该资源可增加总利润，应扩大购入直至影子价格下降至等于市场价格资源出售决策—当某资源的市场价格高于其影子价格时，出售多余资源比用于生产更有利，应出售直至剩余量的影子价格上升至等于市场价格零影子价格—影子价格为零的资源表示该资源在当前最优方案下已有剩余，增加其供给不会改善目标函数值有效范围—影子价格仅在当前最优基不变的范围内有效，超出此范围需要用灵敏度分析重新计算Chapter03对偶单纯形法从对偶可行到原始可行——灵敏度分析的计算工具LinearProgramming·Duality对偶单纯形法的基本思想对偶单纯形法与标准单纯形法方向相反：从检验数已满足最优性条件（对偶可行）但基变量可能为负（原始不可行）的解出发，通过迭代逐步使基变量恢复非负，最终同时达到原始可行与对偶可行的最优解。01标准单纯形法路径保持原始可行（基变量≥0），逐步满足对偶可行（检验数≤0），每步迭代在原始可行域内移动，最终到达最优解。PrimalFeasible02对偶单纯形法路径保持对偶可行（检验数≤0），逐步满足原始可行（基变量≥0），每步迭代在对偶可行域内移动，最终到达最优解。DualFeasible03镜像关系标准法在原始空间寻优，对偶法在对偶空间寻优，两条路径最终到达同一个最优点，体现对偶理论的核心思想。同一最优点04核心优势当参数变化使原最优解原始不可行但对偶仍可行时，可直接从当前表继续迭代，无需重新建模，计算效率高。无需重建05适用场景新增约束条件、资源限量减少等导致原最优基不可行的灵敏度分析问题，是处理参数变化的强大工具。SensitivityAlgorithmSteps对偶单纯形法的计算步骤对偶单纯形法的迭代过程包含四个关键步骤：检查原始可行性、确定换出行、确定换入列和主元消去。与标准单纯形法相比，换出行与换入列的选择逻辑互换，但主元消去操作完全相同。迭代从检验b列可行性开始，逐步确定换出行与换入列，完成主元消去后循环直至最优或判定无界。01最优性检验检查b列各元素，若所有bi≥0则当前解为最优解，迭代终止；否则进入下一步02确定换出行选取b列中最负值所在行r，br=min{bi|bi<0}，该基变量离开基03确定换入列行r中arj<0时计算θ=σj/arj，取绝对值最小比值对应列s04主元消去以ars为主元，按行变换规则更新单纯形表，返回步骤一继续检验无界判定若换出行所有arj≥0，对偶问题无界，原问题无可行解IterationFlow检验换出行换入列消去循环迭代直至b列全部非负或判定无界NUMERICALDEMONSTRATION对偶单纯形法数值演算通过具体数值例子演示对偶单纯形法的完整迭代过程，展示从原始不可行但对偶可行的初始表出发，经过有限步主元消去达到最优解的计算逻辑。01初始表状态基变量x₂=-2原始不可行，x₄=3可行；所有检验数σ≤0对偶可行，需继续迭代σ≤0对偶可行02换出行选择b列中x₂=-2为最负值，确定第1行为换出行；a₁₁=-1、a₁₃=-3均为负x₂=-2最负值行03换入列选择θ₁=(-2)/(-1)=2，θ₃=(-6)/(-3)=2，最小比值均为2，选取x₁换入θ=2最小比值04主元消去以a₁₁=-1为主元行变换，x₁=2、x₄=5均为正，b列全非负，σ仍≤0a₁₁=-1主元05一次迭代即达最优新最优解x₁=2、x₂=0，最优目标值Z*=6，验证了对偶单纯形法的高效性Z*=6最优目标值Chapter04灵敏度分析参数变化下的最优解稳定性与决策调整LINEARPROGRAMMING·SENSITIVITY灵敏度分析的意义与框架灵敏度分析研究线性规划模型参数变化对最优解的影响，帮助决策者在参数不确定性环境下快速判断原最优方案的适用范围，并在参数超出允许范围时高效计算新的最优方案。核心问题参数变化后最优基是否仍优？解与值如何变化？最优基三类参数资源系数b影响可行域，价值系数c影响目标方向，A影响两者b·c·A基本思路利用最优基B⁻¹计算新表，判断最优性与可行性B⁻¹结果判断满足条件更新数值，不满足则用对偶或标准法迭代迭代应用价值避免从头求解的高成本，是持续应用的关键技术低成本SENSITIVITYANALYSIS资源系数b变化的灵敏度分析资源系数b的变化直接影响基变量的取值和最优目标值，但不改变检验数。只要变化后基变量仍非负，最优基不变；最优值的变化量等于对应影子价格乘以资源变化量。01参数变化模型：b→b'=b+Δb，新基变量值xB'=B⁻¹b'=B⁻¹(b+Δb)=xB+B⁻¹Δb，检验数σ不变（c和A未变）σ恒定02最优基不变条件：新基变量值xB'=xB+B⁻¹Δb≥0，即B⁻¹各列与Δb的线性组合不使任何基变量变为负值xB'≥003最优值变化：ΔZ*=y*·Δb=CBB⁻¹Δb，其中y*=CBB⁻¹是对偶最优解（影子价格），资源增量的价值由影子价格决定y*定价04单独变化范围：当某个br单独变化Δbr时，对所有i满足(B⁻¹)ir·Δbr≥−xBi，Δbr的上下限由B⁻¹第r列决定B⁻¹第r列05超出范围处理：若Δbr超出允许范围导致基变量为负，利用对偶单纯形法从当前表继续迭代（检验数仍满足最优性条件）对偶迭代SensitivityAnalysis价值系数c变化的灵敏度分析价值系数c的变化直接影响检验数但不改变基变量取值。非基变量系数变化只需检查单个检验数，基变量系数变化则影响所有检验数，需要根据检验数的符号判断最优基是否改变。01非基变量系数变化：cⱼ变化Δcⱼ时，新检验数σ'ⱼ=σⱼ+Δcⱼ。最优基不变条件为σ'ⱼ≤0，即Δcⱼ≤−σⱼ；超出范围则xⱼ应换入基。02基变量系数变化：c_Bᵢ变化Δc_Bᵢ时，所有非基变量检验数均受影响，σ'ⱼ=σⱼ−Δc_Bᵢ·(B⁻¹A)ᵢⱼ，需逐列检查是否仍满足≤0。03允许范围求解：对所有非基变量j满足σⱼ−Δc_Bᵢ·yᵢⱼ≤0，联立不等式组求Δc_Bᵢ的上下界。04最优值变化：最优基不变时ΔZ*=Δcⱼ·x*ⱼ（对基变量）；非基变量系数变化不影响最优值（因x*ⱼ=0）。05迭代恢复最优：若检验数出现正值，利用标准单纯形法从当前表继续迭代（基变量值仍可行），选择正检验数最大的变量换入。SENSITIVITYANALYSIS·TECHCOEFFICIENT技术系数A变化的灵敏度分析技术系数A的变化同时影响基变量值和检验数，是三类灵敏度分析中最复杂的情形。非基变量列的系数变化只需局部更新，基变量列的变化则需要重新计算基矩阵的逆，通常建议重新求解。LocalUpdate非基变量列更新Aⱼ变为A'ⱼ后，最优表该列更新为B⁻¹A'ⱼ，检验数更新为cⱼ−CBB⁻¹A'ⱼ，只需检查是否≤0。此情形计算量最小，可直接在原最优表基础上局部修改。局部计算快速验证SimplexIterate检验数越界处理列变化导致检验数>0时，将更新列加入当前表，以xⱼ为换入变量用标准单纯形法迭代。此时基矩阵结构保持不变，仅需继续迭代至最优。继续迭代保持基结构GlobalImpact基变量列连锁反应基矩阵B本身改变，B⁻¹需重新计算，所有基变量值和所有检验数均受影响，复杂度显著增加。原最优解可能不再可行，需全面重新分析。全局影响重新求逆Re-solve重新求解策略牵一发动全身，实践中建议以当前解为初始点重新运行单纯形法，而非逐项分析。利用对偶单纯形法或内点法可加速收敛过程。热启动效率优先Application工艺改进场景单位原料消耗降低相当于对应列系数减小，可能使该产品变得更有利可图。灵敏度分析帮助决策者评估技术升级的经济效益与最优生产结构调整方向。技术升级成本优化SensitivityAnalysis灵敏度分析综合示例通过完整的生产问题示例，演示资源系数、价值系数和新增约束三类变化的灵敏度分析全过程，展示如何利用最优表快速响应参数变化并更新决策方案。问题背景原最优解x₁*=4、x₂*=2，最大利润Z*=26，影子价格y₁*=3、y₂*=1，最优表中基矩阵逆B⁻¹已知，为后续三类灵敏度分析提供计算基础。Z*=26资源变化原料1限量增加Δb₁=5，利用影子价格快速计算新目标值，新基变量值经检验仍非负，最优基保持不变。Z*'=41价值变化产品A利润c₁从5降至4，重新计算非基变量检验数，结果均≤0，满足最优性条件，最优基不变。Z*'=22新增约束新增约束2x₁+x₂≤10恰好取等不起作用；若改为≤9则违反原最优解，需引入松弛变量后用对偶单纯形法迭代求解。对偶单纯形处理优先级资源变化优先用影子价格速算，价值变化查检验数判断，新增约束用对偶单纯形法，三类工具构成完整灵敏度分析工具箱。工具箱SensitivityAnalysis参数允许变化范围的确定灵敏度分析的核心输出之一是参数的允许变化范围：在该范围内最优基保持不变，管理者可据此评估决策方案的稳健性和参数不确定性下的风险边界。资源系数bᵣ联立不等式xB+B⁻¹Δb≥0求解Δbᵣ上下界，确定资源限量的稳定区间b₁∈[15,30]价值系数cⱼ由σⱼ+Δcⱼ≤0得非基变量上界，超过此值该变量应换入生产计划cⱼ≤cⱼ−σⱼ基变量系数cBᵢ联立多个不等式σⱼ−ΔcBᵢ·yᵢⱼ≤0求交集，因影响全局范围通常较窄多约束交集百分之百法则多参数同时变化时，各变化量占允许变化量百分比之和不超过100%，最优基不变∑≤100%管理决策价值判断当前方案在多大程度环境变化下仍有效，为应急预案和决策调整提供量化依据量化依据Chapter05原始对偶内点算法与应用从理论到实践——现代求解方法与实际决策场景ALGORITHM原始对偶内点算法原理原始对偶内点算法从可行域内部穿行而非沿边界移动，通过同时维护原问题与对偶问题的近似解并利用互补松弛条件引导搜索方向，在大规模线性规划问题上具有显著的计算效率优势。01与单纯形法的本质区别—单纯形法沿可行域顶点移动，内点法从可行域内部穿行，通过障碍函数或对数罚函数保持迭代点在严格内部02原始对偶框架—同时维护原始变量x>0和对偶变量y、s>0，要求互补松弛条件xs=μe，μ→0时逼近最优解03搜索方向确定—在每个迭代点对KKT条件进行牛顿法线性化，求解线性方程组得到原始和对偶搜索方向，步长由正性条件确定04障碍参数更新策略—μ在每次迭代中按固定比例缩小（如μ←0.1μ），使得迭代点逐渐逼近边界上的最优解05计算复杂度—理论多项式时间复杂度O(n³·⁵L)，对大规模稀疏问题实际表现优于单纯形法的指数最坏情况复杂度Software&Implementation内点算法实现与软件工具MATLAB、Python及商业优化求解器提供了成熟的线性规划求解和灵敏度分析工具，支持单纯形法与内点法双算法选择，可自动输出影子价格和参数允许范围。MATLABlinprog支持simplex与interior-point双算法，输出最优解、最优值及拉格朗日乘子linprog灵敏度分析通过lambda.ineqlin获取对偶变量，upper/lower获取边际价值LambdaPython生态SciPy、PuLP、CVXPy均支持线性规划，可选内点法或单纯形法SciPy·PuLP商业求解器Gurobi、CPLEX支持大规模高效求解，内置灵敏度分析报告Gurobi·CPLEX实践建议小规模用单纯形法理解对偶理论，大规模用内点法配合工具提效SimplexvsIPMApplicationCase应用案例：供应链资源优化对偶理论与灵敏度分析在供应链管理中具有直接应用价值：影子价格识别资源瓶颈与优先级，灵敏度分析评估运价波动和需求变化对最优方案的影响，为动态环境下的供应链决策提供量化支撑。场景建模5个仓库向8个配送中心分配运输资源，构建运输成本最小化的线性规划模型，确定供应约束与需求约束。40×13矩阵影子价格通过求解对偶问题识别瓶颈仓库与配送中心的服务紧迫程度，为资源扩容与优先级调整提供量化依据。瓶颈识别与优先级运价灵敏度分析运价波动对最优方案的影响范围，当运价在允许区间内变化时，当前运输路线方案保持最优不变。c₁₂∈[3.5,5.2]需求灵敏度利用影子价格量化需求变化对总成本的影响，影子价格与需求增量的乘积即为成本增量，支持动态调整。ΔC=π·Δb新路线评估将新增运输路线视为非基变量，通过计算检验数判断其经济性，检验数为负则应纳入最优运输方案。σⱼ<0时纳入CASESTUDY应用案例：投资组合优化对偶理论为投资组合优化提供了风险定价视角：影子价格量化了风险约束的边际价值，灵敏度分析评估资产收益率波动对最优组合的影响，帮助投资者在不确定性环境下做出稳健的资产配置决策。模型构建原问题为max预期收益Σrᵢxᵢ，约束含总投资额、风险上限与单资产比例上限。通过拉格朗日函数建立对偶关系，将复杂约束转化为可计算的对偶变量。maxΣrᵢxᵢ风险影子价格对偶变量y*反映每增加一单位风险容忍度的额外收益，即风险的边际价格。该指标指导投资者权衡风险与收益的最优平衡点，实现风险预算的精准配置。边际定价收益率灵敏度rⱼ变化时利用灵敏度分析判断资产是否仍应持有，超出下界则剔除。灵敏度系数揭示最优组合对参数扰动的稳定区间，为动态调仓提供量化依据。Δrⱼ边界比例约束定价影子价格>0表示上限已成制约因素，可适度放宽以提高组合收益。该分析识别有效约束与冗余约束，帮助管理者优化投资规则与监管框架。xᵢ≤0.2市场波动场景利用百分之一百法则评估多只股票收益率同时变化时的组合稳健性。该法则保证在允许变化范围内最优基不变，为压力测试与情景分析提供理论支撑。100%RuleDUALITYAPPLICATION应用案例：电力系统经济调度对偶理论为电力系统经济调度提供了节点边际电价的理论基础：负荷约束的影子价格直接构成电力市场定价依据，灵敏度分析评估设备检修和负荷波动对系统运行成本的影响。经济调度模型原问题为min总发电成本ΣCᵢ(Pᵢ)，约束包括功率平衡ΣPᵢ=D、机组出力限制及线路潮流约束MINΣCᵢ(Pᵢ)节点边际电价（LMP）功率平衡约束的对偶变量即为该节点边际电价，反映每增加1MW负荷的系统边际成本，是电力现货市场核心定价机制1MW边际机组出力约束的影子价格影子价格>0的机组已达出力上限，为该时段"瓶颈机组"；影子价格=0的机组仍有调节裕度瓶颈识别线路检修灵敏度输电线路容量降低时，用资源系数b的灵敏度分析计算系统成本增加量，评估检修对电价的影响程度Δb分析可再生能源接入风电/光伏出力波动相当于b的随机变化，灵敏度分析确定系统可接纳最大波动范围，指导储能配置决策波动范围CHAPTER06总结与展望从理论体系到前沿方向——对偶理论的全景回顾KNOWLEDGEMAP课程知识体系总结对偶理论与灵敏度分析构成线性规划理论的核心深化模块：从对偶问题的形式转换出发，经由三大定理建立理论基础，通过对偶单纯形法提供计算工具，最终以灵敏度分析实现参数变化下的高效决策更新。CHAPTER01基础层对偶问题的