《线规划的单纯形算法和线代数的分块初等变换的教学结合.ppt》由会员分享，可在线阅读，更多相关《线规划的单纯形算法和线代数的分块初等变换的教学结合.ppt（18页珍藏版）》请在三一办公上搜索。
1、线性规划的单纯形算法和线性代数的分块初等变换的教学结合,福建师范大学数学与计算机科学学院郑开杰,大纲,教学困惑 教学结合 其他,一、教学困惑,1.线性代数的应用实例的教学困惑（1）教师角度：教师的教学往往是“以不变应万变”，不同专业的学生讲一样的应用实例 为讲线性代数的应用“造”实例 受制于课时，不敢完整地讲甚至不敢讲应用实例（2）学生不买帐 老师讲的实例不真、不完整、与专业无关且无法实现 不考试,【解】设x1、x2分别为甲、乙产品的产量，数学模型为：,生产计划问题,2012-11-24 福建省*次会议,5,2010：把吃出来的病吃回去 令人佩服的骗子 张悟本,2012-11-24 福建省*次
2、会议,6,2010：“曲美”减肥胶囊（盐酸西布曲明胶囊）-抑制食欲,2011：把吃出来的肉吃回去-减肥疯子 XXX,科学食谱能否减肥？,2012-11-24 福建省*次会议,7,合成后,合成前,5,一、教学困惑,2.线性规划的单纯形算法的教学困惑 现有大部分运筹学课程要求完整地讲授单纯形算法，但实际上，应用工作者无需了解太深 为讲单纯形算法，需复习相关线性代数的内容，占课时 单纯形算法的迭代过程多采用表格形式，工作量极其大,一、教学困惑,3.解决途径：将单纯形算法融入到线性代数中 省运筹学至少6课时，且仅需至多增加两个线性代数的课时 适用的学生面广 无需教授数学软件，Excel即可简便实现,二
3、、分块初等行变换观点看单纯形算法,矩阵形式,标准型,max cTx|Ax=b,x 0 其中，R(Amn)=m,1.线性规划概念,2.最优解的判定,仅为叙述算法方便，不妨设A=（Bmm，N）且 r(A)=r(B)=m,Ax=bBxB+NxN=bxB=B-1b-B-1NxN,基变量、检验数、基本解、基本可行解；基本解成为最大值解当且仅当（1）x0（2）自由变量的检验数非正,二、分块初等行变换观点看单纯形算法,3.单纯形算法,检验数的自动计算,标准型：max cTx|Ax=b,x 0,原始单纯形法的思路：step1：找一个自由变量等于零的非负解（初始基本可行解）step2：不断改善该基本可行解，,启
4、发式的认为：（1）为使目标函数上升最快，进基变量应选择检验数最大的，（2）出基变量的选择应使解可行,基本可行解唯一取决于自由变量的选择，故改善解的过程本质上是：“不断地调整自由变量组”或“选择进基变量和离基变量”,二、分块初等行变换观点看单纯形算法,4.算例：用单纯形法求最优解,【解】step1：化为标准型,step2：求初始基本可行解X(1)=(0,0,40,30)T,故最优解为（x1，x2）=（15，10）,step3：单纯形迭代（单纯形过程简化写法）,进基列,出基行,bi/ai2，ai20,i,基变量,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：单纯形迭代（单纯形表格写法）,二、分块初等行变换观点看单纯形算法,5.Excel实现,三、层次分析法与最大特征值,Step1：建立递阶层次结构模型Step2：构造各个层次的判断矩阵Step3：检验判断矩阵的一致性Step4：层次单排序、层次总排序,三、层次分析法与最大特征值,Thank you!,
