《单纯形法求解PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《单纯形法求解PPT讲稿.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、单纯形法求解2023/4/18第1页，共28页，编辑于2022年，星期五LP的基本定理的基本定理定义定义 凸集（凸集（convex set），顶点（极点），顶点（极点corner point ）定理定理1：线性规划问题的可行域是凸集：线性规划问题的可行域是凸集定理定理2：线性规划问题的最优解在极点上：线性规划问题的最优解在极点上定理定理3：若：若LP问题有最优解，一定存在一个基可行问题有最优解，一定存在一个基可行解是最优解。解是最优解。凸集凸集凸集凸集不是凸集不是凸集极点极点第2页，共28页，编辑于2022年，星期五单纯形表单纯形表 基变量基变量 C1 C2 Cm Cm+1 Cm+k Cn X
2、1 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页，编辑于2022年，星期五maxZ=40X1+50X2 X1+2X2+X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 0 0（2）列（初始）单纯形表）列（初始）单纯形表引例用单纯形法求解生产计划问题。引例用单纯形法求解生产
3、计划问题。解：解：（1）化标准型）化标准型第4页，共28页，编辑于2022年，星期五 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
4、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页，编辑于2022年，星期五 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 0 40 40 50 50
5、 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 15
6、1540 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页，编辑于2022年，星期五 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
7、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
8、 1 0 0 1/2 24第7页，共28页，编辑于2022年，星期五 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
9、 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页，编辑于2022年，星期五 40 50 0 0 0 40 50 0 0 0 X1 X2 X3 X4 X5CB XB 0 0 40 40 50 50 0 0
10、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 151
11、540 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页，编辑于2022年，星期五 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 1
12、5/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页，编辑于2022年，星期五0(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)从一个基可行解到另一个基可行解从一个基可行解到另一个基可行解第11页，共28页，编辑于2022年，星期五单纯形法基本步骤单纯形法基本步骤(1)、定初始基，初始基本可行解、定初始基，
13、初始基本可行解(3)、若有若有 k 0 0，Pk全全 0，停，停，没有有限最优解；没有有限最优解；否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数 j全全 0。若是，停，得到最优解；若是，停，得到最优解；若否，转若否，转(3)。第12页，共28页，编辑于2022年，星期五=min aim+k 0 =0 =biaim+kbrarm+k定定X Xr为换出变量，为换出变量，a arm+k为主元。为主元。由最小由最小比值法求：比值法求：maxmax j=m+kXm+k 换入变量换入变量 j00(4)、第13页，共28页，编辑于2022年，星期五转转(2)(2)m+k 0 a1m+k
14、 0arm+k 1amm+k 0初等行变换初等行变换Pm+k=(5)、以、以a arm+k为中心，换基迭代为中心，换基迭代第14页，共28页，编辑于2022年，星期五单纯形法的进一步讨论（简介）单纯形法的进一步讨论（简介）(一一)、大、大M法法 the Big M Method 初始基本可行解的求法初始基本可行解的求法 -加入人工变量加入人工变量 大大M使人工变量使人工变量-0第15页，共28页，编辑于2022年，星期五例：用大例：用大 M M 法求解下列问题。法求解下列问题。maxZ=6X1+4X2 2X1+3X2 1004X1+2X2 120 X1 =14 X2 22X1 X2 0第16页
15、，共28页，编辑于2022年，星期五解解：（1）化标准型化标准型maxZ=6X1+4X22X1+3X2+X3 =1004X1+2X2 +X4 =120 X1 =14 X2 -X5 =22X1 X5 0第17页，共28页，编辑于2022年，星期五（2）加人工变量）加人工变量X6，X7，问题化为问题化为maxZ=6X1+4X2-MX6-MX72X1+3X2+X3 =1004X1+2X2 +X4 =120 X1 +X6 =14 X2 -X5 +X7=22X1 X7 0（3）单纯形求解单纯形求解判定无解条件：当进行到最优表时，仍有人工变量在基判定无解条件：当进行到最优表时，仍有人工变量在基中，且中，且
16、0，则说明原问题无可行解。则说明原问题无可行解。第18页，共28页，编辑于2022年，星期五原问题原问题 maxZ=Cj xj j=1n xj 0j=1n aij xj=bi(i=1,2,m)(二二)、两阶段法、两阶段法 The Two-phase Method第19页，共28页，编辑于2022年，星期五作辅助问题作辅助问题 minW=yi i=1m Xj，yi 0j=1n aij xj+yi=bi(i=1,2,m)解题过程：解题过程：第第1 1阶段：解辅助问题阶段：解辅助问题当进行到最优表时，当进行到最优表时，、若、若W=0,则得到原则得到原问题的一个基本可行解，转入第问题的一个基本可行解，
17、转入第2阶段。阶段。、若若W0,则判定原问题无可行解。则判定原问题无可行解。第20页，共28页，编辑于2022年，星期五第第1 1阶段的任务是将人工变量尽快迭代出去，阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行从而找到一个没有人工变量的基础可行解解第第2 2阶段：阶段：以第一阶段得到的基础可行解为初始解，以第一阶段得到的基础可行解为初始解，采用原单纯型法求解采用原单纯型法求解第21页，共28页，编辑于2022年，星期五两阶段法原理：两阶段法原理：(1)、辅助问题的基本可行解、辅助问题的基本可行解X(0)为最优解，对应为最优解，对应最小值最小值=0 则则X(0)的前的前
18、n个分量是原问题的基本可行解。个分量是原问题的基本可行解。第22页，共28页，编辑于2022年，星期五小结与应用举例 小结应用举例第23页，共28页，编辑于2022年，星期五(1)(1)、LPLP数学模型及标准型数学模型及标准型maxZ=CXAX=b(b 0)X 0(2)(2)、LPLP问题解的性质：图解法分析问题解的性质：图解法分析小结第24页，共28页，编辑于2022年，星期五(3)(3)、单纯形法：、单纯形法：1)1)、标准型中有单位基。、标准型中有单位基。2)2)、标准型中没有单位基，用大、标准型中没有单位基，用大M M法加人工变法加人工变量，使之构成单位基。量，使之构成单位基。求求m
19、axZ时，目标中时，目标中M MXj 求求minZ时，目标中时，目标中M MXj3)3)、判定最优解定理：、判定最优解定理：maxZ问题，检验数问题，检验数 j 0minZ问题，检验数问题，检验数 j 0第25页，共28页，编辑于2022年，星期五4)4)、解的几种情况：、解的几种情况：唯一解唯一解无穷多解无穷多解 （多重解（多重解 ）无有限最优解无有限最优解 （无界解）（无界解）无可行解无可行解第26页，共28页，编辑于2022年，星期五多重解多重解多个解都是最优解，这些解在同一个超平多个解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行面上，且该平面与目标函数等值面平行最优单纯型表中有非基变量的检验数为最优单纯型表中有非基变量的检验数为0最优解的线性组合仍是最优解，即最优解的线性组合仍是最优解，即 X=aX1+bX2，a+b=1第27页，共28页，编辑于2022年，星期五无界解无界解可行区域不闭合可行区域不闭合(缺约束条件缺约束条件)单纯型表中入变量单纯型表中入变量 x j*对应的列中所有对应的列中所有无可行解无可行解约束条件互相矛盾，无可行域约束条件互相矛盾，无可行域单纯型表达到最优解检验条件时，人工变量仍在基变量中单纯型表达到最优解检验条件时，人工变量仍在基变量中第28页，共28页，编辑于2022年，星期五