运筹学 第二章线性规划的对偶理论(研究生)

第二章线性规划的对偶理论北京物资学院信息学院2010年10月北京物资学院运筹学教学课件本章主要内容第一节、对偶问题的提出第二节、原问题与对偶问题第三节、对偶问题的基本性质第四节、影子价格第五节、对偶单纯形方法第六节、灵敏度分析第七节、线性规划的求解软件第一节、对偶问题的提出ABCD原料拥有量（单位）含量（单位/公斤）糖524260蛋白质321440脂肪312535单价（元/公斤）157912建立其数学模型。例1甲食品厂用糖、蛋白质和脂肪三种原料生产四种复合食品A、B、C、D，复合食品中含有各种原料的数量、复合食品的单价、三种原料的拥有量分别如下表所示，问甲厂如何安排生产才能使总产值达到最大？x1x2x3x4解：设甲厂安排A、B、C、D的产量分别为x1、x2、x3、x4公斤，总产值为z元。于是，例1的数学模型为：12341234123412341234max15791252426032440..32535,,,0zxxxxxxxxxxxxstxxxxxxxx例2.假设乙食品厂欲将甲厂的原料收买过来，问乙厂至少应付出多少代价，才能使甲厂放弃生产活动，出让原料？建立该问题的数学模型。ABCD原料拥有量（单位）含量（单位/公斤）糖524260蛋白质321440脂肪312535单价（元/公斤）157912y1y2y3解：设y1,y2和y3（元/单位）分别代表乙厂收购糖、蛋白质和脂肪的单价，乙厂收购原料付出的总费用为w元，于是例2的数学模型为：123123123123123123min60403553315227..42924512,,0wyyyyyyyyystyyyyyyyyy例1和例2的数学模型比较12341234123412341234max15791252426032440..32535,,,0zxxxxxxxxxxxxstxxxxxxxx123123123123123123min60403553315227..42924512,,0wyyyyyyyyystyyyyyyyyy令1234xxXxx(15,7,9,12)C524232143125A123(,,)Yyyy604035b123412341234max1579125242603214403125350000xxzxxxxxxxxxx123123123min604035533152217412924512000ywyyyyyyyy以上两个线性规划分别称为线性规划的原问题和对偶问题。第二节原问题和对偶问题一、对称对偶规划二、非对称对偶规划三、一般对偶规划四、原问题和对偶问题的对应关系若两个线性规划分别是和则称它们是一对对称的对偶规划。一、对称的对偶规划112211112211211222221122..........................................................01,2,.....nnnnnnmmmnnmjMaxzcxcxcxaxaxaxbaxaxaxbstaxaxaxbxjnmin0wYbYACYmax0zCXAXbX112211121211121222221122..........................................................01,2,.....mmmmmmnnmnmniMinwbybybyayayaycayayaycstayayaycyim对称对偶规划还可以写成表格形式，称为对偶表MaxzMinw原问题（求极大）c1x1c2x2……cnxn右端项对偶问题求极小b1y1a11a12…a1nb1b2y2a21a22…a2nb2………………bmymam1am2…amnbm右端项c1c2…cn对偶规划中的两个问题分别称为原问题和对偶问题（互为对偶）。一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。(2)一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。(3)原问题目标函数系数是对偶问题的约束条件右端项；原问题的约束条件右端项是对偶问题的目标函数系数。(4)两个规划模型中的变量皆非负。例3：写出下列线性规划的对偶规划解：原规划的对偶规划为12max2wyyy1y2..st2515y126224yy12,0yy12323123123min1524562..521,,0zxxxxxstxxxxxx不等式约束对应非负变量二、非对称对偶规划max0zCXAXbXminwYbYAC叫做非对称的对偶规划。非对称的对偶规划可以由对称对偶规划推出。例4：写出下列线性规划问题的对偶规划。123412341234max53345810243280(1,2,3,4)jzxxxxxxxxxxxxxj解：将上述线性规划化成对称对偶规划的形式12341234123412341234max533458105810..24328243280(1,2,3,4)jzxxxxxxxxxxxxstxxxxxxxxxj写出它的对偶规划''111222121212121212,min10852543..33824,yyyyyywyyyyyystyyyyyy令得无符号限制y1'y1y2'y2''1122''1122''1122''1122''1122''1122min10108855225443..33388224,,,0wyyyyyyyyyyyystyyyyyyyyyyyy等式约束对应自由变量111max(1,2,...,)(1,...,)0(1,2,...,)(1,...,)njjjnijjijnijjijjjzcxaxbipaxbipmxjqxjqn无符号限制111min1,2,...)01,...)(1,2,...,)(1,...,)miiiiimijijimijijiwbyyipyipmaycjqaycjqn无符号限制（（(D)三、一般对偶规划(P)一般对偶规划的特点（1）原问题是“max，=,≤”形式，对偶问题是“min，=,≥”形式（2）原问题的每个等式约束，对应对偶问题一个自由变量，原问题的每个不等式约束，对应对偶问题的一个非负变量；反之亦然，即原问题中的每个非负变量对应的是对偶问题中的一个不等式约束，而原始问题中的每个自由变量对应对偶问题中的一个等式约束。（3）原问题目标函数中的系数c就是对偶问题约束条件的右端常数项，而原问题约束的右端常数项就是对偶问题目标函数中的系数。（4）如果用矩阵和向量形式写出问题(P)和(D)的约束，可以看出这两个问题的约束系数矩阵互为转置。例5.写出下面线性规划的对偶规划12341234134123412max5732252726022430..510,0zxxxxxxxxxxxxxxstxxx解先将约束条件变形为“≤”形式y1y2y3y4y5123412341341234412max5732252726022430..105,0zxxxxxxxxxxxxxxstxxxx再根据非对称形式的对应关系，直接写出对偶规划1234512313123124512345min256030105221321274527,,,,0wyyyyyyyyyyyyyyyyyyyyyy无符号限制例６．写出下列线性规划问题的对偶规划1231231232313min7434262436415..53300,0zxxxxxxxxxstxxxx111'23'23'2323'13min7434262436415..53300,0zxxxxxxxxxstxxxx解：令x1=x1，将约束化成相对规范形式y1'y2y311111'23'2'23'23'2max2415304372654..64330,0wyyyyyyyystyyyyy直接写出对偶规划1231212312312max2415304372654..64330,0wyyyyyyyystyyyyy1231231232313min7434262436415..53300,0zxxxxxxxxxstxxxx比较原规划和对偶规划11111'23'2'23'23'2max2415304372654..64330,0wyyyyyyyystyyyyy令y1=y1',并把第一个约束两端乘以-1得不符合要求的约束对应非正变量四、线性规划原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）目标函数max目标函数minn个变量00无限制n个约束条件=目标函数中变量的系数约束条件右端常数m个约束条件=m个0变量0无限制约束条件右端常数目标函数中变量的系数第三节、对偶问题的基本性质（对偶定理）max()..0zCXPAXbstX原问题与对偶问题的解之间的关系定理1(弱对偶定理)设X0和Y0分别是原问题和对偶问题的可行解，则CX0Y0b；特别当CX0=Y0b时，X0和Y0分别是原问题和对偶问题的最优解。定理2（强对偶定理）若原问题有最优解，则其对偶问题也一定有最优解，并且此时目标函数的最优值相等。min()..0wYbDYACstY证明：将原问题加上松弛变量化成标准形式：(,0)(,)..0XMaxzCSXAEbSstXS0..0,0MaxzCXSAXESbstXS用单纯形方法求解得最优解X，设其最优基为B，则XB=B-1b,检验数为1(,0)(,)0BCCBAE10BCCBA100BCB令1BYCB则Y是对偶问题的可行解又因为1BCXCBbYb由定理1知Y是对偶问题的最优解。即即max()..0zCXPAXbstXmin()..0wYbDYACstY原问题和对偶问题的解的情况如下对偶原始有最优解问题无界无可行解有最优解①问题无界③无可行解③②定理3给定一个线性规划的原问题和它的