1、第第2章章 对偶理论对偶理论(Duality Theory)一、对偶问题的提出一、对偶问题的提出二、线性规划的对偶理论二、线性规划的对偶理论三、对偶问题的经济解释三、对偶问题的经济解释-影子价格影子价格四、对偶单纯形法四、对偶单纯形法五、灵敏度分析五、灵敏度分析一、问题的提出一、问题的提出 对偶是什么：对同一事物（或问题），从不同对偶是什么：对同一事物（或问题），从不同的角度（或立场）提出对立的两种不同的表述。的角度（或立场）提出对立的两种不同的表述。在平面内，矩形的面积与其周长之间的关系，在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。有两种不同的表述方法。（1）周长一定，面积
2、最大的矩形是正方形。）周长一定，面积最大的矩形是正方形。（2）面积一定，周长最短的矩形是正方形。）面积一定，周长最短的矩形是正方形。这种表述有利于加深对事物的认识和理解。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。线性规划问题也有对偶关系。例：资源的合理利用问题例：资源的合理利用问题 常山机器厂生产常山机器厂生产、两种产品。这两种产品两种产品。这两种产品都要分别在都要分别在A、B、C三种不同设备上加工。按工三种不同设备上加工。按工艺资料规定，生产每件产品艺资料规定，生产每件产品需占用各设备分别需占用各设备分别为为2h、4h、0h，生产每件产品，生产每件产品需占用各设备分需占
3、用各设备分别为别为2h、0h、5h，已知各设备计划期内用于生产，已知各设备计划期内用于生产这两种产品的能力分别是这两种产品的能力分别是12h、16h、15h，又知每，又知每生产一件产品生产一件产品企业能获得企业能获得2元利润，每生产一件元利润，每生产一件产品产品企业能获得企业能获得3元利润，问该企业应安排生产元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大。两种产品各多少件，使总的利润收入为最大。0,0155164 1222.32max21212121xxxxxxtsxxZ 下面从另一个角度来讨论这个问题：下面从另一个角度来讨论这个问题：假设该厂的决策者打算不再自己生产甲假设该
4、厂的决策者打算不再自己生产甲,乙产乙产品，而是把各种设备的有限台时数租让给其他工品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设厂使用，这时工厂的决策者应该如何确定各种设备的租价。备的租价。建立数学模型如下：建立数学模型如下：如何安排生产，如何安排生产，使获利最多使获利最多？出出租租出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。价格应该尽量价格应该尽量低，这样，才低，这样，才能有竞争力能有竞争力出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。0352242321
5、3121yyyyyyy,321151612yyyWmin 约束条件：约束条件：把设备租出去所获得的租金不应低于把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润利用这些设备自行生产所获得的利润 目标函数：所获租金总额尽量少目标函数：所获租金总额尽量少单位产品单位产品出租出租收入不低于收入不低于2 2元元单位产品单位产品出租出租收入不低于收入不低于3 3元元设设y1，y2，y3分别为出租三种设备每小时的收费分别为出租三种设备每小时的收费该问题的数学模型为：该问题的数学模型为：0,352242.151612min3213121321yyyyyyytsyyyW模型对比：模型对比：（原原
6、问问题题）,.max0015516412223221212121xxxxxxtsxxZ（对对偶偶问问题题）03522421516123213121321yyyyyyytsyyyW,.min厂厂家家一对对偶问题一对对偶问题租租借借 每一个线性规划每一个线性规划(LP)必然有与之相伴而生的必然有与之相伴而生的另一个线性规划问题，即任何一个求另一个线性规划问题，即任何一个求 maxZ 的的LP都有一个求都有一个求 minZ 的的LP。其中的一个问题叫。其中的一个问题叫“原原问题问题”，记为，记为“P”，另一个称为，另一个称为“对偶问题对偶问题”，记为记为“D”。（1）对称型对偶问题：已知）对称型对偶
7、问题：已知 P，写出，写出 D。二、线性规划的对偶理论二、线性规划的对偶理论),2,1(0),2,1(.max :11njxmibxat sxczjinjijijnjjjP),2,1(0),2,1(.min :11miynjcyatsybwijmiiijmiiiD1 1、对偶问题的形式、对偶问题的形式“Max-”“Min-”特点：目标函数求极大值时，所有约束条件为特点：目标函数求极大值时，所有约束条件为号，号，变量非负；目标函数求极小值时，所有约束条件变量非负；目标函数求极小值时，所有约束条件为为号，变量非负。号，变量非负。例：写出线性规划问题的对偶问题例：写出线性规划问题的对偶问题 0,56
8、43 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先将原式变形解：首先将原式变形 0,5 64 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZ 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW对对偶偶问问题题：（2）非对称型对偶问题）非对称型对偶问题对偶的基本定理：对偶的基本定理：若一个问题的某约束为等式，若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反那么对应的对偶问题的相应变量无非负限制；反之，之，若一个问题的某变量无非负
9、限制，那么对应若一个问题的某变量无非负限制，那么对应的对偶问题的相应约束为等式。的对偶问题的相应约束为等式。0max11jinjjijnjjjxbxaxczP：),2,1(),2,1(min11miynjcyaybwijmiiijmiii无符号限制（无约束）D：例：例：无无约约束束解解：对对偶偶问问题题为为 ,467534 3 2 32 532min 321321321321321yyyyyyyyyyyyyyyW 0,5643732532432max321321321321321xxxxxxxxxxxxxxxZ 原问题为原问题为（3）混合型对偶问题）混合型对偶问题无约束213232131222
10、212112121112211,0maxXXbXAXAbXAXAbXAXAXCXCZP：D：无约束23123232221211313212111332211,0,0minYYYCAYAYAYCAYAYAYYbYbYbW式中Y为行向量Y=(y1,y2,ym)例例 无无约约束束4321432142143214321,0,06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZP：无无约约束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyWD：对偶变换的规则对偶变换的规则 zmax zmi
11、n例：线性规划问题如下：例：线性规划问题如下：无约束，、4321432431432143210 06 442 25 3 532minxxx,xxxxxxxxxxxxxxxZ无约束对偶问题：3213213213121321,0,01 4 5233 2 2 645maxyyyyyyyyyyyyyyyyW无约束、，4321432143243214321321321321321321,0024732543 0432 .4323min0,564 37 32532.s422minxxxxxxxxxxxxxxxtsxxxxZxxxxxxxxxxxxtxxxZ练习：练习：1.2.束无 约y0,y0,y44y4
12、y4y 37y3y3y 23yy 2y32y y 2y5y3y2.maxW 0y,y0,y46y7y5y24yy 3y2y 3y2y 5y3y2y1.maxW答案：32132132132131321321321321321321练习P78-2.1（a）（b）min Z=-CXs.t.-AX -bX 0（1 1）对称性：对偶问题的对偶是原问题。）对称性：对偶问题的对偶是原问题。min W=Y bs.t.ATY C Y 0max Z=C Xs.t.AX b X 0对偶的定义对偶的定义对偶的定义对偶的定义max W=-Ybs.t.-ATY -C Y 02 2、对偶问题的性质、对偶问题的性质（2 2）
13、弱对偶性：设）弱对偶性：设 和和 分别是问题（分别是问题（P）和（）和（D）的可行解，则必有的可行解，则必有_X_Y njmiiijjbyxcbYXC11_,即即推论推论1：若：若 和和 分别是问题（分别是问题（P）和（）和（D）的可行解，）的可行解，则则 是（是（D）的目标函数最小值的一个下界；）的目标函数最小值的一个下界；是（是（P）的目标函数最大值的一个上界。）的目标函数最大值的一个上界。_XCbY_X_Y例例 02023220322 432max41432143214321xxxxxxxxxxxxxZ试估计它们目标函数的界，并验证弱对偶性原理。试估计它们目标函数的界，并验证弱对偶性原理
14、。P：解：解：0,04233322 212 2020min212121212121yyyyyyyyyyyyWD：由观察可知：由观察可知：=（1,1,1,1），），=（1,1），分别），分别是（是（P）和（）和（D）的可行解。）的可行解。Z=10，W=40，故有，故有 ，弱对偶定理成立。由推论可知，弱对偶定理成立。由推论可知，W 的的最小值不能小于最小值不能小于10，Z 的最大值不能超过的最大值不能超过40。_XCbY_X_Y推论推论2：在一对对偶问题：在一对对偶问题（P）和（）和（D）中，若其中）中，若其中一个问题可行但目标函数一个问题可行但目标函数无界，则另一个问题不可无界，则另一个问题不可
15、行；反之不成立。这也是行；反之不成立。这也是对偶问题的无界性。对偶问题的无界性。关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可无可行解行解无可无可行解行解问题无界问题无界对偶问题对偶问题原问题原问题 0,024 2max21212121xxxxxxxxZ无界无界如：如：（P）0,012 24min21212121yyyyyyyyW无可无可行解行解（D）推论推论3：在一对对偶问题（：在一对对偶问题（P）和（）和（D）中，若一个可）中，若一个可行（如行（如P），而另一个不可行，（如），而另一个不可行，（如D），则该可行的），则该可行的问题无界。问题无界。0,1222max3213
16、2132121xxxxxxxxxxxZ :p 0,02122min:2121212121yyyyyyyyyyWD 试用对偶理论证明原问题无界。试用对偶理论证明原问题无界。解：解：=（0,0,0）是）是 P 的一个可行解，而的一个可行解，而 D 的第一的第一个约束条件不能成立（因为个约束条件不能成立（因为y1,y2 0)。因此，对偶问题。因此，对偶问题不可行，由推论可知，原问题无界。不可行，由推论可知，原问题无界。_X（3）最优性：若）最优性：若 X*和和 Y*分别是分别是（P）和）和（D）的的可行解且可行解且CX*=Y*b，则，则X*,Y*分别是问题分别是问题（P）和）和（D）的最优解。的最优
17、解。例如，上例找到例如，上例找到 X*=（0，0，4，4），），Y*=（1.2，0.2），则），则Z=28，W=28。故。故X*，Y*分分别是别是 P和和D 的最优解。的最优解。0,2023220322 :432max4321432143214321xxxxxxxxxxxxPxxxxZ0,04233322 212 :2020min212121212121yyyyyyyyyyDyyW（4）强对偶性：若一对对偶问题（）强对偶性：若一对对偶问题（P）和（和（D）都有可行解，则它们都有最优解，且目标函数的都有可行解，则它们都有最优解，且目标函数的最优值必相等。最优值必相等。推论推论4：若：若（P）和）
18、和（D）的任意一个有最优解，的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。则另一个也有最优解，且目标函数的最优值相等。（5 5）互补松弛性：在线性规划问题的最优解中，）互补松弛性：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即等式，则其对应的对偶变量一定为零，也即00*1*1*jinjjijinjjijiybxabxay，则如果，则如果将互补松弛性应用于其对偶问题地可以这样叙述：将互补
19、松弛性应用于其对偶问题地可以这样叙述：00*1*1*jjmiiijjmiiijjxcyacyax，则如果，则如果约束条件约束条件变量变量或或0 0非非0 0,5)1,2,(j 0 x3 xx3x x-2x43xx2xx xst.3x2x5xx32xMinWj5432154321543210y,y3y 3y 2y y 53y2y 3y -y 22yy st.3y4yMaxZ21212121212121其对偶问题是其对偶问题的最优其对偶问题的最优解、最优值分别为：解、最优值分别为：Y*=(4/5,3/5)Z*=5将将y1*,y2*的值代入约束条件，得的值代入约束条件，得(2)(3)(4)为为严格不
20、等式；由互补松弛性得严格不等式；由互补松弛性得x2*=x3*=x4*=0,因因y1*,y2*0得，原问题两个得，原问题两个约束条件取严格等式。故有约束条件取严格等式。故有3 x2x43x x*5*1*5*1求解得求解得x1*=1,x5*=1;故原问题的最优解为故原问题的最优解为X(1,0,0,0,1)T;W*=52=21/5317/557/55在新增加的约束条件中引入松弛变量得在新增加的约束条件中引入松弛变量得2x1+2x2+x3+x6=5加入最优表得加入最优表得2210010 x6005x6023300 x1x2x3x4x510-14/3-1/3012-1/31/312x1x223CBXBb
21、0 x6002210015x60023-8/32/31300-1-201-100-1-5/3-1/30230 x1x2x41/313/61/210-5/30-1/30113/601/32/3-1/600101/2-1/200-1/60-1/3-5/615/6 7 7、A A中的元素发生变化中的元素发生变化N中中Pj改变的情形：与增加一个变量时完全相改变的情形：与增加一个变量时完全相同，只需要认为新增加一个产品，其利润与同，只需要认为新增加一个产品，其利润与xj的利的利润相同为润相同为cj，而其消耗系数，而其消耗系数Pn+1等于变化后的等于变化后的Pj，则可以直接用处理增加一个变量的方法进行处理
22、。则可以直接用处理增加一个变量的方法进行处理。例：对例例：对例1中的线性规划，若中的线性规划，若a23由由7改变为改变为5，试讨论其最优解，试讨论其最优解的情况。的情况。-124/3-1/31001-1/31/3-1-5/300-1/312x1x223Cj-zjx3x4x1x2x530230XBCBb171011140139x4x5003023039/4Cj-zj初始单纯形表初始单纯形表最终单纯形表最终单纯形表解：虚拟一种产品解：虚拟一种产品D，其单位利润为其单位利润为c6=3，资源消耗为资源消耗为P6(1，5)T，则，则6C6-CBB-1P6-1/30由此可知，最优解不由此可知，最优解不变。
23、变。试讨论试讨论a23在什么范围在什么范围变化时最优解不变？变化时最优解不变？23000 x1x2x3x4x5000 x3x4x58161214020410001000123000CBXBb203x3x24420010-21/21/41/2-1/80100-3/2-1/80初始单纯形表初始单纯形表最终单纯形表最终单纯形表问题一：若原计划生产产品问题一：若原计划生产产品I的工艺结构有了改进，这时有关它的工艺结构有了改进，这时有关它的技术系数向量变为的技术系数向量变为P1(2,5,2)T，每件利润为，每件利润为4元。试分析对原元。试分析对原计划有什么影响？计划有什么影响？问题二：若原计划生产产品问
24、题二：若原计划生产产品I的工艺结构有了改进，这时有关它的的工艺结构有了改进，这时有关它的技术系数向量变为技术系数向量变为P1(4,5,2)T，每件利润为，每件利润为4元。试问该厂应如元。试问该厂应如何安排最优生产方案？何安排最优生产方案？8/32/14/5PB118/3 PBCc11B11解：把改进工艺的产品解：把改进工艺的产品I看作产品看作产品I，设，设x1为其产量，计算在最为其产量，计算在最终表中终表中x1对应的列向量对应的列向量B-1P1和检验数和检验数1。1005/41/23/803/881/12/74/5PB118/21 PBCc11B115/4-7/211/8-21/8Cj-zjCj-zj
