《对偶与对偶单纯形法的应用精选PPT.ppt》由会员分享，可在线阅读，更多相关《对偶与对偶单纯形法的应用精选PPT.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于对偶与对偶单纯形法的应用第1页，讲稿共56张，创作于星期日一、对偶问题的提出一、对偶问题的提出每一个线性规划问题，都存在每一个与它密切相关每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为的线性规划的问题，我们称其为原问题，另一个为对偶问题。对偶问题。原问题：原问题：某工厂在计划期内安排某工厂在计划期内安排、两种产品，生两种产品，生产单位产品所需设备产单位产品所需设备A A、B B、C C台时如表所示，该工厂台时如表所示，该工厂每生产一单位产品每生产一单位产品 可获利可获利5050元，每生产一单位产品元，每生产一单位产品可获利可获利100100元，问工
2、厂应分别生产多少元，问工厂应分别生产多少 产品和产品和产品，才能使工厂获利最多？产品，才能使工厂获利最多？第2页，讲稿共56张，创作于星期日解：设x1为产品I的计划产量，x2产品的计划产量，则有Max z z=50 x1+100 x2x1+x2 3002x1+x2 400 x2 250 x1，x20第3页，讲稿共56张，创作于星期日假如有另外一个工厂要求租用该厂的设备假如有另外一个工厂要求租用该厂的设备A A、B B、C C，那么该厂的厂长应该如何来确定合理的租金呢？那么该厂的厂长应该如何来确定合理的租金呢？对原厂：租金收入对原厂：租金收入自己组织生产的收入自己组织生产的收入对租借厂：总租金最
3、低对租借厂：总租金最低变量改变变量改变产品产品设备设备设备不再是约束条件，必须从产品入手设备不再是约束条件，必须从产品入手设设y1y1，y2y2，y3y3是是A A、B B、C C每小时的出租价格每小时的出租价格对于产品对于产品I I：每件：每件I I自行生产的收入是自行生产的收入是5050元，元，租金收入是租金收入是y y1 1+2y+2y2 2元。元。对于产品对于产品来说，自行生产收入来说，自行生产收入100100元元，租金收入是，租金收入是y y1 1+y+y2 2+y+y3 3元元第4页，讲稿共56张，创作于星期日Minw=300y1+400y2+250y3（设备租用总收入）（设备租用
4、总收入）S.T y1+2y2 50 y1+y2+y3 100其中其中y1，y2，y3均均0比较一下与原线性规划问题的不同？比较一下与原线性规划问题的不同？1、目标函数、目标函数 2、变量、变量 3、约束条件、约束条件第5页，讲稿共56张，创作于星期日这样从两个不同的角度来考虑同一个工厂的最大利这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做型就是一对对偶问题，其中一个叫做原问题原问题，而另，而另外一个叫外一个叫对偶问题对偶问题。矩阵形式比较：矩阵形式比较：解解1：MaxZ=CX
5、AX b X 0 解解2：minW=b Y A Y C Y 0第6页，讲稿共56张，创作于星期日二、原问题和对偶问题的转化二、原问题和对偶问题的转化1、目标函数、目标函数MAXMin2、约束条件、约束条件变量变量约束条件约束条件n个个变量变量n个个约束条件约束条件0 变量变量 0约束条件约束条件 0 变量变量 0约束条件约束条件=0变量无约束变量无约束要点：要点：max为反向关系（约束条件为反向关系（约束条件变量）变量）第7页，讲稿共56张，创作于星期日3、变量、变量约束条件约束条件变量变量m个个约束条件约束条件m个个变量变量0约束条件约束条件 0变量变量 0 约束条件约束条件 0变量无约束变
6、量无约束约束条件约束条件=0 4、目标函数中变量的系数、目标函数中变量的系数C为对偶问题中约为对偶问题中约束条件的右端常数项束条件的右端常数项b，个数对等变动。，个数对等变动。第8页，讲稿共56张，创作于星期日记忆要点：记忆要点：1、把握、把握“三要素三要素”，目标函数、约束目标函数、约束条件条件变量、变量、C-b的转化。的转化。2、把握重点、把握重点变量与约束条件的关系。变量与约束条件的关系。（1）约束条件）约束条件=0的情况，变量无约束。的情况，变量无约束。（2）在约束条件）在约束条件0 0时候，看原问题目标函数。时候，看原问题目标函数。1）max：约束条件：约束条件变量，反向；变量变量，
7、反向；变量约束条件，正向。约束条件，正向。（反正）（反正）2）min：约束条件：约束条件变量，正向；变量变量，正向；变量约束条件，反向。约束条件，反向。（正反）（正反）第9页，讲稿共56张，创作于星期日记忆宝典：记忆宝典：1、MaxMin2、C b3、无约束等于、无约束等于0，个数，个数m变变n。4、max就反正，就反正，min就正反。就正反。（约束条（约束条件件变量）变量）第10页，讲稿共56张，创作于星期日示例：转化为对偶问题第11页，讲稿共56张，创作于星期日第一种做法：按照定义来第12页，讲稿共56张，创作于星期日其中 第三个条件用两个式子替代。第13页，讲稿共56张，创作于星期日第1
8、4页，讲稿共56张，创作于星期日第15页，讲稿共56张，创作于星期日第16页，讲稿共56张，创作于星期日用所学原则写一次？第17页，讲稿共56张，创作于星期日示例示例2：写出下列问题的对偶问题：写出下列问题的对偶问题：minz=7x1+4x2-3x3S.T-4x1+2x2-6x3 24-3x1-6x2-4x3 15 5x2+3x3=30其中，其中，x1 0，x2无约束，无约束，x3 0第18页，讲稿共56张，创作于星期日Maxz=24y1+15y2+30y3S.T-4y1-3y2 72y1-6y2+5y3 =4-6y1-4y2+3y3-3y1 0，y2 0，y3取值无约束取值无约束第19页，讲
9、稿共56张，创作于星期日三、对偶问题的性质三、对偶问题的性质（一）对称性。对偶问题的对偶问题是原问题。对偶问题的对偶问题是原问题。（类似于（类似于“负负得正负负得正”）Minw=300y1+400y2+250y3S.T y1+2y2 50 y1+y2+y3 100其中其中y1，y2，y3均均0其对偶问题是？其对偶问题是？第20页，讲稿共56张，创作于星期日Max z=50 x1+100 x2x1+x2 3002x1+x2 400 x2 250 x1，x20第21页，讲稿共56张，创作于星期日（二）若原问题为（二）若原问题为（弱对偶性定理）（弱对偶性定理）maxZ=CXAX bX 0其对偶问题为
10、其对偶问题为Minw=YbYA CY 0 若若X为原问题任一可行解，为原问题任一可行解，Y为对偶问题任一为对偶问题任一可行解，则必有可行解，则必有CX Yb第22页，讲稿共56张，创作于星期日弱对偶性定理的意义：弱对偶性定理的意义：原问题任一个可行解是对偶问题最优目标函原问题任一个可行解是对偶问题最优目标函数值的一个下界。数值的一个下界。反过来说：反过来说：对偶问题的任一个可行解是原问题目标函数对偶问题的任一个可行解是原问题目标函数值的一个上界。值的一个上界。理解：理解：（1）很多个界。）很多个界。（2）看目标函数的类型判断。）看目标函数的类型判断。第23页，讲稿共56张，创作于星期日（三）若
11、原问题为（三）若原问题为（无界性定理）（无界性定理）maxZ=CXAX bX 0其对偶问题为其对偶问题为Minw=YbYA CY 0 若原问题有可行解，则目标函数为无界解的若原问题有可行解，则目标函数为无界解的充要条件是对偶问题无可行解。充要条件是对偶问题无可行解。第24页，讲稿共56张，创作于星期日（四）若（四）若X和和Y分别为原问题和对偶问题的可分别为原问题和对偶问题的可行解，当行解，当CX=Yb（目标函数值相同目标函数值相同）时，则）时，则X和和Y分别为原问题和对偶问题的最优解。分别为原问题和对偶问题的最优解。（最优性定理）（最优性定理）一般情况下是：一般情况下是：CXYb，当取，当取=
12、时，时，Yb最小，最小，CX最大。最大。第25页，讲稿共56张，创作于星期日（五）若原问题和对偶问题具有可行解，若（五）若原问题和对偶问题具有可行解，若原问题或对偶问题之一有最优解，则另一个原问题或对偶问题之一有最优解，则另一个对偶问题也必有最优解，且最优值相同。对偶问题也必有最优解，且最优值相同。（主对偶性定理）（主对偶性定理）证明证明含义：含义：若原问题有一个对应于基若原问题有一个对应于基B的最优解，则的最优解，则CBB-1为对偶问题的最优解。为对偶问题的最优解。第26页，讲稿共56张，创作于星期日（六）若（六）若X，Y为原问题和对偶问题的的可行为原问题和对偶问题的的可行解，则解，则X，Y
13、为最优解的充要条件是为最优解的充要条件是V*X=0，Y*U=0，其中，其中V是对偶问题的剩余变量，是对偶问题的剩余变量，U是是原问题的松弛变量。原问题的松弛变量。（互补松弛性定理）（互补松弛性定理）第27页，讲稿共56张，创作于星期日（七）原问题在单纯性法迭代过程中的检验（七）原问题在单纯性法迭代过程中的检验数对应于对偶问题的一个基本解。数对应于对偶问题的一个基本解。（对应性（对应性定理）定理）原问题原问题 XB XN XS 对应基对应基B检验数检验数 0 CN-CBB-1BN CBB-1对偶问题的变量对偶问题的变量 -YS1 -YS2 -Y第28页，讲稿共56张，创作于星期日原问题：maxZ
14、=12x1+8x2+5x33x1 +2x2+x3 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张，创作于星期日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
15、 -y6=5y1，y2，y3，y4，y5，y60第30页，讲稿共56张，创作于星期日原问题的松弛变量（XS）=对偶问题的变量原问题的变量=对偶问题的剩余变量（YS）第31页，讲稿共56张，创作于星期日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张，创作于星期日对偶问题性质的启示对偶问题性质的
16、启示原问题原问题 对偶问题对偶问题有最优解有最优解 有最优解有最优解无可行解无可行解 无可行解无可行解有可行解无上界有可行解无上界 无有限最优解无有限最优解无有限最优解无有限最优解 有可行解但无下界有可行解但无下界第33页，讲稿共56张，创作于星期日四、对偶问题经济学含义四、对偶问题经济学含义影子价格影子价格因为因为Z*=Y*=Yb所以：所以：Z/b=YZ/b=Ybb资源的量资源的量ZZ目标函数目标函数经济学含义：资源每变动一个单位，目标函经济学含义：资源每变动一个单位，目标函数（利润、总产值等）变动的大小。数（利润、总产值等）变动的大小。资源对生产做出的贡献。资源对生产做出的贡献。（影子价格
17、）（影子价格）是对现有资源实现最大效益的一个评价，叫是对现有资源实现最大效益的一个评价，叫机会成本。机会成本。第34页，讲稿共56张，创作于星期日五、对偶单纯形法五、对偶单纯形法思路思路：单纯性法的解题思路：单纯性法的解题思路：从可行域的一个顶点（基本可行解）通过迭从可行域的一个顶点（基本可行解）通过迭代（初等行变换）换到另一个顶点（基本可代（初等行变换）换到另一个顶点（基本可行解），保持顶点的最优性不变（每一个顶行解），保持顶点的最优性不变（每一个顶点所取得的目标函数值处于增加（点所取得的目标函数值处于增加（max）或）或者减少（者减少（min）的情况，直到取得最优解）的情况，直到取得最优解
18、（目标函数值不可能继续增大（减少）（目标函数值不可能继续增大（减少）=所有所有变量的检验数全部变量的检验数全部0 0。第35页，讲稿共56张，创作于星期日按照对偶问题的性质7来说，当原问题获得一个基本可行解（顶点）时，对偶问题获得一个基本解。当对偶问题获得基本解，同时也为可行解时，原问题的检验数全部0，即原问题获得最优解。第36页，讲稿共56张，创作于星期日作业题中原问题作业题中原问题 与与对偶问题解之间的关系。对偶问题解之间的关系。x1 x2 x3 x4 x5 x6 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
19、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张，创作于星期日对偶单纯性法的思想：对偶单纯性法的思想：根据原问题对偶问题的特性（主对偶定理、根据原问题对偶问题的特性（主对偶定理、最优性定理、对应性定理），用单纯性法求最优性定理、对应性定理），用单纯性法求解线性规划问题（解线性规划问题（单纯性法的一种单纯性法
20、的一种）。）。解题思路：解题思路：每次迭代中，保持对偶问题的解是可行解，每次迭代中，保持对偶问题的解是可行解，不管原问题的基本解是否为基本可行解，当不管原问题的基本解是否为基本可行解，当原问题取得基本可行解时，则这个解是原问原问题取得基本可行解时，则这个解是原问题的最优解。题的最优解。第38页，讲稿共56张，创作于星期日二、例题二、例题例例:用对偶单纯性法求解线性规划问题。用对偶单纯性法求解线性规划问题。Minw=12y1+16y2+15y32y1+4y2 22y1 +5y33y1，y2，y30在不用对偶单纯性法之前，用什么方法，请在不用对偶单纯性法之前，用什么方法，请写出初始单纯性表？写出初
21、始单纯性表？第39页，讲稿共56张，创作于星期日用用“大大M”法，或者二阶段法。（必须用法，或者二阶段法。（必须用“人人工工变量法变量法”）MaxZ=-12y1-16y2-15y3+0y4+0y5-My6-My72y1+4y2 -y4 +y5 =22y1 +5y3 -y6 +y7 =3y1，y2，y3，y4，y5，y6，y70第40页，讲稿共56张，创作于星期日用对偶单纯性解题：用对偶单纯性解题：第一步：化成第一步：化成“标准型标准型”Maxz=-12y1-16y2-15y3+0y4+0y5-2y1-4y2 +y4 =-2-2y1 -5y3 +y5=-3y1,y2,y3,y4,y50bi00添
22、加的人工变量不一样。添加的人工变量不一样。第41页，讲稿共56张，创作于星期日初始对偶单纯性表初始对偶单纯性表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 0确定出基变量确定出基变量：bk=minbi,bi0=min-2，-3=-3;确定进基变量确定进基变量：=min/akj,akj0=-15/-5从而确定从而确定主元素主元素akr，以此为中心做初等行变换。，以此为中心做初等行变换。第42页，讲稿共56张，创作于星期日对偶单纯性表对偶单纯性表2ci -12
23、 -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，此时，原问题取得基本可行，此时，原问题取得基本可行解，即目标函数值达到最优。解，即目标函数值达到最优。第44页，讲稿共56张，创作于星期日对偶单纯性法和一般单纯性法的区别对偶单纯性法和一般单纯性法的区别：相同点：相同点：解题步骤一样解题步骤一样建立初始单纯性表建立初始单纯性表判断是否最优
24、判断是否最优选选定进出基变量定进出基变量初等行变换（迭代）初等行变换（迭代）单纯性表最优。单纯性表最优。不同点不同点：思路不同，步骤不同。思路不同，步骤不同。一般单纯性法一般单纯性法：原问题保持基本可行解不：原问题保持基本可行解不变，直到对偶问题由基本解取得基本可行解。变，直到对偶问题由基本解取得基本可行解。第45页，讲稿共56张，创作于星期日对偶单纯性法的要点对偶单纯性法的要点1、单纯性法的一种（利用原问题对偶问题、单纯性法的一种（利用原问题对偶问题的性质求解），并不是求解原问题的对偶问的性质求解），并不是求解原问题的对偶问题的单纯性法。题的单纯性法。（针对的还是原问题）（针对的还是原问题）
25、2、适用的范围、适用的范围（适用条件很苛刻）适用条件很苛刻）：（1）原问题约束条件有）原问题约束条件有0 0；（2 2）目标函数价值系数）目标函数价值系数maxmax函数，且函数，且C Ci i00（原问题的对偶问题是基本可行解）。（原问题的对偶问题是基本可行解）。不必引入人工变量，简化计算。不必引入人工变量，简化计算。第46页，讲稿共56张，创作于星期日对偶单纯性法：保持对偶问题为基本可行对偶单纯性法：保持对偶问题为基本可行解，直到原问题由基本解变成基本可行解。解，直到原问题由基本解变成基本可行解。解题思路正好相反。解题思路正好相反。2、具体解题步骤、具体解题步骤（1）判断最优性的标准）判断
26、最优性的标准一般单纯性法：当前表中所有变量的检验数一般单纯性法：当前表中所有变量的检验数（主要指非基变量）（主要指非基变量）0 0。相当于对偶问题取相当于对偶问题取得基本可行解。得基本可行解。对偶单纯性法：当前表中所有对偶单纯性法：当前表中所有b bi i00。相当于相当于原问题取得基本可行解。原问题取得基本可行解。第47页，讲稿共56张，创作于星期日（2）确定主元素（进出基变量）确定主元素（进出基变量）1）次序不一样。）次序不一样。一般单纯性法：先确定进基变量一般单纯性法：先确定进基变量再确定再确定出基变量。（出基变量。（先进后出先进后出先纵向后横向先纵向后横向）对偶单纯性法：先确定出基变量
27、对偶单纯性法：先确定出基变量再确定再确定进基变量。（进基变量。（先出后进先出后进先横向后纵向先横向后纵向）2）确定进基变量）确定进基变量一般单纯性法：一般单纯性法：max(j0)=k，确定，确定xk为进为进基基变变量。（量。（首先首先进进行行横向横向对对比比）对对偶偶单纯单纯性法：性法：min/akj,akj0=，确定，确定ajk为为出基出基变变量。（量。（第二步第二步进进行行纵纵向向对对比比）对对偶偶单纯单纯性法：性法：min bj0）；）；4、进出基最小化原则；、进出基最小化原则；第50页，讲稿共56张，创作于星期日练习：P 125页minf=x1+2x2+3x2x1-x2+x34x1+x
28、2+2x38 x2-x32X1，x2，x30第51页，讲稿共56张，创作于星期日第一步：化成第一步：化成“标准型标准型”minz=-x1-2x2-3x2-x1+x2-x3+x4 =-4x1+x2+2x3 +x5 =8 -x2+x3 +x6=-2X1，x2，x3，x4，x5，x60第52页，讲稿共56张，创作于星期日初始对偶单纯性表初始对偶单纯性表ci -1 -2 -3 0 0 0CB B b x1 x2 x3 x4 x5 x60 x4 -4 -1 1 -1 1 0 00 x5 8 1 1 2 0 1 00 x6 -2 0 -1 1 0 0 1 -Z 0 -1 -2 -3 0 0 0 1 3第5
29、3页，讲稿共56张，创作于星期日对偶单纯性表一对偶单纯性表一ci -1 -2 -3 0 0 0CB B b x1 x2 x3 x4 x5 x6-1 x1 4 1 -1 1 -1 0 00 x5 4 0 2 1 1 1 00 x6 -2 0 -1 1 0 0 1 -Z 4 0 -3 -2 -1 0 0 3 第54页，讲稿共56张，创作于星期日对偶单纯性表一对偶单纯性表一ci -1 -2 -3 0 0 0CB B b x1 x2 x3 x4 x5 x6-1 x1 6 1 0 0 -1 0 -10 x5 0 0 0 3 1 1 2-2 x2 2 0 1 -1 0 0 -1 -Z 10 0 0 -5 -1 0 -3 第55页，讲稿共56张，创作于星期日15.09.2022感感谢谢大大家家观观看看第56页，讲稿共56张，创作于星期日