《线性规划及单纯形法优秀课件》由会员分享,可在线阅读,更多相关《线性规划及单纯形法优秀课件(75页珍藏版)》请在金锄头文库上搜索。
1、第1章 线性规划及单纯形法姚明臣2011年3月线性规划及单纯形法优秀课件 All rights reserved本次课程要求掌握的内容n会建立简单的线性规划问题的数学模型;n理解并记忆线性规划模型的各种形式;1.分量形式2.向量形式3.矩阵形式n会将一般线性规划模型化成标准型;n有关线性规划问题解的若干重要概念可行解、最优解、基、基(本)解、基可行解等。n熟练掌握含两个决策变量问题的图解法;n凸集的相关概念和单纯形法若干基本定理。8/14/202421 线性问题的数学模型n问题的提出 例1. 用一块边长为a的正方形铁皮做一个容器,应如何裁剪,才能使做成容器的容积最大?ax解:利用高等数学的知识
2、V=(a - 2x)2 x求 V(x) 的最大值即可。 问题?8/14/20243线性规划的数学模型n问题的提出 例2(生产计划安排,要求利润最大)n解:设在计划期内生产产品I和产品II分别为x1和x2件(决策变量)n目标是要使 z = 2 x1 + 3 x2达到最大。(目标函数)n限制条件是:(约束条件)2x1 + 2x2 12 和2x1 16 以及 5x2 15要求 x1, x2 0 加工设备ABC单件利润产品 I2402元产品 II2053元设备时限12h16h15h8/14/20244线性规划的数学模型n问题的提出 例子之三(合理下料问题)现有一批10m长的贵重钢筋,需要截取3m和4m
3、长的钢筋各50根,试问如何截取,才能使原料最省?n问题分析:先确定截取方案建立数学规划模型n问题:模型是否有别的形式?截取方案IIIIII3m钢筋2304m钢筋102废料长0m1m2m8/14/20245线性规划问题数学模型的定义n线性规划模型组成的三要素:决策变量目标函数约束条件n定义1 在线性规划数学模型中,如果决策变量为可控的连续变量,目标函数和约束条件都是线性的,称这类模型为线性规划问题的数学模型。n问题:例一中的问题是否为线性规划模型?8/14/20246线性规划问题数学模型的一般形式n关于幻灯片中的数学符号:小写斜体字母表示实数,如a,b,c,x,x1,y,z等小写黑体字母表示向量
4、,如x,y,z等大写黑体字母表示矩阵,如 A, B,C等n线性规划(LP)数学模型的一般形式或8/14/20247线性规划数学模型向量和矩阵形式n(LP)向量形式n(LP)矩阵形式8/14/20248线性规划问题的标准形式n什么是(LP)问题的标准形式?满足如下条件:目标函数是求极大值;约束条件全为等式;bi和xj全为非负数。8/14/20249(LP)一般形式向标准形式的转化n(LP)一般形式向标准形转化的情况:目标函数是求极小值;约束条件为不等式“”的情形(松弛变量,例2);约束条件为不等式“” 的情形(剩余变量,例3);取值无约束的变量;某个变量 xj 0问题:某个变量有上下界限制,比如
5、l xj u,如何处理?n例3. 见书P12。8/14/202410线性规划问题解的若干重要概念n线性规划问题的任务从满足约束条件(2)和非负条件(3)的方程组中,找到使目标函数(1)取得最大值的解。n可行解和可行域满足约束和非负条件的解x。n最优解n基、基向量、基变量设A=(aij)mn,r(A) = m,称A的一个m阶满秩子矩阵B称为(LP)问题的的一个基。n基解由基矩阵B确定的m个基变量,并上非基变量取0的解。n基(本)可行解同时是可行解的基解。n可行基8/14/202411利用初等变换求基可行解n例4. 教材14页,列出(LP)问题的全部基,基解、基可行解并指出最优解。n问题: I)
6、如何判断一个解是基可行解; II)表1-1中为何少了两行?n利用p1,p2, p4 求基解的过程8/14/2024122 图解法求最优解n什么时候用图解法?(LP)模型仅含两个决策变量。n求解方法和根据:根据约束画出求解区域,一般为第一象限的凸多边形(有界或无界),标记出顶点坐标;求目标函数的梯度:设目标函数是 z=c1x1+c2x2,则n = grad z = (c1,c2) 为等值线c1x1+c2x2= h的法线方向,沿n的方向函数值增加的最快,沿-n方向函数值减少的最快。移动等值线 c1x1+c2x2= h 在区域顶点或边界达到最大最小值。n书中的方法是把目标函数z当做参数处理。8/14
7、/202413一般情况求解区域的确定n约束一般都可化成 ax1+bx2+c = 0 (a 0,b 0)的形式特殊情形?8/14/202414一个用图解法求极值的例子n用图解法求如下线性规划问题的极值。最大值点 x* = (1,4), Zmax = 3;最小值点 x* = (4,1), Zmin = 3;A(2,0)B(4,1)C(1,4)D(0,2)8/14/202415图解法的其他情形 无穷多最优解n无穷多最优解(书,P16,见下图)问题1:什么情况下发生?n问题2:这个最优解如何表示?8/14/202416图解法的其他情形 无界解(无最优解)n求下面规划问题的最优解。 问题1:如果目标函数
8、是求极大,是否有最优解? 问题2:能否定量说明 z 是无下界的?8/14/202417图解法的其他情形 无可行解n求下面规划问题的最优解。8/14/2024183 单纯形基本原理 预备知识n凸集 定义1.1:如果集合C中任意两点x(1),x(2),其连线上的所有点也在集合C中,即对任何x(1)C, x(2)C,0 0 (1 i k), 若x是基可行解,则必有 k m(为什么?),由可行基的定义,部分向量组 p1,p2, ,pk 必线性无关。必要性 若x为可行解(同上假设),其对应系数列向量 p1,p2, ,pk 线性独立(无关),同样 k m (为什么?)。(1)、若k = m, 则 p1,p
9、2, ,pk 刚好构成一个基矩阵,而x = (x1 , x2 , , xk , 0,0)T为对应基可行解。(2)、若k m ,则可以利用p1,p2, ,pk构造一个基,因为rank(A) = m, 从pk+1,p2, ,pn中必可以选出mk列,和p1,p2, ,pk共同组成一个基,这样一定可以办到(为什么?) ,其对应基解恰为x。这样的x称为退化的基可行解。8/14/202421单纯形法的基本定理 凸组合性质n凸组合 定义1.3 设x(1), x(2) , x(m)是En中的m个向量, 而1, 2, , m是满足1+ 2+ + m=1,i0的m个实数,称向量x = 1x(1)+ 2 x(2)
10、+ + m x(m)为x(1), x(2) , x(m)的凸组合。问题:凸组合和普通线性组合有什么区别?n引理1.2En中的点集为凸集的充要条件是对任何正整数m, 中任意m个点x(1), x(2) , x(m)的凸组合x都在内。充分性:利用定义证凸集;必要性:数学归纳法+凸集定义。8/14/202422单纯形法的基本定理 - 顶点表示定理n引理1.3 设(LP)问题的可行域C有界,则任何可行解xC都可以表示成C的顶点的凸组合。(证明略,图解示意,考虑x的三种情况:顶点、边界点和内点)8/14/202423一个顶点表示的例子n例 设x是三角形中任意一点, x(1), x(2) , x(3) 是三
11、角形的三个顶点,试将x表示为x(1), x(2) 和x(3) 的凸组合。n解:连接x(1)和x交x(2) x(3) 于x,因三角形是凸集, x = x(1) + (1 ) x (1) x = x(2) + (1 ) x(3) (2) 0 , m-1 % 如果如果 r(B) = 3n Base = ; n for j=1:mn % 将将B表示成(表示成(p1 p2 .pk)的形式)的形式n Base = Base,blanks(10), p,int2str(ploc(j);n endn disp(BASE = , Base); % 显示基是哪些列构成的显示基是哪些列构成的n x(ploc)= B
12、b % 求求 x_B 并放入基列位置并放入基列位置n zvalue = c*x(1:m) % 计算最优值计算最优值n endnend8/14/202431初始基可行解的获得n设法构造一个初始单位阵基。如果约束条件都是 “ ” 形式,化标准型直接获得;如果约束条件是 “=” 或 “ ” 形式,采用人工变量法(稍后讲)。n不妨设(LP)标准形前m列是单位阵,即典型形式(典式)。8/14/202432最优解的判别 - 检验数n最优解的判别:用非基变量表示目标函数值。8/14/202433单纯形表的建立cjc1c2cmcm+1cjcnCBBbx1x2xmxm+1xjxnc1x1b11a1m+1a1ja
13、1nc2x2b21a2m+1a2ja2ncmxmbm1amm+1amjamnj=cj-zj000nB 基(变量);CB - 基变量对应目标函数系数;b 右端项检验数的计算: j= cj zj = cj (c1a1j+ c2a2j+ cmamj)8/14/202434用单纯形表求解的例子(书p26.例5)cj23000CBBbx1x2x3x4x50x312221000x416400100x51505001j=cj zj23000化标准型建立初始单纯形表,计算检验数;确定进基变量,x2进基(检验数最大);确定离基变量,=min12/2,16/0,15/5 = 3, x5离 基 。由主元a32确定。
14、8/14/202435单纯形表上的迭代算法cj23000CBBbx1x2x3x4x50x312221000x416400100x51505001j=cj zj230000 1 0 0 1/533 x22 0 1 0 -2/562 0 0 0 -3/5所有检验数非正,最优解 x*=(3,3,0,4,0)T,最优值 z*=15第1次迭代:对主元所在行和列进行初等变换,并计算检验数。第2次迭代:x1进基,x3离基,主元a12=2,消元并计算检验数。2 x131 0 1/2 0 -1/50 x43 x240 0 -2 1 4/530 1 0 0 1/5j=cj zj0 0 -1 0 -1/58/14/
15、202436单纯形算法的一般形式cjc1clcmckcjCBBbx1xlxmxkxjc1x1b11a1ka1jcixibiaikaijclxlbl1alkaljcmxmbm1amkamjj=cj-zj000kj8/14/202437单纯形算法的计算步骤把(LP)化成标准形式,建立初始单纯形表;(一般能获得一个单位阵基作为初始可行基)计算所有变量的检验数,若所有 j 0 (1 j n),则当前解 x 即为最优解,迭代结束。否则转;确定 k = maxj| j 0, 则xk待进基;若所有aik 0, 则停止计算,(LP)无最优解,否则转;计算 = minbi/aik | aik 0, 1 i m
16、= bl /alk ,则xl离基;以alk为主元,通过高斯消元法进行基可行解的转换,求得表中一新基可行解,转步骤。(注:若在和中出现多个k或者l, 则按照自然顺序选择)8/14/202438迭代一次之后的形式cjc1clcmckcjCBBbx1xlxmxkxjc1x110cixi0ckxk1cmxm10j=cj-zj0008/14/202439迭代前后解,函数值,检验数等的变化8/14/202440一个讲练的例子(大家参与)8/14/202441最优性检验标准()若所有 j 0 (1 i m), 则 (LP)有无穷多最优解。若有某个 j 0 ( m+1 j n ),但是 pj = (a1j,
17、a2j, , amj) 0, 则(LP)无有限的最优解和最优值(无最优解)。采用人工变量方法时(大M法和二阶段法),满足最优条件时人工变量不为零,则原LP问题无可行解。8/14/2024425 人工变量法 问题的提出n如果原(LP)问题的约束全是“”号的形式,可以引入m个松弛变量xn+m,使得后m列自然形成初始单位阵基,再用单纯形法进行迭代求解。n如果原(LP)问题的约束是“”和“”号,或者三种符号( 、 、 )都有的的混合形式,且化成标准形式后约束矩阵不具备初始单位阵基,这时候怎么办?n解决办法:自然的想法就是在标准形约束矩阵中,人工加入若干单位向量,(和已有的)形成初始单位阵基。化标准型8
18、/14/202443人工变量法 大M法n例6 求解如下线性规划问题(书P29)n标准形中只有p4是单位向量?强行加入两列p6和p7 ,或者说在第2、3个约束上分别加入人工变量,即x6和x7。n人工变量的系数问题?目标函数中人工变量系数都取M (M 0 充分大)。8/14/202444用大M法求解 例6cj-30100-M-MCBBbx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj zj-2M-34M10-M00检 验 数 比 较 :形式 aM+b1. a 0, aM+b 02. a 0, aM+b 03. 若 0a1a2 则a1M+b
19、1 0但p4 =(-1/2,-3) 0, 确定k, 并计算pk = B1pk;若所有aik 0, 则停止计算,(LP)无最优解,否则转;计算 = minbi/aik | aik 0, 1 i m = bl /alk , 修改集合I,J和cB;形成Elk , 并计算 B1=ElkB 1, xB=Elk xB, 转步骤。(注:若在和中出现多个k或者l, 则按照自然顺序选择)8/14/202469单纯形表vs.修正单纯形算法(板书计算)cj-1300CBBbx1x2x3x40x36-12100x451101cj zj-13003x23-1/211/200x423/20-1/21cj zj1/20-3
20、/203x211/3011/31/3-1x14/310-1/32/3cj zj00-4/3-1/38/14/202470应用举例 投资项目的组合问题n例14 .(书P45)兴安公司有一笔30万元的自己,考虑今后三年内用于下列项目的投资:三年内每年年初均可投资,每年获利为投资额的20%,其本利可一起用于下一年的投资;允许第一年初投入,于第二年末收回,本利合计为投资额的150%,但是此类投资限额不超过15万元;允许于第二年初投资,于第三年末收回,本利合计为投资额的160%,但限额投资20万元;允许于第三年初投入,年末收回,可获利40%,但限额为10万元。试为该公司制定一个使第三年末本利和最大的投资
21、组合方案。n求解注意的问题:如何设定决策变量?约束的控制求解的过程8/14/202471综合问题. 解的性质判别(大家参与)n下表给出某极大化问题的单纯形表,问表中a1, a2, c1, c2, d为何值时,以及表中变量属那种类型时(3),有(1). 表中解为唯一解?无穷多最优解之一?无界解?退化的可行解?(2). 下一步迭代将以x1替换基变量x5?(3). 该线性规划问题无可行解?x1x2x3x4x5x3d4a1100x42-1-5010x53a2-3001cj zjc1c20008/14/202472第2次作业总结作业抄袭,再警告1次,下次相同版本作业点名;作业不完整:少题,少项,省略和空
22、白;其他技术性问题:l检验数的写法:czzj ? ij? cz cj? cj zj?l主元的选取:alk 0, b 0。主列(进基),主行(离基)l解的性质判别:无最优解 vs. 无可行解(一般用两阶段或大M法)l大M方法实质是两阶段方法的两个阶段的合并l单纯形表迭代计算的过程和写法:(1) 迭代几次写几张表,确定ck-zk和求的过程可不写;(2) 要求解都写成列向量形式 (图解法除外),最优解和值顺序8/14/202473第2次作业总结(续.一种简洁规范的写法,作业P47 1.3a)n如果用单纯形法,先化标准形,有cj10500CBBbx1x2x3x40x3934100x485201cj zj105000x321/5014/51-3/510x18/512/501/5cj zj010-25x23/2015/14-3/1410x1110-1/72/7cj zj00-5/14-25/148/14/202474作业和习题n课后作业:(1)书P47 1.2(a) 用单纯形法重新求两个最优解,并用1.15的结论给 出所有最优解。(2)书P48 1.8 (写过程)(3)书P49 1.12(写过程,原题有错,a24= -1/5)n追加作业:1.15(用定义),1.16(定义加变换)n上交作业时间:4月6日(下周三)8/14/202475