线性规划及单纯形法1

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

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

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

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

4、式或7/23/20217线性规划数学模型向量和矩阵形式(LP)向量形式(LP)矩阵形式7/23/20218线性规划问题的标准形式什么是(LP)问题的标准形式？满足如下条件：目标函数是求极大值；约束条件全为等式；bi和xj全为非负数。7/23/20219(LP)一般形式向标准形式的转化(LP)一般形式向标准形转化的情况：目标函数是求极小值；约束条件为不等式“”的情形（松弛变量，例2）；约束条件为不等式“”的情形（剩余变量，例3）；取值无约束的变量；某个变量xj0问题：某个变量有上下界限制，比如lxju，如何处理？例3.见书P12。7/23/202110线性规划问题解的若干重要概念线性

5、规划问题的任务从满足约束条件（2）和非负条件（3）的方程组中，找到使目标函数（1）取得最大值的解。可行解和可行域满足约束和非负条件的解x。最优解基、基向量、基变量设A=(aij)mn，r(A)=m，称A的一个m阶满秩子矩阵B称为(LP)问题的的一个基。基解由基矩阵B确定的m个基变量，并上非基变量取0的解。基(本)可行解同时是可行解的基解。可行基7/23/202111利用初等变换求基可行解例4.教材14页，列出(LP)问题的全部基，基解、基可行解并指出最优解。问题:I)如何判断一个解是基可行解；II）表1-1中为何少了两行？利用p1,p2,p4求基解的过程7/23/202112§2图解法求最优

6、解什么时候用图解法？(LP)模型仅含两个决策变量。求解方法和根据：根据约束画出求解区域，一般为第一象限的凸多边形(有界或无界)，标记出顶点坐标；求目标函数的梯度：设目标函数是z=c1x1+c2x2，则n=gradz=(c1,c2)为等值线c1x1+c2x2=h的法线方向，沿n的方向函数值增加的最快，沿-n方向函数值减少的最快。移动等值线c1x1+c2x2=h在区域顶点或边界达到最大最小值。书中的方法是把目标函数z当做参数处理。7/23/202113一般情况求解区域的确定约束一般都可化成ax1+bx2+c=0(a>0，b0)的形式[特殊情形？]7/23/202114一个用图解法求极值的例子用图

7、解法求如下线性规划问题的极值。最大值点x*=(1,4),Zmax=3；最小值点x*=(4,1),Zmin=3；A(2,0)B(4,1)C(1,4)D(0,2)7/23/202115图解法的其他情形–无穷多最优解无穷多最优解(书，P16，见下图)问题1：什么情况下发生？问题2：这个最优解如何表示？7/23/202116图解法的其他情形–无界解(无最优解)求下面规划问题的最优解。问题1：如果目标函数