运筹学基础对偶线性规划1.ppt

《运筹学基础对偶线性规划1.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、才合理?设x1、x2分别表示计划生产产品Ⅰ、Ⅱ的单位数量，由题意原问题的模型为：工厂获得最大利润符合资源限制ⅠⅡ设备128台时原材料A4016Kg原材料B0412Kg每单位产品利润（万元）23原问题的模型改变策略后，需要考虑如何给资源定价的问题！设y1、y2、y3分别表示出租单位设备台时的租金和出售单位原材料A、B的利润.y1+4y2≥2，2y1+4y3≥3则：工厂出租设备、原材料的租金要大于生产的利润才合算。工厂把所有设备台时和资源都出租和出让，其收入为：要寻找使租用者支付的租金最少的策略。ⅠⅡ设备128台时原材料A4016Kg原材料B0412Kg每单位产品利润（万元）23新

3、问题的模型工厂改变策略以后的数学模型为：工厂获得相应利润用户所付租金最少联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据；原模型和对偶模型既有联系又有区别区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营者的立场上追求工厂的销售收入最大，而后者则是站在谈判对手的立场上寻求应付工厂租金最少的策略。所谓对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。原模型与对偶模型有很多的内在联系和相似之处。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变成为对偶问题的右边项，而原问题

4、的约束的右边项则变成为对偶问题目标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。就象一个人对着镜子会左右颠倒一样，原问题与对偶问题之间存在着严格的对应关系。原问题的一般模型可定义为：二、对偶规划的一般数学模型nnxcxcxcZ+++=...max2211s.t.11212111...bxaxaxann£+++22222121...bxaxaxann£+++……….mnmnmmbxaxaxa£+++...22110,...,,21³nxxx相应的对偶问题的一般模型可定义为：mmybybybS+++=...min2211s.t.11221111...cyayayamm³++

5、+22222112...cyayayamm³+++………nmmnnncyayaya³+++...22110,...,,21³myyy上述的原问题P和对偶问题D还可以用矩阵形式写为：(P)maxZ=cxs.t.Ax≤bx≥0其中),..,,(21myyyy=上述的对偶模型都称作为对称型对偶模型。而在当原问题转化为标准型以后所建立的对偶模型则是非对称型的，如：(P)maxZ=cxs.t.Ax=bx≥0s.t.yAy≥c≥0(D)minS=ybs.t.yA≥cy为自由变量(D)minS=yb原问题与对偶问题的矩阵形式问题：如何由原模型写出对偶模型？其规律是什么?三、原问题与对偶问题的

6、对应关系当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。原问题线性规划模型对偶线性规划模型原问题为maxZ的线性规划问题对偶关系表原问题（或对偶问题）对偶问题（或原问题）目标函数最大化(maxZ)n个变量m个约束约束条件限定向量（右边项）目标函数价值向量（系数）≥0变量≤0≥无限制约束≤＝目标函数最小化（minS）n个约束

7、m个变量目标函数价值向量（系数）约束条件限定向量（右边项）≥约束≤≤0＝变量≥0无限制同号反号原问题对偶问题目标函数max目标函数min原问题(maxZ)与对偶之关系：原问题(maxZ)口诀:约束决定变量是反号原问题(maxZ)口诀:变量决定约束是同号解：由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3（还可依对偶问题写出原问题）例1写出下列问题的对偶问题：变量决定约束是同号,约束决定变量是反号maxZ=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0m