运筹学Chapter线性规划及其单纯形法PPT课件

1、2022-7-21一、线性规划问题的数学模型一、线性规划问题的数学模型在现有各项资源条件的限制下，如何确定方案，在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优，这就是规划方法。使预期目标达到最优，这就是规划方法。例例1 1 美佳公司计划制造美佳公司计划制造、两种家电产品。已两种家电产品。已知各制造一件时分别占用的设备知各制造一件时分别占用的设备A A、B B的台时、调试时的台时、调试时间、调试工序每天可用于这两种家电的能力、各售出间、调试工序每天可用于这两种家电的能力、各售出一件时的获利情况，如表一件时的获利情况，如表1-11-1所示。问该公司应制造所示。问该公司应制造两种家电产

2、品各多少件，使获取的利润为最大？两种家电产品各多少件，使获取的利润为最大？返回第一章目录返回第一章目录返回第一章目录第1页/共61页2022-7-22用数学语言来描述这个问题。假设美佳公司每天制造、两种家电产品的数量分别是x1和x2件。max约束条件目标函数Z2x1x25x2156x12x224x1x25x1，x20这就是例1的数学模型第2页/共61页2022-7-23【例例2 2】 某企业计划生产某企业计划生产I I、两种产品。这两种产品都要分别在两种产品。这两种产品都要分别在A A、B B、C C、D D四种不同设备上加工。按工艺资料规定，生产每件产品四种不同设备上加工。按工艺资料规定，生

3、产每件产品I I需占用各设备分别为需占用各设备分别为2 2、1 1、4 4、0 0小时，生产每件产品小时，生产每件产品B B，需占用各设备分别为，需占用各设备分别为2 2、2 2、0 0、4 4小时。已知设备计划小时。已知设备计划期内用于生产这两种产品的能力分别为期内用于生产这两种产品的能力分别为1212、8 8、1616、1212小时，又知每生产一件产品小时，又知每生产一件产品I I企业能获得企业能获得2 2元利润、每生产一件产品元利润、每生产一件产品企业能获得企业能获得3 3元利润，问该企业应安排生产元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大？两种产品各多少件，使总的

4、利润收入为最大？第3页/共61页2022-7-24 产品产品资源资源产品产品产品产品生产能力（生产能力（h）设备设备A（h）2212设备设备B（h）128设备设备C（h）4016设备设备D（h）0412利润（元利润（元/件）件）23假设：假设： 计划期内生产计划期内生产 产品产品x1件，件， 产品产品x2件。件。0,12401604821222.32max212121212121xxxxxxxxxxstxxz第4页/共61页2022-7-25捷运公司拟在下一年度的捷运公司拟在下一年度的1 14 4月份的月份的4 4个月内租用仓库堆放物资。已知各月份个月内租用仓库堆放物资。已知各月份所需仓库面积

5、数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如所需仓库面积数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如表表1-21-2所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签定租借合同的最优决策，签若干份租用面积和租借期限不同的合同，试确定该公司签定租借合同的最优决策，目的是使所付租借费用最小

