对偶理论与灵敏度分析上课.ppt

影子价格 式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price)。 几点说明： 1．资源的影子价格是未知数，有赖于企业资源状况。 2．影子价格是一种边际价格, 相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数z的增量。 3．资源的影子价格实际上又是一种机会成本。 4．生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。 5．对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定资源的恰当估价。 对偶单纯形法 基本思路：在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。 即保持对偶问题有可行解 使原问题具有可行解 检验数为非正 替换负基变量 对偶单纯形法计算步骤 1. 列出初始单纯形表，且检验数非正。 2. b值有否为负，无，计算结束。有，转3 5.以ars为主元素，进行迭代变换。 6 . 返 3，直到b ≥ 0为止。 用对偶单纯形法求解下述线性规划问题 例 化标准型： 整理得： 解： Cj －15 －24 －5 0 0 CB yB b y1 y2 y3 y4 y5 0 y4 －2 0 -6 -1 1 0 0 y5 －1 -5 -2 -1 0 1 σj=cj-zj －24 y2 1/3 0 1 1/6 -1/6 0 0 y5 -1/3 -5 0 -2/3 -1/3 1 σj=cj-zj -15 -24 -5 0 0 -15 0 -1 -4 0 －24 y2 1/4 -5/4 1 0 -1/4 1/4 -5 y3 1/2 15/2 0 1 1/2 -3/2 σj=cj-zj -15/2 0 0 -7/2 -3/2 在得到原始可行解时同时得到对偶可行解，已获得最优解： （y1, y2, y3, y4, y5）=（0,1/4, 1/2,0,0） max w=17/2 对偶问题的最优解为： （x1, x2, x3 ）=（ 7/2, 3/2, 15/2） min z=17/2 对偶单纯形法的优点： 用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引进人工变量，使计算简化。 对偶单纯形法的应用范围： 在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。因此对偶单纯形法一般不单独使用，多用于灵敏度分析等用途。 灵敏度分析 －－当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。 灵敏度分析的定义 灵敏度分析所要研究解决的问题 －－是指对系统或事物因周围条件变化显示出来的敏感程度的分析。 条件变化 aij，bi，cj 最优解 多大范围内变化 1．将参数的改变计算反映到最终单纯形表上来： 灵敏度分析的步骤 最终单纯形表 B-1B 3．检查对偶问题是否仍为可行解； 4．按下表所列情况得以结论和决定继续计算的步骤。 2．检查原问题是否仍为可行解； 灵敏度分析的任务 (1)、参数A，b，C在什么范围内变动，对当前方案无影响？ (2)、参数A，b，C中的一个(几个)变动，对当前方案的影响？ (3)、如果最优方案改变，如何用简便方法求新方案？ 一、分析Cj的变化 Cj的变化仅仅影响到检验数(Cj-Zj)的变化。所以将Cj的变化直接反映到最终单纯形表中，只可能出现前两种情况。 Cj的变化仅仅影响到检验数(Cj-Zj)的变化 最终单纯形表 例: (1)若家电I的利润降至1. 5元／件，而家电的利润增至2元／件时，美佳公司最优生产计划有何变化； (2)若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化？ 在第一章例1的美佳公司例子中: (1) 若家电I的利润降至1. 5元／件，而家电的利润增至2元／件时，美佳公司最优生产计划有何变化； 最终单纯形表如下： 原问题可行，对偶问题不可行,用单纯形法继续迭代求解。 将家电I，II的利润变化cj直接反映到最终单纯形表中。 -2 0 -1 1/8 -9/4 为使表中的解仍为最优解，应有 即家电II的利润C2的变化范围应满足： 2) 若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化？ 0 0