线性规划的对偶理论(第2部分).pptVIP

说明：yi的值相当于在给定的生产条件下，bi每增加一个单位时目标函数的增量。影子价格第i个约束条件的影子价格的经济含义是：其它条件不变的情况下，该资源单位的变化所引起的目标函数最优值的变化量在现有的技术和管理条件下，某种资源的影子价格越大，说明该资源对目标增益的影响越大，同时该资源越紧缺和贵重，应该给与高度关注，通过降低消耗或设法补充，提高收益某种资源的影子价格为零，说明该资源相对富裕；一方面可以转让该资源；另一方面，通过挖潜和增加对影子价格大于零资源的投入，使原有的剩余资源充分利用，甚至于成为新的紧缺资源影子价格不是市场价格，而是在现有技术和管理条件下，新增单位资源所能够创造的价值，是特定企业的一种边际价格；不同企业或同一企业不同时期，同种资源的影子价格可能不同；当市场价格高于影子价格，可以卖出；相反，则应买进，以获取更大收益12例：（第一章例2）

最优解为当第一个约束右端项增加1，变为最优解不变，即设备B的边际价格为零。若第二个约束右端项加1，变为最优解为若第三个约束的右端项加1，变为综上，影子价格是灵敏度分析的一种形式，它通过获取一个单位的追加的产品因素，去测量放宽一个约束条件的价值，比较追加资源的价值和资源的实际成本，就能比较有把握地作出各种可行的决策。5、对偶单纯形法什么是对偶单纯形法？对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！二、单纯形法的求解过程就是：在保持原始可行的前提下（b列保持≥0），通过逐步迭代实现对偶可行（检验数行≤0）。对偶单纯形法思想：换个角度考虑LP求解过程：保持对偶可行的前提下（检验数行保持≤0），通过逐步迭代实现原始可行（b列≥0，从非可行解变成可行解）。对偶单纯形法的实施使用条件：①检验数全部≤0；资源列至少一个元素0；实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。b列≥0——原始单纯形法；检验数全部≤0（非基变量检验数0）至少一个检验数0?基变换：先确定换出变量——解答列中的负元素（选最小的负元素）对应的基变量出基；即01相应的行为主元行。02然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果(最小比值原则),则选为换入变量，相应的列为主元列，主元行和主元列交叉处的元素为主元素。?按主元素进行换基迭代（旋转运算、枢运算），将主元素变成1，主元列变成单位向量，得到新的单纯形表。继续以上步骤，直至求出最优解。例5——用对偶单纯形法求解LP：6、灵敏度分析01灵敏度分析的含义和内容02什么是灵敏度分析？03研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析或优化后分析。04灵敏度分析的内容：?目标函数的系数变化对最优解的影响?约束方程右端系数变化对最优解的影响约束方程增加一个变量变化对最优解的影响约束方程增加一个约束条件对最优解的影响回答两个问题：最优表格的基础上进行；尽量减少附加计算工作量；这些参数在什麽范围内发生变化时，最优基不变（即最优解或最优解结构不变）？参数变化超出上述范围时，如何用最简便的方法求出新的最优解？二、工进行灵敏度分析的基本原则01敏度分析举例：03引入非负的松弛变量X3,x4,x5.将该LP化为02例：04标准型：用表格单纯形法求解最终单纯表如下：Cj→23000θjCBXBbx1x2x3x4x52x13101/20-1/50x4400-214/53x2301001/5σj00-10-1/51、分析Ci的变化范围：试分析λ1和λ2分别在什么范围变化，问题的最优解不变。Cj→2+λ13000θjCBXBbx1x2x3x4x52+λ1x13101/20-1/50x4400-214/53x2301001/5σj00-1-λ1/20-1/5+λ1/5表中解为最优的条件是：1-λ1/2≤0,-1/5+λ1/5≤0,由此推导得当-2≤λ1≤1时满足上述要求。当λ1=0时，再将λ2反映到表下表中得：为使表中解仍为最优解，

应有-1/5-λ2/5≤