1、第第1页页第第2页页第第3页页掌握用矩阵描述单纯形法计算过程的作用：掌握用矩阵描述单纯形法计算过程的作用：有助于加深对单纯形法的理解。有助于加深对单纯形法的理解。有助于下面对偶理论和灵敏度分析的学习。有助于下面对偶理论和灵敏度分析的学习。第第4页页0 .max BNBNNBBXbNXBXtsXCXCz从而线性规划问题的标准型从而线性规划问题的标准型0 max XbAXCXz第第5页页bNXBXNB 当前单纯形表中当前单纯形表中的右端常数的右端常数当前单纯形表中的非基当前单纯形表中的非基变量系数列向量变量系数列向量NBNXbBX NBNXBbBX11 当前单纯形表中的基变量系数列向量总是单位向量
2、当前单纯形表中的基变量系数列向量总是单位向量第第6页页max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts例：例：解：解：0,12 4 16 48 2 .543215241321xxxxxxxxxxxxtsmax z=2x1+3x2第第7页页 410004201B 08/12/112/1204/101B已知最终单纯形表中的基变量为已知最终单纯形表中的基变量为 xB=(x1,x5,x2)，则可以则可以直接直接计算出最终单纯形表中的系数列向量：计算出最终单纯形表中的系数列向量：当前单纯形表中的非基变量系数列向量当前单纯形表中的非基变量系数列向量 8/12/12/1
3、24/1000100108/12/112/1204/101NB第第8页页 410004201B 08/12/112/1204/101B已知当前单纯形表中的基变量为已知当前单纯形表中的基变量为 xB=(x1,x5,x2)，则可以则可以直接直接计算出当前单纯形表中的基变量的值：计算出当前单纯形表中的基变量的值：2441216808/12/112/1204/101bB当前单纯形表中的基变量的值（即右端常数）当前单纯形表中的基变量的值（即右端常数）第第9页页cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80最终单纯形表的形式为：最
4、终单纯形表的形式为：第第10页页NNBBXCXCz 将将 XB 表达式带入目标函数：表达式带入目标函数：NBNXBbBX11 NNNBXCNXBbBC )(11NBNBXNBCCbBC)(11 最优目标函数值最优目标函数值第第11页页NBCCBN1 非基变量检验数非基变量检验数BBCCBB1 基变量检验数基变量检验数)0(ABCCB1 所有检验数：所有检验数：第第12页页 410004201B 08/12/112/1204/101B已知最终单纯形表中的基变量为已知最终单纯形表中的基变量为 xB=(x1,x5,x2)，则可以则可以直接直接计算出最终单纯形表中的检验数：计算出最终单纯形表中的检验数
5、：)08/12/300(10040010040012108/12/112/1204/10)302()00032(1 ABCCB第第13页页cj23000iCBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/8014最终最终单纯形表：单纯形表：bBCzB1 141216808/12/112/1204/10)302(第第14页页总总 结结从从任一单纯形表（不一定是初始单纯形表）任一单纯形表（不一定是初始单纯形表）出发，出发，只要能够知道当前单纯形表中的哪几个变量是基变只要能够知道当前单纯形表中的哪几个变量是基变量
6、，就可以直接计算出量，就可以直接计算出当前单纯形表当前单纯形表。ABA1 bBb1 ABCCB1 （1）约束条件系数矩阵：）约束条件系数矩阵：（2）约束条件右端常数：）约束条件右端常数：（3）检验数：）检验数：第第15页页只要能够知道当前单纯形表中的哪几个变量是基变只要能够知道当前单纯形表中的哪几个变量是基变量，就可以由初始单纯形表直接计算出当前单纯形量，就可以由初始单纯形表直接计算出当前单纯形表。表。要确定当前单纯形表中哪几个变量是基变量，必须要确定当前单纯形表中哪几个变量是基变量，必须要解决的问题：要解决的问题：（1）换入变量的确定。）换入变量的确定。（2）换出变量的确定。）换出变量的确定
7、。第第16页页（1）换入变量的确定）换入变量的确定ABCCB1 计算所有变量检验数：计算所有变量检验数：lklikikiiPBbBPBPBbB)()()0)()()(min11111 （2）换出变量的确定）换出变量的确定换入变量：换入变量：x k换出变量：换出变量：x l第第17页页基变量基变量XB非基变量非基变量 XN等式右边等式右边系数矩阵系数矩阵检验数检验数0IBB 1NB1 bB1 NBCCBN1 第第18页页由此可以看出，由此可以看出，B-1 的计算是整个问题的关键的计算是整个问题的关键第第19页页max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts
8、例：例：第第20页页cj23000iCBXBbx1x2x3x4x50 x381210040 x41640010-0 x5120 4 0013c j z j23000解解：（：（1）从初始单纯形表出发。）从初始单纯形表出发。0 x32 1 010-1/220 x4164001043x2301001/4-c j z j2000-3/41211400010201 B)(243xxx第第21页页cj23000iCBXBbx1x2x3x4x52x121010-1/2-0 x4800-41 2 43x2301001/412c j z j00-201/43411400014201 B11410004201
9、B2x141001/400 x5400-21/213x22011/2-1/80c j z j00-3/2-1/80)(241xxx)(251xxx第第22页页cj23000iCBXBbx1x2x3x4x50 x321010-1/220 x4164001043x2301001/4-c j z j2000-3/42x141001/40-0 x5400-21/213x22011/2-1/80c j z j00-3/2-1/8024（2）从任一单纯形表（非初始单纯形表）出发。）从任一单纯形表（非初始单纯形表）出发。1114/1000402/11 B 251xxx第第23页页1114/1000402/1
10、1 B 18/12/102/1204/10第第24页页 0 ,1 232 411 2 3min32131321321321xxxxxxxxxxxxxxz例：例：第第25页页 0,1 23 2 411 2 003 max76543217316532143217654321xxxxxxxxxxxxxxxxxxxMxMxxxxxxz解：加入解：加入 松弛变量：松弛变量：x4 剩余变量：剩余变量：x5 人工变量：人工变量：x6 和和 x7 得到：得到：第第26页页cj3-1-100-M-MiCBXBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx7
11、1-20 1 00011c j z j3-6MM-13M-10-M000 x4103-20100-1-Mx610 1 00-11-21-1x31-2010001-c j z j1M-100-M01-3M第第27页页cj3-1-100-M-MiCBXBbx1x2x3x4x5x6x70 x412 3 001-22-54-1x210100-11-2-1x31-2010001-c j z j1000-11-M-1-M3x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3c j z j000-1/3-1/31/3-M2/3-M第第28页页由此可
12、以看出，当前单纯形表中基变量所对应的由此可以看出，当前单纯形表中基变量所对应的B-1 等于在出发单纯形表中，系数列向量为单位向量的变等于在出发单纯形表中，系数列向量为单位向量的变量在当前单纯形表中所对应的列向量组成的矩阵。量在当前单纯形表中所对应的列向量组成的矩阵。第第29页页例例 已知某最大化线性规划问题用单纯形法求解时的初已知某最大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括始单纯形表及最终单纯形表如下表所示，求表中各括号内未知数的值。号内未知数的值。第第30页页cj322000CBXBbx1x2x3x4x5x60 x4(b)1111000 x515(a
13、)120100 x6202(c)1001c j z j322000CBXBbx1x2x3x4x5x60 x45/400(d)(l)-1/4-1/43x125/410(e)03/4(i)2x25/201(f)0(h)1/2c j z j0(k)(g)0-5/4(j)第第31页页解：因为基变量所对应的系数列向量为单位向量解：因为基变量所对应的系数列向量为单位向量，故，故 l=1。显然，。显然，k=0。下面，关键是求下面，关键是求 B-1。2/104/304/14/111hiB第第32页页 2/54/254/520152/104/304/14/11bhi2/1 4/1 10 hib，2/54/254
14、/51015204/454/35hib第第33页页 2/12/104/14/304/14/111B第第34页页 010212/12/104/14/304/14/11a2 a 0102/112/14/34/12/1aaa第第35页页 100112/12/104/14/304/14/11c3 c 1002/12/14/14/34/14/3ccc第第36页页 fed1212/12/104/14/304/14/112/1 4/5 4/1 fed，fed2/14/54/1第第37页页最后可计算出：最后可计算出：g=-3/4。第第38页页例例 已知某线性规划问题，用单纯形法计算时得到中间已知某线性规划问题
15、，用单纯形法计算时得到中间某两步的计算表如下表，试将表中空白处数字填上。某两步的计算表如下表，试将表中空白处数字填上。第第39页页cj354000CBXBbx1x2x3x4x5x65x28/32/3101/3000 x514/3-4/305-2/3100 x620/35/304-2/301c j z j-1/304-5/300CBXBbx1x2x3x4x5x65x215/418/41-10/414x3-6/415/414/413x1-2/41-12/4114/41c j z j第第40页页解：解：41/1541/12041/441/5041/1041/811BCBXBbx1x2x3x4x5x6
16、5x215/418/41-10/414x3-6/415/414/413x1-2/41-12/4114/41c j z j10013/5403/4503/201 8/4150/4144/41010001第第41页页（1）确定初始基变量，并计算初始可行基的逆矩阵）确定初始基变量，并计算初始可行基的逆矩阵B-1；（2）检验各非基变量的检验数：）检验各非基变量的检验数：如果如果j 0，j=m+1,.,n，则当前解就是最优解，则当前解就是最优解，最有解为，最有解为 B-1b，停止计算：，停止计算：ABCCB1 第第42页页否则否则，转下步；，转下步；如果如果j 0，j=m+1,.,n 中，若某个非基变量
17、中，若某个非基变量 xj 的系数列向量的系数列向量 Pk 0，则此问题无界，停止计算，否，则此问题无界，停止计算，否则转下步；则转下步；（4）根据）根据max(j 0)=k，来确定，来确定 x k 为换入变量为换入变量（最大检验数有多个时，可任选一个）；（最大检验数有多个时，可任选一个）；第第44页页（5）根据下式来确定）根据下式来确定 x l 为换出变量：为换出变量：最小比值有多个时（下一步迭代会出现非基变量最小比值有多个时（下一步迭代会出现非基变量=0的情况，即退化现象），可任选一个（通常选择下的情况，即退化现象），可任选一个（通常选择下标较小的那个基变量标较小的那个基变量 x l 换出）
18、。换出）。lklikikiiPBbBPBPBbB)()()0)()()(min11111 （6）从而确定新的基变量，计算新的可行基的逆矩）从而确定新的基变量，计算新的可行基的逆矩阵阵 B-1。（7）重复（重复（2）（6），直到找到问题的最优解。），直到找到问题的最优解。第第45页页max z=2x1+3x2 0,12 4 16 482 .212121xxxxxxts例：例：第第46页页解：解：max z=2x1+3x2 0,12 4 16 48 2 .543215241321xxxxxxxxxxxxts（1）XB=(x3,x4,x5)100010001B 1000100011B第第47页页 3
19、412,28min40212168min40210001000112168100010001min 3240042110001000100032 2x5x第第48页页 2,416,12min0413162min0414/1000102/101121684/1000102/101min 4/321004014/1000102/10130002 1x3x（2）XB=(x3,x4,x2)400010201B 4/1000102/1011B第第49页页 44/13,28,min4/122/1382min1004/1002142/101121684/1002142/101min 4/121000014/
20、1002142/10130200 5x4x（3）XB=(x1,x4,x2)400014201B 4/1002142/1011B第第50页页 8/12/300100108/12/112/1204/1030200 （4）XB=(x1,x5,x2)410004201B 08/12/112/1204/101B 2441216808/12/112/1204/101251*bBxxxX 141216808/12/112/1204/103021*bBCzB第第51页页对偶是指对同一问题，从不同角度观察，有两种对对偶是指对同一问题，从不同角度观察，有两种对立的表述。立的表述。周长一定，面积最大的矩形是正方形。
21、周长一定，面积最大的矩形是正方形。面积一定，周长最小的矩形是正方形。面积一定，周长最小的矩形是正方形。第第52页页cyxts )(2 .xymax xcx21max221 maxxcx 0221)21(2 xcdxxcxdcx41 cy41 正方形正方形非线性规划非线性规划第第53页页sxyts .yx maxxsx max01)(2 xsdxxsxdsx sy 正方形正方形非线性规划非线性规划xsx max第第54页页问题问题1 某工厂有某工厂有 I、II 两种产品，已知生产单位产品两种产品，已知生产单位产品所需的设备台时数、原材料所需的设备台时数、原材料 A 的消耗量、原材料的消耗量、原材
22、料B的的消耗量，具体数据如表所示。消耗量，具体数据如表所示。设设 备备原材料原材料A原材料原材料BI140II2048台时台时16kg12kg每生产一件产品每生产一件产品 I 可获利可获利 2 元，每生产一件产品元，每生产一件产品 II 可可获得获得3元，问如果自己生产，产品元，问如果自己生产，产品 I 和和 II 各应生产多各应生产多少获利最大？少获利最大？第第55页页又知道，每生产一件产品又知道，每生产一件产品 I 可获利可获利 2 元，每生产一件元，每生产一件产品产品 II 可获得可获得 3 元，问应如何安排生产计划才能够使元，问应如何安排生产计划才能够使得工厂获利最多？得工厂获利最多？
23、0,12416482.32max21212121xxxxxxtsxxz第第56页页问题问题2 某工厂有某工厂有 I、II 两种产品，已知生产单位产品两种产品，已知生产单位产品所需的设备台时数、原材料所需的设备台时数、原材料 A 的消耗量、原材料的消耗量、原材料B的的消耗量，具体数据如表所示。消耗量，具体数据如表所示。设设 备备原材料原材料A原材料原材料BI140II2048台时台时16kg12kg每生产一件产品每生产一件产品 I 可获利可获利 2 元，每生产一件产品元，每生产一件产品 II 可可获得获得 3 元，问如不自己生产，而是将设备、原材料元，问如不自己生产，而是将设备、原材料 A、原材
24、料、原材料 B 等三种资源卖出，定价多少才能将资源卖等三种资源卖出，定价多少才能将资源卖出？出？第第57页页设设备台时数售价：设设备台时数售价：y1 资源资源 A 售价：售价：y2 资源资源 B 售价：售价：y3生产产品生产产品 I 所需的各种资源的售价总和，不应低所需的各种资源的售价总和，不应低于自己生产产品于自己生产产品 I 所带来的利润：所带来的利润：生产产品生产产品 II 所需的各种资源的售价总和，不应所需的各种资源的售价总和，不应低于自己生产产品低于自己生产产品 II 所带来的利润：所带来的利润：2421 yy34221 yy第第58页页 0,34224.12168 min32131
25、21321yyyyyyytsyyy 从工厂角度来看：从工厂角度来看：越大越好；越大越好；从接受者角度来看：从接受者角度来看：越小越好。越小越好。所以，工厂只能在满足大于等于自己生产产品所带来所以，工厂只能在满足大于等于自己生产产品所带来的利润的条件下，提出一个尽可能低的出售价格，才的利润的条件下，提出一个尽可能低的出售价格，才能实现其意愿，因此问题的目标函数是极小化。能实现其意愿，因此问题的目标函数是极小化。32112168 yyy 卖出的总收入为：卖出的总收入为：第第59页页 0,34224.12168 min3213121321yyyyyyytsyyy 0,12416482.32max21
26、212121xxxxxxtsxxz第第60页页项目项目原问题原问题对偶问题对偶问题A约束条件系数矩阵约束条件系数矩阵约束条件系数矩阵的转置矩阵约束条件系数矩阵的转置矩阵b约束条件右端常数约束条件右端常数目标函数系数目标函数系数C目标函数系数目标函数系数约束条件右端常数约束条件右端常数目标函数目标函数极大化极大化极小化极小化约束条件约束条件决策变量决策变量非非负要求负要求非非负要求负要求约束约束-变量变量约束条件数约束条件数决策变量数决策变量数变量变量-约束约束决策变量数决策变量数约束条件数约束条件数第第61页页满足下列条件的线性规划问题称为具有对称形式：满足下列条件的线性规划问题称为具有对称形
27、式：（1 1）决策变量满足非负要求。）决策变量满足非负要求。（2 2）当目标函数为极大化时，约束条件为）当目标函数为极大化时，约束条件为。（3 3）当目标函数为极小化时，约束条件为）当目标函数为极小化时，约束条件为。第第62页页 ),.,1(0.max221122222121112121112211njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn原问题原问题1.对称形式下原问题对称形式下原问题-对偶问题的完整表述式：对偶问题的完整表述式：第第63页页 ),.,1(0.min221122222112112211112211miycyayayacyaya
28、yacyayayatsybybybinmmmnnmmmmmm 对偶问题对偶问题第第64页页 njxmibxatsxczjijnjijnjjj,.,1,0,.,1,.max11原问题原问题2.对称形式下原问题对称形式下原问题-对偶问题的简化表述式：对偶问题的简化表述式：第第65页页对偶问题对偶问题 miynjcyatsybijjmiijmiii,.,1,0,.,1,.min11 第第66页页 0 .maxXbAXtsCXz 0 .minYCYAtsbYTTTT 对偶问题对偶问题原问题原问题3.对称形式下原问题对称形式下原问题-对偶问题的矩阵表述式：对偶问题的矩阵表述式：第第67页页项目项目原问题
29、原问题对偶问题对偶问题A约束条件系数矩阵约束条件系数矩阵约束条件系数矩阵的转置矩阵约束条件系数矩阵的转置矩阵b约束条件右端常数约束条件右端常数目标函数系数目标函数系数C目标函数系数目标函数系数约束条件右端常数约束条件右端常数目标函数目标函数极大化极大化极小化极小化约束约束-变量变量约束条件数约束条件数决策变量数决策变量数变量变量-约束约束决策变量数决策变量数约束条件数约束条件数约束条件约束条件决策变量决策变量非非负要求负要求非非负要求负要求第第68页页x1x2xn原关系原关系min y1a11a12a1nb1y2a21a21a2nb2ymam1am2amnbm对偶关系对偶关系max z=min
30、max zc1c2cn第第69页页（1）max min。（2）对偶问题的决策变量数）对偶问题的决策变量数=原问题的约束条件数原问题的约束条件数。（3）对偶问题的目标函数系数）对偶问题的目标函数系数=原问题的约束条件原问题的约束条件右端常数右端常数。（4）对偶问题的约束条件系数矩阵）对偶问题的约束条件系数矩阵=原问题约束条原问题约束条件系数矩阵的转置矩阵。件系数矩阵的转置矩阵。第第70页页（5）对偶问题的约束条件右端常数）对偶问题的约束条件右端常数=原问题的目标原问题的目标函数系数。函数系数。（6）约束条件符号：极大化问题，为）约束条件符号：极大化问题，为；极小化问；极小化问题，为题，为；（7）
31、决策变量符号均为）决策变量符号均为 0。第第71页页非对称形式线性规划问题的处理方式：非对称形式线性规划问题的处理方式：如果线性规划的原问题不是对称形式，需要将其转如果线性规划的原问题不是对称形式，需要将其转化为对称形式，然后按照对称形式的要求，写出其化为对称形式，然后按照对称形式的要求，写出其对偶问题。对偶问题。第第72页页 符符号号不不限限321333323213123232221211313212111332211,0,0 .maxxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz（1）（2）（3）式（式（2）：）：2323222121bxaxaxa 2323222121
32、2323222121bxaxaxabxaxaxa（4）解：解：第第73页页式（式（3）：）：2333232131bxaxaxa 2333232131bxaxaxa 式（式（4）：）：0,0 ,0 ,33333222 xxxxxxxx 23232221212323222121 bxaxaxabxaxaxa第第74页页 0,0,0,0 .max3321333333323213123233232221212323323222121131331321211133332211xxxxbxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxatsxcxcxcxcz转化后的对称形式为：转化后的
33、对称形式为：第第75页页 0,0,0,0 .min3221333322322311333332232231132332222222112133122122111133222211yyyycyayayayacyayayayacyayayayacyayayayatsybybybyb 对偶问题为：对偶问题为：设对偶问题的决策变量为：设对偶问题的决策变量为：3221,yyyy 第第76页页原问题原问题对偶问题对偶问题 0,0,0,0 .min3221333322322311333332232231132332222222112133122122111133222211yyyycyayayayacyay
34、ayayacyayayayacyayayayatsybybybyb 0,0,0,0 .max3321333333323213123233232221212323323222121131331321211133332211xxxxbxaxaxaxabxaxaxaxabxaxaxaxabxaxaxaxatsxcxcxcxcz第第77页页令：令：33222yyyyy 0,0 .min3213333223113333322311323322221121331221111332211yyycyayayacyayayacyayayacyayayatsybybyb符符号号不不限限 下面对对偶问题进行简化处理
35、下面对对偶问题进行简化处理第第78页页 0,0 .min321333322311323322221121331221111332211yyycyayayacyayayacyayayatsybybyb符符号号不不限限 符符号号不不限限321333323213123232221211313212111332211,0,0 .maxxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz原问题原问题对偶问题对偶问题第第79页页项目项目原问题原问题对偶问题对偶问题A约束条件系数矩阵约束条件系数矩阵约束条件系数矩阵的转置矩阵约束条件系数矩阵的转置矩阵b约束条件右端常数约束条件右端常数目标函数系
36、数目标函数系数C目标函数系数目标函数系数约束条件右端常数约束条件右端常数目标函数目标函数极大化极大化极小化极小化约束约束-变量变量约束条件数约束条件数决策变量数决策变量数变量变量-约束约束决策变量数决策变量数约束条件数约束条件数非对称形式下原问题非对称形式下原问题-对偶问题的关系对偶问题的关系第第80页页原问题（极大化）原问题（极大化）对偶问题（极小化）对偶问题（极小化）约束条件约束条件变量符号变量符号00=符号不限符号不限变量符号变量符号约束条件约束条件符号不限符号不限=第第81页页极大化问题极大化问题极小化问题极小化问题约束条件符号约束条件符号决策变量符号决策变量符号约束条件符号约束条件符
37、号决策变量符号决策变量符号一致一致相反相反第第82页页（1）max min。（2）对偶问题的决策变量数）对偶问题的决策变量数=原问题的约束条件数原问题的约束条件数。（3）对偶问题的目标函数系数）对偶问题的目标函数系数=原问题的约束条件原问题的约束条件右端常数右端常数。（4）对偶问题的约束条件系数矩阵）对偶问题的约束条件系数矩阵=原问题约束条原问题约束条件系数矩阵的转置矩阵。件系数矩阵的转置矩阵。第第83页页（5）对偶问题的约束条件右端常数）对偶问题的约束条件右端常数=原问题的目标原问题的目标函数系数。函数系数。（6）约束条件符号：由下述关系图确定。）约束条件符号：由下述关系图确定。（7）决策变
38、量符号：由下述关系图确定。）决策变量符号：由下述关系图确定。第第84页页极大化问题极大化问题极小化问题极小化问题约束条件符号约束条件符号决策变量符号决策变量符号约束条件符号约束条件符号决策变量符号决策变量符号一致一致相反相反第第85页页原问题原问题对偶问题对偶问题0 .min YCYAtsYb 0 .max XbAXtsCXz第第86页页1.对称性对称性对偶问题的对偶是原问题。对偶问题的对偶是原问题。证：证：0 .min YCYAtsYb 0 .max XbAXtsCXz对偶问题对偶问题原问题原问题第第87页页0 .min YCYAtsYb 0 )(.)(max YCAYtsbY 0 -.mi
39、n XbAXtsCXz0 .max XbAXtsCXz0 )(.)(max YCAYtsbY 对偶问题对偶问题对偶问题的对偶问题对偶问题的对偶问题对偶问题对偶问题对偶问题对偶问题0 -.min XbAXtsCXz第第88页页2.弱对偶性弱对偶性证：证：若若 是原问题的可行解，是原问题的可行解，是是对偶问题的可行解，对偶问题的可行解，则存在则存在XYbYXC bXA bYXAY)(bYXAY)(bYXAYXC )(CAY 第第89页页推论推论（1）原问题任一可行解的目标函数值是其对偶问题原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目目标函数值的下界；反之，
40、对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。标函数值是其原问题目标函数值的上界。第第90页页（2）如）如原问题为无界解，则对偶问题无可行解；反原问题为无界解，则对偶问题无可行解；反之，如对偶问题为无界解，则原问题无可行解。之，如对偶问题为无界解，则原问题无可行解。（3）如）如原问题为无可行解，且对偶问题有可行解，原问题为无可行解，且对偶问题有可行解，则对偶问题为无界解；反之，如对偶问题为无可行解则对偶问题为无界解；反之，如对偶问题为无可行解，且原问题有可行解，则原问题为无界解。，且原问题有可行解，则原问题为无界解。第第91页页无界解无界解无可行解无可行解无可行解无可行解无界解无界
41、解无可行解无可行解此可行解一定为无界解此可行解一定为无界解对偶问题有可行解对偶问题有可行解第第92页页 0,122 .max32132132121xxxxxxxxxtsxxz例：例：解：解：0,0 1 12.2 min2121212121yyyyyyyytsyy 由第一个约束条件可由第一个约束条件可知：无可行解知：无可行解又因为原问题有可行解又因为原问题有可行解(0,0,0)所以原问题为无界解。所以原问题为无界解。第第93页页3.强强对偶性（对偶定理）对偶性（对偶定理）若原问题及其对偶问题均具有可行解，则两者均具有若原问题及其对偶问题均具有可行解，则两者均具有最优解，且目标函数值相等。最优解，
42、且目标函数值相等。证：证：X是原问题的最优解是原问题的最优解原问题达到最优时，所有检验数均原问题达到最优时，所有检验数均0，即，即bBCzB1 最优目标函数值为最优目标函数值为01 ABCCB第第94页页CABCB )(11 BCB为对偶问题的可行解为对偶问题的可行解1 BCB带入对偶问题的目标函数：带入对偶问题的目标函数：将可行解将可行解bBCYbB1 z 而此时：而此时：由弱对偶性的推论（由弱对偶性的推论（1）可知：）可知：1 BCB也是对偶问题的最优解。也是对偶问题的最优解。bBCzB1 为对偶问题下界值。为对偶问题下界值。=下界值下界值故：故：第第95页页4.可行解可行解是最优解时的性
43、质是最优解时的性质证：证：bYXC bYXC XCbY XCXC XY若若 是原问题的可行解，是原问题的可行解，是是对偶问题的可行解对偶问题的可行解，的充要条件是的充要条件是bYXC YX,为问题的最优解为问题的最优解bYXC YX,为问题的最优解为问题的最优解（1）必要性证明。）必要性证明。第第96页页bYXC bYXC bYbY Y 是对偶问题的最优解是对偶问题的最优解bYXC 是原问题的最优解是原问题的最优解X bYXC YX,为问题的最优解为问题的最优解（2）充分性证明。）充分性证明。由强对偶性可知。由强对偶性可知。第第97页页5.互补松弛定理互补松弛定理在线性规划问题的最优解中在线性
44、规划问题的最优解中如果对应某一约束条件的对偶变量值为非零，则该如果对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式（松弛变量为零）；约束条件为严格等式（松弛变量为零）；如果约束条件为严格不等式（松弛变量不为零），如果约束条件为严格不等式（松弛变量不为零），则其对应的对偶变量最优值一定为零。则其对应的对偶变量最优值一定为零。第第98页页若若 为原问题的可行解，为原问题的可行解，为对偶问题的可行解，为对偶问题的可行解，XY0 XYs0 sXY的充要条件是的充要条件是YX,为问题的最优解。为问题的最优解。第第99页页证：证：0 .min YCYYAtsYbS 0 .max XbXAXtsC
45、XzS对偶问题标准型对偶问题标准型原问题标准型原问题标准型XYYAXXYYACXzSS )(SSYXYAXXAXYYb )(第第100页页SSXYXAYXYXAY 0,0 SSXYXY如果如果 z根据性质根据性质5：则有则有即即 为原问题的最优解，为原问题的最优解，为对偶问题的最优解。为对偶问题的最优解。XY（1）必要性证明）必要性证明0 XYs0 sXYYX,为问题的最优解。为问题的最优解。第第101页页SSXYXAYXYXAY SSXYXY 0,0,0,0 SSXYXY0,0 SSXYXY如果如果 为原问题的最优解，为原问题的最优解，为对偶问题的最优解。为对偶问题的最优解。XY z根据性质
46、根据性质4：（2）充分性证明）充分性证明0 XYs0 sXYYX,为问题的最优解为问题的最优解第第102页页 0,332432.32532 min54321543215432154321xxxxxxxxxxxxxxxtsxxxxx 例：例：已知其对偶问题的最优解为：已知其对偶问题的最优解为：求问题的最优解。求问题的最优解。5/3,5/4*2*1 yy第第103页页解：解：0,3 32 5323 22 .34max 21212121212121yyyyyyyyyyyytsyyz（1）（2）（3）（4）（5）0,0 *2*1 yy所以原问题的约束条件为等式。所以原问题的约束条件为等式。第第104页
47、页0 *4*3*2 xxx代入原问题的约束条件得：代入原问题的约束条件得：5/3,5/4*2*1 yy代入（代入（2）、（）、（3）、（）、（4）：）：将将（2）、（）、（3）、（）、（4）为严格不等式）为严格不等式 32435151xxxx5,)1,0,0,0,1(*TX第第105页页原问题原问题对偶问题对偶问题0,.min SYYCYAtsYb 0,.max SXXbAXtsCXz6.对称形式的原问题对称形式的原问题-对偶问题解的关系对偶问题解的关系 0,.min SSYYCYYAtsYb 0,.max SSXXbXAXtsCXz标准型标准型标准型标准型第第106页页原问题单纯形表的检验数
48、行对应其对偶问题的一原问题单纯形表的检验数行对应其对偶问题的一个个解（不一定是可行解）解（不一定是可行解）；最终单纯形表的检验；最终单纯形表的检验数行对应其对偶问题的数行对应其对偶问题的最优解最优解。第第107页页原问题的原变量原问题的原变量X原问题的松弛变量原问题的松弛变量XS检验数检验数对偶问题的剩余变量对偶问题的剩余变量YS对偶问题的原变量对偶问题的原变量Y可行解可行解ABCCB1 )(1ABCCB 对偶问题变量的值对偶问题变量的值=-（原问题中松弛变量的检验数）（原问题中松弛变量的检验数）对偶问题剩余变量的值对偶问题剩余变量的值=-（原问题中原变量的检验数）（原问题中原变量的检验数）1
49、 BCB)(1 BCB第第108页页证：证：原问题的原变量原问题的原变量X原问题的松弛变量原问题的松弛变量XS检验数检验数ABCCB1 1 BCB)(1ABCCYBS )(1 BCYBSYYA )()(11ABCCABCBB CABCCABCBB 11 第第109页页0)(1 ABCCYBS0)(1 BCYB由最优解判别性质可知，由最优解判别性质可知，Y、YS 为最优解。为最优解。bBCbBCYbBB11)(bBCCXzB1 z 因为最终单纯形表中所有检验数因为最终单纯形表中所有检验数 0故故为可行解为可行解又因为又因为第第110页页对称形式的原问题对称形式的原问题 0,.,.max21221
50、122222121112121112211mmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz第第111页页 0,.,.max2122112222221211112121112211mmmnnmnmmnnnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxatsxcxcxcz原问题的标准型原问题的标准型第第112页页 ),.,1(0.min221122222112112211112211miycyayayacyayayacyayayatsybybybinmmmnnmmmmmm 对偶问题对偶问题第第113页页对偶问题的标准型对偶问题的标准型 )
