线性规划及单纯形法ppt课件.ppt

《线性规划及单纯形法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章线性规划及单纯形法姚明臣2011年3月中国科技网到中国电信网络线路使用分析报告Allrightsreserved本次课程要求掌握的内容会建立简单的线性规划问题的数学模型；理解并记忆线性规划模型的各种形式；分量形式向量形式矩阵形式会将一般线性规划模型化成标准型；有关线性规划问题解的若干重要概念可行解、最优解、基、基(本)解、基可行解等。熟练掌握含两个决策变量问题的图解法；凸集的相关概念和单纯形法若干基本定理。9/7/20212§1线性问题的数学模型问题的提出例1.用一块边长为a的正方形铁皮做一个容器，应如何裁剪，才能使做成容器的容积最大？ax解：利用高等数学的知识

2、V=(a-2x)2x求V(x)的最大值即可。[问题？]9/7/20213线性规划的数学模型问题的提出–例2(生产计划安排，要求利润最大)解：设在计划期内生产产品I和产品II分别为x1和x2件(决策变量)目标是要使z=2x1+3x2达到最大。(目标函数)限制条件是：（约束条件）2x1+2x212和2x116以及5x215要求x1,x20加工设备ABC单件利润产品I2402元产品II2053元设备时限12h16h15h——9/7/20214线性规划的数学模型问题的提出–例子之三(合理下料问题)现有一批10m长的贵重钢筋，需要截取3m和4m长的钢筋各50

3、根，试问如何截取，才能使原料最省？问题分析：先确定截取方案建立数学规划模型问题：模型是否有别的形式？截取方案IIIIII3m钢筋2304m钢筋102废料长0m1m2m9/7/20215线性规划问题数学模型的定义线性规划模型组成的三要素：决策变量目标函数约束条件定义1在线性规划数学模型中，如果决策变量为可控的连续变量，目标函数和约束条件都是线性的，称这类模型为线性规划问题的数学模型。问题：例一中的问题是否为线性规划模型？9/7/20216线性规划问题数学模型的一般形式关于幻灯片中的数学符号：小写斜体字母表示实数，如a,b,c,x,x1,y,z等小写黑体字母表示向量，如x

4、,y,z等大写黑体字母表示矩阵，如A,B,C等线性规划(LP)数学模型的一般形式或9/7/20217线性规划数学模型向量和矩阵形式(LP)向量形式(LP)矩阵形式9/7/20218线性规划问题的标准形式什么是(LP)问题的标准形式？满足如下条件：目标函数是求极大值；约束条件全为等式；bi和xj全为非负数。9/7/20219(LP)一般形式向标准形式的转化(LP)一般形式向标准形转化的情况：目标函数是求极小值；约束条件为不等式“”的情形（松弛变量，例2）；约束条件为不等式“”的情形（剩余变量，例3）；取值无约束的变量；某个变量xj0问题：某个变量有上下界限制，比

5、如lxju，如何处理？例3.见书P12。9/7/202110线性规划问题解的若干重要概念线性规划问题的任务从满足约束条件（2）和非负条件（3）的方程组中，找到使目标函数（1）取得最大值的解。可行解和可行域满足约束和非负条件的解x。最优解基、基向量、基变量设A=(aij)mn，r(A)=m，称A的一个m阶满秩子矩阵B称为(LP)问题的的一个基。基解由基矩阵B确定的m个基变量，并上非基变量取0的解。基(本)可行解同时是可行解的基解。可行基9/7/202111利用初等变换求基可行解例4.教材14页，列出(LP)问题的全部基，基解、基可行解并指出最优解。问题:I)如何判

6、断一个解是基可行解；II）表1-1中为何少了两行？利用p1,p2,p4求基解的过程9/7/202112§2图解法求最优解什么时候用图解法？(LP)模型仅含两个决策变量。求解方法和根据：根据约束画出求解区域，一般为第一象限的凸多边形(有界或无界)，标记出顶点坐标；求目标函数的梯度：设目标函数是z=c1x1+c2x2，则n=gradz=(c1,c2)为等值线c1x1+c2x2=h的法线方向，沿n的方向函数值增加的最快，沿-n方向函数值减少的最快。移动等值线c1x1+c2x2=h在区域顶点或边界达到最大最小值。书中的方法是把目标函数z当做参数处理。9/7/202113一般情

7、况求解区域的确定约束一般都可化成ax1+bx2+c=0(a>0，b0)的形式[特殊情形？]9/7/202114一个用图解法求极值的例子用图解法求如下线性规划问题的极值。最大值点x*=(1,4),Zmax=3；最小值点x*=(4,1),Zmin=3；A(2,0)B(4,1)C(1,4)D(0,2)9/7/202115图解法的其他情形–无穷多最优解无穷多最优解(书，P16，见下图)问题1：什么情况下发生？问题2：这个最优解如何表示？9/7/202116图解法的其他情形–无界解(无最优解)求下面规划问题的最优解。问题1：如果目标函数是求极大，是否有最优