线性规划的对偶理论1

《线性规划的对偶理论1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论北京物资学院李珍萍2013年3月北京物资学院运筹学教学课件本章主要内容第一节、原问题与对偶问题第二节、对偶问题的基本性质第三节、影子价格第四节、对偶单纯形方法第五节、灵敏度分析第六节、线性规划的求解软件第一节、原问题和对偶问题一、引例二、对称形式的对偶规划三、非对称形式的对偶规划四、一般形式的对偶规划一、引例ABCD原料拥有量（单位）含量（单位/公斤）糖524260蛋白质321440脂肪312535单价（元/公斤）157912建立其数学模型。例1甲食品厂用糖、蛋白质和脂肪三种原料生产四种复合食品A、B

2、、C、D，复合食品中含有各种原料的数量、复合食品的单价、三种原料的拥有量分别如下表所示，问甲厂如何安排生产才能使总产值达到最大？x1x2x3x4解：设甲厂安排A、B、C、D的产量分别为x1、x2、x3、x4公斤，总产值为z元。于是，例1的数学模型为：例2.假设乙食品厂欲将甲厂的原料收买过来，问乙厂至少应付出多少代价，才能使甲厂放弃生产活动，出让原料？建立该问题的数学模型。ABCD原料拥有量（单位）含量（单位/公斤）糖524260蛋白质321440脂肪312535单价（元/公斤）157912y1y2y3解：设y1,y2和y3（

3、元/单位）分别代表乙厂收购糖、蛋白质和脂肪的单价，乙厂收购原料付出的总费用为w元，于是例2的数学模型为：例1和例2的数学模型比较令以上两个线性规划分别称为线性规划的原问题和对偶问题。若两个线性规划分别是和则称它们是一对对称形式的对偶规划。二、对称形式的对偶规划对称形式的对偶规划还可以写成表格形式，称为对偶表MaxzMinw原问题（求极大）c1x1c2x2……cnxn右端项对偶问题求极小b1y1a11a12…a1nb1b2y2a21a22…a2nb2………………bmymam1am2…amnbm右端项c1c2…cn对

4、偶规划中的两个问题分别称为原问题和对偶问题（互为对偶）。一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”型不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”型不等式。即“max，≤”和“min，≥”相对应。(2)一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。(3)原问题目标函数系数是对偶问题的约束条件右端项；原问题的约束条件右端项是对偶问题的目标函数系数。(4)两个规划模型中的变量皆非负。例3

5、：写出下列线性规划的对偶规划解：原规划的对偶规划为y1y2不等式约束对应非负变量三、非对称形式的对偶规划叫做非对称形式的对偶规划。非对称形式的对偶规划可以由对称形式的对偶规划推出。例4：写出下列线性规划问题的对偶规划。解：将上述线性规划化成对称对偶规划的形式写出它的对偶规划y1'y1y2'y2等式约束对应自由变量(D)四、一般形式的对偶规划(P)一般形式的对偶规划的特点（1）原问题是“max，=,≤”形式，对偶问题是“min，=,≥”形式（2）原问题的每个等式约束，对应对偶问题一个自由变量，原问题的每个不等式约束，对应对

6、偶问题的一个非负变量；反之亦然，即原问题中的每个非负变量对应的是对偶问题中的一个不等式约束，而原始问题中的每个自由变量对应对偶问题中的一个等式约束。（3）原问题目标函数中的系数c就是对偶问题约束条件的右端常数项，而原问题约束的右端常数项就是对偶问题目标函数中的系数。（4）如果用矩阵和向量形式写出问题(P)和(D)的约束，可以看出这两个问题的约束系数矩阵互为转置。例5.写出下面线性规划的对偶规划解先将约束条件变形为“≤”形式y1y2y3y4y5再根据非对称形式的对应关系，直接写出对偶规划例６．写出下列线性规划问题的对偶规划解：

7、令x1=x1，将约束化成相对规范形式y1'y2y3直接写出对偶规划比较原规划和对偶规划令y1=y1',并把第一个约束两端乘以-1得不符合要求的约束对应非正变量线性规划原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）目标函数max目标函数minn个变量00无限制n个约束条件=目标函数中变量的系数约束条件右端常数m个约束条件=m个0变量0无限制约束条件右端常数目标函数中变量的系数作业：P881、(1)(2)(3)第二节、对偶问题的基本性质（对偶定理）原问题与对偶问题的解之间的关系定理1(对称性

8、)对偶问题的对偶是原问题。定理3（强对偶定理）若原问题有最优解，则其对偶问题也一定有最优解，并且此时目标函数的最优值相等。定理2(弱对偶定理)设X0和Y0分别是原问题和对偶问题的可行解，则CX0Y0b；特别当CX0=Y0b时，X0和Y0分别是原问题和对偶问题的最优解。证明：将原问题加上松