第三章 对偶理论及灵敏度分析.ppt

第三章 对偶理论及灵敏度分析 3.1.1 线性规划对偶问题 3.1.2 对偶问题的基本性质 3.1.3 影子价格 3.1.4 对偶单纯形法 3.2.1 灵敏度问题及其图解法 3.2.2 灵敏度分析 3.2.3 参数线性规划 3.1.1 线性规划的对偶问题 一、对偶问题的提出 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系 一、对偶问题的提出 实例：某家电厂家利用现有资源生产两种 产品， 有关数据如下表： 二、原问题与对偶问题的数学模型 三、原问题与对偶问题的对应关系 线性规划的对偶问题 3.1.2 对偶问题的基本性质 引例 对称性 弱对偶性 最优性 对偶性（强对偶性） 互补松弛性 对偶问题的基本性质 对偶问题的基本性质 二、弱对偶性定理： ——若 和 分别是原问题（1）及对偶问题（2）的可行解，则有 从弱对偶性可得到以下重要结论： 对偶问题的基本性质 三、最优性定理： ——若 和 分别是（1）和（2）的 可行解，且有 则 分别是（1）和（2）的最优解 。 3.1.3 影子价格 在单纯形法的每步迭代中，目标函数取值 ， 和检验数 中都有乘子 ，那么Y的经济意义是什么？ 当线性规划原问题求得最优解 时，其对偶问题也得到最优解 ，且代入各自的目标函数后有： 影子价格的定义 对偶变量 的意义——代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。 影子价格的经济意义 1．资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 影子价格的经济意义 2．影子价格是一种边际价格。 在（3）式中， 。 说明 的值相当于在资源得到最优利用的生产条件下， 每增加一个单位时目标函数 的增量。 影子价格的经济意义 3．资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。 4．在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。 5．从影子价格的含义上考察单纯形表的 检验数的经济意义。 影子价格的经济意义 6．一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。 影子价格 3.1.4 对偶单纯形法 对偶单纯形法的基本思路 单纯形法的基本思路： 原问题基可行解 最优解判断 对偶单纯形法的计算步骤 线性规划问题 练习 用对偶单纯形法求解线性规划问题： 对偶单纯形法 灵敏度问题 背景： 线性规划问题中， 都是常数，但这些系数是估计值和预测值。 市场的变化 值变化； 工艺的变化 值变化； 资源的变化 值变化。 研究内容： 研究线性规划中， 的变化对最优解的影响。 3.2.2 灵敏度分析 研究内容： 研究线性规划中， 的变化对最优解的影响。 实例： 某家电厂家利用现有资源生产两种产品，有关数据如下表： 一、分析 的变化 的变化仅影响 的变化。 最终单纯形表 最终单纯形表 换基后单纯形表为 二、分析 的变化 三、增加一个变量 的分析 四、增加一个约束条件的分析 五、分析 的变化 灵敏