运筹学胡运权第五版课件(第二章)

第二章线性规划的对偶理论DualTheory§2.1对偶问题的提出例常山机器厂生产I、II两种产品。这两种产品都分别要在ABC三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如表：如何安排生产才能使总的利润最大？消耗设备工时III设备工时限量设备A设备B设备C240205121615利润（元）23解：maxz=2x1+3x22x1+2x2124x1165x215x10，x20s.t.LP1假设另有四海机器厂想租借常山机器厂的全部可用资源进行生产。问：常山机器厂应该如何给这些资源定出一个合理的租金，既使四海机器厂愿意租借，又使本厂能得到自己组织生产这些产品时所能获得的最大收益。解：设A、B、C设备每小时出租的价格分别为y1、y2、y3元，则新的线性规划数学模型为：1231213123min121615242s..253,,0wyyyyytyyyyyLP2对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP1）必然有与之相伴而生的另一个线性规划问题（LP2），即任何一个求maxz的LP1都有一个求minw的LP2。将LP1称为“原问题”，记为P；将LP2称为“对偶问题”，记为D。12121212max232212416s.t.515,0zxxxxxxxx1231213123min121615242s.t.253,,0wyyyyyyyyyy原问题（P）：对偶问题（D）：1、基本概念原问题P对偶问题D原变量x1,x2对偶变量y1,y2,y3原目标z对偶目标w原约束对偶约束1213123242253,,0yyyyyyy1212122212416515,0xxxxxx变量约束2、一般形式原问题Pmaxz=c1x1+c2x2+···+cnxns.t.a11x1+a12x2+···+a1nxnb1a21x1+a22x2+···+a2nxnb2···am1x1+am2x2+···+amnxnbmxj0，（j=1,2,···,n）对偶问题Dminw=b1y1+b2y2+···+bmyms.t.a11y1+a21y2+···+am1ymc1a12y1+a22y2+···+am2ymc2···a1ny1+a2ny2+···+amnymcnyi0，(i=1,2,···,m)0s.t.max3XbAXCXzP、矩阵形式：0s.t.minYCYAYbwDTTT12(,,,)nCccc12nxxXx其中111212122212nnmmmnaaaaaaAaaa12mbbbb12myyYy,,,,TTTbACbAC为的转置例：写出下列LP问题的对偶问题0,12416482..65max21212121xxxxxxtsxxz0,,64254..12168min3213121321yyyyyyytsyyyw解：对偶问题为：§2.2原问题与对偶问题0s.t.maxXbAXCXzP0s.t.minYCYAYbwDTTT（max的基本形式）（min的基本形式）1、基本形式的联系与区别（1）原目标求极大，对偶目标求极小；（2）原约束个数=对偶变量个数原变量个数=对偶约束个数原约束决定对偶变量原变量决定对偶约束；（3）原约束≤方向，对偶约束≥方向；（4）原目标的系数对应对偶约束的右端常数原约束的右端常数对应对偶目标的系数；（5）原系数矩阵与对偶系数矩阵互为转置；（6）原变量与对偶变量都是非负取值。例将下列问题作为原问题，写出其对偶问题。1231213123min121615242s.t.253,,0wyyyyyyyyyy1231213123max121615242s.t.253,,0wyyyyyyyyyy12121212min232212416s.t.515,0zxxxxxxxx解：先改写为原问题的基本形式：再对偶化：12121212max232212416s.t.515,0zxxxxxxxx最后简化得到已知问题的对偶问题：2、基本形式的表格比较3、互为对偶关系若LP2是LP1的对偶问题，则LP1是LP2的对偶问题。minZ’=-CXs.t.-AX≥-bX≥0minW=bTYs.t.ATY≥CTY≥0maxZ=CXs.t.AX≤bX≥0对偶的定义对偶的定义maxW’=-bTYs.t.-ATY≤-CTY≥0改写改写例写出下列问题的对偶问题。12312312323123min7434262436415s.t.53300,0zxxxxxxxxxxxxxx无约束，解：第一步改写为min的基本形式112221223122312232232231223min7434262436415s.t.533053300xxxxxzxxxxxxxxxxxxxxxxxxxxxx令，（）（）（）（）（），，，第二步对偶化1234121234123412341234max2415303043726554s.t.2655464333,,,0wyyyyyyyyyyyyyyyyyyyyyy第三步简化为已知问题的对偶问题：1133412312123123123max2415304372654s.t.64330,0,yyyyywyyyyyyyyyyyyyy令，无约束比较原问题和对偶问题：12312312323123min7434262436415s.t.53300,0zxxxxxxxxxxxxxx无约束，12312123123123max2415304372654s.t.64330,0,wyyyyyyyyyyyyyy无约束基本形式非基本形式4、原问题与对偶问题的互化原问题（或对偶问题）对偶问题（或原问题）目标函数max（基本）目标函数min（基本）约束条件m个m个变量≤（基本）≥0（基本）≥≤0=无约束变量n个n个约束条件≥0（基本）≥（基本）≤0≤无约束=约束条件的右端项目标函数的系数目标函数的系数约束条件的右端项例直接写出下列线性规划问题的对偶问题。无约束，432143243143214321006442253s.t.532zminx,xx,xxxxxxxxxxxxxxx无约束对偶问题：3213213213121321,0,014523322s.t.645maxyyyyyyyyyyyyyyyyw练习写出下列问题的对偶问题。无约束、，4321432143243214321,00247325433432s.t.4323minxxxxxxxxxxxxxxxxxxxZ无约束32132132132131321y0,y0,y44y4y4y37y3y3y23yy2y32yys.t.253maxyyyW解：对偶问题为：§2.3对偶问题的基本性质0s.t.maxXbAXCXzP0s.t.minYCYAYbwDTTT在本节中设原问题和对偶问题如下：1、弱对偶性（弱对偶原理）：设和分别是问题P和D的可行解，则必有__X__YYbXCT__TTTTTTTTAXbYAXYbAYCCYACXYAXYbbY证明：2、最优性：若X*和Y*分别是P和D的可行解且CX*=bTY*，则X*，Y*分别是问题P和D的最优解。证明：PD**********PDTTTTTTTTXYCXbYXCXCXbYbYCXCXbYbYCXbYCXCXbYbYXY另设和分别是和的最优解，则是最优解，同理，即又即和也分别是和的最优解。3、无界性若原问题有无界解，则对偶问题无可行解。若对偶问题有无界解，则原问题无可行解。证明：注：逆定理不成立。即“如果原问题无可行解，那么对偶问题有无界解”不成立。此时，对偶问题可能有无界解，也可能无可行解。PDTTTTXYCXbYCXYCXbYbYXCXbY由弱对偶性：当和分别是和的可行解时，若，则不存在使得；若，则不存在使得。4、强对偶性（对偶定理）若原问题有最优解，则对偶问题一定有最优解，且zmax=wmin.证：设X*是原问题的最优解，则所有检验数都非正。即=C-CBB-1A0∴CBB-1AC令CBB-1=Y*T，有Y*TAC,转置得ATY*CT-----------------------①又因为S′=-CBB-1=-Y*T0，所以Y*=-（S′）T0------②由①②知Y*是对偶问题的可行解，而CX*=CBb′，其满足:CX*=CB(B-1b)=CBB-1b=Y*Tb=bTY*由最优性(性质2)，∴Y*是对偶问题的最优解。注意：若原问题有最优解，则在最终单纯形表中，原问题的最优解是第三列，而对偶问题的最优解是松弛变量检验数的相反数。对偶问题的最优解。请直接写出该问题及为松弛变量，其中问题的最优单纯形表，下面是某例,,543xxxLPT*)0,81,23(Y其对偶问题的最优解为1001/4000-21/21011/2-1/804422X10X53X2x1x2x3x4x5CBXBb23000Cj00-3/2-1/80T*)400,2,4(X，，则该问题的最优解为5、互补松弛性j1j1**PD*0***0nniijjiijjiiXYyaxbaxby和分别是和的最优解，若＞，则；若＜，则=。证明：1111111111111************0*0***0*0nmnmjjijjiiijijinmjjiijinmnmmnjjijjiiiijjiijijiijniijjiijjiijicxaxybycxbycxaxybyaxbyyaxbiaxbyy由弱对偶性，又由最优性有，移项得（）又，对任意有（）因此若＞，则j1j1***0nnijjiijjiiaxbaxby；若＜，则=。松条件---变量＞0，约束为等式；紧条件---变量=0，约束不等式。将该性质应用于其对偶问题时，则有：11*0*;**0;mjijijimijijjixaycaycx0,,,2023220322s.t.432max4321432143214321xxxxxxxxxxxxxxxxz0,4233322212s.t.2020min212121212121yyyyyyyyyyyyw)(P)(D例考虑下面问题的最优解。用互补松弛性求出的最优解为已知)()51,56()(*PYDT解:0,0*2*1yy由互补松弛性知)1(20322*4*3**1xxxx)2(20232*4*3*2*1xxxx**1221.20.41.61yy另一方面**1222.40.22.62yy代入(