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