第三节第三节 对偶单纯形法对偶单纯形法n 对偶单纯形法的基本思路对偶单纯形法的基本思路用用对偶原理对偶原理求解求解原问题原问题的一种方法，的一种方法，而不是求解对偶问题解的单纯形法而不是求解对偶问题解的单纯形法n 对偶单纯形法的计算步骤对偶单纯形法的计算步骤返回返回返回返回继续继续继续继续对偶单纯形影子价格返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶单纯形法的基本思路对偶单纯形法的基本思路对偶单纯形法的基本思路对偶单纯形法的基本思路单纯形法的基本思路：单纯形法的基本思路：原问题基可行解原问题基可行解 最优最优解判断解判断对偶问题的可行解对偶问题的可行解对偶问题对偶问题最优解判断最优解判断对偶单纯形法对偶单纯形法对偶单纯形法对偶单纯形法基本思路基本思路基本思路基本思路C-CBB-1A0实质：保证原问题可行的条件下实质：保证原问题可行的条件下实质：保证原问题可行的条件下实质：保证原问题可行的条件下向对偶问题可行的方向迭代向对偶问题可行的方向迭代向对偶问题可行的方向迭代向对偶问题可行的方向迭代返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶单纯形法的计算步骤对偶单纯形法的计算步骤n线性规划问题 不妨设 为对偶问题的初始可行基，则 。 若 ，即表中原问题和对偶问题均为最优解，否则换基。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题确定换出基变量 对应变量 为换出基的变量确定换入基变量 为主元素， 为换入基变量返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题初始可行基例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：对偶问题的初始可行基返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题例、用对偶单纯形法求解例、用对偶单纯形法求解例、用对偶单纯形法求解例、用对偶单纯形法求解线性规划问题：线性规划问题：线性规划问题：线性规划问题：换出 换出换出换出返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题最优解最优解例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n n对偶单纯形法的优点：对偶单纯形法的优点：n不需要人工变量；不需要人工变量；n当变量多于约束时，用对偶单纯形法可减少当变量多于约束时，用对偶单纯形法可减少迭代次数；迭代次数；n在灵敏度分析中，有时需要用对偶单纯形法在灵敏度分析中，有时需要用对偶单纯形法处理简化。处理简化。n n对偶单纯形法缺点：对偶单纯形法缺点：n对初始单纯形表形式要求较严格（在对偶问对初始单纯形表形式要求较严格（在对偶问题可行的前提下），普遍适用性较差。题可行的前提下），普遍适用性较差。 因此，对偶单纯形法一般不单独使用。因此，对偶单纯形法一般不单独使用。返回返回返回返回继续继续继续继续第四节 影子价格影子价格在单纯形法的每步迭代中，目标函数取值 ，和检验数 中都有乘子 ，那么它的经济意义是什么？ 对偶单纯形影子价格返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n 当线性规划原问题求得最优解时，其对偶问题也得到最优解 ，且代入各自的目标函数后有：是线性规划原问题约束条件的右端项，它代表第 种资源的拥有量；（3）返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 对偶变量 的意义代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。影子价格的定义影子价格的定义返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n1资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格的经济意义影子价格的经济意义市场价格影子价格市场企业返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题影子价格的经济意义影子价格的经济意义n2影子价格是一种边际价格。 在（3）式中， 。 说明 的值相当于在资源得到最优利用的生产条件下， 每增加一个单位时目标函数 的增量。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题引例数学模型返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n几何解释：引例图解法分析几何解释：引例图解法分析。（3，3）（15/4，5/4）,z=8.75（7/2，3/2），z=8.5返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题影子价格的经济意义影子价格的经济意义3资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n4从影子价格的含义上考察单纯形表的 检验数的经济意义。（4）第j种产品的产值生产第j中产品所消耗各项资源的影子价格的总和。（即隐含成本）可见，产品产值可见，产品产值隐含成本隐含成本 可生产该产品；可生产该产品；否则，不安排生产。否则，不安排生产。检验数的经济意义检验数的经济意义返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题影子价格的经济意义影子价格的经济意义n5一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。经济学研究如何管理自己的稀缺资源