单纯形法求解课件.ppt

LP的基本定理的基本定理定义定义 凸集（凸集（convex set），顶点（极点），顶点（极点corner point ））●定理定理1：线性规划问题的可行域是凸集：线性规划问题的可行域是凸集●定理定理2：线性规划问题的最优解在极点上：线性规划问题的最优解在极点上●定理定理3：若：若LP问题有最优解，一定存在一个基可行问题有最优解，一定存在一个基可行解是最优解解是最优解凸集凸集凸集凸集不是凸集不是凸集极点极点单纯形表单纯形表 基变量基变量 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……………………………………maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 … X5  0 0（（2）列（初始）单纯形表）列（初始）单纯形表引例用单纯形法求解生产计划问题。

引例用单纯形法求解生产计划问题解：解： （（1）化标准型）化标准型 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 [1][1] 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][2] 9 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24 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 [1][1] 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] 9[2] 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24 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 [2][2] 0 0 1 0 0 1 1212 XB 600600 40 40 0 0 0 -25 0 0 0 -250 0 X3 6 6 [1][1] 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][2] 9 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24 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 [2][2] 0 0 1 0 0 1 1212 XB -600-600 40 40 0 0 0 -25 0 0 0 -250 0 X3 6 6 [1][1] 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] 9[2] 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24 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 [2][2] 0 0 1 0 0 1 1212 XB -600-600 40 40 0 0 0 -25 0 0 0 -250 0 X3 6 6 [1][1] 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][2] 9 950 50 X2 12 0 1 0 0 1/2 24 12 0 1 0 0 1/2 24 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.图解分析见下。

图解分析见下0(0,0)X X2 2X X1 1A A D DC CB B(0,12)(6,12)(15,7.5)从一个基可行解到另一个基可行解从一个基可行解到另一个基可行解单纯形法基本步骤单纯形法基本步骤(1)、定初始基，初始基本可行解、定初始基，初始基本可行解(3)、、若有若有  k > >0 0，，Pk全全  0，，停，停， 没有有限最优解；没有有限最优解； 否则转否则转(4)(2)、对应于非基变量检验数、对应于非基变量检验数  j全全  0 若是，停，得到最优解；若是，停，得到最优解； 若否，转若否，转(3)θ= θ= min aim+k > >0 =0 =biaim+kbrarm+k定定X Xr为换出变量，为换出变量，a arm+k为主元由最小由最小θθ比值法求：比值法求：maxmax j =   m+k→Xm+k 换入变量换入变量  j>0>0(4)、、转转(2) (2)   m+k 0 …… ……a1m+k 0arm+k 1amm+k 0初等行变换初等行变换Pm+k = =…………(5)、以、以a arm+k为中心，换基迭代为中心，换基迭代单纯形法的进一步讨论（简介）单纯形法的进一步讨论（简介）(一一)、大、大M法法 the Big M Method 初始基本可行解的求法初始基本可行解的求法 ---------- 加入人工变量加入人工变量 大大M使人工变量使人工变量 -------- 0例：用大例：用大 M M 法求解下列问题。

法求解下列问题maxZ= 6X1 +4X2 2X1 +3X2   1004X1 +2X2   120 X1 = =14 X2   22X1 X2  0解解：： （（1））化标准型化标准型maxZ=6X1+4X22X1 +3X2 +X3 = =1004X1 +2X2 +X4 = =120 X1 = =14 X2 - X5 = 22X1 … X5  0（（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，，则说明原问题无可行解。

则说明原问题无可行解原问题原问题 maxZ= Cj xj j=1n xj   0j=1n aij xj =bi ( i=1,2, …,m)(二二)、两阶段法、两阶段法 The Two-phase Method作辅助问题作辅助问题 minW= yi i=1m Xj ，， yi   0j=1n aij xj + yi =bi ( i=1,2, …,m)解题过程：解题过程：第第1 1阶段：解辅助问题阶段：解辅助问题当进行到最优表时，当进行到最优表时，①①、若、若W=0, 则得到原则得到原问题的一个基本可行解，转入第问题的一个基本可行解，转入第2阶段 ②②、、若若W>0, 则判定原问题无可行解则判定原问题无可行解第第1 1阶段的任务是将人工变量尽快迭代出去，阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行从而找到一个没有人工变量的基础可行解解第第2 2阶段：阶段：以第一阶段得到的基础可行解为初始解，以第一阶段得到的基础可行解为初始解，采用原单纯型法求解采用原单纯型法求解两阶段法原理：两阶段法原理：(1)、辅助问题的基本可行解、辅助问题的基本可行解X(0) 为最优解，对为最优解，对应应最小值最小值 =0 则则X(0) 的前的前n个分量是原问题的基本可行解。

个分量是原问题的基本可行解小结与应用举例 小结应用举例(1)(1)、、LPLP数学模型及标准型数学模型及标准型maxZ=CXAX=b (b 0) )X 0(2)(2)、、LPLP问题解的性质：图解法分析问题解的性质：图解法分析小结(3)(3)、单纯形法：、单纯形法：1)1)、标准型中有单位基标准型中有单位基2)2)、标准型中没有单位基，用大、标准型中没有单位基，用大M M法加人工变法加人工变量，使之构成单位基量，使之构成单位基 求求maxZ时，目标中－时，目标中－M MXj 求求minZ时，目标中＋时，目标中＋M MXj3)3)、判定最优解定理：、判定最优解定理：maxZ问题，检验数问题，检验数  j   0minZ问题，检验数问题，检验数  j  04)4)、解的几种情况：、解的几种情况：唯一解唯一解无穷多解无穷多解 （多重解（多重解 ））无有限最优解无有限最优解 （无界解）（无界解）无可行解无可行解多重解多重解–多个解都是最优解，这些解在同一个多个解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值超平面上，且该平面与目标函数等值面平行面平行–最优单纯型表中有非基变量的检验数最优单纯型表中有非基变量的检验数为为0–最优解的线性组合仍是最优解，即最优解的线性组合仍是最优解，即 X=aX1+bX2，，a+b=1。