第一节 线性规划的对偶问题

第三章对偶理论与灵敏度分析3.1线性规划的对偶问题3.2对偶单纯形法3.3灵敏度分析*每一个求极大值线性规划问题都有一个与之伴随的求极小值的线性规划问题，这个伴随的线性规划问题称之为它的对偶问题。3.1线性规划的对偶问题引例某工厂用甲乙两种资源生产A、B、C、D四种产品，现有资源数、单位产品所需资源数以及单位产品可获利润如下表所示.问如何组织生产能使利润最大？产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)ABCD110231832541382012153.1.1对偶问题的提出产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)ABCD11023183254138201215显然，该问题的线性规划模型为：1234maxS=8201215xxxx12341102318000xxxx1234325413000xxxx12340,0,0,0xxxx现在从另一个角度考虑问题。假设该厂不生产A、B、C、D四种产品了，而是将甲、乙两种资源出租给其它单位，其原则是：使别的单位愿意租，又使本单位获利不低于原利润。问如何给甲、乙两种资源定价最合理？产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)ABCD11023183254138201215解设甲、乙两种资源的价格为12,.yy设总收入为W，则12W1800013000yy约束条件为产品(公斤/件)单位利润(元)资源甲乙现有资源(吨)ABCD110231832541382012151238yy1210220yy122y512y123415yy120yy、min1234S=8201215xxxx1234maxS=8201215xxxx12341102318000xxxx1234325413000xxxx12340,0,0,0xxxx比较一下这两个线性规划问题：原问题对偶问题12min1800013000Wyy12y38y1210y220y122y512y123415yy120yy、线性规划问题和它的对偶问题之间的关系：（2）原始问题约束不等式的个数等于对偶问题变量的个数；（3）原始问题的收益系数，成为对偶问题中约束不等式右端的常数项；（5）约束不等式，一个全是“≤”，另一个全是“≥”；（4）两个约束方程组的系数矩阵互为转置矩阵．（6）原始问题和对偶问题是相对的，可以互相转化；（1）目标函数，原始问题是求最大值，对偶问题是求最小值；对偶问题的矩阵表示：原问题对偶问题maxSCXAXbX12(,,,),nCccc12,nxxXx12,mbbbb12(,,,)nYyyyminTTTWbYAYCY12nyyYy对偶问题的矩阵表示：原问题对偶问题maxSCXAXbXminWYbYACY12(,,,),nCccc12,nxxXx12,mbbbb12(,,,)nYyyyminTTTWbYAYCY()TTTABBA对偶问题的矩阵表示：原问题对偶问题maxSCXAXbXminWYbYACY例1写出线性规划问题的对偶问题121212212max5831853,0Sxxxxxxxxx123min1853Wyyy1235yy123,,0yyy1238yyy对称形式：maxSCXAXbXminWYbYACY练习写出下列问题的对偶问题（77页）121212121(1)max5+2-32350Sxxxxxxxx、、12min35Wyy1225yy1232yy120yy、12123123123(2)min6+363+23+4+50Sxxxxxxxxxxx、、12max25Wyy12636yy12343yy120yy、120yy非对称形式例3.3写出下面线性规划问题的对偶问题12312312312312max321210214,0Sxxxxxxxxxxxxxx解先化为对称形式12312312312312max321210214,0Sxxxxxxxxxxxxxx123max32Sxxx12312xxx12310xxx123214xxx123123123121212xxxxxxxxx12312xxx解先化为对称形式12312312312312max321210214,0Sxxxxxxxxxxxxxx123max32Sxxx12312xxx12310xxx123214xxx12312xxx345xxx1245,,,0xxxx解先化为对称形式12312312312312max321210214,0Sxxxxxxxxxxxxxx123max32Sxxx12312xxx12310xxx123214xxx12312xxx1245,,,0xxxx124512xxxx124512xxxx124510xxxx1245214xxxx1245max32Sxxxx345xxx解先化为对称形式12312312312312max321210214,0Sxxxxxxxxxxxxxx1245,,,0xxxx124512xxxx124512xxxx124510xxxx1245214xxxx1245max32Sxxxx写出其对偶问题,1234yyyy、、、设对偶问题的变量为1234min12121014Wyyyy123423yyyy12342yyyy12341yyyy12341yyyy12340yyyy、、、1245,,,0xxxx124512xxxx124512xxxx124510xxxx1245214xxxx1245max32Sxxxx1234min12121014Wyyyy123423yyyy12342yyyy12341yyyy12341yyyy12340yyyy、、、这样的对偶问题与原问题无法对照,12312312312312max321210214,0Sxxxxxxxxxxxxxx？1234min12121014Wyyyy123423yyyy12342yyyy12341yyyy12341yyyy12340yyyy、、、1122334--zyyzyzy，，123min121014Wzzz12323zzz1232zzz1231zzz230,0zz123min121014Wzzz12323zzz1232zzz1231zzz230,0zz12312312312312max321210214,0Sxxxxxxxxxxxxxx原问题对偶问题对偶关系对应表原始问题（对偶问题）对偶问题（原始问题）目标函数系数矩阵目标函数系数为常数列向量为约束条件决策变量maxACbm个≥型(第i个)＝型(第i个)≤型(第i个)n个0jx0jx无限制目标函数系数矩阵目标函数系数为minWTA常数列向量为TCTb约束条件对偶变量≥型(第j个)＝型(第j个)≤型(第j个)m个0iy无限制0iyn个练习写出下列问题的对偶问题（77页）1212122(3)max5+6+2=5+530Sxxxxxxx12121212(4)max+2=53=6Sxxxxxxxx、12min53Wyy12=5yy12256yy12min56Wyy122+3=1yy12=1yy无符号限制12yy、无符号限制20y本小节所用课时数：两节第一节课讲完定理3.4第二节课专门讲定理3.5最后两个定理的证明可以不讲不强调抽象晦涩的证明过程多关注对定理的理解和应用3.1.3对偶问题的基本理论3.1.3对偶问题的基本理论定理3.1若和分别是原始问题和对偶问题的任一可行解，则必有．00XY00CXYb证明：00AXbYAC000YAXYb000YAXCX00CXYb假设线性规划的原问题和对偶问题分别为minmaxSCXWYbAXbYACXOYO和定理3.1若和分别是原始问题和对偶问题的任一可行解，则必有．推论1最小值原始问题的任意一个可行解对应的目标函数值是其对偶问题最优值的一个上界．推论2最大值原始问题的任意一个可行解是其对偶问题最优值的一个下界．推论3若原始问题可行，而目标函数无界，则其对偶问题无可行解．00XY00CXYb0,XXXX１２３，，，0,YYYY１２３，，，0CXCXCXCX３２１0123YAYAYAYA例(补充)已知线性规划问题：123max472wxxx123,,0xxx123210xxx试用对偶理论证明该问题的最优值不超过25．12323310xxx12min1010zyy12,0yy1224yy12237yy1232yy解写出其对偶问题显然，是对偶问题的一个可行解，1212,2yy它对应的目标函数值为25,z根据对偶理论，最小值问题的任一可行解都是其对偶问题最优值的一个上界，max25w123max472wxxx123,,0xxx123210xxx12323310xxx定理3.2若和分别是原始问题和对偶问题的可行解，且有，则和分别是原始问题和对偶问题的最优解．XY=CXYbXY证明：设是原始问题的任一可行解CXYbX由定理2.1可得=CXYb又已知CXCX由的任意性可知，是原始问题的最优解．同理可证是对偶问题的最优解．XYX定理3.3(对偶定理)在互为对偶的线性规划问题中,如果其中一个有最优解,则另一个也有最优解，且它们的最优值相等．证明：假设原始问题为如下的标准形式minSCXAXbXO则其对偶问题为maxWYbYACY无符号限制最优值为即是对偶问题的一个可行解,设是原始问题的最优解，它对应的最优基为B，则相应的基变量为检验数为令则XBXminSCX10BCBAC1BYCBYACY而1BYbCBb1BCBbCX由定理3.２可知，是对偶问题的最优解．YminSCXAXbXOmaxWYbYACY无符号限制minmaxsw1BCBbXY1,Bb推论1在互为对偶的线性规划问题中，若原始问题的最优基为B，则对偶问题的最优解为．推论2设为原始问题的一个可行解，相应的可行基为B，而为其对偶问题的可行解，则和分别