运筹学绪论要点.pptx
《运筹学绪论要点.pptx》由会员分享,可在线阅读,更多相关《运筹学绪论要点.pptx(77页珍藏版)》请在咨信网上搜索。
1、运筹学运筹学主讲:黄建华主讲老师简介主讲老师简介 黄建华,博士、副教授。东南大学管理学硕士,大连理工大学工学博士。研究方向:复杂网络与复杂系统、供应链管理。主持课题:(1)国家社科基金:干扰模拟与基于二维网络视角的农产品供应链脆弱性研究;(2)教育部人文社科基金:农产品供应链网络的抗毁性能研究-基于复杂网络理论的研究视角;(3)福建省社科基金:区域农产品供应链的抗毁性能及农业产业安全策略研究。第一作者在系统工程理论与实践、系统管理学报、系统工系统工程理论与实践、系统管理学报、系统工程、北京理工大学学报程、北京理工大学学报等国内外核心期刊发表学术论文20余篇,其中EI收录5篇。绪绪 论论一、运筹
2、学的简史 1、运筹学的早期发展历史v1914年提出兰彻斯特(Lanchester)战斗方程。v1917年丹麦工程师爱尔朗(Erlang)提出排队论的部分著名公式、v20世纪20年代,提出存储论的最优批量公式。2、二战期间的运筹学发展v20世纪30年代,运筹学(Operational research)作为科学名字出现。v运用于雷达防空系统。v应用于护航舰队保护商船的编队问题。v应用于反潜深水炸弹的合理爆炸深度研究。v应用于船只遭受敌机攻击时,转向逃避的问题研究。该阶段运筹学研究和解决的问题,大部分都是些短期的和战术性的问题。3、二战之后的发展v正式的运筹研究组织成立,开始着重研究战略性的问题。
3、v60年代后,除了军事方面的研究,运筹学在工业、农业、经济和社会问题等各领域都有广泛应用。v运筹学技术自身得到飞速发展,并且形成了许多分支。二、运筹学的主要内容1 1、数学规划、数学规划v线性规划(线性规划(19471947年由丹捷格提出)年由丹捷格提出)v非线性规划非线性规划v整数规划整数规划v目标规划(目标规划(19611961年由查恩斯、库伯提出)年由查恩斯、库伯提出)v动态规划(动态规划(19511951年由贝尔曼提出)年由贝尔曼提出)v随机规划随机规划2 2、图论与网络、图论与网络3 3、排队论(随机服务系统理论)、排队论(随机服务系统理论)4 4、存储论、存储论5 5、对策论(竞赛
4、论、博弈论)、对策论(竞赛论、博弈论)6 6、决策论(多目标决策)、决策论(多目标决策)三、运筹学的工作步骤1、提出和形成问题(目的、约束、可控变量)。2、建立模型。3、求解(利用各种数学方法或者计算机)。4、解的检验。5、解的控制。6、解的实施。第一章第一章 线性规划及单纯形法线性规划及单纯形法1线性规划问题及其数学模型一、问题的提出:问题1:合理利用资源问题例1:产品一产品一产品二产品二设备设备128台时台时原材料原材料A4016kg原材料原材料B0412kg每件产每件产品利润品利润2元元3元元线性规划数学模型的三个条件(特征)每一个问题都用一组决策变量表示某一方案,每一个问题都用一组决策
5、变量表示某一方案,一般这些变量的取值是非负。一般这些变量的取值是非负。存在一定的约束条件,这些约束条件可以用一存在一定的约束条件,这些约束条件可以用一组线性等式或不等式来表示。组线性等式或不等式来表示。都有一个都有一个要求达到的目标,它可以用决策变量达到的目标,它可以用决策变量的线性函数(称为目标函数)来表示。按照问的线性函数(称为目标函数)来表示。按照问题的不同要求实现最大或者最小化。题的不同要求实现最大或者最小化。课堂练习:课堂练习:某饲养场饲养动物出售,设每头动物每天至少需某饲养场饲养动物出售,设每头动物每天至少需700克克蛋白质、蛋白质、30克矿物质、克矿物质、100毫克维生素。现有五
6、种饲料毫克维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量及单价如表可供选用,各种饲料每公斤营养成分含量及单价如表所示:所示:要求确定既满足动物生长的营养需要,又使费用最省要求确定既满足动物生长的营养需要,又使费用最省的选料方案。的选料方案。饲料饲料蛋白质蛋白质(克)(克)矿物质矿物质(克)(克)维生素维生素(毫克毫克)价格价格(元(元/千克)千克)1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8第一章第一章 线性规划及单纯形法线性规划及单纯形法问题问题2:下料问题:下料问题问题问题3:配料问题:配料问题 问问题题4:成成批批生生产产
7、企企业业年年度度生生产产计计划划的的按按月分配月分配问题问题5:连续投资问题:连续投资问题二、二、数学模型数学模型:第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法线性规划数学模型的标准化线性规划数学模型的标准化变变量量 =0不处理不处理 =0取相反数取相反数 无约束无约束两非负数之差两非负数之差约约束束条条件件b大于等于大于等于0不处理不处理b小于等于小于等于0两边乘以两边乘以-1小于等于号小于等于号加松弛变量加松弛变量等于号等于号加人工变量加人工变量大于等于号大于等于号减去剩余变量,
8、加上人减去剩余变量,加上人工变量工变量目目标标函函数数Max z不处理不处理Min z取相反数取相反数加入变量的系数加入变量的系数松弛、剩余变量松弛、剩余变量人工变量人工变量0-M第一章 线性规划及单纯形法四、线性规划问题的解:四、线性规划问题的解:1 可行解、可行域2 最优解第一章第一章 线性规划及单纯形法线性规划及单纯形法1 基阵2 基向量、非基向量、基变量、非基变量3 基解、基可行解、可行解2 图解法图解法一、图解法步骤:一、图解法步骤:第一章第一章 线性规划及单纯形法线性规划及单纯形法第一章 线性规划及单纯形法二、线性规划解的几种情形二、线性规划解的几种情形1无无穷穷多多最最优优解解。
9、目目标标函函数数执执行行平平行行于于可可行域某一边行域某一边2唯一解唯一解3无界解无界解4.无可行解无可行解 第一章 线性规划及单纯形法三、图解法得到的启示:三、图解法得到的启示:1解的情形2可行域为一凸集3最优解一定在可行域凸集的某个顶点处获得4解题思路 第一章 线性规划及单纯形法3 单纯形法原理单纯形法原理一、凸集及顶点凸集、顶点二、几个基本定理定理1 若(LP)存在可行解,则其可行域为凸集 引理:线性规划问题的可行解 第一章 线性规划及单纯形法 为基可行解充要条件是X的正分量所对应的系数列向量是线性无关的。定理2 线性规划问题基可行解X对应线性规划问题可行域(凸集)的顶点定理3 若线性规
10、划问题有最优解,一定存在一个基可行解是最优解。三、单纯形法迭代原理1、确定初始基可行解(顶点)1 约束为“”2 约束为“”、“=”第一章 线性规划及单纯形法2、第一章 线性规划及单纯形法第一章线性规划及单纯形法为对应于基B的一个基可行解,且对于一切 为最优解。定理2:若存在 则线性规划有无穷多解。定理3:若 为一基可行解,存在 且 则线性规划问题无解。3 寻找改进的基可行解 换入变量的确定:若存在 则令 则 为换入变量。第一章线性规划及单纯形法换出变量的确定 第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划及单纯形法5 单纯形法的进一步讨论单纯形法的进一步讨论 一、找初始基可行解
11、的两阶段法:第一阶段:对约束为:加入人工变量 求解:第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划及单纯形法6 应用举例应用举例例一(下料问题):例一(下料问题):现要做现要做100套钢架,每套用长套钢架,每套用长为为2.9m,2.1m,1.5m的元钢各一根,已知料长的元钢各一根,已知料长为为7.4m,问应该如何下料,使用的原材料最省。,问应该如何下料,使用的原材料最省。第一章线性规划及单纯形法2.92.11.5例二(配料问题):例二(配料问题):某工厂要用三种原材料某工厂要用三种原材料C、P、H混合混合调配出三种不同规格的产品调配出三种不同规格的产品A、B、D。已知产品的规格
12、。已知产品的规格要求,产品单价,每天能供应的原材料数量及原材料单要求,产品单价,每天能供应的原材料数量及原材料单价,分别见表一、表二,该工厂应该如何安排生产,使价,分别见表一、表二,该工厂应该如何安排生产,使利润收入最大?利润收入最大?第一章线性规划及单纯形法产品名称产品名称规格要求规格要求单价(元单价(元/kg)A原材料原材料C不少于不少于50%,P不超过不超过25%50B原材料原材料C不少于不少于25%,P不超过不超过50%35D不限制不限制25原材料名称原材料名称每天最多供应量(每天最多供应量(kg)单价(元单价(元/kg)C10065P10025H6035人力资源分配问题人力资源分配问
13、题 例3某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下:设司机和乘务人员分别在各时间段一开始时上班,并连续工作八小时,问该公交线路怎样安排司机和乘务人员,既能满足工作需要,又配备最少司机和乘务人员?第一章线性规划及单纯形法例例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?解:解:产销平衡问题:总产量=总销量设xij为从产地Ai运往销地Bj的运输量,得到下列运输量表:Min f=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+
14、x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1、2;j=1、2、3)运运 输输 模模 型型建模步骤建模步骤第第第第一一一一步步步步:决决决决策策策策变变变变量量量量。决决决决策策策策变变变变量量量量选选选选取取取取得得得得当当当当,不不不不仅仅仅仅能能能能顺顺顺顺利利利利地地地地建建建建立立立立模模模模型型型型而而而而且且且且能能能能方方方方便便便便地地地地求求求求解解解解,否否否否则则则则很很很很可可可可能事倍功半。能事倍功半。能事倍功半。能事倍功半。第第第第二二二二步步步步:约约约约束束束束条条条
15、条件件件件。并并并并用用用用决决决决策策策策变变变变量量量量的的的的线线线线性性性性方方方方程程程程或或或或线线线线性性性性不不不不等等等等式式式式来来来来表表表表示示示示。当当当当限限限限制制制制条条条条件件件件多多多多,背背背背景景景景比比比比较较较较复复复复杂杂杂杂时时时时,可可可可以以以以采采采采用用用用图图图图示示示示或或或或表表表表格格格格形形形形式式式式列列列列出出出出所所所所有有有有的的的的已已已已知知知知数数数数据据据据和和和和信信信信息息息息,以以以以避避避避免免免免“遗遗遗遗漏漏漏漏”或或或或“重重重重复复复复”所造成的错误。所造成的错误。所造成的错误。所造成的错误。第三
16、步:目标函数。第三步:目标函数。确定对函数是取极确定对函数是取极大还是取极小的要求。大还是取极小的要求。决策变量的非负要求可以根据问题决策变量的非负要求可以根据问题的实际意义加以确定。的实际意义加以确定。讨论:这三步的顺序可以颠倒吗?讨论:这三步的顺序可以颠倒吗?为什麽?为什麽?经济管理领域中经济管理领域中 几类典型的几类典型的LPLP问题问题 经经经经济济济济管管管管理理理理领领领领域域域域中中中中有有有有大大大大量量量量的的的的实实实实际际际际问问问问题题题题可可可可以以以以归归归归结结结结为为为为线线线线性性性性规规规规划划划划问问问问题题题题来来来来研研研研究究究究,这这这这些些些些问
17、问问问题题题题背背背背景景景景不不不不同同同同,表现各异,但数学模型却有着完全相同的形式。表现各异,但数学模型却有着完全相同的形式。表现各异,但数学模型却有着完全相同的形式。表现各异,但数学模型却有着完全相同的形式。尽尽尽尽可可可可能能能能多多多多地地地地掌掌掌掌握握握握一一一一些些些些典典典典型型型型的的的的模模模模型型型型不不不不仅仅仅仅有有有有助助助助于于于于深深深深刻刻刻刻理理理理解解解解线线线线性性性性规规规规划划划划本本本本身身身身的的的的理理理理论论论论和和和和方方方方法法法法,而而而而且且且且有有有有利利利利于于于于灵灵灵灵活活活活地地地地处处处处理理理理千千千千差差差差万万万
18、万别别别别的的的的实实实实际际际际问问问问题题题题,提提提提高高高高解决实际问题的能力。解决实际问题的能力。解决实际问题的能力。解决实际问题的能力。例题例题1:人力资源分配问题:人力资源分配问题公交线路需要公交线路需要24小时值班,每次值班小时值班,每次值班8小小时。不同时段需要的人数不等。时。不同时段需要的人数不等。序号序号时段时段最少人数最少人数106106021014703141860418225052202206020630问题:如何安排,所需人数最少问题:如何安排,所需人数最少?例题例题1:人力资源分配问题:人力资源分配问题设设xi为第为第i班次开始上班的人数班次开始上班的人数目标函
19、数:目标函数:min Z=x1+x2+x3+x4+x5+x6约束条件:约束条件:x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1+x6 60非负性约束:非负性约束:xj 0,j=1,2,6例题例题2:人力资源分配问题:人力资源分配问题福安商场是个中型的百货商场,它对售货人福安商场是个中型的百货商场,它对售货人员的需求经过统计分析如下所示员的需求经过统计分析如下所示例题例题2:人力资源分配问题:人力资源分配问题为了保证售货人员充分休息,售货人员每周工作为了保证售货人员充分休息,售货人员每周工作五天,休息两天,并要求休息的两天是连续的,五天,休息两天,
20、并要求休息的两天是连续的,问应该如何安排售货人员的作息,既满足了工作问应该如何安排售货人员的作息,既满足了工作需要,又使配备的售货人员的人数最少需要,又使配备的售货人员的人数最少?分析:设分析:设xi为星期为星期i开始休息的人数,开始休息的人数,i=1,2,3,7,目标是要求售货人员的总数最少目标是要求售货人员的总数最少,因为每个百货员因为每个百货员都工作五天,休息两天,所以只要计算出连续休都工作五天,休息两天,所以只要计算出连续休息两天的售货员人数,也就计算出了售货员的总息两天的售货员人数,也就计算出了售货员的总数。把连续休息两天的售货员按照开始休息的时数。把连续休息两天的售货员按照开始休息
21、的时间分成间分成7类,类,例题例题2:人力资源分配问题:人力资源分配问题 解:设解:设 x xi i(i=1,2,(i=1,2,7),7)表示星期表示星期i i开始休息的人数。开始休息的人数。目标函数:目标函数:Min Min x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 约束条件:约束条件:s.t.s.t.x x1 1+x x2 2+x x3 3+x x4 4+x x5 5 28 28 x x2 2+x x3 3+x x4 4+x x5 5+x x6 6 15 15 x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 24
22、 24 x x4 4+x x5 5+x x6 6+x x7 7+x x1 1 25 25 x x5 5+x x6 6+x x7 7+x x1 1+x x2 2 19 19 x x6 6+x x7 7+x x1 1+x x2 2+x x3 3 31 31 x x7 7+x x1 1+x x2 2+x x3 3+x x4 4 28 28 x1,x2,x3,x4,x5,x6,x7 0例题例题3 生产计划问题生产计划问题明兴公司面临一个是外包协作还是自行生产的明兴公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品,这三问题。该公司生产甲、乙、丙三种产品,这三种产品都要经过铸造、机加
23、工和装配三个车间。种产品都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作,亦可以甲、乙两种产品的铸件可以外包协作,亦可以自行生产,但产品丙必须本厂铸造才能保证质自行生产,但产品丙必须本厂铸造才能保证质量。公司可利用的总时数:铸造量。公司可利用的总时数:铸造80008000小时;机小时;机加工加工1200012000小时;装配小时;装配1000010000小时。有关搞况见小时。有关搞况见下表:下表:例题例题3 生产计划问题生产计划问题例题例题3 生产计划问题生产计划问题设设x1,x2,x3分别为三道工序都由本公司加工分别为三道工序都由本公司加工的甲、乙、丙三种产的件数,设的甲
24、、乙、丙三种产的件数,设x4,x5分别为分别为由外协铸造再由本公司机加工和装配的甲、乙由外协铸造再由本公司机加工和装配的甲、乙两种产品的数量:两种产品的数量:计算每件产品的利润:计算每件产品的利润:产品甲全部自制的利润产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协,其余自制的利润产品甲铸造外协,其余自制的利润=23-(5+2+3)=13 产品乙全部自制的利润产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸造外协,其余自制的利润产品乙铸造外协,其余自制的利润 =18-(6+1+2)=9 产品丙的利润产品丙的利润 =16-(4+3+2)=7 可得到可得到 xi(i=
25、1,2,3,4,5)的利润分别为的利润分别为 15、10、7、13、9 元。元。例题例题3 生产计划问题生产计划问题数学模型数学模型:目标函数:目标函数:Max 15Max 15x x1 1+10+10 x x2 2+7+7x x3 3+13+13x x4 4+9+9x x5 5 约束条件:约束条件:5 5x x1 1+10+10 x x2 2+7+7x x3 3 8000 8000 6 6x x1 1+4+4x x2 2+8+8x x3 3+6+6x x4 4+4+4x x5 5 12000 12000 3 3x x1 1+2+2x x2 2+2+2x x3 3+3+3x x4 4+2+2x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 绪论 要点
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。