单纯形法灵敏度分析线性规划对偶理论.ppt

单纯形法灵敏度分析线性规划对偶理论 单纯形法是线性规划中一种常用的解决方法，它通过对偶理论来分析参数变化对最优解的影响。本文主要介绍单纯形法灵敏度分析的理论和应用。 单纯形法灵敏度分析是研究线性规划中参数变化对最优解的影响的方法。参数变化可能是系数ci、aij、bj的变化，或者是其他条件的变化。单纯形法灵敏度分析的目的是研究这些变化对最优解的影响，并找出对偶价格，从而指导决策。 单纯形法灵敏度分析可以分为两种：目标函数中的系数ci的灵敏度分析和约束条件中右边系数bj的灵敏度分析。 目标函数中的系数ci的灵敏度分析是研究ci变化对目标函数等值线的影响。ci的变化只影响目标函数等值线的斜率。当ci变化时，目标函数等值线的斜率也会变化，从而影响最优解。例如，在目标函数z = 50x1 + 100x2中，ci的变化会使目标函数等值线的斜率变化，从而影响最优解。 约束条件中右边系数bj的灵敏度分析是研究bj变化对可行域的影响。bj的变化会使可行域扩大或缩小，从而影响最优解。例如，在约束条件x1 + x2 ≤ 300中，bj的变化会使可行域扩大或缩小，从而影响最优解。 单纯形法灵敏度分析的应用非常广泛，例如在生产计划、投资决策、资源配置等方面都可以应用单纯形法灵敏度分析来指导决策。 线性规划的矩阵描述是将线性规划问题描述成矩阵形式。max z = c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1nxn = b1, a21x1 + a22x2 + … + a2nxn = b2, …, am1x1 + am2x2 + … + amnxn = bm, x1, x2, …, xn ≥ 0。其中，C = (c1, c2, …, cn), X = (x1, x2, …, xn)T, A = [a11, a12, …, a1n; a21, a22, …, a2n; …; am1, am2, …, amn]。 单纯形法的矩阵描述是将单纯形表重排A, C, X，并写成分块矩阵形式。B = [B1, B2, …, Bn], N = [N1, N2, …, Nn], X = [x1, x2, …, xn]T, Δ = [Δ1, Δ2, …, Δn]。 迭代次数基变量cB x1 x2 s1 s2 s3b比值bi/aij 50 100 0 0 02x1s2x2500100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 15050250zjσj = cj - zj 单纯形法灵敏度分析可以在实际问题中应用，例如在生产计划中，单纯形法灵敏度分析可以用来研究设备台数的变化对生产计划的影响。在投资决策中，单纯形法灵敏度分析可以用来研究投资金额的变化对投资回报的影响。 单纯形法灵敏度分析是线性规划中的一种重要方法，可以应用于实际问题中指导决策。