《运筹学基础-对偶线性规划(1)》由会员分享，可在线阅读，更多相关《运筹学基础-对偶线性规划(1)（37页珍藏版）》请在金锄头文库上搜索。
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的线性规划问题对偶关系表,原问题 对偶问题
6、 目标函数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.,，,练习：试求下列线性规划问题的对偶问题,maxZ=5y1+4y2+6y3y1+2y2 2y1
7、 +2y2 +y3 3-3y1 +y3 -5y1 -y2 +y31y1 0, y2 , y3 0,答案：,线性规划的对偶理论包括以下几个基本定理。,定理1 （对称性定理）,2.2 线性规划的对偶理论,定理2 （弱对偶定理）,即对偶问题的对偶是原问题。,设x和y分别是原问题和对偶问题的可行解，则必有cxyb，即原问题的目标值小于对偶问题的目标值,定理3 （无界性）,若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。,若原（对偶）问题有可行解,对偶（原）问题无可行解，则原（对偶）问题一定无界；,注:此定理可以判定解的情况,定理4 （可行解是最优解的性质）,定理5 （强对偶定理）,设X*
8、是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时， X*与Y*是最优解 。,若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等,综合上述结论得原问题与对偶问题的解的关系,一般是：cxyb,原问题与对偶问题解的对应关系,由原问题与对偶问题的解的关系可以判定线性规划的解。,Min w = 2y1 +y2S.t. y1 2y2 1 y1 + y2 1 y1 y2 0 y1,y2 0,应用如上关系求解线性规划问题,试用对偶理论证明上述规划问题无最优解。,由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解， 由于原问题存在可行解，所以解无界。,解 该问题存在可行解，如X=
9、(0，0，0)；,其对偶问题为：,对偶问题无可行解,定理6（互补松弛定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,注：证明过程参见教材59页性质5证明,讨论:,互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。,1.如果原问题的某一约束为紧约束（严格等式:松弛变量为
10、零），该约束对应的对偶变量应大于或等于零；,2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必为零；,3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等式)；,4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。,线性规划达到最优时的关系,22,1/5 3,17/55,7/5 2,3=3,解：写出对偶问题为：Max Z = 4y1 + 3yS.t. y1 + 2y2 2 y1 y2 3 2y1 +3y2 5 y1 + y2 2 3y1 +y2 3 y1,y2 0,又例:应用如上关系求解线性
11、规划问题,已知对偶问题的最优解为 y1 = 4/5, y2 = 3/5, 试应用对偶理论求解原问题。,x2 = 0,x3 = 0,x4 = 0,等号,又因y1,y2 0，故原问题的两个约束必为紧约束，即,解得：x1 = x5 = 1。,maxZ=5=minS=5,得原问题的最优解X*=(1,0,0,0,1) minS=5,Max.Z=2x1+4x2+x3+x4s.t. x1+3x2 +x482x1+x2 6x2 + x3 +x46x1 + x2 +x3 9xj0（j=1,2,3,4）,附 练习答案：y1=4/5, y2=3/5, y3=1, y4=0,已知原问题的最优解为:X*=(2,2,4,
12、0)T，试根据互补松弛定理解出其对偶问题的最优解。,线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4s.t. y1+2y2 +y4 23y1+y2 + y3 +y4 4y3 +y4 1y1 +y3 1yj0（j=1,2,3,4）,练习：已知线性规划问题为：,为严格不等式，由互补松弛定知，必有y4 = 0；,Max.Z=2x1+4x2+x3+x4s.t. x1+3x2 +x482x1+x2 6x2 + x3 +x46x1 + x2 +x3 9 xj0（j=1,2,3,4）, 8=8, 6=6, 6=6, 89,解之，有： y1=4/5, y2=3/5, y3=1，y4 = 0
13、,答案：因为原问题的最优解为:X*=(2,2,4,0)T ：,又因x1, x2 , x30，故对偶问题的前三个约束必为紧约束,线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4s.t. y1+2y2 +y4 23y1+y2 + y3 +y4 4y3 +y4 1y1 +y3 1yj0（j=1,2,3,4）,等号,（1）写出对偶问题； （2）已知原问题的最优解为X*=（2，0，1，1）T，求对偶问题的最优解。,已知线性规划问题,定理7,结论：用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解的同时，其：,线性规划原问题及其对偶问题之间存在一对互补的基解，其中原问题的
14、松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这两个解代入各自的目标数中有 z=w。,注：证明过程参见教材60页性质6证明,检验数行的-(cj-zj)值是其对偶问题的一个基本解yi ；,用单纯形法同时求解原问题和对偶问题,原问题是：,maxZ=2x1 +x25x2 156x1 + 2x2 24x1 + x2 5x1 , x2 0,原问题的标准型是：,maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24x1 + x2 +x5 = 5xi 0,maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =156x1 + 2x2 +x4 = 24x1 + x2 +x5 = 5xi 0,原问题变量,原问题松驰变量,对偶问题剩余变量 y4、y5,
