对偶与对偶单纯形法的应用

1、关于对偶与对偶单纯形法的应用第1页，共56页，2022年，5月20日，22点31分，星期三一、对偶问题的提出每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。原问题：某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示，该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？第2页，共56页，2022年，5月20日，22点31分，星期三解：设x1为产品I的计划产量，x2产品的计划产量，则有Max z=50 x1 +100 x2x1 +x2 3002x1+x2

2、 400 x2 250 x1，x20第3页，共56页，2022年，5月20日，22点31分，星期三假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？对原厂：租金收入自己组织生产的收入对租借厂：总租金最低变量改变产品设备设备不再是约束条件，必须从产品入手设y1，y2，y3是A、B、C每小时的出租价格对于产品I：每件I自行生产的收入是50元，租金收入是y1+2y2元。对于产品来说，自行生产收入100元，租金收入是y1+y2+y3元第4页，共56页，2022年，5月20日，22点31分，星期三Minw=300y1+400y2+250y3（设备租用总收入） S.

3、T y1+2y2 50 y1 + y2+y3 100其中y1，y2，y3均0比较一下与原线性规划问题的不同？1、目标函数 2、变量 3、约束条件第5页，共56页，2022年，5月20日，22点31分，星期三这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。矩阵形式比较：解1：MaxZ=CX AX b X 0 解2：minW=b Y A Y C Y 0第6页，共56页，2022年，5月20日，22点31分，星期三二、原问题和对偶问题的转化1、目标函数MAXMin2、约束条件变量约束条件n个变量n个

4、约束条件0 变量 0约束条件 0 变量 0约束条件=0变量无约束要点：max为反向关系（约束条件变量）第7页，共56页，2022年，5月20日，22点31分，星期三3、变量约束条件变量m个约束条件m个变量0约束条件 0变量 0 约束条件 0变量无约束约束条件=0 4、目标函数中变量的系数C为对偶问题中约束条件的右端常数项b，个数对等变动。第8页，共56页，2022年，5月20日，22点31分，星期三记忆要点：1、把握“三要素”，目标函数、约束条件变量、C-b的转化。2、把握重点变量与约束条件的关系。（1）约束条件=0的情况，变量无约束。（2）在约束条件0时候，看原问题目标函数。1）max：约束

5、条件变量，反向；变量约束条件，正向。（反正）2）min：约束条件变量，正向；变量约束条件，反向。（正反）第9页，共56页，2022年，5月20日，22点31分，星期三记忆宝典：1、MaxMin2、C b3、无约束等于0，个数m变n。4、max就反正，min就正反。（约束条件变量）第10页，共56页，2022年，5月20日，22点31分，星期三示例：转化为对偶问题第11页，共56页，2022年，5月20日，22点31分，星期三第一种做法：按照定义来第12页，共56页，2022年，5月20日，22点31分，星期三其中 第三个条件用两个式子替代。第13页，共56页，2022年，5月20日，22点31

6、分，星期三第14页，共56页，2022年，5月20日，22点31分，星期三第15页，共56页，2022年，5月20日，22点31分，星期三第16页，共56页，2022年，5月20日，22点31分，星期三用所学原则写一次？第17页，共56页，2022年，5月20日，22点31分，星期三示例2：写出下列问题的对偶问题：minz=7x1+4x2-3x3S.T-4x1+2x2-6x3 24-3x1-6x2-4x3 15 5x2+3x3=30其中，x1 0，x2无约束，x3 0第18页，共56页，2022年，5月20日，22点31分，星期三Maxz=24y1+15y2+30y3S.T-4y1-3y2 7

7、2y1-6y2+5y3 =4-6y1-4y2+3y3 -3y1 0，y2 0，y3取值无约束第19页，共56页，2022年，5月20日，22点31分，星期三三、对偶问题的性质（一）对称性。对偶问题的对偶问题是原问题。（类似于“负负得正”）Minw=300y1+400y2+250y3S.T y1+2y2 50 y1 + y2+y3 100其中y1，y2，y3均0其对偶问题是？第20页，共56页，2022年，5月20日，22点31分，星期三Max z=50 x1 +100 x2x1 +x2 3002x1+x2 400 x2 250 x1，x20第21页，共56页，2022年，5月20日，22点31

8、分，星期三（二）若原问题为（弱对偶性定理）maxZ=CXAX bX 0其对偶问题为Minw=YbYA CY 0 若X为原问题任一可行解，Y为对偶问题任一可行解，则必有CX Yb第22页，共56页，2022年，5月20日，22点31分，星期三弱对偶性定理的意义：原问题任一个可行解是对偶问题最优目标函数值的一个下界。反过来说：对偶问题的任一个可行解是原问题目标函数值的一个上界。理解：（1）很多个界。（2）看目标函数的类型判断。第23页，共56页，2022年，5月20日，22点31分，星期三（三）若原问题为（无界性定理）maxZ=CXAX bX 0其对偶问题为Minw=YbYA CY 0 若原问题有

