单纯形法求解优秀PPT.ppt

单纯形法求解2022/10/15第1页，本讲稿共28页LP的基本定理的基本定理定义定义 凸集（凸集（convex set），顶点（极点），顶点（极点corner point ）定理定理1：线性规划问题的可行域是凸集：线性规划问题的可行域是凸集定理定理2：线性规划问题的最优解在极点上：线性规划问题的最优解在极点上定理定理3：若：若LP问题有最优解，一定存在一个基可行问题有最优解，一定存在一个基可行解是最优解。解是最优解。凸集凸集凸集凸集不是凸集不是凸集极点极点第2页，本讲稿共28页单纯形表单纯形表 基变量基变量 C1 C2 Cm Cm+1 Cm+k Cn X1 X2 Xm Xm+1 Xm+k XnCB XB -Z0 0 0 0 m+1 m+k nC1 X1 b1 1 0 0 a1m+1 a1m+k a1nC2 X2 b2 0 1 0 a2m+1 a2m+k a2nCr Xr br 0 0 0 arm+1 arm+k arnCm Xm bm 0 0 1 amm+1 amm+k amn第3页，本讲稿共28页maxZ=40X1+50X2 X1+2X2+X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 0 0（2）列（初始）单纯形表）列（初始）单纯形表引例用单纯形法求解生产计划问题。引例用单纯形法求解生产计划问题。解：解：（1）化标准型）化标准型第4页，本讲稿共28页 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 0 40 40 50 50 0 0 00 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X4 6060 3 3 2 0 1 0 2 0 1 0 30300 0 X5 24 0 2 0 0 1 24 0 2 0 0 1 1212 XB 600600 40 40 0 0 0 -25 0 0 0 -250 0 X3 6 6 11 0 1 0 -1 0 1 0 -1 6 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840840 0 0 -40 0 0 0 -40 0 151540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4 18 0 0 -3 1 18 0 0 -3 1 22 9 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24第5页，本讲稿共28页 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 0 40 40 50 50 0 0 00 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X4 6060 3 3 2 0 1 0 2 0 1 0 30300 0 X5 24 0 2 0 0 1 24 0 2 0 0 1 1212 XB 600600 4040 0 0 0 -25 0 0 0 -250 0 X3 6 6 11 0 1 0 -1 0 1 0 -1 6 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840840 0 0 -40 0 0 0 -40 0 151540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4 18 0 0 -3 1 18 0 0 -3 1 2 92 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24第6页，本讲稿共28页 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 0 40 40 50 50 0 0 00 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X4 6060 3 3 2 0 1 0 2 0 1 0 30300 0 X5 24 0 24 0 22 0 0 1 0 0 1 1212 XB 600600 40 40 0 0 0 -25 0 0 0 -250 0 X3 6 6 11 0 1 0 -1 0 1 0 -1 6 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 840840 0 0 -40 0 0 0 -40 0 151540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4 18 0 0 -3 1 18 0 0 -3 1 22 9 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24第7页，本讲稿共28页 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 0 40 40 50 50 0 0 00 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X4 6060 3 3 2 0 1 0 2 0 1 0 30300 0 X5 24 0 24 0 22 0 0 1 0 0 1 1212 XB -600-600 40 40 0 0 0 -25 0 0 0 -250 0 X3 6 6 11 0 1 0 -1 0 1 0 -1 6 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 -840-840 0 0 -40 0 0 0 -40 0 151540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4 18 0 0 -3 1 18 0 0 -3 1 2 92 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24第8页，本讲稿共28页 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 0 40 40 50 50 0 0 00 0 0 0 0 X3 30 1 2 1 0 0 15 30 1 2 1 0 0 150 0 X4 6060 3 3 2 0 1 0 2 0 1 0 30300 0 X5 24 0 24 0 22 0 0 1 0 0 1 1212 XB -600-600 40 40 0 0 0 -25 0 0 0 -250 0 X3 6 6 11 0 1 0 -1 0 1 0 -1 6 60 0 X4 36 3 0 0 1 -1 1236 3 0 0 1 -1 1250 50 X2 12 0 1 0 0 1/2 12 0 1 0 0 1/2 -840-840 0 0 -40 0 0 0 -40 0 151540 40 X1 6 1 0 1 0 -16 1 0 1 0 -10 0 X4 18 0 0 -3 1 18 0 0 -3 1 22 9 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24第9页，本讲稿共28页 XB -975-975 0 0 -35/2 -15/2 0 0 0 -35/2 -15/2 040 40 X1 15 1 0 -1/2 1/2 0 15 1 0 -1/2 1/2 0 0 0 X5 9 0 0 -3/2 1/2 1 9 0 0 -3/2 1/2 1 50 50 X2 15/2 0 1 3/4 -1/4 0 15/2 0 1 3/4 -1/4 0(3)本问题的最优解本问题的最优解 X=(X1,X2,X3,X4,X5)T =(15,15/2,0,0,9)T且且Z=975.X3,X4=0表示资源表示资源1，2用完用完,X5=9表示资源表示资源3剩余剩余9.图解分析见下。图解分析见下。第10页，本讲稿共28页0(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)从一个基可行解到另一个基可行解从一个基可行解到另一个基可行解第11页，本讲稿共28页单纯形法基本步骤单纯形法基本步骤(1)、定初始基，初始基本可行解、定初始基，初始基本可行解(3)、若有若有 k 0 0，Pk全全 0，停，停，没有有限最优解；没有有限最优解；否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全全 0。若是，停，得到最优解；若是，停，得到最优解；若否，转若否，转(3)。第12页，本讲稿共28页=min aim+k 0 =0 =biaim+kbrarm+k定定X Xr为换出变量，为换出变量，a arm+k为主元。为主元。由最小由最小比值法求：比值法求：maxmax j=m+kXm+k 换入变量换入变量 j00(4)、第13页，本讲稿共28页转转(2)(2)m+k 0 a1m+k 0arm+k 1amm+k 0初等行变换初等行变换Pm+k=(5)、以、以a arm+k为中心，换基迭代为中心，换基迭代第14页，本讲稿共28页单纯形法的进一步讨论（简介）单纯形法的进一步讨论（简介）(一一)、大、大M法法 the Big M Method 初始基本可行解的求法初始基本可行解的求法 -加入人工变量加入人工变量 大大M使人工变量使人工变量-0第15页，本讲稿共28页例：用大例：用大 M M 法求解下列问题。法求解下列问题。maxZ=6X1+4X2 2X1+3X2 1004X1+2X2 120 X1 =14 X2 22X1 X2 0第16页，本讲稿共28页解解：（1）化标准型化标准型maxZ=6X1+4X22X1+3X2+X3 =1004X1+2X2 +X4 =120 X1 =14 X2 -X5 =22X1 X5 0第17页，本讲稿共28页（2）加人工变量）加人工变量X6，X7，问题化为问题化为maxZ=6X1+4X2-MX6-MX72X1+3X2+X3 =1004X1+2X2 +X4 =120 X1 +X6 =14 X2 -X5 +X7=22X1 X7 0（3）单纯形求解单纯形求解判定无解条件：当进行到最优表时，仍有人工变量在基判定无解条件：当进行到最优表时，仍有人工变量在基中，且中，且0，则说明原问题无可行解。则说明原问题无可行解。第18页，本讲稿共28页原问题原问题 maxZ=Cj xj j=1n xj 0j=1n aij xj=bi(i=1,2,m)(二二)、两阶段法、两阶段法 The Two-phase Method第19页，本讲稿共28页作辅助问题作辅助问题 minW=yi i=1m Xj，yi 0j=1n aij xj+yi=bi(i=1,2,m)解题过程：解题过程：第第1 1阶段：解辅助问题阶段：解辅助问题当进行到最优表时，当进行到最优表时，、若、若W=0,则得到原问则得到原问题的一个基本可行解，转入第题的一个基本可行解，转入第2阶段。阶段。、若若W0,则判定原问题无可行解。则判定原问题无可行解。第20页，本讲稿共28页第第1 1阶段的任务是将人工变量尽快迭代出去，阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行从而找到一个没有人工变量的基础可行解解第第2 2阶段：阶段：以第一阶段得到的基础可行解为初始解，以第一阶段得到的基础可行解为初始解，采用原单纯型法求解采用原单纯型法求解第21页，本讲稿共28页两阶段法原理：两阶段法原理：(1)、辅助问题的基本可行解、辅助问题的基本可行解X(0)为最优解，对应为最优解，对应最小值最小值=0 则则X(0)的前的前n个分量是原问题的基本可行解。个分量是原问题的基本可行解。第22页，本讲稿共28页小结与应用举例 小结应用举例第23页，本讲稿共28页(1)(1)、LPLP数学模型及标准型数学模型及标准型maxZ=CXAX=b(b 0)X 0(2)(2)、LPLP问题解的性质：图解法分析问题解的性质：图解法分析小结第24页，本讲稿共28页(3)(3)、单纯形法：、单纯形法：1)1)、标准型中有单位基。、标准型中有单位基。2)2)、标准型中没有单位基，用大、标准型中没有单位基，用大M M法加人工变法加人工变量，使之构成单位基。量，使之构成单位基。求求maxZ时，目标中时，目标中M MXj 求求minZ时，目标中时，目标中M MXj3)3)、判定最优解定理：、判定最优解定理：maxZ问题，检验数问题，检验数 j 0minZ问题，检验数问题，检验数 j 0第25页，本讲稿共28页4)4)、解的几种情况：、解的几种情况：唯一解唯一解无穷多解无穷多解 （多重解（多重解 ）无有限最优解无有限最优解 （无界解）（无界解）无可行解无可行解第26页，本讲稿共28页多重解多重解多个解都是最优解，这些解在同一个超平面多个解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行上，且该平面与目标函数等值面平行最优单纯型表中有非基变量的检验数为最优单纯型表中有非基变量的检验数为0最优解的线性组合仍是最优解，即最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=1第27页，本讲稿共28页无界解无界解可行区域不闭合可行区域不闭合(缺约束条件缺约束条件)单纯型表中入变量单纯型表中入变量 x j*对应的列中所有对应的列中所有无可行解无可行解约束条件互相矛盾，无可行域约束条件互相矛盾，无可行域单纯型表达到最优解检验条件时，人工变量仍在基变量单纯型表达到最优解检验条件时，人工变量仍在基变量中中第28页，本讲稿共28页