运筹学完整教案.doc
《运筹学完整教案.doc》由会员分享,可在线阅读,更多相关《运筹学完整教案.doc(66页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精品文档,仅供学习与交流,如有侵权请联系网站删除第一章 线性规划与单纯形法1、教学计划第 1 次课 2 学时授课章节绪论;第一章第1节、第2节、第3节授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。掌握两个决策变量线性规划问题可行域(凸集)、最优解的位置;了解无解(无界解、无可行解)、有解(唯一解、无穷多个解)的几何意义。课堂教学重点及难点重点:线性规划的数学模型及其标准形。在数学模型中,要求熟悉矩阵形式;在标准形中,要求学生掌握非标准形式的几种具体情形及其相应的标准化方法;如何用几何的方法求两个决策变量的线性规划问题的
2、最优解。难点:线性规划的基本概念,例如基、基变量、基解、基可行解和可行基;多个最优解如何表示。教学过程教学过程教学方法及手段引 言运筹学模型,运筹学发展历史与现状,研究方法;考核方法与教学大纲等。1.1 线性规划问题及其数学模型线性规划的数学模型:变量的确定、约束条件与目标函数。1.2 线性规划问题的标准形式线性规划的标准形式及非标准形式的标准化处理。1.3线性规划问题的解基、基变量、基解、基可行解和可行基。多媒体讲解实例讲解第 2 次课 2 学时授课章节第一章第4节授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求掌握单纯形法思想以及具体操作过程。课堂教学重点及难点重点:单纯形法
3、迭代过程:(1)换入基变量的确定; (2)换出基变量的确定;(3)判定当前解已经最优。难点:单纯形法思想。教学过程教学过程教学方法及手段1.4 单纯形法单纯形数表的构造,要注意代数形式和表格形式的一一对应性。单纯形法迭代过程:(1)换入基变量的确定; (2)换出基变量的确定;(3)判定当前解已经最优。多媒体讲解实例讲解第 3 次课 2 学时授课章节第一章第5节授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求掌握人工变量法的基本思想以及大M法和两阶段法的求解。课堂教学重点及难点重点:人工变量法的基本思想。难点:大M法和两阶段法的求解。教学过程教学过程教学方法及手段1.5单纯形法的进
4、一步讨论及小结人工变量法的思想,大M法和两阶段法的求解思路和步骤。单纯形法小结多媒体讲解实例讲解2、课件1.1线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。例1:某工厂要安排生产、两种产品,每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多?设备128台时原材料A4016kg原材料B0412kg单位产品的利润(元)23解:设生产产品、的数量分别为和。首先,我们的目标是要获得最大利润,即其次,该生产计划受到一系列现实条件的约束,设备台时约束:生产所用的设备台时不得超过所拥有的设备台时,即原材料约束:生产所用的两种原材料A、B不
5、得超过所用有的原材料总数,即非负约束:生产的产品数必然为非负的,即由此可得该问题的数学规划模型:总结:线性规划的一般建模步骤如下:(1)确定决策变量确定决策变量就是将问题中的未知量用变量来表示,如例1中的和。确定决策变量是建立数学规划模型的关键所在。(2)确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。(3)确定约束条件将现实的约束用数学公式表示出来。线性规划数学模型的特点(1)有一个追求的目标,该目标可表示为一组变量的线性函数,根据问题的不同,追求的目标可以是最大化,也可以是最小化。(2)问题中的约束条件表示现实的限制,可以用线性等式或不等式表示。(3)问题用一组决策
6、变量表示一种方案,一般说来,问题有多种不同的备选方案,线性规划模型正式要在这众多的方案中找到最优的决策方案(使目标函数最大或最小),从选择方案的角度看,这是规划问题,从目标函数最大或最小的角度看,这是最优化问题。1.2 线性规划问题的标准形式根据问题的性质,线性规划有多种形式,目标函数有要求最大化的,也有要求最小化的;约束条件可以是“”或“”的不等式,也可以是“=”;虽然决策变量一般是非负的,但也可是无约束的,即,可以在取值。为了分析问题的简化,一般规定如下的标准形式:非标准形式转化为标准形式:(1)若目标函数要求实现最小化,则可令,可将原问题的目标函数转化为即可。(2)若约束方程为“”,则可
7、在“”的左边加上非负的松弛变量;若约束方程为“”,则可在“”的左边减去非负的剩余变量。(3)若存在取值无约束的变量,则可令,其中,。例:将如下问题转化为标准形式:解:首先,用替换,其中,;其次,在第一个约束条件的左端加上非负的松弛变量;再次,在第二个约束条件的左端减去非负的剩余变量;最后,令,将求改为求。由此,可得标准形如下:1.3线性规划问题的解首先,将线性问题的标准形式用矩阵和向量形式表示如下:其中,;,1、可行解和最优解满足约束条件的所有解成为线性规划问题的可行解,其中,使目标函数达到最大的可行解成为最优解。2、基和基解设为约束方程组的维矩阵,其秩为。设为矩阵中的阶非奇异子矩阵(),则称
8、为线性规划的一个基。不妨设前个变量的系数矩阵为线性规划的一个基,则为对应于这个基的基变量。用高斯消去法可求得一个解该解得非零分量的数目不大于方程个数,称为基解。3、基可行解若基解满足非负约束,则称其为基可行解。4、可行基对应于基可行解的基,成为可行基。1.4 单纯形法一、单纯形表考察一种最简单的形式:目标函数最大化、所有约束条件均为“”。利用所有约束条件化为等号的方法,在每个约束条件的左端加一个松弛变量,并整理,重新对变量及系数矩阵进行编号,得将其与目标函数的变换形式组成个变量、个方程的方程组。若将看成不参与基变换的基变量,它与的系数构成一个基,利用初等变换将变为零,则可得据此,可设计如下的数
9、表1000010列表示基变量,在这里为;列为基变量对应的价值系数;列为约束方程的右端项;行为所有变量的价值系数;列的数字是在确定换入变量后,按规则计算后填入;最后一行为各变量的检验数,尤其要注意的是非基变量的检验数。例,求解 首先将其转换为标准形式,构造初始单纯形表如下:230000812100401640010-01204001323000由上表可得初始基可行解由于和的检验数大于零,表明上述解不是最优解,由于的检验数更大,所以,先以为换入变量。根据规则,可确定为换出变量,计算得新表如下:23000021010-1/220164001043301001/4-2000-3/4可得新解,目标函数取
10、值。的检验数为2,换入。根据规则,可确定为换出变量,计算得新表如下:23000221010-1/2-0800-41243301001/41200-201/4得新解,目标函数取值。的检验数为1/4,换入。根据规则,可确定为换出变量,计算得:23000241001/400400-21/2132011/2-1/8000-3/2-1/80得解,目标函数取值。由于所有的检验都小于零,达到最优。PS:如果目标函数是求最小化,则,检验数的最优准则为检验数大于零。1.5单纯形法的进一步讨论及小结一、人工变量法如果初始约束条件不全是小于等于号,则不能直接得到初始基(单位基)和初始基可行解,此时必须要构造人工变量
11、。在迭代结束后,如果最后基变量中不再含有非零的人工变量,表示原问题有解;反之,则表示无可行解。例:在第一个约束条件中加入松弛变量;在第二个约束条件中加入剩余变量和人工变量;在第三个约束条件中加入人工变量。(1)大M法:在一个线性规划问题的约束条件中加入人工变量后,要求人工变量对目标函数值不产生影响,可假定人工变量在目标函数中的系数为(-M)(M为很大的正数),这样在目标函数要实现最大化时,必须将人工变量从基变量中换出,否则目标函数不会实现最大化。对上例求解,加入人工变量后,规划问题变成然后,利用单纯形法求解,详见P33。(2)两阶段法第一阶段:不考虑原问题是否有基可行解;给原线性规划问题加上人
12、工变量后,构造仅含人工变量的目标函数和要求实现最小化;然后用单纯形法求解,若得到该规划的最优解为零,说明原问题存在基可行解,否则原问题无可行解,停止计算。第二阶段:将第一阶段的最重计算表出去人工变量,换回原目标函数的系数作为第二阶段计算的初始表,利用单纯形法求解。前一个例子的两阶段法求解如下:构造出第一阶段的数学模型如下:00000110111-2110001113-4120-1103/211-201000116-1-3010000000110103-20100-1-110100-11-2101-2010001-0-10010000000110123001-22-5-010100-11-210
13、1-2010001-0000011得最优解。由于人工变量,说明是原问题的基可行解,可进行第二阶段运算。利用单纯形法,从下表开始:-311000123001-2-110100-1111-20100-10001-31100-341001/3-2/3-110100-11190012/3-4/3-0001/31/3二、解的退化所有的检验数均1、基变量中有非零的人工变量,无可行解;2、某非基变量的检验数为零,有无穷多解;对于任一检验数,若对应的系数向量,则有无界解。单纯形法小结变量不需处理令;无约束令,约束条件不需处理约束条件两端同乘-1加松弛变量=加人工变量减剩余变量,加人工变量目标函数加入变量的系数
14、松弛变量0人工变量第三章 运输问题1、教学计划第 4 次课 2 学时授课章节第三章授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求掌握运输问题的模型特点;熟悉表上作业法的基本步骤如初始调运方案的确定,非基变量检验数的确定方法,当前解是否最优解的判断,闭回路调整方法;非平衡运输问题的求解。课堂教学重点及难点重点:初始调运方案的确定,非基变量检验数的确定,判断当前解是否最优解,闭回路调整方法,非平衡运输问题的求解方法。难点:初始基可行解的确定、判断,非平衡问题的求解思路。教学过程教学过程教学方法及手段3.1 运输问题的提出及其模型特征运输问题的提出背景及其模型特征3.2运输问题的求解
15、:表上作业法表上作业法的思路和步骤如初始基可行解的确定(最小元素法和伏格尔法),最优解的判断方法,闭回路调整方法。3.3产销不平衡的运输问题将不平衡问题转化为平衡问题。多媒体讲解实例讲解2、课件3.1 运输问题的提出及其模型特征1、背景大规模的物资调运,将物资从生产地点运往消费地点,要求在现有的交通网络下,制定出总费用最小的运输方案。2、模型特征销地产地12产量12.销量个变量,个约束方程,但由于总产量等于总销量的关系存在,所以,独立的约束方程为,因此,其可行解中的基变量个数必然是。系数矩阵:变量的系数向量除第个分量和第个为1外其余为零。3.2 运输问题的求解:表上作业法表上作业法实际上是单纯
16、形法在求解运输问题时的一个简化,主要步骤:(1)找出初始基可行解:最小元素法和伏格尔(Vogel)法最小元素法:优先满足运价最小的供销关系例: 销地产地B1B2B3B4产量(吨)A13113107A219284A3741059销量(吨)3656 销地产地B1B2B3B4产量(吨)A13113107A2(3)9284A3741059销量(吨)3656 销地产地B1B2B3B4产量(吨)A13113107A2(3)9(1)84A3741059销量(吨)3656 销地产地B1B2B3B4产量(吨)A1311(4)107A2(3)9(1)84A3741059销量(吨)3656 销地产地B1B2B3B4
17、产量(吨)A1311(4)107A2(3)9(1)84A37(6)1059销量(吨)3656 销地产地B1B2B3B4产量(吨)A1311(4)10(3)7A2(3)9(1)84A37(6)10(3)9销量(吨)3656 销地产地B1B2B3B4产量(吨)A1437A2314A3639销量(吨)3656伏格尔法:优先满足最小运价与次小运价差值最大的行、列中的最小运价所对应的供销关系。 销地产地B1B2B3B4行差A13113100A219281A371051列差2513(2)求各非基变量(空格)的检验数。闭回路法:首先找到与空格对应的闭回路,规则是从要检验空格出发用水平或垂直线向前滑,碰到数字
18、格转90度(也可不转,空格处绝不转),最后回到出发空格形成闭回路。然后,在该空格处试着增加1单位运量,并保持平衡,在闭回路作相应的调整,调整后回路的总运费相对于调整前的变动量就是该空格的检验数 销地产地B1B2B3B4产量(吨)A1437A2314A3639销量(吨)3656 销地产地B1B2B3B4产量(吨)A1437A2314A3639销量(吨)3656如空格A3B1的检验数:7*1-5*1+10*1-3*1+2*1-1*1=10空格A2B4的检验数:8*1-2*1+3*1-10*1=-1位势法:构造位势和;由基变量的检验数,可得;任取、其中之一为零,可求得其他、;最后,由可求得个非基变量
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 完整 教案
限制150内