运筹学基础-对偶线性规划(1) - 副本.ppt

1、任一线性规划问题都存在另一与之伴随的线性规划问题，他们从不同角度对一个实际问题提出并描述，组成一对互为对偶的线性规划问题。,第二章 线性规划的对偶理论,2.1 对偶线性规划问题的提出,一、对偶线性规划问题,某工厂计划安排生产、两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示：,【例1】,原问题的策略: 问应如何安排生产才能使工厂获利最大？,现在的策略: 假设不生产、产品 ,而是计划将现有资源出租或出售,从而获得利润,这时需要考虑如何定价才合理?,设x1、x2分别表示计划生产产品、的单位数量，由题意原问题的模型为：,工厂获

2、得最大利润,符合资源限制,原问题的模型,改变策略后，需要考虑如何给资源定价的问题！,设y1、y2 、y3分别表示出租单位设备台时的租金和出售单位原材料A、B的利润.,y1+4y22，,2y1+4y33,则：,工厂出租设备、原材料的租金要大于生产的利润才合算。,工厂把所有设备台时和资源都出租和出让，其收入为：,要寻找使租用者支付的租金最少的策略。,新问题的模型,工厂改变策略以后的数学模型为：,工厂获得相应利润,用户所付租金最少,联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据；,原模型和对偶模型既有联系又有区别,区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营者的立场上

3、追求工厂的销售收入最大，而后者则是站在谈判对手的立场上寻求应付工厂租金最少的策略。,所谓对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。,原模型与对偶模型有很多的内在联系和相似之处。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变成为对偶问题的右边项，而原问题的约束的右边项则变成为对偶问题目标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。就象一个人对着镜子会左右颠倒一样，原问题与对偶问题之间存在着严格的对应关系。,原问题的一般模型可定义为：,二、对偶规划的一般数学模型,相应的对偶问题的一般模型可定

4、义为：,上述的原问题P和对偶问题 D还可以用矩阵形式写为：,其中,上述的对偶模型都称作为对称型对偶模型。 而在当原问题转化为标准型以后所建立的对偶模型则是非对称型的，如：,原问题与对偶问题的矩阵形式,问题：如何由原模型写出对偶模型？其规律是什么?,三、原问题与对偶问题的对应关系,当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。,下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。,原问题线

5、性规划模型,对偶线性规划模型,原问题为maxZ的线性规划问题对偶关系表,原问题对偶问题 目标函数max 目标函数min,原问题(maxZ)与对偶之关系：,原问题(maxZ)口诀: 约束决定变量是反号,原问题(maxZ)口诀: 变量决定约束是同号,解：,由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3,（还可依对偶问题写出原问题）,例1,写出下列问题的对偶问题：,变量决定约束是同号,约束决定变量是反号,min w=15y1+24y2+5y3,6y2+y3 2,s.t.,y1 , y2 , y3 0,5y1 +2y2 +y3 1,原问题为minS的线性规划问题对偶关系表,原问题对偶问题 目标函数min 目标函数max,原问题(minS) 与对偶之关系：,原问题(minS)口诀: 约束决定变量是同号,原问题(minS)口诀: 变量决定约束是反号,解：,由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3,s.t.,（还可依对偶问题写出原问题）,例2,写出下列问题的对偶问题：,s.t.,1,3,2,1,+,-4,x,x,2x,x1,x2,x3 0,变量决定约束是反号,约束决定变量是同号,练习：试求下列线性规划问题的对偶问题,练习：试求下列线性规划问题的对偶问题,答案：,s.t.,，,练习：试求下列线性规划