线性规划的单纯形算法和线性代数的分块初等变换的教学结合.ppt

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