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

1、线性规划的单纯形算法和线性代数的分块初等变换的教学结合福建师范大学数学与计算机科学学院郑开杰大纲 教学困惑 教学结合 其他一、教学困惑一、教学困惑1.线性代数的应用实例的教学困惑（1）教师角度：教师的教学往往是“以不变应万变”，不同专业的学生讲一样的应用实例 为讲线性代数的应用“造”实例 受制于课时，不敢完整地讲甚至不敢讲应用实例（2）学生不买帐 老师讲的实例不真、不完整、与专业无关且无法实现 不考试12300400 xx【解解】设设x1、x2分别为甲、乙分别为甲、乙产品的产量，数学模型为：产品的产量，数学模型为：120,0 xx12240 xx121.530 xxmax 产品 资源 甲 乙现

2、有资源材料A2140材料B11.530利润（元/件）300400生产计划问题生产计划问题12122=401.5=30 xxxx2012-11-24 福建省*次会议52012-11-24 福建省*次会议6科学食谱能否减肥？科学食谱能否减肥？2012-11-24 福建省*次会议7合成后合成前 5 5 一、教学困惑一、教学困惑2.线性规划的单纯形算法的教学困惑 现有大部分运筹学课程要求完整地讲授单纯形算法，但实际上，应用工作者无需了解太深 为讲单纯形算法，需复习相关线性代数的内容，占课时 单纯形算法的迭代过程多采用表格形式，工作量极其大一、教学困惑一、教学困惑3.解决途径：将单纯形算法融入到线性代数

3、中 省运筹学至少6课时，且仅需至多增加两个线性代数的课时 适用的学生面广 无需教授数学软件，Excel即可简便实现二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法max(min)(,)0Tc xAxbx 或或矩阵形式矩阵形式标准型标准型max cTx|Ax=b,x 0 其中，其中，R(Amn)=m1.线性规划概念线性规划概念2.最优解的判定最优解的判定仅为叙述算法方便，不妨设仅为叙述算法方便，不妨设A=（Bmm，N）且）且 r(A)=r(B)=mBNxxx Ax=bBxB+NxN=bxB=B-1b-B-1NxNBNccc (,)BTTTTTBNBBNNNxc xccc xc

4、 xx 11()TTBNNNcB bB Nxc x11()TBBNTTNccc B bxB N1 TBjjjc B bx为自由未知量指标11BjjnjC Bbx 基变量、检验数、基本解、基变量、检验数、基本解、基本可行解；基本可行解；基本解成为最大值解当且仅当基本解成为最大值解当且仅当（1 1）x00（2 2）自由变量的检验数非正）自由变量的检验数非正二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法3.单纯形算法单纯形算法检验数的自动计算检验数的自动计算xBxNBxBBNbcBcNxBxNbxBEB-1NB-1b检验数0cN T-cBTB1N标准型：标准型：max cTx|

5、Ax=b,x 0 原始单纯形法的思路：原始单纯形法的思路：step1：找一个自由变量等于零的非：找一个自由变量等于零的非负解（初始基本可行解）负解（初始基本可行解）step2：不断改善该基本可行解，：不断改善该基本可行解，启发式的认为：启发式的认为：（1）为使目标函数上升最快，）为使目标函数上升最快，进基变量应选择检验数最大的，进基变量应选择检验数最大的，（2）出基变量的选择应使解可行）出基变量的选择应使解可行11jnBjjZC Bbx 基本可行解唯一取决于自由变量的选择，基本可行解唯一取决于自由变量的选择，故改善解的过程本质上是：故改善解的过程本质上是：“不断地调整自由变量组不断地调整自由变

6、量组”或或“选择进基变量和离基变量选择进基变量和离基变量”二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法4.4.算例：算例：用单纯形法求最优解用单纯形法求最优解 12121212max3004002403/230,0Zxxxxxxxx【解解】step1：化为标准型：化为标准型121231241234m ax3004002403/230,0Zxxxxxxxxxxxxstep2：求初始基本可行解：求初始基本可行解X(1)=(0,0,40,30)T 1234 21301040101340000003/2xxxxb201004/3012/32/3102/3200/30800/31

7、1511003/41/201/210025250故最优解为（故最优解为（x1，x2）=（15，10）step3：单纯形迭代：单纯形迭代（单纯形过程简化写法）（单纯形过程简化写法）进基列进基列出出基基行行bi/ai2，ai20i(a)XBx1x2x3x4bx3211040 x413/20130j30040000 (b)x3x2j (c)x1 x210 j 基变量基变量120002/302/3204/31-2/340100/30-800/330103/4-1/21501-1/2 11000-25-250将将3/23/2化为化为1 12015step3step3：单纯形迭代（单纯形表格写法）：单纯形迭代（单纯形表格写法）二、二、分块初等行变换观点看单纯形算法分块初等行变换观点看单纯形算法5.Excel实现实现三、层次分析法与最大特征值三、层次分析法与最大特征值Step1Step1：建立递阶层次结构模型建立递阶层次结构模型Step2Step2：构造各个层次的判断矩阵：构造各个层次的判断矩阵Step3Step3：检验判断矩阵的一致性：检验判断矩阵的一致性Step4Step4：层次单排序、层次总排序：层次单排序、层次总排序三、层次分析法与最大特征值三、层次分析法与最大特征值