6、。目的是使所付租借费用最小。第5页/共61页2022-7-26假设用xij表示捷运公司第i（i1，2，4）个月月初签订租借期为j（j1，2，4）个月的仓库面积数(单位为100m2）。则表 1-2 例 2 的基本数据 （page 9-10）月份1234所需仓库面积（100m2）15102012合同租借期限1 个月2 个月3 个月4 个月合同期内的租费（元/100m2）2800450060007300min z2800(x11+x21+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)+7300 x14x11+x12+x13+x1415x12+x13+x14+x21+

7、x22+x23 10 x13+x14+x22+x23+x31+x32 20 x14+x23+x32+x41 12xij 0 (i1，2，4；j1，2，4）租借期为一个月的仓库面积租借期为二个月的仓库面积租借期为三个月的仓库面积租借期为四个月的仓库面积一月份拥有的租借面积二月份拥有的租借面积三月份拥有的租借面积四月份拥有的租借面积一月份仓库需求面积约束二月份仓库需求面积约束三月份仓库需求面积约束四月份仓库需求面积约束非负约束第6页/共61页2022-7-27max Z2x1x25x2156x12x224x1x25x1，x20目标函数：约束条件第7页/共61页2022-7-28模型中，cj称为价值

8、系数。bi是资源限制量。aij称为技术系数或工艺系数。max(或min)zc1x1+c2x2+cnxna11x1+a12x2+a1nxn（或，）b1a21x1+a22x2+a2nxn（或，）b2am1x1+am2x2+amnxn（或，）bmx1,x2,xn0), 2 , 1(0), 2 , 1(),(min)max(11njxmibxaxczjinjjijnjjj或或简写为：0),(min)max(1jnjjjxbxPCXz或或向量形式：0(min)max(XbAXCXz），或或矩阵形式：),(21ncccCmjjjjaaaP21mbbbb21mnmmnnaaaaaaaaaA212222111

9、211第8页/共61页2022-7-29若得出的线性规划模型不是标准形式，应通过下列方法将其化为标准形式：1.目标函数为求极小值的情况，即), 2 , 1(0), 2 , 1(max11njxmibxaxczjinjjijnjjj本教材规定，线性规划模型的标准形式为：本教材规定，线性规划模型的标准形式为：其特点是：(1)目标函数求极大；(2)约束条件取等式；(3)变量非负；(4)约束条件右边常数为正值。njjjxcz1min化为标准形式的方法是，令zz，则njjjxczz1)min(max第9页/共61页2022-7-2103.3.约束条件为不等式的情况约束条件为不等式的情况。当约束条件为“”

10、时，在约束符号的左边加上一个松弛变量，将“”变为“”；如6x1+2x224,化为标准形式为6x1+2x2x324，x30。当约束条件为“”时，在约束符号的左边减去一个剩余变量，将“”变为“”；如10 x1+12x218,化为标准形式为10 x1+12x2x318， x30。4.4.对变量无约束的情况对变量无约束的情况。如x在（，）之间变化，即x的取值可正可负时，令xxx代入线性规划模型即可，其中x0， x0。5.5.对于对于x 00的情况的情况，令xx，显然x0。2.2.若约束条件右边常数项若约束条件右边常数项bim），其秩为其秩为m，B是矩阵是矩阵A中的一个中的一个mm阶的满秩子矩阵，称阶的

11、满秩子矩阵，称B是线性规划问题的一个基是线性规划问题的一个基。mnmmnnaaaaaaaaaA21222211211),(21212222111211mmmmmmmPPPaaaaaaaaaB：图解法返回第一章目录返回第一章目录返回第一章目录第15页/共61页2022-7-216基B中的每一个列向量Pj(j=1，2，m）称为，与基向量Pj对应的变量xj称为；除基变量以外的变量称为。：在约束方程中，将非基变量移到等式右边：nmnnnmmmmmmmmmmmmmnmmmmxaaaxaaaxaaabbbxaaaxaaaxaaa212222211112112121222212112111P1P2Pm令非基

12、变量xm+1xm+2xn0，得mmmnmmmmbbbxaaaxaaaxaaa2121222212112111第16页/共61页2022-7-217基可行解基可行解：满足非负约束的解称为基可行解。可行基可行基：对应于基可行解的基称为可行基。例：找出下述线性规划问题的全部基解，指出其中的基找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解可行解，并确定最优解。max z2x1+3x2+x3x1+x35x1+2x2+x410 x2+x54x150 x1x2x3x4x5z是否基可行解0051045045201750054100550-120100-5041552.5001.517.554

13、0-30222430019*：用穷举法找出该线性规划问题的全部基解。打者为基可行解。最优解为：x12，x24，x33，x40，x50与最优解对应的目标函数值为z19第17页/共61页2022-7-218凸集凸集设设C C为为n n维欧氏空间的一个点集。若对于维欧氏空间的一个点集。若对于C C中任意两点中任意两点X X1 1，X X2 2满足满足X X1 1 + (1 - )X + (1 - )X2 2C (0C (01)1)则称则称C C为凸集为凸集。也就是说，如果也就是说，如果X X1 1CC，X X2 2CC，则线段则线段X X1 1X X2 2上的所有点上的所有点X X也属于也属于C C

14、。即即：X XXX1 1 + (1 - )X + (1 - )X2 2C (0C (01)1)称称C C为凸集为凸集。从直观上看，凸集没有凹入部分，其内部没有孔洞。凸集凸集凸集凸集凸集凸集第18页/共61页2022-7-219不是凸集不是凸集不是凸集不是凸集第19页/共61页2022-7-220XxxxnX单纯形法迭代原理单纯形法迭代原理单纯形法迭代原理第20页/共61页2022-7-221Pjxjbj=1nPjx1jbj=1nPjx2jbj=1n；（1-9）X X1 1，X X2 2连线上任意一点可表示为：连线上任意一点可表示为：Xa aX1（1a a）X2 （00a1a1) ) (1-10

15、)(1-10)将（1-91-9）代入（1-101-10）得：bbbbxPxPxPxxPxPnjnjnjjjjjjjnjnjjjjjjaaaaaa1112211121)1 (所以 X X1 1CC，X X2 2CC。由于集合中任意两点连线上的点均在集合内，所以C C为凸集。第21页/共61页2022-7-222返回第22页/共61页2022-7-223定理定理2 2：线性规划的基本可行解对应于其线性规划的基本可行解对应于其可行域的顶点。可行域的顶点。证: :本定理需要证明:X:X是可行域顶点X X是基可行解。用反证法证明：X X不是可行域的顶点X X不是基可行解。（1 1）X X不是基可行解X

16、X不是可行域的顶点。假设X X的前m m个分量为正，有)11. 1 (1bxPnjjj第23页/共61页2022-7-224)2()1()2()1(2121,XXXCXCX，又引理第24页/共61页2022-7-225rjjjnjjjbxPxP11因有）（故有14. 111njrjjjjjbyPyP）（ 15. 111njrjjjjjbzPzP0)(1rjjjjPzy第25页/共61页2022-7-226是目标函数的最大值。njjjxcCXZ10)0(第26页/共61页2022-7-227：先找出一个基可行解，判断它是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直到求

17、得最优解或判断问题无解为止。)17. 1 (), 2 , 1(0)16. 1 (max11njxbxPxczjnjjjnjjj在约束条件（1.16）的系数矩阵中，总可以找到一个单位矩阵：第27页/共61页2022-7-228基阵基阵P1,P2,Pm称为，与其对应的变量x1,x2,xm称为，模型中的其它变量称为。在约束条件中令所有的非基变量等于零，即可得到一个解：X(x1,x2,xm,xm+1,xn)T（b1,b2, ,bm,0, ,0)T因b0，所以X满足非负约束，是一个基可行解。定义：定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。18. 1100010001,21mPPP

18、第28页/共61页2022-7-229设初始基可行解中的前设初始基可行解中的前m个为基变量为：个为基变量为：X(0)(x10,x20,xm0,0,，0)T将其代入约束条件（1.16）有19. 110bxPmiiimmnmjmmnjmnjmnjmmbaaabaaabaaabPPPPPP1,2221, 21111, 1121100010001miiijjPaP120101miiijjPaP或第29页/共61页2022-7-230miiijjPaP120. 101miiijjPaP21. 101miiijjPaP22. 110bPPaxjmiiijibxPnjjj124. 10min00ljliji

19、jiiaxaax第30页/共61页2022-7-231由式由式（1.24）知知因alj0，故由矩阵元素组成的行列式不为零，P1,P2,Pl-1,Pl,Pl+1,Pm是一个基。在上述增广矩阵中作初等变换，将第l行乘上（1/alj),再分别乘以（-aij)(i=1,2,l-1,l+1,m)加到各行去，则增广矩阵左半部分变成单位矩阵。)(,0)(,00liliaxiji所以，X(1)是一个可行解。与变量xl1,x1l-1,x1l+1,xm,xj对应的向量经重新排列后得mmjljllljljljjmlllbababababababPPPPPP000000100000000001000001000001

20、1, 11, 122111121又因又因bl/alj ，所以所以 b=(b1- a1j,bl-1- al-1,j,bl+1- al+1,j,bm- amj)T 由此由此X(1)是同是同X(0)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。第31页/共61页2022-7-232将基本可行解X(0)和X(1)分别代入目标函数得25. 11)0(11010)1(10)0(miijijmiijijmiiijmiijiimiiiacczaccxccaxczxcz式中，因为0,所以只要01miijijacc就有。或简写为通常将jjjmiijijzcacc

21、)(1第32页/共61页2022-7-233（1）当所有j0时，当前基可行解是线性规划问题的最优解；（2）当所有j0，若对某个非基变量xj有cjzj0,则该线性规划问题有无穷多个最优解；若对所有非基变量有j0，线性规划问题有唯一最优解。（3） 若存在j0，又Pj0，则表明线性规划问题有无界解。miijijjjjacczc1检验数：第33页/共61页2022-7-2341-4 1-4 单纯形法计算步骤单纯形法计算步骤第一步：求初始基可行解，列出初始单纯形表。第一步：求初始基可行解，列出初始单纯形表。cjc1 cmcjcnCB基bx1 xmxjxnc1x1b110a1ja1nc2x2b200a2j

22、a2n cmxmbm01amjamncjzj00miijijacc1miininacc1返回第一章目录返回第一章目录返回第一章目录第34页/共61页2022-7-235若单纯形表中所有检验数cjzj0，且基变量中不含有人工变量，则得到线性规划问题的最优解，计算结束；若存在cjzj0，而Pj0，则问题为无界解，计算结束；否则转下一步。1. 确定换入基的变量。只要有检验数j0，其对应的xj就可以作为换入基的变量，当有一个以上检验数大于零时，从中找出最大的一个k，其对应的变量xk为换入基的变量（简称换入变量）。2. 确定换出基的变量。用Pk列的系数分别去除常数项，找出最小比值0maxjjjj27.

23、10minlklikikiabaab确定xl为换出基的变量，元素alk 决定了从一个基可行解到相邻基可行解的转移去向，所以，称alk为主元。第35页/共61页2022-7-2363. 用换入变量用换入变量xk替换换出变量替换换出变量xl，作初等变换，作初等变换，得到一个新的单纯形表。得到一个新的单纯形表。初等变换的方法是： 用单纯形法求解线性规划问题0,524261552max212121221xxxxxxxxxz解：在约束方程中加松弛变量，将该线性规划问题化为标准形式5 , 2 , 10524261550002max5214213254321jxxxxxxxxxxxxxxzj其约束条件系数矩

24、阵的增广矩阵为：51001124010261500150P1P2P3P4bP5基变量为x3、x4、x5 ；非基变量为x1、x2。单位矩阵构成一个基第36页/共61页2022-7-237令非基变量令非基变量x1、x2等于零，的初始基本可行解为：等于零，的初始基本可行解为：X(0)(0,0,15,24,5)T初始单纯形表cj 21000CB基bx1x2x3x4x50 x315051000 x424620100 x5511001cjzj210005 , 2 , 10524261550002max5214213254321jxxxxxxxxxxxxxxzj因为存在120，210。所以初始基可行解不是最

25、优解。选择最大检验数对应的非基变量作为换入变量。求最小比值，确定换入变量。主元列462415,624,min主元行第37页/共61页2022-7-238迭代运算x3x1x5020141/301/60015510006161012456113261212/30616110-1/610623103131211/30-1/3023321,314,515mini第38页/共61页2022-7-239迭代运算第二次迭代的单纯形表cj 21000CB基bx1x2x3x4x5cjzjx3x1x2021103/204132)61(-1/43/2021323101210112721147/204121)61(6

26、11/4-1/202153250021521511515/2145215)61(05/4-15/20)000112(2)(313212111111acacaccacczcmiijijjjj00)001102(1)(323222121221acacaccacczcmiijijjjj0041450)41(14120)(343242141441acacaccacczcmiijijjjj-1/421)215(0)23(1)21(20)(353252151551acacaccacczcmiijijjjj-1/2第39页/共61页2022-7-240迭代运算结迭代运算结果果因为所有检验数j0，且基变量中不

27、含人工变量，所以得到线性规划问题的最优解为：TX0 , 0 ,215,23,27代入目标函数得：21723272221xxz第40页/共61页2022-7-2411-5 单纯形法的进一步讨论线性规划模型化为标准形式后，若其约束条件的系数矩阵中不含有单位矩阵，需加人工变量，以便求解。 用单纯形法求解线性规划问题0,431243max3213232132131xxxxxxxxxxxxxz0,)32. 1 (43)32. 1 (12)32. 1 (4003max32132532143215431xxxcxxbxxxxaxxxxxxxxz)7 , 2 , 1(043124003max732653214

28、321765431jxxxxxxxxxxxxxMxMxxxxxzj100010001P4P6P7人工变量返回第一章目录返回第一章目录返回第一章目录第41页/共61页2022-7-242单纯形法求解过程1-21-10-110033211-100313063)2(0631966403-3113030(2)+(M)66M36M3200001+(M)00031020(1)+(M)44M14M1400100+(M)00050010(1)+(M)33M3M6M0(1)01+(M)(3)4M4M7M0000+(M)100第42页/共61页2022-7-243单纯形法求解过程1102/301/2-1/21/6

29、0)31(6203)31(6131)31(01131)31(411/300)31(3100)31()3(1031)31(101/3021630000214201212131-1/22121)3(11/2212110-1/20 1) 3(00003100 0) 3(1000020332)3(3100013300)3(00100402321)3(00)21(0053/223)21()3(2102106MM2161)3(3102107MM-M-3/2-M+1/2第43页/共61页2022-7-244单纯形法求解过程单纯形法求解过程103/23/203/4-3/41/4021323101-1/2252

30、1135/204121210-1/44121)21(01/4412161311/400001-1/21/2-1/20293230029000292910-9/202900043292123-3/44329)21()23(MM-M+3/4412961)21(MM-M-1/4所有检验数均0，且人工变量为零，得到问题的最优解。X(0,5/2,3/2,0,0)T; z3x1x33/2两阶段法第44页/共61页2022-7-245检验数计算320)2(1037176164141)7, 6, 4111MMMacacaccaccaccacczciijisiijijmiijijjjjMMMacacaccacc

