线性规划的对偶问题

《线性规划的对偶问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、教案五线性规划的对偶问题教学内容第四节线性规划的对偶问题1．线性规划的对偶问题2．对偶单纯形法3．线性规划的灵敏度分析4．线性规划在卫生管理中的应用教学学时7学时教学目标1．理解对偶问题的基本概念2．掌握对偶单纯形法3．掌握线性规划的灵敏度分析4．掌握线性规划在卫生管理中的应用重点难点重点是对偶问题的基本概念、对偶单纯形法线、灵敏度分析、线性规划在卫生管理中的应用。难点是对偶问题的基本概念和线性规划的灵敏度分析教学手段教师与学生互动使用多媒体课件教学过程一、复习巩固1．单纯形法的基本原理（见课件）2．单纯形解法（见课件）3．大法

2、（见课件）二、讲授新课1．线性规划的对偶问题（1）对偶问题的基本概念（见课件）对偶现象每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶．其中一个问题称为原问题，另一个问题称为其对偶问题．两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解．下面通过一个实例来解释对偶线性规划的概念．例2-12以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法．现在假定该制药厂决定在计划期内不生产药品Ⅰ、Ⅱ，而将生产设备的有效台时全部租给某公司，那么该公司应对设备每小时付多少租金，才能使成本最小，而又能为制药厂所

3、接受？从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低于制药厂自己生产该两种药品所得利润，否则，制药厂宁可自己生产，而不租给公司．设公司租用该制药厂四种设备的租金（元/小时）分别为、、和．在考虑租用设备的定价时，能使该制药厂接受的条件是：公司租用该制药厂用以生产每千克药品Ⅰ所需四种设备的台时的租金不应少于200元，即同样，公司租用该制药厂用以生产每千克药品Ⅱ所需四种设备的台时的租金不应少于300元，即公司在考虑自身利益时，其目标是使付出的租金总额为最小，即于是，上面的问题可以用下

4、列线性规划的数学模型表示：若把制药厂利润最大的线性规划问题称为原问题，则想租用四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题（dualproblem）；反之，若把租用四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题．影子价格一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解称为第种资源的影子价格．它并不是某种资源在市场上的价格，而是代表单位资源在最优利用的条件下所产生的经济效果．为了和市场价格相区别，我们才称它为影子价格．它在经济上是一个很有意

5、义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小．另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准．（2）对称的对偶线性规划（见课件）如果一个线性规划具备下面两个条件，则称它具有对称形式：①所有的变量都是非负的；②所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于（）的符号，在目标函数是求极小值的情况，不等式具有大于和等于（）的符号．对称形式的原问题和对偶问题叫做对称的对偶线性规划．原问题和对偶问题在形式上的对比如果我们把线性规划…………………………

6、称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题：…………………………而且用简缩形式表示：原问题为对偶问题为;矩阵形式表示：原问题为对偶问题为MinW＝Yb其中，原问题与对偶问题之间的关系1）原问题是求目标函数的最大值，对偶问题是求目标函数的最小值．2）原问题约束条件的右端项变成对偶问题目标函数的系数．原问题目标函数中的系数变成对偶问题约束条件的右端项．3）原问题约束条件是“”，对偶问题的约束条件则是“”．4）原问题约束条件的每一行正好对应于对偶问题的每一列，所以原问题中约束条件的数目等于对偶问题中变量的数目．5）原问

7、题中约束条件的每一列正好对应于对偶问题的每一行，所以原问题中变量的数目正好等于对偶问题中的约束条件的数目．6）对偶问题的对偶规划正是原问题．例2-13设原问题为：　　　　　　　　　　　　　　　　　　　试写出它的对偶问题．解　　　　　　　　　　（3）非对称的对偶线性规划（见课件）对于我们经常遇到的非对称形式的线性规划，我们可首先将其化为等价的对称形式的线性规划问题，然后再按对称的对偶线性规划原问题与对偶问题之间的对应关系，将其化为对偶问题．实际上，我们在考虑对称的对偶线性规划或非对称的对偶线性规划（dualofanonnormal

8、LP）时，也可以按表2-13原问题与对偶问题之间的对应关系，直接进行变换，得到原问题或对偶问题．表2-13原问题与对偶问题间的转换原问题（或对偶问题）对偶问题（或原问题）目标函数目标函数约束条件数：个对偶变量数：个第个约束条件为“”对偶变量0第个约束条件为“”对