9、可行解，则目标函数为无界解的充要条件是对偶问题无可行解。第24页，共56页，2022年，5月20日，22点31分，星期三（四）若X和Y分别为原问题和对偶问题的可行解，当CX=Yb（目标函数值相同）时，则X和Y分别为原问题和对偶问题的最优解。（最优性定理）一般情况下是：CXYb，当取=时，Yb最小，CX最大。第25页，共56页，2022年，5月20日，22点31分，星期三（五）若原问题和对偶问题具有可行解，若原问题或对偶问题之一有最优解，则另一个对偶问题也必有最优解，且最优值相同。（主对偶性定理）证明含义：若原问题有一个对应于基B的最优解，则CBB-1为对偶问题的最优解。第26页，共56页，20

10、22年，5月20日，22点31分，星期三（六）若X，Y为原问题和对偶问题的的可行解，则X，Y为最优解的充要条件是V*X=0，Y*U=0，其中V是对偶问题的剩余变量，U是原问题的松弛变量。（互补松弛性定理）第27页，共56页，2022年，5月20日，22点31分，星期三（七）原问题在单纯性法迭代过程中的检验数对应于对偶问题的一个基本解。（对应性定理）原问题 XB XN XS 对应基B检验数 0 CN-CBB-1BN CBB-1对偶问题的变量 -YS1 -YS2 -Y第28页，共56页，2022年，5月20日，22点31分，星期三原问题：maxZ =12x1+8x2+5x33x1 +2x2+x3

11、20 x1 +x2 +x3 1112x1+4x2+x3 5x1，x2，x30标准化：maxZ =12x1+8x2+5x33x1 +2x2+x3 +x4 =20 x1 +x2 +x3 +x5 =1112x1+4x2+x3 +x6 =5x1，x2，x3，x4，x5 ，x6 0第29页，共56页，2022年，5月20日，22点31分，星期三Minw=20y1+11y2+5y33y1+y2+12y3 122y1+4y2+y3 8y1+y2+y3 5y1，y2，y30Maxf=-20y1-11y2-5y33y1+y2+12y3 y4 =122y1+4y2+y3 -y5 =8y1+y2+y3 -y6 =5

12、y1，y2，y3，y4，y5，y60第30页，共56页，2022年，5月20日，22点31分，星期三原问题的松弛变量（XS）=对偶问题的变量原问题的变量=对偶问题的剩余变量（YS）第31页，共56页，2022年，5月20日，22点31分，星期三X（1）=（0,0,0,20,11,48）Y（1）=（0,0,0，-12，-8，-5）X（2）=（4,0,0,8,7,0）Y（2）=（0,0,1，0，-4，-4）X（3）=（4/3,8,0,0,5/3,0）Y（3）=（4,0,0，0，0，-1）X（4）=（2,5,4,0,0,0）Y（4）=（12/5,12/5,1/5，0，0，0）第32页，共56页，20

13、22年，5月20日，22点31分，星期三对偶问题性质的启示原问题 对偶问题有最优解 有最优解无可行解 无可行解有可行解无上界 无有限最优解无有限最优解 有可行解但无下界第33页，共56页，2022年，5月20日，22点31分，星期三四、对偶问题经济学含义影子价格因为Z*=Y*=Yb所以：Z/ b=Yb资源的量Z目标函数经济学含义：资源每变动一个单位，目标函数（利润、总产值等）变动的大小。资源对生产做出的贡献。（影子价格）是对现有资源实现最大效益的一个评价，叫机会成本。第34页，共56页，2022年，5月20日，22点31分，星期三五、对偶单纯形法思路：单纯性法的解题思路：从可行域的一个顶点（基

14、本可行解）通过迭代（初等行变换）换到另一个顶点（基本可行解），保持顶点的最优性不变（每一个顶点所取得的目标函数值处于增加（max）或者减少（min）的情况，直到取得最优解（目标函数值不可能继续增大（减少）=所有变量的检验数全部0。第35页，共56页，2022年，5月20日，22点31分，星期三按照对偶问题的性质7来说，当原问题获得一个基本可行解（顶点）时，对偶问题获得一个基本解。当对偶问题获得基本解，同时也为可行解时，原问题的检验数全部0，即原问题获得最优解。第36页，共56页，2022年，5月20日，22点31分，星期三作业题中原问题 与对偶问题解之间的关系。x1 x2 x3 x4 x5 x

