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

Presentation on theme: "线性规划的单纯形算法和线性代数的分块初等变换的教学结合"— Presentation transcript:

1 线性规划的单纯形算法和线性代数的分块初等变换的教学结合
福建师范大学 数学与计算机科学学院 郑开杰

2 大纲 教学困惑 教学结合 其他

3 一、教学困惑 1. 线性代数的应用实例的教学困惑 （1）教师角度： 教师的教学往往是“以不变应万变”，不同专业的学生讲一样的应用实例
为讲线性代数的应用“造”实例 受制于课时，不敢完整地讲甚至不敢讲应用实例 （2）学生不买帐 老师讲的实例不真、不完整、与专业无关且无法实现 不考试

4 生产计划问题 【解】设x1、x2分别为甲、乙 产品的产量，数学模型为： 产品 资源 甲 乙 现有 材料A 2 1 40 材料B 1.5 30
利润（元/件） 300 400 【解】设x1、x2分别为甲、乙 产品的产量，数学模型为：

5 2010：把吃出来的病吃回去 令人佩服的骗子– 张悟本 福建省**次会议

6 科学食谱能否减肥？ 2010：“曲美”减肥胶囊 （盐酸西布曲明胶囊） ---- 抑制食欲 2011：把吃出来的肉吃回去
---减肥疯子 XXX 福建省**次会议

7 合成前 合成后 福建省**次会议

8 5

9 一、教学困惑 2. 线性规划的单纯形算法的教学困惑 现有大部分《运筹学》课程要求完整地讲授单纯形算法，但实际上，应用工作者无需了解太深
为讲单纯形算法，需复习相关线性代数的内容，占课时 单纯形算法的迭代过程多采用表格形式，工作量极其大

10 一、教学困惑 3. 解决途径：将单纯形算法融入到线性代数中 省《运筹学》至少6课时，且仅需至多增加两个线性代数的课时 适用的学生面广
无需教授数学软件，Excel即可简便实现

11 二、分块初等行变换观点看单纯形算法 仅为叙述算法方便，不妨设 1. 线性规划概念 A =（Bm×m，N）且 r(A) = r(B) = m
Ax = b BxB+NxN = b xB = B-1b-B-1NxN 矩阵形式 标准型 max{ cTx | Ax=b, x ≥0} 其中，R (Am×n) = m 2. 最优解的判定 基变量、检验数、基本解、 基本可行解； 基本解成为最大值解当且仅当 （1）x≥0 （2）自由变量的检验数非正

12 二、分块初等行变换观点看单纯形算法 检验数的自动计算 3. 单纯形算法 标准型：max { cTx | Ax=b, x ≥0}
原始单纯形法的思路： step1：找一个自由变量等于零的非负解（初始基本可行解） step2：不断改善该基本可行解， 检验数的自动计算 xB xN B N b cB cN 基本可行解唯一取决于自由变量的选择， 故改善解的过程本质上是： “不断地调整自由变量组” 或“选择进基变量和离基变量” xB xN b E B-1N B-1b 检验数λ cN T - cBTB－1N 启发式的认为： （1）为使目标函数上升最快， 进基变量应选择检验数最大的， （2）出基变量的选择应使解可行

13 二、分块初等行变换观点看单纯形算法 step3：单纯形迭代 （单纯形过程简化写法） 4. 算例： 用单纯形法求最优解
X(1)=(0,0,40,30)T 故最优解为（x1，x2）=（15，10）

14 step3：单纯形迭代（单纯形表格写法） θi 将3/2化为1 40 20 1 -2/3 20 15 4/3 2/3 1 2/3 20 30
bi /ai2，ai2>0 基变量 进基列 出基行 (a) XB x1 x2 x3 x4 b 2 1 40 3/2 30 λj 300 400 (b) (c) 10 θi 将3/2化为1 40 20 1 -2/3 20 15 4/3 2/3 1 2/3 20 30 100/3 -800/3 1 3/4 -1/2 15 1 -1/2 1 10 -25 -250

15 二、分块初等行变换观点看单纯形算法 5. Excel实现

16 三、层次分析法与最大特征值 Step1：建立递阶层次结构模型 Step2：构造各个层次的判断矩阵 Step3：检验判断矩阵的一致性

17 三、层次分析法与最大特征值

18 Thank you !