《运筹学基础教程教学课件》由会员分享，可在线阅读，更多相关《运筹学基础教程教学课件（504页珍藏版）》请在金锄头文库上搜索。
1、1,培训内容：运筹学部分 数模QQ群：2327087377,欢迎参加 数学建模培训,2,一分耕耘，一分收获！ 一次参赛，终生受益！,三天三夜疯狂的数学经历 让你一生难忘!,3,毕节学院2013年全国数学建模竞赛第一阶段培训计划,4,上课时间：上午： 8:10-11:30 （四节）下午：14:3018:00（四节）晚上：19:3021:00（二节） 上课地点：绣山实验楼D301，D401,培训方式,5,商人们怎样安全过河,问题(智力游戏)：, 3名商人 3名随从,随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.,但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?,问题分析
2、：,多步决策过程,决策 每一步(此岸到彼岸或彼岸到此岸)船上的人员,要求在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.,6,建立模型,xk第k次渡河前此岸的商人数,yk第k次渡河前此岸的随从数,xk, yk=0,1,2,3;k=1,2, ,sk=(xk , yk)过程的状态,S=(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2,S 允许状态集合,uk第k次渡船上的商人数,vk第k次渡船上的随从数,dk=(uk , vk)决策,D=(u , v) u+v=1, 2 允许决策集合,uk, vk=0,1,2;k=1,2, ,sk+1=
3、sk dk,+(-1)k,状态转移律,求dkD(k=1,2, n), 使skS, 并按转移律由 s1=(3,3)到达 sn+1=(0,0).,多步决策问题,7,模型求解,穷举法 编程上机,图解法,状态s=(x,y) 16个格点,允许决策 移动1或2格; k奇,左下移; k偶,右上移.,s1,sn+1,d1, ，d11给出安全渡河方案,评注和思考,规格化方法,易于推广,考虑4名商人各带一随从的情况,允许状态,S=(x , y) x=0, y=0,1,2,3;x=3, y=0,1,2,3; x=y=1,2,8,概述,运筹学（Operations Research）是用数学方法研究各种系统的最优化问
4、题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。运筹学的内容有数学规划、运输问题、图与网络分析、排队论、存储论、决策论和对策论等，其中数学规划又包括线性规划、整数规划、非线性规划、目标规划和动态规划等，虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。,9,所以可对运筹学做如下概括：.运筹学的研究对象是各种系统。.运筹学的研究目的是实现系统的最优化，
5、求得合理利用各种资源的最优方案。.运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解。.运筹学的研究动机是为决策者提供科学决策的依据。运筹学在工业、农业、商业、物流、经济计划、人力资源、军事等行业都有着非常广泛的应用。有人曾对世界上500家著名的企业集团或跨国公司进行过调查，发现其中95%曾使用过线性规划，75%使用过运输模型，90%使用过网络计划技术，90%使用过存储模型，43%使用过动态规划。由此可见运筹学是一门应用性很强的学科。特别是随着计算机技术的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越显示出其广泛的使用价值。,10,运筹学这
6、一名词最早出现于1938年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如：.防空雷达的布置问题：英美等国为了对付德国的空袭配备了先进的雷达作为防空系统的一部分，但是由于雷达系统的布置不甚合理，通过防空演习发现实际效果并不理想。.护航舰队的编队问题：英美等国需要对本国的商船队配备护航舰队，以防止德国潜艇的攻击，这里有一个如何合理编队才能使商船队一旦遭受德国潜艇攻击时损失最少的问题。为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为“Operational Research”，其他英语
7、国家称为“Operations Research”，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。,11,二战以后，在军事运筹小组中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。1947年美国数学家G.B.Dantzig在研究美国空军资源配置时,提出了求解线性规划的有效方法单纯形法。20世纪50年代初，应用计算机求解线性规划获得成功。至50年代末，一些工业先进国家的大型企业已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至60年代中期，运筹学开始应用于一些
8、服务性行业和公用事业。同时很多国家成立了运筹学研究学会，一些大学的相关专业也陆续设置了运筹学的有关课程。专门发表运筹学研究论文的刊物开始出版，运筹学的理论研究日趋成熟，在实际应用上则日趋广泛。,12,我国运筹学的研究始于20世纪50年代中期，当时由钱学森教授将运筹学从西方国家引入我国，以华罗庚教授为代表的一大批科学家在有关企事业单位积极推广和普及运筹学方法，在建筑、纺织、交通运输、水利建设和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我国年轻的数学家管梅谷于1962年首先提出的，在国际上统称为中国邮递员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。如今对运筹学的研究
9、大致在三个领域发展：运筹学应用、运筹科学和运筹数学。一般的共识是，运筹学的研究不能忘记其原有的应用性强的特色，必须强调多学科的交叉联系和解决实际问题的研究。我们面临的很多系统通常涉及到大量的经济、技术、社会、政治和心理等综合因素，这些综合因素受到人的影响和干预，存在非结构性的复杂问题，仅用数学模型是很难加以描述和解决的。总之随着社会的不断发展和进步，实践将对运筹学提出更新更多的研究课题，运筹学正处于不断发展，不断进步的时期。,13,目 录,第1章 线性规划的基本概念 第2章 单纯形法 第3章 对偶规划与灵敏度分析 第4章 运输问题 第5章 图与网络分析 第6章 排队论 第7章 存贮论 第8章
10、决策分析,14,第1章 线性规划的基本概念,线性规划问题及其数学模型线性规划的图解法线性规划的标准形式标准型线性规划的解的概念线性规划的基本理论,15,问题的提出：在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等 最佳：有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题：如何合理的使用有限的资源，使生产经营的效益达到最大；在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。,线性规划问题及其数学模型,16,与规划问题有关的数学模型总有两部分组成：约束条件：反映了有限资源
11、对生产经营活动的种种约束，或者生产经营必须完成的任务；目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。,17,例 某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：,已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？,18,定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。目标： 使总利润 Z=5x1+2x2 极大化 约束： 每周资源总量的限制，
12、 30x1+20x21605x1+ x2 15甲种药品每周产量不应超过4吨的限制x14计划生产数不可能是负数， x10 x20,19,数学模型为s.t. （subject to)(such that) 这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。 在满足一组约束条件的限制下，寻求决策变量x1，x2的决策值，使目标函数达到最大值。,20,例 某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有A、B、C三种化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知
13、甲、乙两种原料的成本分别是每公斤3元和2元，厂方希望总成本达到最小，问如何配置该产品？,化学成分,21,定义x1，x2分别为每公斤产品中甲，乙两种原料的数量， 目标：使总成本 Z=3x1+2x2 极小化 约束：配料平衡条件， x1+x2=1产品中A、B、C三种化学成分的最低含量12x1+3x242x1+3x223x1+15x25非负性条件 x10,x20,化学成分,22,数学模型：s.t.这是一个原料配制问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量x1和x2的值使目标函数取得最小值。,化学成分,23,例 某铁器加工厂要制
14、作100套钢架，每套要用长为2.9米、2.1米和1.5米的圆钢各一根。已知原料长为7.4米，问应如何下料，可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8种不同的下料方案：,问题归纳为如何混合使用这8种不同的下料方案，来制造100套钢架，且要使剩余的料头总长为最短。,24,设xj表示用第j种下料方案下料的原料根数，j=1,2,8, 目标：使料头总长度 Z=0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8极小化 约束：三种规格圆钢根数 x1+2x2 +x4 +x6 =1002x3+2x4 +x5+x6+3x7 =1003x1+x2+2x
15、3 +3x5+x6 +4x8=100非负取整条件 xj0 (j=1,2,8)且取整数,25,数学模型s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量x1至x8的值,使目标函数取得最小值。,且为整数,26,线性规划的一般数学模型线性规划模型的特征： （1）用一组决策变量x1,x2,xn表示某一方案，且在一般情况下，变量的取值是非负的。 （2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。 （3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。 （4）要求目标函数实现极大化（max）或极小化（min）。满足上述4个特征的规划问题称为线性规划问题,27,线性规划的模型的一般形式: 目标函数满足约束条件通常称 为决策变量， 为价值系数，为消耗系数, 为资源限制系数。,28,线性规划的图解法,适用于求解两个变量的线性规划问题图解法的基本步骤例4 利用例1说明图解法的主要步骤。例1的数学模型为 s.t.,29,O,5,10,15,x1,x1=4,x2,5,10,1,A,B( 2, 5),C,Z,5x1+x2=15,30x1+20x2=160,
