线规划的单纯形算法和线代数的分块初等变换的教学结合市公开课一等奖百校联赛特等奖课件.pptx

2012-11-24 福建省*次会议,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,2012-11-24 福建省*次会议,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,2012-11-24 福建省*次会议,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2012-11-24 福建省*次会议,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2012-11-24 福建省*次会议,*,2012-11-24 福建省*次会议,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,线性规划单纯形算法和线性代数分块初等变换教学结合,福建师范大学,数学与计算机科学学院,郑开杰,第1页,纲领,教学迷惑,教学结合,其它,第2页,一、教学迷惑,1,.线性代数应用实例教学迷惑,（1）教师角度：,教师教学往往是“以不变应万变”，不一样专业学生讲一样应用实例,为讲线性代数应用,“造”实例,受制于课时，不敢完整地讲甚至不敢讲应用实例,（2）学生不买帐,老师讲实例不真、不完整、与专业无关且,无法实现,不考试,第3页,【,解,】,设,x,1,、,x,2,分别为甲、乙,产品产量，数学模型为：,产品,资源,甲,乙,现有,资源,材料,A,2,140,材料,B,1,1.5,30,利润（元,/,件）,300,400,生产计划问题,第4页,：把吃出来病吃回去,令人佩服骗子 张悟本,5,-11-24 福建省*次会议,第5页,：“,曲美,”,减肥,胶囊,（盐酸西布曲明胶囊）,-,抑制食欲,：把吃出来肉吃回去,-,减肥疯子,XXX,科学食谱能否减肥？,6,-11-24 福建省*次会议,第6页,合成后,合成,前,7,-11-24 福建省*次会议,第7页,5,第8页,一、教学迷惑,2.线性规划单纯形算法教学迷惑,现有大部分运筹学课程要求完整地讲授单纯形算法，但实际上，应用工作者无需了解太深,为讲单纯形算法，需复习相关线性代数内容，占课时,单纯形算法迭代过程多采取表格形式，工作量极其大,第9页,一、教学迷惑,3.处理路径：,将单纯形算法融入到线性代数中,省运筹学最少6课时，且仅需至多增加两个线性代数课时,适用学生面广,无需教授数学软件，Excel即可简便实现,第10页,二、,分块初等行变换观点看单纯形算法,矩阵形式,标准型,max,c,T,x|Ax=b,x,0,其中，,R,(,A,mn,),=m,1.线性规划概念,2.最优解判定,仅为叙述算法方便，不妨设,A=,（,B,mm,，,N,）且,r,(,A,)=,r,(,B,)=,m,Ax=b,Bx,B,+Nx,N,=b,x,B,=B,-,1,b-B,-,1,Nx,N,基变量、检验数、基本解、基本可行解；,基本解成为最大值解当且仅当,（,1,）,x,0,（,2,）自由变量检验数非正,第11页,二、,分块初等行变换观点看单纯形算法,3.单纯形算法,检验数自动计算,x,B,x,N,B,x,B,B,N,b,c,B,c,N,x,B,x,N,b,x,B,E,B,-,1,N,B,-,1,b,检验数,0,c,N,T,-c,B,T,B,1,N,标准型：,max,c,T,x|Ax=b,x,0,原始单纯形法思绪：,step1：找一个自由变量等于零非负解（初始基本可行解）,step2：不停改进该基本可行解，,启发式认为：,（,1,）为使目标函数上升最快，,进基变量应选择检验数最大，,（,2,）出基变量选择应使解可行,基本可行解唯一取决于自由变量选择，,故改进解过程本质上是：,“不停地调整自由变量组”,或“选择进基变量和离基变量”,第12页,二、,分块初等行变换观点看单纯形算法,4.算例：,用单纯形法求最优解,【,解,】,step1：化为标准型,step2：求初始基本可行解,X,(1)=(0,0,40,30),T,故最优解为（,x,1,，,x,2,）,=,（,15,，,10,）,step3：单纯形迭代,（单纯形过程简化写法）,第13页,进基列,出基行,b,i,/a,i2,，,a,i2,0,i,(,a,),X,B,x,1,x,2,x,3,x,4,b,x,3,2,1,1,0,40,x,4,1,3/2,0,1,30,j,300,400,0,0,(,b,),x,3,x,2,j,(,c,),x,1,x,2,10,j,基变量,1,20,0,0,2/3,0,2/3,20,4/3,1,-,2/3,40,100/3,0,-,800/3,30,1,0,3/4,-,1/2,15,0,1,-,1/2,1,10,0,0,-,25,-,250,将,3/2,化为,1,20,15,step3：单纯形迭代（单纯形表格写法）,第14页,二、,分块初等行变换观点看单纯形算法,5.Excel实现,第15页,三、层次分析法与最大特征值,Step1,：建立递阶层次结构模型,Step2,：结构各个层次判断矩阵,Step3,：检验判断矩阵一致性,Step4,：层次单排序、层次总排序,第16页,三、层次分析法与最大特征值,第17页,Thank you !,18,-11-24 福建省*次会议,第18页,