2019年运筹学对偶理论.ppt

对偶理论DualTheory2.1线性规划的对偶模型DualModelofLP2.2对偶性质Dualproperty2.3对偶单纯形法DualSimplexMethod2.4灵敏度与参数分析SensitivityandParametricAnalysis运筹学OperationsResearch2.1线性规划的对偶模型DualModelofLP对偶理论制作与教学在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。【例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：建立总收益最大的数学模型。产品资源ABC资源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550单件产品利润10080702.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：0,5504673002384507455006897080100max3,21321321321321321xxxxxxxxxxxxxxxxxxZ现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学设y1，y2，y3及y4分别表示四种资源的单位增值价格（售价＝成本＋增值），总增值最低可用minw=500y1+450y2+300y3+550y4表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即10078594321yyyy同理，对产品B和C有70427680634843214321yyyyyyyy价格不可能小于零，即有yi≥0,i=1,…,4.从而企业的资源价格模型为2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学4,,1,07042768063481007859550300450500min4321432143214321iyyyyyyyyyyyyyyyyywi这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型,这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学上面两种形式的线性规划称为规范形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。规范形式（CanonicalForm）的定义：目标函数求极大值时，所有约束条件为≤号，变量非负；目标函数求极小值时，所有约束条件为≥号，变量非负。规范形式的线性规划的对偶问题亦是规范形式。以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。2.1线性规划的对偶模型DualmodelofLP0)1.2(maxXbAXCXZ0)2.2(minXbAXCXZ对偶理论制作与教学原始问题Maxz=CTXs.t.AX≤bX≥0对偶问题Minw=bTys.t.ATy≥Cy≥0≤maxbACTCATbT≥minmnmn对偶的定义对偶理论制作与教学规范对偶问题minz=CTXs.t.AX≥bX≥0maxw=bTys.t.ATy≤Cy≥0maxz=CTXs.t.AX≤bX≥0minw=bTys.t.ATy≥Cy≥0对偶理论制作与教学0,,0maxSNBSNBSNNBBXXXbEXNXBXXXCXCZXBXNXSbXBBNEbCCBCN00XBXNXSbXBEB－1NB－1B－1bλ0CN－CBB－1N－CBB－1－CBB－1b表2-2表2－32.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学设线性规划模型是式（2.1）的规范形式．由表2-3知，当检验数0011BCABCCBB时得到最优解，是的检验数,和,令,由得ABCCB1），＝（NBXXXBBCCBB1NBCCBN11BCYB0011BCABCCBB与0YCYA在两边有乘b,则有,又因Y≥0无上界,从而只存在最小值，得到另一个线性规划问题1BCYBZbBCYbB＝12.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学0minYCYAYbw即是原线性规划问题式（2.1）的对偶线性规划问题，反之，式（2.3）的对偶问题是式（2.1）．原问题和对偶问题是互为对偶的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形式，参数矩阵的对应关系参看表2-4．因此已知一个规范形式问题就可写出另一个对偶问题．2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学【例2.2】写出下列线性规划的对偶问题0,,15744325min321321321321xxxxxxxxxxxxZ【解】这是一个规范形式的线性规划，设Y=（y1，y2），则有)3,2,5()57,4(571114),(414),(max212121212121yyyyyyyyYAyyyyYbw，－－2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学从而对偶问题为0,03527544max2121212121yyyyyyyyyyZ对偶变量yi也可写成xi的形式。)3,2,5()57,4(571114),(414),(max212121212121yyyyyyyyYAyyyyYbw，－－2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学【例2.3】写出下列线性规划的对偶问题0,01038576534max2121212121xxxxxxxxxxZ【解】这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“≥”约束，即3,2,1,03324751086min321321321iyyyyyyyyyywi2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表2-1中的对应关系写出非规范形式的对偶问题。将上述原问题与对偶问题的对应关系列于表2-1例如，原问题是求最小值，按表2-1有下列关系：1.第i个约束是“≤”约束时，第i个对偶变量yj≤02．第i个约束是“=”约束时，第i个对偶变量yi无约束；3．当xj≤0时，第j个对偶约束为“≥”约束，当xj无约束时，第j个对偶约束为“=”约束。2.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数系数（资源限量）约束条件系数矩阵A(AT)目标函数min资源限量（目标函数系数）约束条件系数矩阵AT(A)变量n个变量第j个变量≥0第j个变量≤0第j个变量无约束约束n个约束第j个约束为≥第j个约束为≤第j个约束为=约束m个约束第i个约束≤第i个约束≥第i个约束为=变量m个变量第i个变量≥0第i个变量≤0第i个变量无约束表2-42.1线性规划的对偶模型DualmodelofLP对偶理论制作与教学当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。对偶理论制作与教学【例2.4】写出下列线性规划的对偶问题0,,0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ无约束【解】目标函数求最小值，应将表2－4的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3个变量4个约束，对照表2－1的对应关系，对偶问题为：123131231312max1810147226885wyyyyyyyyyyyy2.1线性规划的对偶模型DualmodelofLP=≥≤≤1549y1≤0，y2≥0，y3无约束对偶理论制作与教学minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40≤≥=≥unr≤≥≥=≤≥x1≥0x2≤0x3:unr原始问题变量的个数(3)等于对偶问题约束条件的个数(3)；原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示练习对偶理论制作与教学1.本节以实例引出对偶问题;2.介绍了如何写规范与非规范问题的对偶问题;作业：教材P61T1、22.1线性规划的对偶模型DualmodelofLP下一节：对偶性质2.2对偶性质Dualproperty对偶理论制作与教学0maxXbAXCXZ对偶问题是（记为DP）：0minYCYAYbw这里A是m×n矩阵X是n×1列向量，Y是1×m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。【性质1】对称性对偶问题的对偶是原问题。【证】设原问题是0,,maxXbAXCXZ设原问题是（记为LP）：2.2对偶性质Dualproperty2.2.1对偶性质对偶理论制作与教学0,,minYCYAYbw它与下列线性规划问题是等价的：0,,)max(YCYAYbw再写出它的对偶问题。0,,'minXbAXCXw它与下列线性规划问题是等价的0,,maxXbAXCXZ即是原问题。由表2-4知，它的对偶问题是2.2对偶性质Dualproperty≥对偶理论制作与教学【证】因为X°、Y°是可行解，故有AX°≤b,X°≥0及Y°A≥C，Y°≥0,将不等式AX°≤b【性质2】弱对偶性设X°、Y°分别为LP(max)与DP(min)的可行解，则bYCX00两边左乘Y°，得Y0AX°≤Y0b再将不等式Y°A≥C两边右乘X°，得CX°≤Y°AX°故CX°≤Y°AX≤Y°b这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。2.2对偶性质Dualproperty对偶理论制作与教学由这个性质可得到下面几个结论：（1）（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。注意上述结论（2）及（3）的条件不能少。一个问题无可行解时，另一个问题可能有可行解