对偶理论与灵敏度分析.pptVIP

第二章 线性规划的对偶理论 第一节 对偶问题的提出 原问题 第二节 LP问题的对偶理论 例 线性规划的矩阵表示 初始单纯形表 初始单纯形表 初始单纯形表 推论：对偶问题的最优解对应于原问题的最优单纯型表中松弛变量检验数的相反数或剩余变量的检验数。 Min z=2x1+3x2 x1+x2 ≥350 x1 ≥125 2x1+x2 ≤ 600 x1, x2 ≥0 互补松弛性:在线形规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之,如果约束条件取严格不等式,则其对应的对偶变量一定为零。 第三节 对偶问题的经济解释----影子价格 资源的影子价格是针对具体生产或具体企业而言的： 同一种资源在不同的生产条件下或不同的范围内可能有不同的影子价格；A 产品的市场价格发生变化，资源的影子价格也会发生变化；C 资源的数量结构不同，资源的影子价格也不同。b 二、影子价格的作用 第四节 对偶单纯形法 正则解：设X(0)是线性规划问题(Max)的一个基本解，如果它的检验数σj≤0(j∈J)，则称X(0)是该线性规划问题的一个正则解。相应的基称为正则基。 第四节 对偶单纯形法 单纯形法 第五节 线性规划的灵敏度分析 四、右端项 b 的变化分析——求B-1 四、右端项 b 的变化分析——求B-1 四、右端项 b 的变化分析——公式推导 四、右端项 b 的变化分析——例题 （2）工厂新增24公斤原材料A，则 六、技术矩阵 A 的变化分析 例10 0 0 -3/2 -1/8 0 -14 σj 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 4 4 2 2 x1 0 x5 3 x2 x1 x2 x3 x4 x5 CB XB b 2 3 0 0 0 cj 用单纯形法求得最优单纯形表如下： 最优生产计划为：生产4件产品I，2件产品II；最大利润为14。 B-1 0 0 -3/2 -1/8 0 -17 σj 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 10 16 -1 2 x1 0 x5 3 x2 x1 x2 x3 x4 x5 CB XB b 2 3 0 0 0 cj 新的最优生产计划为：生产8件产品I，0件产品II；最大利润为16。 将其代入原最优表，并利用对偶单纯形法迭代： 0 -1 -2 0 0 -16 σj 1 2 1 0 0 0 4 0 0 1 0 -8 -4 1 0 8 12 8 2 x1 0 x5 0 x4 ×(-8) x4 1 -1 2 1 0 2 x2 3 -1 -1 x5 0 -3 3 x4 0 -3 0 0 σ -1 0 1 1 x1 2 x3 x2 x1 b XB CB 1 3 2 cj 例5 下面是一张LP问题的最优单纯形表,观察其目标函数系数的改变对检验数的影响 五、价值系数 C 的变化分析 cj 的变化会引起检验数σj= cj -CBB-1Pj 的变化,有两种情况: 非基变量的价值系数cj 变化，不影响其它检验数. 基变量的价值系数cj 变化，影响所有非基变量检验数. 1.非基变量价值系数的改变 若非基变量的价值系数cj 变为cj ’= cj +△cj ， 讨论：