单纯形法求解课件.ppt

上传人(卖家):三亚风情 文档编号:2279215 上传时间:2022-03-29 格式:PPT 页数:26 大小:434KB
下载 相关 举报
单纯形法求解课件.ppt_第1页
第1页 / 共26页
单纯形法求解课件.ppt_第2页
第2页 / 共26页
单纯形法求解课件.ppt_第3页
第3页 / 共26页
单纯形法求解课件.ppt_第4页
第4页 / 共26页
单纯形法求解课件.ppt_第5页
第5页 / 共26页
点击查看更多>>
资源描述

1、LP的基本定理的基本定理定义定义 凸集(凸集(convex set),顶点(极点),顶点(极点corner point )定理定理1:线性规划问题的可行域是凸集:线性规划问题的可行域是凸集定理定理2:线性规划问题的最优解在极点上:线性规划问题的最优解在极点上定理定理3:若:若LP问题有最优解,一定存在一个基可行问题有最优解,一定存在一个基可行解是最优解。解是最优解。凸集凸集凸集凸集不是凸集不是凸集极点极点单纯形表单纯形表 基变量基变量 miiibCZ10miijijjaCC1 C1 C2 Cm Cm+1 Cm+k Cn X1 X2 Xm Xm+1 Xm+k XnCB XB -Z0 0 0 0

2、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 amnmaxZ=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

3、 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 302 0 1 0 300 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/

4、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 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 302 0 1 0 300 0 X5

5、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

6、/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 302 0 1 0 300 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 123

7、6 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 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

8、 1 0 0 150 0 X4 6060 3 3 2 0 1 0 302 0 1 0 300 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

9、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 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 302 0 1 0 300 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

10、 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 XB -975 -975 0 0 -35/2 -15/2 0 0 0 -35/2

11、 -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 1

12、A 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为主元。为主元。由最小由

13、最小比值法求:比值法求:maxmax j = m+kXm+k 换入变量换入变量 j00(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 1004X

14、1 +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)单纯形求解)单纯形求解判定无解条件:当进行到最优表时,仍有人工变量在基判定无解条件:当进行到

15、最优表时,仍有人工变量在基中,且中,且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阶段。阶段

16、。 、若若W0, 则判定原问题无可行解。则判定原问题无可行解。第第1 1阶段的任务是将人工变量尽快迭代出去,阶段的任务是将人工变量尽快迭代出去,从而找到一个没有人工变量的基础可行从而找到一个没有人工变量的基础可行解解第第2 2阶段:阶段:以第一阶段得到的基础可行解为初始解,以第一阶段得到的基础可行解为初始解,采用原单纯型法求解采用原单纯型法求解两阶段法原理:两阶段法原理:(1)、辅助问题的基本可行解、辅助问题的基本可行解X(0) 为最优解,对应为最优解,对应最小值最小值 =0 则则X(0) 的前的前n个分量是原问题的基本可行解。个分量是原问题的基本可行解。小结与应用举例 小结应用举例(1)(1

17、)、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 04)4)、解的几种情况:、解的几种情况:唯一解唯一解无穷多解无穷多解 (多重解(多重解 )无有限最优解无有限最优解 (无界解)(无界解)无可行解无可行解多重解多重解 多个解都是最优解,这些解在同一个多个解都是最优解,这些解在同一个超平面上,且该平面与目标函数等值超平面上,且该平面与目标函数等值面平行面平行 最优单纯型表中有非基变量的检验数最优单纯型表中有非基变量的检验数为为0 最优解的线性组合仍是最优解,即最优解的线性组合仍是最优解,即 X=aX1+bX2,a+b=1

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(单纯形法求解课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|