《线规划的单纯形算法和线代数的分块初等变换的教学结合市公开课一等奖百校联赛特等奖课件.pptx》由会员分享，可在线阅读，更多相关《线规划的单纯形算法和线代数的分块初等变换的教学结合市公开课一等奖百校联赛特等奖课件.pptx（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性规划单纯形算法和线性代数分块线性规划单纯形算法和线性代数分块初等变换教学结合初等变换教学结合q福建师范大学q数学与计算机科学学院q郑开杰第1页纲领纲领 教学迷惑 教学结合 其它第2页一、教学迷惑一、教学迷惑q1.线性代数应用实例教学迷惑q（1）教师角度：教师教学往往是“以不变应万变”，不一样专业学生讲一样应用实例 为讲线性代数应用“造”实例 受制于课时，不敢完整地讲甚至不敢讲应用实例q（2）学生不买帐 老师讲实例不真、不完整、与专业无关且无法实现 不考试第3页 5 第8页一、教学迷惑一、教学迷惑q2.线性规划单纯形算法教学迷惑 现有大部分运筹学课程要求完整地讲授单纯形算法，但实际上，应用工
2、作者无需了解太深 为讲单纯形算法，需复习相关线性代数内容，占课时 单纯形算法迭代过程多采取表格形式，工作量极其大第9页一、教学迷惑一、教学迷惑q3.处理路径：将单纯形算法融入到线性代数中 省运筹学最少6课时，且仅需至多增加两个线性代数课时 适用学生面广 无需教授数学软件，Excel即可简便实现第10页二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法矩阵形式矩阵形式标准型标准型max cTx|Ax=b,x0 其中，其中，R(Amn)=m1.线性规划概念线性规划概念2.最优解判定最优解判定仅为叙述算法方便，不妨设仅为叙述算法方便，不妨设A=（Bmm，N）且）且 r(A)=r(B
3、)=mAx=bBxB+NxN=bxB=B-1b-B-1NxN基变量、检验数、基本解、基变量、检验数、基本解、基本可行解；基本可行解；基本解成为最大值解当且仅当基本解成为最大值解当且仅当（1）x0（2）自由变量检验数非正）自由变量检验数非正第11页二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法3.单纯形算法单纯形算法检验数自动计算检验数自动计算xBxNBxBBNbcBcNxBxNbxBEB-1NB-1b检验数0cN T-cBTB1N标准型：标准型：max cTx|Ax=b,x0 原始单纯形法思绪：原始单纯形法思绪：step1：找一个自由变量等于零非负：找一个自由变量等于零非
4、负解（初始基本可行解）解（初始基本可行解）step2：不停改进该基本可行解，：不停改进该基本可行解，启发式认为：启发式认为：（1）为使目标函数上升最快，）为使目标函数上升最快，进基变量应选择检验数最大，进基变量应选择检验数最大，（2）出基变量选择应使解可行）出基变量选择应使解可行基本可行解唯一取决于自由变量选择，基本可行解唯一取决于自由变量选择，故改进解过程本质上是：故改进解过程本质上是：“不停地调整自由变量组不停地调整自由变量组”或或“选择进基变量和离基变量选择进基变量和离基变量”第12页二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法4.算例：算例：用单纯形法求最优解用
5、单纯形法求最优解【解解】step1：化为标准型：化为标准型step2：求初始基本可行解：求初始基本可行解X(1)=(0,0,40,30)T 故最优解为（故最优解为（x1，x2）=（15，10）step3：单纯形迭代：单纯形迭代（单纯形过程简化写法）（单纯形过程简化写法）第13页进基列进基列出出基基行行bi/ai2，ai20i(a)XBx1x2x3x4bx3211040 x413/20130j30040000(b)x3x2j(c)x1x210j基变量基变量120002/302/3204/31-2/340100/30-800/330103/4-1/21501-1/2 11000-25-250将将3/2化为化为12015step3：单纯形迭代（单纯形表格写法）：单纯形迭代（单纯形表格写法）第14页二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法5.Excel实现实现第15页三、层次分析法与最大特征值三、层次分析法与最大特征值Step1：建立递阶层次结构模型：建立递阶层次结构模型Step2：结构各个层次判断矩阵：结构各个层次判断矩阵Step3：检验判断矩阵一致性：检验判断矩阵一致性Step4：层次单排序、层次总排序：层次单排序、层次总排序第16页三、层次分析法与最大特征值三、层次分析法与最大特征值第17页18-11-24 福建省*次会议第18页