第1章 线性规划及单纯形法姚明臣2011年3月线性规划及单纯形法优秀课件 All rights reserved本次课程要求掌握的内容n会建立简单的线性规划问题的数学模型；n理解并记忆线性规划模型的各种形式；1.分量形式2.向量形式3.矩阵形式n会将一般线性规划模型化成标准型；n有关线性规划问题解的若干重要概念可行解、最优解、基、基(本)解、基可行解等。n熟练掌握含两个决策变量问题的图解法；n凸集的相关概念和单纯形法若干基本定理。8/14/202421 线性问题的数学模型n问题的提出 例1. 用一块边长为a的正方形铁皮做一个容器，应如何裁剪，才能使做成容器的容积最大？ax解：利用高等数学的知识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长的钢筋各50根，试问如何截取，才能使原料最省？n问题分析：先确定截取方案建立数学规划模型n问题：模型是否有别的形式？截取方案IIIIII3m钢筋2304m钢筋102废料长0m1m2m8/14/20245线性规划问题数学模型的定义n线性规划模型组成的三要素：决策变量目标函数约束条件n定义1 在线性规划数学模型中，如果决策变量为可控的连续变量，目标函数和约束条件都是线性的，称这类模型为线性规划问题的数学模型。n问题：例一中的问题是否为线性规划模型？8/14/20246线性规划问题数学模型的一般形式n关于幻灯片中的数学符号：小写斜体字母表示实数，如a,b,c,x,x1,y,z等小写黑体字母表示向量，如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问题：某个变量有上下界限制，比如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) 如何判断一个解是基可行解； 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/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：如果目标函数是求极大，是否有最优解？ 问题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,p2, ,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) + + 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) 是三角形的三个顶点，试将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)= Bb % 求求 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+1a1ja1nc2x2b21a2m+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确定。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/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 = 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, a2j, , amj) 0, 则(LP)无有限的最优解和最优值（无最优解）。采用人工变量方法时(大M法和二阶段法)，满足最优条件时人工变量不为零，则原LP问题无可行解。8/14/2024425 人工变量法 问题的提出n如果原（LP）问题的约束全是“”号的形式，可以引入m个松弛变量xn+m，使得后m列自然形成初始单位阵基，再用单纯形法进行迭代求解。n如果原（LP）问题的约束是“”和“”号，或者三种符号（ 、 、 ）都有的的混合形式，且化成标准形式后约束矩阵不具备初始单位阵基，这时候怎么办？n解决办法：自然的想法就是在标准形约束矩阵中，人工加入若干单位向量，(和已有的)形成初始单位阵基。化标准型8/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+b1 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/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万元。试为该公司制定一个使第三年末本利和最大的投资组合方案。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次，下次相同版本作业点名；作业不完整：少题，少项，省略和空白；其他技术性问题：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