线性规划的对偶问题线性划的对偶问题.docVIP

教案五 线性规划的对偶问题 教学内容 第四节 线性规划的对偶问题 1．线性规划的对偶问题 2．对偶单纯形法 3．线性规划的灵敏度分析 4．线性规划在卫生管理中的应用 教学学时 7学时 教学目标 1．理解对偶问题的基本概念 2．掌握对偶单纯形法 3．掌握线性规划的灵敏度分析 4．掌握线性规划在卫生管理中的应用 重点难点 重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。难点是对偶问题的基本概念和线性规划的灵敏度分析 教学手段 教师与学生互动 使用多媒体课件 教学过程 一、复习巩固 1．单纯形法的基本原理（见课件） 2．单纯形解法（见课件） 3．大法（见课件） 二、讲授新课 1．线性规划的对偶问题 （1）对偶问题的基本概念（见课件） 对偶现象 每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶．其中一个问题称为原问题，另一个问题称为其对偶问题．两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解． 下面通过一个实例来解释对偶线性规划的概念． 例2-12 以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法． 现在假定该制药厂决定在计划期内不生产药品Ⅰ、Ⅱ，而将生产设备的有效台时全部租给某公司，那么该公司应对设备每小时付多少租金，才能使成本最小，而又能为制药厂所接受？ 从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低于制药厂自己生产该两种药品所得利润，否则，制药厂宁可自己生产，而不租给公司． 设公司租用该制药厂四种设备的租金（元/小时）分别为、、和．在考虑租用设备的定价时，能使该制药厂接受的条件是： 公司租用该制药厂用以生产每千克药品Ⅰ所需四种设备的台时的租金不应少于200元，即 同样，公司租用该制药厂用以生产每千克药品Ⅱ所需四种设备的台时的租金不应少于300元，即 公司在考虑自身利益时，其目标是使付出的租金总额为最小，即 于是，上面的问题可以用下列线性规划的数学模型表示： 若把制药厂利润最大的线性规划问题称为原问题，则想租用四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题（dual problem）；反之，若把租用四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题． 影子价格 一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解称为第种资源的影子价格．它并不是某种资源在市场上的价格，而是代表单位资源在最优利用的条件下所产生的经济效果．为了和市场价格相区别，我们才称它为影子价格．它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小．另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准． （2）对称的对偶线性规划（见课件） 如果一个线性规划具备下面两个条件，则称它具有对称形式：①所有的变量都是非负的；②所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于（）的符号，在目标函数是求极小值的情况，不等式具有大于和等于（）的符号． 对称形式的原问题和对偶问题叫做对称的对偶线性规划． 原问题和对偶问题在形式上的对比 如果我们把线性规划 ………………………… 称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题： ………………………… 而且 用简缩形式表示： 原问题为 对偶问题为 ; 矩阵形式表示： 原问题为 对偶问题为 Min W＝Yb 其中， 原问题与对偶问题之间的关系 1）原问题是求目标函数的最大值，对偶问题是求目标函数的最小值．