15、6 y1 y2 y3 y4 y5 y60 0 0 20 11 48 0 0 0 0 0 04 0 0 8 7 0 0 -4 -4 0 0 14/3 8 0 0 5/3 0 0 0 -1 4 0 02 5 4 0 0 0 0 0 0 12/5 12/5 1/5从顶点1迭代到顶点4，对偶问题一直是基本解，当为基本可行解的时候，原问题和对偶问题共同取得最优解。第37页，共56页，2022年，5月20日，22点31分，星期三对偶单纯性法的思想：根据原问题对偶问题的特性（主对偶定理、最优性定理、对应性定理），用单纯性法求解线性规划问题（单纯性法的一种）。解题思路：每次迭代中，保持对偶问题的解是可行解，不

16、管原问题的基本解是否为基本可行解，当原问题取得基本可行解时，则这个解是原问题的最优解。第38页，共56页，2022年，5月20日，22点31分，星期三二、例题例:用对偶单纯性法求解线性规划问题。Minw=12y1+16y2+15y32y1+4y2 22y1 +5y33y1，y2，y30在不用对偶单纯性法之前，用什么方法，请写出初始单纯性表？第39页，共56页，2022年，5月20日，22点31分，星期三用“大M”法，或者二阶段法。（必须用“人工变量法”）MaxZ=-12y1-16y2-15y3+0y4+0y5-My6-My72y1+4y2 -y4 +y5 =22y1 +5y3 -y6 +y7

17、=3y1，y2，y3，y4，y5，y6，y70第40页，共56页，2022年，5月20日，22点31分，星期三用对偶单纯性解题：第一步：化成“标准型”Maxz=-12y1-16y2-15y3+0y4+0y5-2y1-4y2 +y4 = -2-2y1 -5y3 +y5 = -3y1,y2,y3,y4,y50bi0添加的人工变量不一样。第41页，共56页，2022年，5月20日，22点31分，星期三初始对偶单纯性表ci -12 -16 -15 0 0CB B b y1 y2 y3 y4 y50 y4 -2 -2 -4 0 1 0 0 y5 -3 -2 0 -5 0 1 -12 -16 -15 0

18、0确定出基变量：bk=minbi, bi0=min-2，-3=-3;确定进基变量：=min/akj,akj0=-15/-5从而确定主元素akr，以此为中心做初等行变换。第42页，共56页，2022年，5月20日，22点31分，星期三对偶单纯性表2ci -12 -16 -15 0 0CB B b y1 y2 y3 y4 y50 y4 -2 -2 -4 0 1 0 -15 y3 3/5 2/5 0 1 0 -1/5 -6 -16 0 0 -3确定出基变量：bk=minbi , bi0=min-15=-15;确定进基变量：=min/akj,akj0，此时，原问题取得基本可行解，即目标函数值达到最优。

19、第44页，共56页，2022年，5月20日，22点31分，星期三对偶单纯性法和一般单纯性法的区别：相同点：解题步骤一样建立初始单纯性表判断是否最优选定进出基变量初等行变换（迭代）单纯性表最优。不同点：思路不同，步骤不同。一般单纯性法：原问题保持基本可行解不变，直到对偶问题由基本解取得基本可行解。第45页，共56页，2022年，5月20日，22点31分，星期三对偶单纯性法的要点1、单纯性法的一种（利用原问题对偶问题的性质求解），并不是求解原问题的对偶问题的单纯性法。（针对的还是原问题）2、适用的范围（适用条件很苛刻）：（1）原问题约束条件有0；（2）目标函数价值系数max函数，且Ci0（原问题的

20、对偶问题是基本可行解）。不必引入人工变量，简化计算。第46页，共56页，2022年，5月20日，22点31分，星期三对偶单纯性法：保持对偶问题为基本可行解，直到原问题由基本解变成基本可行解。解题思路正好相反。2、具体解题步骤（1）判断最优性的标准一般单纯性法：当前表中所有变量的检验数（主要指非基变量）0。相当于对偶问题取得基本可行解。对偶单纯性法：当前表中所有bi0。相当于原问题取得基本可行解。第47页，共56页，2022年，5月20日，22点31分，星期三（2）确定主元素（进出基变量）1）次序不一样。一般单纯性法：先确定进基变量再确定出基变量。（先进后出先纵向后横向）对偶单纯性法：先确定出基变量再确定进基变量。（先出后进先横向后纵向）2）确定进基变量一般单纯性法： max(j0)=k，确定xk为进基变量。（首先进行横向对比）对偶单纯性法： min/akj,akj0= ，确定ajk为出基变量。（第二步进行纵向对比）对偶单纯性法： min bj0）；4、进出基最小化原则；第50页，共56页，2022年，5月20日，22点31分，星期三练习：P 125页minf=x1+2x2+3x2x1-x2+x34x1+x2+2x38 x2-x32X1，x2，x3