课程名称：运筹学 专业：信息管理与信息系统 班级： (1)建立初始单纯形表，使得所有检验数0，≤0： (2)检查b列元素，如果所有b≥0，则已得到最优解，结束。否则转入下一步 (3)确定换出变量：设mn色，b,<0}=b,第1方程原基变量为换出变量，第1行 为主元行： ④定我人支：宁侣，小-品“为微入变是，第列为主无外 a楼 (5)以为主元作换基迭代运算，方法与单纯形法完全相同，得到新的单纯形表， 返回步骤(2)。 例1.6用对偶单纯形法解线性规划 mino=12%1+16y2+15y3 24+4y32≥2 s.t32y +5y3≥3 4,y2,y3≥0 标准化： maxd'=-12y-16y2-15y3 「-2y-4y2 +=-2 s1-2 -5y +=-3 y≥0i=1,.,5) c -12-1615 0 0 cB 12 1v3 12-2,-15-5 -12 =16.-15 -12 -16 -15 /-2,-16/-4 o i -16 1 13 4 原问题的最优解为：Y*=(1,0,15,0.0),W*=15 其对偶问题的最优解为：X*=(3,3),Z*=15
课程名称：运筹学 专业：信息管理与信息系统 班级： 24 （1）建立初始单纯形表，使得所有检验数σj≤0； （2）检查 b 列元素，如果所有 bi≥0，则已得到最优解，结束。否则转入下一步； （3）确定换出变量：设 i i l i min b b 0 = b ，第 l 方程原基变量为换出变量，第 l 行 为主元行； （4）确定换入变量：设 lk k lj lj j j a a a = min 0 ，xk 为换入变量，第 k 列为主元列； （5）以 alk 为主元作换基迭代运算，方法与单纯形法完全相同，得到新的单纯形表， 返回步骤（2）。 例 1.6 用对偶单纯形法解线性规划 + + = + + , , 0 2 5 3 2 4 2 . . min 12 16 15 1 2 3 1 3 1 2 1 2 3 y y y y y y y st y y y 标准化： = − − + = − − − + = − = − − − 0( 1, ,5) 2 5 3 2 4 2 . . max ' 12 16 15 1 3 5 1 2 4 1 2 3 y i y y y y y y st y y y i cj -12 -16 -15 0 0 b i cB yB y1 y2 y3 y4 y5 0 y4 -2 -4 0 1 0 -2 0 y5 -2 0 [-5] 0 1 -3 (-12/-2, -15/-5) σj -12 -16 -15 0 0 cj -12 -16 -15 0 0 b cB yB y1 y2 y3 y4 y5 0 y4 [-2] -4 0 1 0 -2 (-6/-2，-16/-4) -15 y3 2/5 0 1 0 -1/5 3/5 σj -6 -16 0 0 -3 -12 y1 1 2 0 -1/2 0 1 -15 y3 0 -4/5 1 1/5 -1/5 1/5 σj 0 -4 0 -3 -3 原问题的最优解为： Y*= （1 , 0,1/5 ,0,0），W*= 15 其对偶问题的最优解为：X*=（3 , 3 ），Z* =15
课程名称：运筹学 专业：信息管理与信息系统 班级： 小结 学习要点： 理解对偶单纯形法的原理，正确使用此方法。 课后作业：(P79) 2.6(a §6灵敏度分析 1.灵敏度分析的概念： 当某一 个参数发生变化后，引起最优解如何改变的分析。 可以改变的参数有： bi- 约束右端项的变化，通常称资源的改变： ©一一目标函数系数的变化，通常称市场条件的变化： pi -约束条件系数的变化，通常称工艺系数的变化： 其他的变化有：增加一种新产品、增加一道新的工序等。 2.分析原理 借助最终单纯形表将变化后的结果按下述基本原则反映到最终表里去 (1)bi变化：(b+△b)'=B-1(b+△b)=B-1b+B-1△b=b'+B-l△b (2)pj变化：(pjt△pi)'=B-l(pjt△pj)=B-1pjtB-l△pj=pj'+B-1△pj (3)c变化：直接反映到最终表中，计算检验数。 (4)增加一个约束方程：直接反映到最终表中。 (5)增加新产品：仿照p变化 小结 学习要点： 能熟练准确地就C、b、A中的元素发生变化来进行灵敏度分析，求出新的最优解。 课后作业：(P79)2.8,2.9
课程名称：运筹学 专业：信息管理与信息系统 班级： 25 小结 学习要点： 理解对偶单纯形法的原理，正确使用此方法。 课后作业： （P79） 2.6 （a） §6 灵敏度分析 1．灵敏度分析的概念： 当某一个参数发生变化后，引起最优解如何改变的分析。 可以改变的参数有： bi —— 约束右端项的变化，通常称资源的改变； cj ——目标函数系数的变化，通常称市场条件的变化； pj ——约束条件系数的变化，通常称工艺系数的变化； 其他的变化有：增加一种新产品、增加一道新的工序等。 2．分析原理： 借助最终单纯形表将变化后的结果按下述基本原则反映到最终表里去。 （1）bi 变化：（b+△b）´=B-1 （b+△b）= B-1 b+ B-1 △b = b´+B-1 △b （2）pj 变化：（pj+△ pj ）´= B-1 （pj+△ pj ）= B-1 pj+ B-1 △ pj = pj ´+ B-1 △ pj （3）cj 变化：直接反映到最终表中，计算检验数。 （4）增加一个约束方程：直接反映到最终表中。 （5）增加新产品：仿照 pj 变化。 小结 学习要点： 能熟练准确地就 C、b、A 中的元素发生变化来进行灵敏度分析，求出新的最优解。 课后作业： （P79） 2.8，2.9
课程名称：运筹学 专业：信息管理与信息系统 班级： 第3章运输问题 章节名称 第3章运输问题 课堂教学 1.理解运输问题的模型和特征： 目的 2.会用表上作业法求解运输问题。 1.运输问题的模型和特征 2.用表上作业法求解运输问题 教学内容及 (1)编制初始调运方案 (2)最优性检验 学时分配 (3)用闭回路法调整运输方案一一改进基本可行解 3.其他运输问题的处理 (共4学时) 重点、难点 重点：运输问题的表上作业法 以及对策 难点：运输问题的表上作业法 教学方法和 教学方式：讲授+实验 手段 教学辅助手段：教具、板书、现代教学设施设备 教 具 多媒体计算机、投影仪 P101课后习题3.1（表3-35、表3-36） 作业、思考题 P103课后习题3.6 实际问题中多是产销不平衡问题，从简单的平衡到复杂的不平衡问 课后记 题，注重问题的分析思路的培养和锻炼
课程名称：运筹学 专业：信息管理与信息系统 班级： 26 第 3 章 运输问题 章节名称 第 3 章 运输问题 课堂教学 目的 1.理解运输问题的模型和特征； 2.会用表上作业法求解运输问题。 教学内容及 学时分配 1.运输问题的模型和特征 2.用表上作业法求解运输问题 （1）编制初始调运方案 （2）最优性检验 （3）用闭回路法调整运输方案——改进基本可行解 3.其他运输问题的处理 （共 4 学时） 重点、难点 以及对策 重点：运输问题的表上作业法 难点：运输问题的表上作业法 教学方法和 手段 教学方式：讲授+实验 教学辅助手段：教具、板书、现代教学设施设备 教 具 多媒体计算机、投影仪 作业、思考题 P101 课后习题 3.1(表 3-35、表 3-36)， P103 课后习题 3.6 课后记 实际问题中多是产销不平衡问题，从简单的平衡到复杂的不平衡问 题，注重问题的分析思路的培养和锻炼
课程名称：运筹学 专业：信息管理与信息系统 班级： 第三章运输问题 §1运输问题及其数学棋型 运输问题的一般提法是：设某种物资有m个产地和n个销地。产地A,的产量为 a(亿=1,2，m:销地B,的销量为b,(U=l,2,.,)。从第i个产地A,向第j个销地B,运 输每单位物资的运价为C,。这就是由多个产地供应多个销地的单品种物资运输问题。问 如何调运这些物资才能使总运费达到最小。 产销平衡表 销地 产地 B B2 Bn 产量 x11x12 a x21 A. X ml Xm2 X mm 销量 b b2 单位运价表 、销地 B B2 . B 产地 A c11 C12 Cm Cm2 ·Cn 产销平衡的运输问题的数学模型为 m:-22x ,=a6=l2.m =U=2川 (3-1) 、x≥00=l,2.,mj=12,.,m） 其中a,和b,满足
课程名称：运筹学 专业：信息管理与信息系统 班级： 27 ≥ 第三章 运输问题 §1 运输问题及其数学模型 运输问题的一般提法是：设某种物资有 m 个产地和 n 个销地。产地 Ai 的产量为 a (i 1,2, ,m) i = ；销地 Bj 的销量为 b ( j 1,2, , n) j = 。从第 i 个产地 Ai 向第 j 个销地 Bj 运 输每单位物资的运价为 Cij 。这就是由多个产地供应多个销地的单品种物资运输问题。问 如何调运这些物资才能使总运费达到最小。 产销平衡表 单位运价表 销 地 产 地 B1 B2 Bn Am A A 2 1 m m mn n n c c c c c c c c c 1 2 21 22 2 11 12 1 产销平衡的运输问题的数学模型为： = = = m i n j ij ij z c x 1 1 min 0 ( 1,2, , ; 1,2, , ) ( 1,2, , ) ( 1,2, , ) 1 1 x i m j n x b j n x a i m ij j m i ij i n j ij = = = = = = = = （3-1） 其中 i a 和 j b 满足 销 地 产 地 B1 B2 Bn 产量 Am A A 2 1 m m mn n n x x x x x x x x x 1 2 21 22 2 11 12 1 a m a a 2 1 销量 b1 b2 bn
课程名称：运筹学 专业：信息管理与信息系统 班级： 24-2 (3-2)称为产销平衡条件。 将(3-1)的结构约束加以整理，可知其系数矩阵的结构比较松散，且特殊 x1x2.xnx21x2.2n.Xmn2.x 11.1 11·1 m行 ”。 11.1 1 1 1 、 n行 1 1 该系数矩阵中对应于变量x,的系数向量中除第i个和第m+j个为1以外，其余的都 为零。 小结 学习要点： 1.掌握运输问题模型结构： 2.了解运输问题模型特点， §2表上作业法 1、初始基本可行解的确定 (1)最小元素法 基本思想：优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限 度满足其供销量为原则确定供销业务。然后，在余下的未确定的供销业务中找运价最小 的，同样以最大限度满足其供销量为原则确定供销业务，同样的方法反复进行直到 了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。由于该方法基于 优先满足单位运价最小的供销业务，故称为最小元素法。 (2)西北角法 西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是 优先满足运输表中西北角（左上角）上空格的供销需求。按以上方法进行下去，最后可 得到初始方案 (3)伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运价。伏 格尔法考虑到，某产地的产品假如不能按最小运价就近供应，就考虑次小运价，这就有 个差额。差额越大，说明不能按最小运价调运时，运费增加越多。因而对差额最大的 行或列，就应当采用 小运价调运。基于此思想，伏格尔法给出的初始解比用最小元素 法给出的初始解更接近最优解。 2、解的最优性检验 (1)闭回路法
课程名称：运筹学 专业：信息管理与信息系统 班级： 28 = = = n j j m i ai b 1 1 （3-2）称为产销平衡条件。 将（3-1）的结构约束加以整理，可知其系数矩阵的结构比较松散，且特殊 n n m m mn x x x x x x x x x 11 12 1 21 22 2 1 2 = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 A 该系数矩阵中对应于变量 ij x 的系数向量中除第 i 个和第 m + j 个为 1 以外，其余的都 为零。 小结 学习要点： 1.掌握运输问题模型结构； 2.了解运输问题模型特点。 §2 表上作业法 1、初始基本可行解的确定 （1）最小元素法 基本思想：优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限 度满足其供销量为原则确定供销业务。然后，在余下的未确定的供销业务中找运价最小 的，同样以最大限度满足其供销量为原则确定供销业务，同样的方法反复进行直到确定 了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。由于该方法基于 优先满足单位运价最小的供销业务，故称为最小元素法。 （2）西北角法 西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是 优先满足运输表中西北角（左上角）上空格的供销需求。按以上方法进行下去，最后可 得到初始方案。 （3）伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其它处要多花几倍的运价。伏 格尔法考虑到，某产地的产品假如不能按最小运价就近供应，就考虑次小运价，这就有 一个差额。差额越大，说明不能按最小运价调运时，运费增加越多。因而对差额最大的 行或列，就应当采用最小运价调运。基于此思想，伏格尔法给出的初始解比用最小元素 法给出的初始解更接近最优解。 2、解的最优性检验 （1）闭回路法 m 行 n 行