1、Page 11.6 线性规划的对偶理论线性规划的对偶理论 （Duality Theory）窗含西岭千秋雪，门泊东吴万里船窗含西岭千秋雪，门泊东吴万里船对偶对偶是一种普遍现象是一种普遍现象Page 2 线性规划的对偶模型线性规划的对偶模型 对偶性质对偶性质 对偶单纯形法对偶单纯形法 学习要点：学习要点：1.理解线性规划的对偶性质理解线性规划的对偶性质 2.掌握对偶单纯形法的解题思路及求解步骤掌握对偶单纯形法的解题思路及求解步骤Page 3一、线性规划的对偶模型一、线性规划的对偶模型设某工厂生产两种产品甲和乙，生产中需设某工厂生产两种产品甲和乙，生产中需4种设备按种设备按A，B，C，D顺序加工，每
2、件产品加工所需的机时数、每件产品的利润顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表值及每种设备的可利用机时数列于下表：表表1.产品数据表产品数据表 设备设备产品产品ABCD产品利润产品利润（元件）（元件）甲甲 21402乙乙 22043设备可利用设备可利用机时机时数（时）数（时）1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？获得最大利润？1.Page 4线性规划的对偶模型线性规划的对偶模型解：解：设甲、乙型产品各生产设甲、乙型产品各生产x1及及x2件，则数学模型
3、为：件，则数学模型为：0,124164821222.32max2121212121xxxxxxxxtsxxz反过来问：反过来问：若厂长决定不生产甲和乙型产品，决定若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？机器的机时如何定价才是最佳决策？Page 5线性规划的对偶模型线性规划的对偶模型在市场竞争的时代，厂长的最佳决策显然应符合两条：在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获
4、利润。由此原则，便构成了新规划的不等式约乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。总收费，以便争取更多用户。设设A、B、C、D设备的机时价分别为设备的机时价分别为y1、y2、y3、y4，则新的，则新的线性规划数学模型为：线性规划数学模型为：0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyyPage 6线性规划的对偶模型线性规划的对偶模型把同种问题的两种提法所获得的数学模型用表把同种问
5、题的两种提法所获得的数学模型用表2表示，表示，将会发现一个有趣的现象。将会发现一个有趣的现象。表表2.原问题与新问题对比表原问题与新问题对比表A（y1）B（y2）C（y3）D（y4）甲（甲（x1）21402乙（乙（x2）220431281612 min max z Page 7线性规划的对偶模型线性规划的对偶模型2.0,124164821222.32max2121212121xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原问题原问题（对偶问题）（对偶问题）对偶问题对偶问题（原问题）（原问题）原始规划与
6、对偶规划是同一组数原始规划与对偶规划是同一组数据参数据参数,只是位置有所不同只是位置有所不同,所描所描述的问题实际上是同一个问题从述的问题实际上是同一个问题从另一种角度去描述另一种角度去描述.Page 8线性规划的对偶模型线性规划的对偶模型特点特点：目标函数求极大值时，所有约束条件为：目标函数求极大值时，所有约束条件为号，变量非负号，变量非负;目标函数求极小值时，所有约束条件目标函数求极小值时，所有约束条件为为号，变量非负号，变量非负.min .0TLPZC XAXbs tX ：:max .0TTDPWb YA YCs tY 对称形式对称形式的对偶线性规划问题的对偶线性规划问题原始线性规划问题
7、原始线性规划问题对偶线性规划问题对偶线性规划问题Page 9对合性对合性定理定理6.1 对偶线性规划的对偶问题是原始线性对偶线性规划的对偶问题是原始线性规划问题。规划问题。min.0TC XAXbs tX max.0TTb YA YCs tY 对偶定义对偶定义min.0TTb YA YCs tY max.0TC XAXbs tX 对偶定义对偶定义Page 10线性规划的对偶模型线性规划的对偶模型例例1 写出线性规划问题的对偶问题写出线性规划问题的对偶问题 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先将原问题变形为解：首先将原问
8、题变形为 0,5 64 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZPage 11线性规划的对偶模型线性规划的对偶模型 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW对对偶偶问问题题：若给出的线性规划不是对称形式，可以先化成若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。对称形式再写对偶问题。Page 12线性规划的对偶模型线性规划的对偶模型12121212212 max()4532204310.50,f xxxxxxxs txxxx 例例原原线线性性规规不不限限划划问问题题12
9、2122122122122122 max()45532220433105.5 ,0(max,)f xxxxxxxxxxxxxs txxxxxx 化化为为型型标标准准问问题题Page 1312341234123412341234min()201055344235.235,0h wwwwwwwwwwwwws twwwww www 应应用用对对称称形形式式对对偶偶变变换换规规则则123123123123min()20105344.2350,0,g yyyyyyys tyyyyyy 不不限限1122334,ywywyww 令令12121212212 m ax()4532204310.50,fxxxxx
10、xxs txxxx 例例原原 线线 性性 规规不不 限限划划 问问 题题Page 14线性规划的对偶变换规则线性规划的对偶变换规则原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量00=无约束无约束变变量量n个个n个个约约束束条条件件00无约束无约束=Page 15对偶问题的形成对偶问题的形成min z=2x1+4x2-x3s.t.3x1-x2+2x3 6
11、 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2 -y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3:unrq原始问题变量的个数原始问题变量的个数(3)等于对偶问题约束条件的个数等于对偶问题约束条件的个数(3)；原始问题约束条件的个数原始问题约束条件的个数(4)等于对偶问题变量的个数等于对偶问题变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用原始问题变量的性质影响对偶问题约
12、束条件的性质，用 表示表示 原始问题约束条件的性质影响对偶问题变量的性质，用原始问题约束条件的性质影响对偶问题变量的性质，用 表示表示Page 16例例3 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题.无无约约束束4321432142143214321,0,06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ解：原问题的对偶问题为解：原问题的对偶问题为 无无约约束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyyyyyyyyyyyyyWPage 17 min .0TLPZC XAXbs
13、tX ：:max .0TTTDPWY bYACs tY 原始线性规划问题原始线性规划问题对偶线性规划问题对偶线性规划问题非非对称形式对称形式的对偶线性规划问题的对偶线性规划问题Page 18123412341341234123max57322527260.22430510,0,Zxxxxxxxxxxxs txxxxxxx 自自由由变变量量练习练习 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型Page 19解：解：先将约束条件变形为先将约束条件变形为“”形式形式1234134123441234322527260224301050,0,xxxxxxxxxxxxxxxx 自自由由变变
14、量量Page 20再根据非对称形式的对应关系，直接写出对偶再根据非对称形式的对应关系，直接写出对偶规划规划1234512313123124512345min2560301052213212745.27,0fyyyyyyyyyyyyys tyyyyyyyyy 没没有有非非负负限限制制Page 21 min .0TLPZC XAXbs tX ：:max .0TTTDPWY bYACs tY 原始线性规划问题原始线性规划问题对偶线性规划问题对偶线性规划问题为了便于讨论，下面不妨总是以非对称形式的线性为了便于讨论，下面不妨总是以非对称形式的线性规划问题作证明规划问题作证明.二、对偶性质二、对偶性质Pa
15、ge 22若若x 0,y 0分别是分别是(LP)与与(DP)的的可行解可行解,则则定理定理6.2 弱对偶原理弱对偶原理(弱对偶性弱对偶性)：设设 和和 分别是分别是问题问题(LP)和和(DP)的可行解，则必有的可行解，则必有0X0Y0011nmTTjjiijiC XYbc xy b 即即：证明：证明：0,AXb 0TTYAC 于是，于是，000TTYAXC X 0TYb 推论推论1:原问题任一可行解的目标函数值是其对偶问原问题任一可行解的目标函数值是其对偶问题目标函数值的上界；反之，对偶问题任意可行解题目标函数值的上界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的下界。的目标函数
16、值是其原问题目标函数值的下界。Page 23二、对偶性质二、对偶性质推论推论2:在一对对偶问题（在一对对偶问题（LP）和（）和（DP）中，若其）中，若其中一个问题可行但目标函数无界，则另一个问题无中一个问题可行但目标函数无界，则另一个问题无可行解；可行解；这也是对偶问题的无界性。这也是对偶问题的无界性。推论推论3：在一对对偶问题（在一对对偶问题（LP）和（）和（DP）中，若一）中，若一个有可行解，而另一个无可行解，则该可行的问题个有可行解，而另一个无可行解，则该可行的问题目标函数值无界目标函数值无界。min .0TLPZC XAXbs tX ：:max .0TTTDPWY bYACs tY 0
17、0TTC XYb Page 24定理定理6.3 最优性定理最优性定理：如果如果 是原问题的可行解，是原问题的可行解，是其对偶问题的可行解，并且是其对偶问题的可行解，并且:0X0Y00:zwTTC XYb 即即则则 是原问题的最优解，是原问题的最优解，是其对偶问题的最优解。是其对偶问题的最优解。0X0Y设设x 是是(LP)问题的任一问题的任一可行解可行解,则则证明：证明：0X于于是是，是是原原始始线线性性规规划划问问题题的的最最优优解解.0TTC XYb 0Y类类似似可可证证，是是对对偶偶线线性性规规划划问问题题的的最最优优解解.二、对二、对偶性质偶性质0TC X Page 25考虑如下的线性规
18、划考虑如下的线性规划121231241234532430min().,zxxxxxLPs txxxx xx x 2 2考虑考虑基解基解(0,1,0,-2)T(不可不可行行)对应的规范式为对应的规范式为 1312313412343 72 3222172220min/./,xxxxxs txxxx x x x 其判别数向量其判别数向量(7/2,0,3/2,0)是非负的是非负的.二、对二、对偶性质偶性质Page 26判别数向量用判别数向量用(LP)中的符号可以记为中的符号可以记为1TTBcc B A 则判别数向量为则判别数向量为1(),TTByc B 令TTcy A 上述的判别数向量非负，因此有上述
19、的判别数向量非负，因此有0TTcy A即即.TA yc 这说明这说明y是对偶规划的可行解是对偶规划的可行解.1()TTByc B 并并且且这一可行解对应的目标函数值为这一可行解对应的目标函数值为即为在原始线性规划中基解对应的目标函数值即为在原始线性规划中基解对应的目标函数值.1TTBy bc B b 二、对二、对偶性质偶性质判别数非负判别数非负对偶解可行对偶解可行Page 27对偶的线性规划问题的解对偶的线性规划问题的解原始规划的最优性原始规划的最优性10TTBcc BA 1()TTByc B 对偶规划的可行性对偶规划的可行性.TA yc 定理定理6.4 设设B是问题是问题min.0TZc X
20、AXbs tX 的一个的一个基矩阵基矩阵,对应的对应的基解满足最优性条件基解满足最优性条件10TTBcc B A 则对偶线性规划问题则对偶线性规划问题有可行解有可行解1(),TTByc B TTBBc XY b 且且在上述条件下在上述条件下,(LP)的的基解的目标基解的目标函数值函数值等于等于(DP)的解的目标函数值的解的目标函数值.如果如果xB是可行解是可行解,则显然是则显然是(LP)的的最优解最优解.此时对应的此时对应的y是是(DP)的最的最优解优解.Page 28定理定理6.5 若原始线性规划问题与对偶线性规划问题之一有若原始线性规划问题与对偶线性规划问题之一有最优解最优解,则另一个也有
21、最优解则另一个也有最优解,并且它们目标函数的最优值相并且它们目标函数的最优值相等等.证明证明:考虑到对合性考虑到对合性,只需选取两个规划中的任一个证明只需选取两个规划中的任一个证明.min.0TZc XAXbs tX 设设有最优解有最优解x0,且其为基可行解且其为基可行解再设基矩阵为再设基矩阵为B,10TTBc xc B b x0为最优解为最优解,判别数非负判别数非负,有有10TTBcc B A 10(),TTByc B 令0.则TA yc y0可行可行,且且100TTTBy bc B bc x y0是对偶规划最优解是对偶规划最优解.对偶的线性规划问题的解对偶的线性规划问题的解Page 29定
22、理定理6.6 强对偶性强对偶性：若原问题及其对偶问题均具有可行解，：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。则两者均具有最优解，且它们最优解的目标函数值相等。推论推论4：（LP）与（）与（DP）要么两者都有最优解，要么都无最）要么两者都有最优解，要么都无最优解。优解。二、对二、对偶性质偶性质两个互为对偶的线性规划的解的情况两个互为对偶的线性规划的解的情况(3)一个有可行解一个有可行解,无最优解无最优解(目标函数无界目标函数无界),则则 另一个无可行解另一个无可行解.(1)两个都有可行解两个都有可行解,两个都有最优解两个都有最优解,且最且最 优值相等优
23、值相等.(2)两个都无最优解两个都无最优解.(4)一个有可行解，另一个无可行解，则可一个有可行解，另一个无可行解，则可 行的一个目标函数无界行的一个目标函数无界.Page 30判断下列结论是否正确？判断下列结论是否正确？3）互为对偶问题，或者同时都有最优解，或者）互为对偶问题，或者同时都有最优解，或者同时都无最优解同时都无最优解.1）任何线性规划都存在一个对应的对偶线性规划）任何线性规划都存在一个对应的对偶线性规划.2）原问题第）原问题第i个约束是个约束是“”约束，则对偶变量约束，则对偶变量yi0.4）对偶问题有可行解，则原问题也有可行解）对偶问题有可行解，则原问题也有可行解.5）原问题有多重
24、解，对偶问题也有多重解）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解对偶问题具有无界解.Page 317）原问题无最优解，则对偶问题无可行解）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能有无界解）对偶问题不可行，原问题可能有无界解.9）原问题与对偶问题都可行，则都有最优）原问题与对偶问题都可行，则都有最优解解.10）原问题具有无界解，则对偶问题不可行）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最）对偶问题具有无界解，则原问题无最优解优解.12）若）若X*、
25、Y*是原问题与对偶问题的最优解，是原问题与对偶问题的最优解，则则X*=Y*.Page 32二、对偶性质二、对偶性质分别求解下列分别求解下列2个互为对偶关系的线性规划问题个互为对偶关系的线性规划问题 052426155.2max5214213221jxxxxxxxxxtsxxz 012526.52415min5321432321iyyyyyyyytsyyyw分别用单纯形法求解上述分别用单纯形法求解上述2个规划问题，得到最个规划问题，得到最终单纯形表如下表：终单纯形表如下表：Page 33对偶性质对偶性质XBb原问题的变量原问题的变量原问题的松弛变量原问题的松弛变量x1x2x3x4x5x315/2
26、0015/4-15/2x17/21001/4-1/2x23/2010-1/43/20001/41/2j XBb对偶问题的变量对偶问题的变量对偶问题的剩余变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2j 原问原问题最题最优表优表对偶对偶问题问题最优最优表表Page 34对偶性质对偶性质在单纯形表中，原问题的松弛变量对应对在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问偶问题的变量，对偶问题的剩余变量对应原问题的变量。题的变量。Page 35对偶定理对偶定理定理定理6.7 互补松
27、弛性互补松弛性：设设X0和和Y0分别是分别是(LP)问题和问题和(DP)问问题的可行解，则它们分别是最优解的充要条件是：题的可行解，则它们分别是最优解的充要条件是：0000TsTsYXYX 其中：其中：Xs为松弛变量为松弛变量、Ys为剩余变量为剩余变量.互补松弛条件互补松弛条件证：证：由定理所设，可知有由定理所设，可知有00(1)(2)sTTTSAXXbYAYc 分别以分别以Y0T左乘左乘(1)式，以式，以X0右乘右乘(2)式后，两式相减，即得式后，两式相减，即得000TTssYXYX 000,0TTssYXYX 由可行性及最优性条件，可知有由可行性及最优性条件，可知有反之亦然。反之亦然。证毕
28、。证毕。Page 36AXb TTb Yc X()0TTA YcX()0TTA YcX(1)0,1,(2),01,TjjjTjjjxy pcjny pcxjn 若若则则若若则则，定理定理6.7*互补松弛性互补松弛性：设设X0和和Y0分别是分别是(LP)问题和问题和(DP)问问题的可行解，则它们分别是最优解的充要条件是：题的可行解，则它们分别是最优解的充要条件是：互补松弛条件互补松弛条件可写为：可写为：Page 37对偶性质对偶性质定理定理6.7的应用：的应用：该性质给出了已知一个问题最优解求另一个问题最优该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知解的方法，即已知Y*求求X*
29、或已知或已知X*求求Y*s00TTsYXYX 由于变量都非负，要使求和式等于零，则必定每一分量为零，由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：因而有下列关系：若若Y*0，则，则Xs必为必为0；若；若X*0，则，则Ys必为必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。Page 38对偶性质对偶性质例例2.4已知线性规划已知线性规划 3,2,1,0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是X*=(6,2,0)T
30、,求其对偶问题的最优解求其对偶问题的最优解Y*。解：解：写出原问题的对偶问题，即写出原问题的对偶问题，即 0,1422321610min2121212121yyyyyyyyyyw 0,1422321610min5432152142132121yyyyyyyyyyyyyyyyw标准化标准化Page 39对偶性质对偶性质设对偶问题最优解为设对偶问题最优解为Y*(y1，y2),由互补松弛性定理可知，由互补松弛性定理可知，X*和和 Y*满足：满足：00 ssXYXY即：即：0),)(,(0),)(,(5421321543 TTxxyyxxxyyy因为因为x10，x20，所以对偶问题的第一、二个约束的松
31、弛变，所以对偶问题的第一、二个约束的松弛变量等于零，即量等于零，即y30，y40，带入方程中：，带入方程中：422322121yyyy解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：从而对偶问题的最优解为：Y*=(1,1)，最优值，最优值w=26。Page 40对偶性质对偶性质例例2.5 已知线性规划已知线性规划 无约束无约束321321321321,0,06422minxxxxxxxxxxxxz的对偶问题的最优解为的对偶问题的最优解为Y*=(0,-2)，求原问题的最优解。，求原问题的最优解。解解:对偶问题是对偶问题是 021264max2121212121yyyy
32、yyyyyyw无无约约，标准化标准化 0,0,21264max43212142132121yyyyyyyyyyyyyyw无无约约Page 41对偶性质对偶性质设对偶问题最优解为设对偶问题最优解为X*(x1，x2，x3)T,由互补松弛性定理由互补松弛性定理可知，可知，X*和和 Y*满足：满足：0),)(,(0),)(,(5421321543 TTxxyyxxxyyy将将Y*带入由方程可知，带入由方程可知，y3y50，y41。y2=-20 x50又又y4=10 x20将将x2，x5分别带入原问题约束方程中，得：分别带入原问题约束方程中，得：643131xxxx解方程组得：解方程组得：x1=-5,x
33、3=-1,所以原问题的最优解为所以原问题的最优解为X*=(-5,0,-1)，最优值，最优值 z=-12Page 42三、单纯形方法三、单纯形方法对偶单纯形法对偶单纯形法 用单纯形方法求解线性规划时用单纯形方法求解线性规划时,x的可行性是的可行性是满足的满足的,但是最优性条件不满足，即但是最优性条件不满足，即w不可行不可行.迭迭代是使最优性条件逐步得到满足代是使最优性条件逐步得到满足,（检验数非负），（检验数非负），即使即使w逐步可行的过程。逐步可行的过程。构造另一种方法构造另一种方法,最优性条件始终满足最优性条件始终满足,即即y可可行行,而而x不可行不可行.逐步迭代使逐步迭代使x最终可行最终可
34、行,从而是最从而是最优解优解.对偶单纯形法是求解线性规划的另一个基本对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。而不是求解对出来的，因此称为对偶单纯形法。而不是求解对偶问题的单纯形法。偶问题的单纯形法。Page 43判别数向量非负判别数向量非负1()TTByc B 为对偶规划的可行解为对偶规划的可行解单纯形方法单纯形方法保证解可行保证解可行最优性条件不满足最优性条件不满足(有负判别数有负判别数)对偶规划解不可行对偶规划解不可行最优性条件满足最优性条件满足(判别数非负判别数非负)对偶规划解
35、可行对偶规划解可行形方法形方法对偶单纯对偶单纯划解可行划解可行保证对偶规保证对偶规解不可行解不可行解可行解可行两种方法都始终保证两种方法都始终保证()0TTA Y c X 所以只要所以只要x,y都可行都可行,必然最必然最优优Page 44对偶单纯形法对偶单纯形法 找出一个对偶问题的可行基，保持对偶问题为找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断可行解的条件下，判断XB是否可行（是否可行（XB为非负），为非负），若否，通过变换基解，直到找到原问题基可行解若否，通过变换基解，直到找到原问题基可行解（即（即XB为非负），这时原问题与对偶问题同时达到为非负），这时原问题与对偶问题同时
36、达到可行解，由定理可行解，由定理6.4可得最优解。可得最优解。Page 45对偶单纯形法对偶单纯形法找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束Page 46对偶单纯形法对偶单纯形法1.最优解的判别最优解的判别已知线性规划问题的基矩阵已知线性规划问题的基矩阵B及它对应的基解及它对应的基解,10BxB b 若若则所得的基解为最优解则所得的基解为最优解.并且此基解的所有判别数非负并且此基解的所有判别数非负.2.确定出确定出(离离)基变量基变量111iimi
37、n0()lB bB bB b 令令()|()则则以以xl为离基变量为离基变量若若xl所在行的所有系数所在行的所有系数alj0(j=1,2,n),则线性规划问题则线性规划问题无可行解无可行解.(此时若有可行解此时若有可行解1122ln0)lllnba xa xa x Page 473.确定进基变量确定进基变量对偶单纯形法对偶单纯形法设目标函数的形式为设目标函数的形式为已确定离基变量为已确定离基变量为xl,设进基变量为设进基变量为xk.在目标函在目标函数中数中,用用xk替换替换xl ，0jjj Tffx lljjlkklj Tj kba xa xx 0()ljlkkjkjlj Tlklklkj k
38、abffxxaaa （）+1()klljjlj Tlkj kxba xxa 得得Page 480()ljlkkjkjlj Tlklklkj kabffxxaaa （）+3.确定进基变量确定进基变量0(1)0,(2),klkljjklkaaajT jk 由由(1)式，式，0lka 0(2)lja 若若，式式恒恒成成立立；0lja 若若，max|0jkljlkljaaa 令令则则xk为进基变量为进基变量最大比例原则最大比例原则为保持判别数非负，有为保持判别数非负，有Page 49例例 2.6.用对偶单纯形法求解：用对偶单纯形法求解：1234123124min128161224222430(1.2.
39、3 4)jZxxxxxxxxxxxj ，引入松引入松弛变量弛变量得到标得到标准型线准型线性规划性规划123412351246min1281612242.22430(1.2.34,5,6)jZxxxxxxxxs txxxxxj ，解：解：Page 50123412351246min1281612242.2243Zxxxxxxxxstxxxx 构造对偶单纯形表构造对偶单纯形表选取离基变量选取离基变量63min|0jjbbb 选取进基变量选取进基变量46466m0ax|jjjaaa Page 51Page 52基解已可基解已可行行,最优解最优解为为x*=(0,3/2,1/8,0)T最优值为最优值为z
40、*=14Page 53对偶单纯形法对偶单纯形法例例2.7 用对偶单纯形法求解：用对偶单纯形法求解：)3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解解:将模型化为标准型。将模型化为标准型。Page 54对偶单纯形法对偶单纯形法1231234123512361 6min9121522 1023 12 5 140Zxxxxxxxxxxxxxxxx cj91215000cBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001(9/-1，12/-1，15/-5)91
41、215000ij Page 55对偶单纯形法对偶单纯形法cj91215000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1/515x314/51/51/5100-1/5(-30/9,-45/14,-15/1)690003ij Page 56cj91215000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/1412x223/79/14100-5/141/14(-3/9,-45/9,-33/1)15x315/71/140101/14-3/143/1400045/1433/14ij
42、Page 57对偶单纯形法对偶单纯形法cj91215000cBxBbx1x2x3x4x5x69x12100-14/911/912x220101-1015x320011/90-2/90001/337/3j 原问题的最优解为：原问题的最优解为：X*=（2,2,2,0,0,0），），Z*=72 其对偶问题的最优解为：其对偶问题的最优解为：Y*=（1/3,3,7/3），），W*=72Page 58对偶单纯形法对偶单纯形法 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题：用对偶单纯形法求解线性规划是一种求解方法，用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解而不是去求对偶问题的
43、最优解.初始表中一定要满足对偶问题可行，也就是说检初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则验数满足最优判别准则.对偶单纯形法与普通单纯形法的换基顺序不一样，对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；偶单纯形法是先确定出基变量后确定进基变量；Page 59对偶单纯形法对偶单纯形法 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，其目的是保证下一个原问题的基本解可行，0minikikiiaab其目的是保
44、证下一个对其目的是保证下一个对偶问题的基本解可行偶问题的基本解可行.max|0jljjljaa 对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的规则，任选一个小于零的b bi i对应对应的基变量出基，不影响计算结果，只是迭代次数可能的基变量出基，不影响计算结果，只是迭代次数可能不一样。不一样。0|min iilbbb对偶单纯形法的最大比值是对偶单纯形法的最大比值是Page 60练习：用对偶单纯形法求解下列规划问题练习：用对偶单纯形法求解下列规划问题0,44262.35)(min432143214321421xxxxxxxxxxxxtsxxxx
45、f解：解：化原问题为适合对偶解法的标准型化原问题为适合对偶解法的标准型0,44262.35)(min6543216432154321421xxxxxxxxxxxxxxxxtsxxxxfPage 61对偶单纯形法的单纯形表对偶单纯形法的单纯形表(min)(min)1x1612 11 100 x6 160 3(2)321 612 11 10IIcj zj0312101x11417/205/2 2 1/20 x3803/213/2 1 1/2 1417/205/2 2 1/2III最最优优解解cj zj03/201/221/2答：最优解为答：最优解为x1=14,x3=8,x2=x4=0,OBJ=14Page 62
