对偶与对偶单纯形法的应用讲稿.ppt

《对偶与对偶单纯形法的应用讲稿.ppt》由会员分享，可在线阅读，更多相关《对偶与对偶单纯形法的应用讲稿.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于对偶与对偶单纯形法的应用第一页，讲稿共五十六页哦一、对偶问题的提出一、对偶问题的提出每一个线性规划问题，都存在每一个与它密切相关每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为的线性规划的问题，我们称其为原问题，另一个为对偶问题。对偶问题。原问题：原问题：某工厂在计划期内安排某工厂在计划期内安排、两种产品，生两种产品，生产单位产品所需设备产单位产品所需设备A A、B B、C C台时如表所示，该工厂台时如表所示，该工厂每生产一单位产品每生产一单位产品 可获利可获利5050元，每生产一单位产品元，每生产一单位产品可获利可获利100100元，问工厂应分别生

2、产多少元，问工厂应分别生产多少 产品和产品和产品，才能使工厂获利最多？产品，才能使工厂获利最多？第二页，讲稿共五十六页哦 资源限量 设备A 1 1 300台时 设备B 2 1 400台时 设备C 0 1 250台时 解：设x1为产品I的计划产量，x2产品的计划产量，则有Max z z=50 x1+100 x2x1+x2 3002x1+x2 400 x2 250 x1，x20第三页，讲稿共五十六页哦假如有另外一个工厂要求租用该厂的设备假如有另外一个工厂要求租用该厂的设备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元元第四页，讲稿共五十六页哦 Minw=3

4、00y1+400y2+250y3（设备租用总收入）（设备租用总收入）S.T y1+2y2 50 y1+y2+y3 100其中其中y1，y2，y3均均0 比较一下与原线性规划问题的不同？比较一下与原线性规划问题的不同？1、目标函数、目标函数 2、变量、变量 3、约束条件、约束条件第五页，讲稿共五十六页哦这样从两个不同的角度来考虑同一个工厂的最大利这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做型就是一对对偶问题，其中一个叫做原问题原问题，而另，而另外一个叫外一个叫对偶问题对偶问题。

5、矩阵形式比较：矩阵形式比较：解解1：MaxZ=CX AX b X 0 解解2：minW=b Y A Y C Y 0第六页，讲稿共五十六页哦二、原问题和对偶问题的转化二、原问题和对偶问题的转化1、目标函数、目标函数MAXMin2、约束条件、约束条件变量变量约束条件约束条件n个个变量变量n个个约束条件约束条件0 变量变量 0约束条件约束条件 0 变量变量 0约束条件约束条件=0变量无约束变量无约束要点：要点：max为反向关系（约束条件为反向关系（约束条件变量）变量）第七页，讲稿共五十六页哦3、变量、变量约束条件约束条件变量变量m个个约束条件约束条件m个个变量变量0约束条件约束条件 0变量变量 0

6、约束条件约束条件 0变量无约束变量无约束约束条件约束条件=0 4、目标函数中变量的系数、目标函数中变量的系数C为对偶问题中约为对偶问题中约束条件的右端常数项束条件的右端常数项b，个数对等变动。，个数对等变动。第八页，讲稿共五十六页哦记忆要点：记忆要点：1、把握、把握“三要素三要素”，目标函数、约束目标函数、约束条件条件变量、变量、C-b的转化。的转化。2、把握重点、把握重点变量与约束条件的关系。变量与约束条件的关系。（1）约束条件）约束条件=0的情况，变量无约束。的情况，变量无约束。（2）在约束条件）在约束条件0 0时候，看原问题目标函数。时候，看原问题目标函数。1）max：约束条件：约束条件