31、accacczciijisiijijmiijijjjj4)3() 1(1007276264242)7, 6, 4221MMMacacaccaccaccacczciijisiijijmiijijjjj)0()1(0007576564545)7, 6, 4551单单单纯纯纯形形形法法法求求求解解解过过过程程程第45页/共61页2022-7-246第46页/共61页2022-7-247用两阶段法求解线性规划问题)7 , 2 , 1(0931243max73265321432131jxxxxxxxxxxxxxxxzj)7 , 2 , 1(093124min73265321432176jxxxxxxxx

32、xxxxxxxwj)7 , 2 , 1(093124min732653214321761jxxxxxxxxxxxxxxxwj第47页/共61页2022-7-248表 1 -11表1-12第48页/共61页2022-7-249表 1 -12-3010000303/2x4x2x3001103/403/23/201-1/25/200001-1/20-1/4-9/2000-3/4因为所有j0,所以得到问题的最优解为：X=(0,5/2,3/2,0,5)T; z（-3）03/23/2表1-11第49页/共61页2022-7-250三、单纯形法计算中的几个问题三、单纯形法计算中的几个问题1. 目标函数极小化

33、时解的判别目标函数极小化时解的判别。以所有检验数j0作为判别表中解是否最优的标志，或将其化为极大化问题求解。2. 退化。按最小比值确定换出变量时，有时同时出现两个相同的最小值，从而使下一个表的基可行解出现一个或多个基变量等于0的退化解。原因：是模型中存在多余的约束，使多个基可行解对应同一顶点。存在退化解，就可能出现迭代运算循环。解决办法：在同等条件下，始终选择下标值最小的变量作为换入变量，下标值最大的变量作为换出变量。3. 无可行解的判别。求解过程中，若出现所有检验数j0，而基变量中仍含有非零的人工变量，表明问题无解。第50页/共61页2022-7-2510,62222max21212121x

34、xxxxxxxz)5 , 2 , 1(06222002max542132154321jxxxxxxxxMxxxxxzj标准化加人工变量cj2100-MCB基 bx1x2x3x4x50 x3211100-Mx56220-11cj-zj2+2M1+2M0-M02x1-Mx5cj-zj121100020-2-1100-2-2M-M0第51页/共61页2022-7-252四、单纯形法小结四、单纯形法小结1. 一般线性规划模型化为标准形式的方法线性规划模型化为标准形式变量xj0不变xj0令xj xj ，则 xj0 xj无约束令xj xj xj； xj0， xj0约束条件右端项bi0不变bi0约束条件两端

35、乘“-1”形式bixsibibixaibibixsixaibi目标函数极大或极小max z 不变min z 令zz，化为求max z变量前的系数加松弛变量xs时max z0 xsi加人工变量xa时max zMxainjjijxa1njjijxa1njjjxc1njjjxc1第52页/共61页2022-7-253Y单纯形法计算步骤框单纯形法计算步骤框图图找出初始基可行解列出初始单纯形表计算检验数j所有j0对某一j0有Pj0 为换入变量kjjkxmax为换出变量为主元，设llklklikikixaabaab0min迭代运算1. 用xk替换xl2.列出新的单纯形表将主元化为1，主元所在列的其他元素化

36、为0。无界解基变量中含非零的人工变量存在非基变量检验数为零无可行解无穷多最优解唯一最优解NNYYNYN第53页/共61页2022-7-254用长8m 的角钢切割钢窗用料。每付钢窗含1.5m的料2根，1.45m的2根，1.3m的6根，0.35m的12根。若需钢窗用料100付，问最少需切割8m长的角钢多少根？试建立其线性规划数学模型。解：为了节省材料，可以考虑各种套裁下料方案（见下表）。 方案 规格 所需材料根数 1.5 1 1 2 1 4 3 0 0 0 2100=200 1.45 1 4 2 0 0 0 0 3 1 2100=200 1.3 2 0 0 5 1 0 4 2 1 6100=600 0.35 7 2 6 0 2 10 8 3 15 12100=1200 合计 8 8 8 8 8 8 8 8 8 料头 0 0 0 0 0 0 0 0 0 x2x1x3x4x5x6x7x8x9假设变量第54页/共61页2022-7-255假设按表列九个方案切割假设按表列九个方案切割8 8m m长的角钢长的角钢分别为分别为x1,x2,x3,x4,x5,x6,x7,x8,x9根。则该线根。则该线性规划问题的数学模型为：性规划问题的数学模型为：求一组决策变量xj( j =1,2,9 )满足约束条件)9 , 2 , 1(0120015381026276002452200324200342