7、变量，反向；变量变量，反向；变量约束条件，正向。约束条件，正向。（反正）（反正）2）min：约束条件：约束条件变量，正向；变量变量，正向；变量约束条件，反向。约束条件，反向。（正反）（正反）第九页，讲稿共五十六页哦记忆宝典：记忆宝典：1、MaxMin2、C b3、无约束等于、无约束等于0，个数，个数m变变n。4、max就反正，就反正，min就正反。就正反。（约束条（约束条件件变量）变量）第十页，讲稿共五十六页哦示例：转化为对偶问题321643maxxxxz0,20035,10046,440632321321321321xxxxxxxxxxxx第十一页，讲稿共五十六页哦第一种做法：按照定义来32

8、1643maxxxxz0,2003520035,10046,440632321321321321321xxxxxxxxxxxxxxx第十二页，讲稿共五十六页哦其中 第三个条件用两个式子替代。2003520035321321xxxxxx第十三页，讲稿共五十六页哦3 321200200100440minyyyyf,0,66,43343,355623 3213 3213 3213 321yyyyyyyyyyyyyyyy第十四页，讲稿共五十六页哦)(200100440min3 321yyyyf,0,6)(6,4)(343,3)(5623 3213 3213 3213 321yyyyyyyyyyyyyy

9、yy第十五页，讲稿共五十六页哦321200100440minyyyf没有限制。321321321321,0,66,4343,3562yyyyyyyyyyyy第十六页，讲稿共五十六页哦用所学原则写一次？第十七页，讲稿共五十六页哦示例示例2：写出下列问题的对偶问题：写出下列问题的对偶问题：minz=7x1+4x2-3x3S.T-4x1+2x2-6x3 24-3x1-6x2-4x3 15 5x2+3x3=30其中，其中，x1 0，x2无约束，无约束，x3 0第十八页，讲稿共五十六页哦Maxz=24y1+15y2+30y3S.T-4y1-3y2 72y1-6y2+5y3 =4-6y1-4y2+3y3-

10、3y1 0，y2 0，y3取值无约束取值无约束第十九页，讲稿共五十六页哦三、对偶问题的性质三、对偶问题的性质（一）对称性。对偶问题的对偶问题是原问题。对偶问题的对偶问题是原问题。（类似于（类似于“负负得正负负得正”）Minw=300y1+400y2+250y3S.T y1+2y2 50 y1+y2+y3 100其中其中y1，y2，y3均均0其对偶问题是？其对偶问题是？第二十页，讲稿共五十六页哦 Max z=50 x1+100 x2 x1+x2 300 2x1+x2 400 x2 250 x1，x20第二十一页，讲稿共五十六页哦（二）若原问题为（二）若原问题为（弱对偶性定理）（弱对偶性定理）ma

11、xZ=CXAX bX 0其对偶问题为其对偶问题为Minw=YbYA CY 0 若若X为原问题任一可行解，为原问题任一可行解，Y为对偶问题任一为对偶问题任一可行解，则必有可行解，则必有CX Yb第二十二页，讲稿共五十六页哦弱对偶性定理的意义：弱对偶性定理的意义：原问题任一个可行解是对偶问题最优目标函原问题任一个可行解是对偶问题最优目标函数值的一个下界。数值的一个下界。反过来说：反过来说：对偶问题的任一个可行解是原问题目标函数对偶问题的任一个可行解是原问题目标函数值的一个上界。值的一个上界。理解：理解：（1）很多个界。）很多个界。（2）看目标函数的类型判断。）看目标函数的类型判断。第二十三页，讲稿

12、共五十六页哦（三）若原问题为（三）若原问题为（无界性定理）（无界性定理）maxZ=CXAX bX 0其对偶问题为其对偶问题为Minw=YbYA CY 0 若原问题有可行解，则目标函数为无界解的若原问题有可行解，则目标函数为无界解的充要条件是对偶问题无可行解。充要条件是对偶问题无可行解。第二十四页，讲稿共五十六页哦（四）若（四）若X和和Y分别为原问题和对偶问题的可分别为原问题和对偶问题的可行解，当行解，当CX=Yb（目标函数值相同目标函数值相同）时，则）时，则X和和Y分别为原问题和对偶问题的最优解。分别为原问题和对偶问题的最优解。（最优性定理）（最优性定理）一般情况下是：一般情况下是：CXYb，

13、当取，当取=时，时，Yb最小，最小，CX最大。最大。第二十五页，讲稿共五十六页哦（五）若原问题和对偶问题具有可行解，若（五）若原问题和对偶问题具有可行解，若原问题或对偶问题之一有最优解，则另一个原问题或对偶问题之一有最优解，则另一个对偶问题也必有最优解，且最优值相同。对偶问题也必有最优解，且最优值相同。（主对偶性定理）（主对偶性定理）证明证明含义：含义：若原问题有一个对应于基若原问题有一个对应于基B的最优解，则的最优解，则CBB-1为对偶问题的最优解。为对偶问题的最优解。第二十六页，讲稿共五十六页哦（六）若（六）若X，Y为原问题和对偶问题的的可行为原问题和对偶问题的的可行解，则解，则X，Y为最

14、优解的充要条件是为最优解的充要条件是V*X=0，Y*U=0，其中，其中V是对偶问题的剩余变量，是对偶问题的剩余变量，U是是原问题的松弛变量。原问题的松弛变量。（互补松弛性定理）（互补松弛性定理）第二十七页，讲稿共五十六页哦（七）原问题在单纯性法迭代过程中的检验（七）原问题在单纯性法迭代过程中的检验数对应于对偶问题的一个基本解。数对应于对偶问题的一个基本解。（对应性（对应性定理）定理）原问题原问题 XB XN XS 对应基对应基B检验数检验数 0 CN-CBB-1BN CBB-1对偶问题的变量对偶问题的变量 -YS1 -YS2 -Y第二十八页，讲稿共五十六页哦原问题：maxZ=12x1+8x2+

15、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第二十九页，讲稿共五十六页哦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=5y1，y2，y3

16、，y4，y5，y60第三十页，讲稿共五十六页哦原问题的松弛变量（XS）=对偶问题的变量原问题的变量=对偶问题的剩余变量（YS）第三十一页，讲稿共五十六页哦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）第三十二页，讲稿共五十六页哦对偶问题性质的启示对偶问题性质的启示原问题原问题 对偶问题对偶问题有最优解有最优解 有

17、最优解有最优解无可行解无可行解 无可行解无可行解有可行解无上界有可行解无上界 无有限最优解无有限最优解无有限最优解无有限最优解 有可行解但无下界有可行解但无下界第三十三页，讲稿共五十六页哦四、对偶问题经济学含义四、对偶问题经济学含义影子价格影子价格因为因为Z*=Y*=Yb所以：所以：Z/b=YZ/b=Ybb资源的量资源的量ZZ目标函数目标函数经济学含义：资源每变动一个单位，目标函经济学含义：资源每变动一个单位，目标函数（利润、总产值等）变动的大小。数（利润、总产值等）变动的大小。资源对生产做出的贡献。资源对生产做出的贡献。（影子价格）（影子价格）是对现有资源实现最大效益的一个评价，叫是对现有资

18、源实现最大效益的一个评价，叫机会成本。机会成本。第三十四页，讲稿共五十六页哦五、对偶单纯形法五、对偶单纯形法思路思路：单纯性法的解题思路：单纯性法的解题思路：从可行域的一个顶点（基本可行解）通过迭从可行域的一个顶点（基本可行解）通过迭代（初等行变换）换到另一个顶点（基本可代（初等行变换）换到另一个顶点（基本可行解），保持顶点的最优性不变（每一个顶行解），保持顶点的最优性不变（每一个顶点所取得的目标函数值处于增加（点所取得的目标函数值处于增加（max）或）或者减少（者减少（min）的情况，直到取得最优解）的情况，直到取得最优解（目标函数值不可能继续增大（减少）（目标函数值不可能继续增大（减少）=

19、所有所有变量的检验数全部变量的检验数全部0 0。第三十五页，讲稿共五十六页哦按照对偶问题的性质7来说，当原问题获得一个基本可行解（顶点）时，对偶问题获得一个基本解。当对偶问题获得基本解，同时也为可行解时，原问题的检验数全部0，即原问题获得最优解。第三十六页，讲稿共五十六页哦作业题中原问题作业题中原问题 与与对偶问题解之间的关系。对偶问题解之间的关系。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 0 0 14/3 8 0 0 5/3 0 0 0 -1 4 0 02 5 4 0 0

20、0 0 0 0 12/5 12/5 1/5从顶点从顶点1迭代到顶点迭代到顶点4，对偶问题一直是基本解，对偶问题一直是基本解，当为基本可行解的时候，原问题和对偶问题共同当为基本可行解的时候，原问题和对偶问题共同取得最优解。取得最优解。第三十七页，讲稿共五十六页哦对偶单纯性法的思想：对偶单纯性法的思想：根据原问题对偶问题的特性（主对偶定理、根据原问题对偶问题的特性（主对偶定理、最优性定理、对应性定理），用单纯性法求最优性定理、对应性定理），用单纯性法求解线性规划问题（解线性规划问题（单纯性法的一种单纯性法的一种）。）。解题思路：解题思路：每次迭代中，保持对偶问题的解是可行解，每次迭代中，保持对偶问

21、题的解是可行解，不管原问题的基本解是否为基本可行解，当不管原问题的基本解是否为基本可行解，当原问题取得基本可行解时，则这个解是原问原问题取得基本可行解时，则这个解是原问题的最优解。题的最优解。第三十八页，讲稿共五十六页哦二、例题二、例题例例:用对偶单纯性法求解线性规划问题。用对偶单纯性法求解线性规划问题。Minw=12y1+16y2+15y32y1+4y2 22y1 +5y33y1，y2，y30在不用对偶单纯性法之前，用什么方法，请在不用对偶单纯性法之前，用什么方法，请写出初始单纯性表？写出初始单纯性表？第三十九页，讲稿共五十六页哦用用“大大M”法，或者二阶段法。（必须用法，或者二阶段法。（必

22、须用“人人工工变量法变量法”）MaxZ=-12y1-16y2-15y3+0y4+0y5-My6-My72y1+4y2 -y4 +y5 =22y1 +5y3 -y6 +y7 =3y1，y2，y3，y4，y5，y6，y70第四十页，讲稿共五十六页哦用对偶单纯性解题：用对偶单纯性解题：第一步：化成第一步：化成“标准型标准型”Maxz=-12y1-16y2-15y3+0y4+0y5-2y1-4y2 +y4 =-2-2y1 -5y3 +y5=-3y1,y2,y3,y4,y50bi00添加的人工变量不一样。添加的人工变量不一样。第四十一页，讲稿共五十六页哦初始对偶单纯性表初始对偶单纯性表ci -12 -1

23、6 -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，以此为中心做初等行变换。，以此为中心做初等行变换。第四十二页，讲稿共五十六页哦对偶单纯性表对偶单纯性表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

24、0 1 0 -1/5 -6 -16 0 0 -3确定确定出基变量出基变量：bk=minbi,bi0=min-15=-15;确定确定进基变量进基变量：=min/akj,akj0，此时，原问题取得基本可行，此时，原问题取得基本可行解，即目标函数值达到最优。解，即目标函数值达到最优。第四十四页，讲稿共五十六页哦对偶单纯性法和一般单纯性法的区别对偶单纯性法和一般单纯性法的区别：相同点：相同点：解题步骤一样解题步骤一样建立初始单纯性表建立初始单纯性表判断是否最优判断是否最优选选定进出基变量定进出基变量初等行变换（迭代）初等行变换（迭代）单纯性表最优。单纯性表最优。不同点不同点：思路不同，步骤不同。思路不

25、同，步骤不同。一般单纯性法一般单纯性法：原问题保持基本可行解不：原问题保持基本可行解不变，直到对偶问题由基本解取得基本可行解。变，直到对偶问题由基本解取得基本可行解。第四十五页，讲稿共五十六页哦对偶单纯性法的要点对偶单纯性法的要点1、单纯性法的一种（利用原问题对偶问题、单纯性法的一种（利用原问题对偶问题的性质求解），并不是求解原问题的对偶问的性质求解），并不是求解原问题的对偶问题的单纯性法。题的单纯性法。（针对的还是原问题）（针对的还是原问题）2、适用的范围、适用的范围（适用条件很苛刻）适用条件很苛刻）：（1）原问题约束条件有）原问题约束条件有0 0；（2 2）目标函数价值系数）目标函数价值系

26、数maxmax函数，且函数，且C Ci i00（原问题的对偶问题是基本可行解）。（原问题的对偶问题是基本可行解）。不必引入人工变量，简化计算。不必引入人工变量，简化计算。第四十六页，讲稿共五十六页哦对偶单纯性法：保持对偶问题为基本可行对偶单纯性法：保持对偶问题为基本可行解，直到原问题由基本解变成基本可行解。解，直到原问题由基本解变成基本可行解。解题思路正好相反。解题思路正好相反。2、具体解题步骤、具体解题步骤（1）判断最优性的标准）判断最优性的标准一般单纯性法：当前表中所有变量的检验数一般单纯性法：当前表中所有变量的检验数（主要指非基变量）（主要指非基变量）0 0。相当于对偶问题取相当于对偶问

27、题取得基本可行解。得基本可行解。对偶单纯性法：当前表中所有对偶单纯性法：当前表中所有b bi i00。相当于相当于原问题取得基本可行解。原问题取得基本可行解。第四十七页，讲稿共五十六页哦（2）确定主元素（进出基变量）确定主元素（进出基变量）1）次序不一样。）次序不一样。一般单纯性法：先确定进基变量一般单纯性法：先确定进基变量再确定再确定出基变量。（出基变量。（先进后出先进后出先纵向后横向先纵向后横向）对偶单纯性法：先确定出基变量对偶单纯性法：先确定出基变量再确定再确定进基变量。（进基变量。（先出后进先出后进先横向后纵向先横向后纵向）2）确定进基变量）确定进基变量一般单纯性法：一般单纯性法：ma

28、x(j0)=k，确定，确定xk为进基变量。（为进基变量。（首先进行首先进行横向对比横向对比）对偶单纯性法：对偶单纯性法：min/akj,akj0=，确定，确定ajk为出基变量。（为出基变量。（第二步进行第二步进行纵向对比纵向对比）对偶单纯性法：对偶单纯性法：min bj0）；）；4、进出基最小化原则；、进出基最小化原则；第五十页，讲稿共五十六页哦练习：P 125页minf=x1+2x2+3x2x1-x2+x34x1+x2+2x38 x2-x32X1，x2，x30第五十一页，讲稿共五十六页哦第一步：化成第一步：化成“标准型标准型”minz=-x1-2x2-3x2-x1+x2-x3+x4 =-4x

29、1+x2+2x3 +x5 =8 -x2+x3 +x6=-2X1，x2，x3，x4，x5，x60第五十二页，讲稿共五十六页哦初始对偶单纯性表初始对偶单纯性表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第五十三页，讲稿共五十六页哦对偶单纯性表一对偶单纯性表一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 第五十四页，讲稿共五十六页哦对偶单纯性表一对偶单纯性表一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 第五十五页，讲稿共五十六页哦9/6/2022感谢大家观看感谢大家观看第五十六页，讲稿共五十六页哦