《管理运筹学教案1-绪论及线性规划模型课件》由会员分享，可在线阅读，更多相关《管理运筹学教案1-绪论及线性规划模型课件（38页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学,赵 鹏 徐 彬 电话：51687005 办公地点：8711 邮箱: ,2019/4/28,管理运筹学课程组,2,1 运筹学的由来,鲍德西（Bawdsey）雷达站的研究（1935年） 研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“Operational Research”，即“运筹学”。,一、绪论,运筹学的活动是从二次世界大战初期的军事任务开始的。当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内
2、的各项活动。,2019/4/28,管理运筹学课程组,3,大西洋反潜战（1942年） 应英国要求，美国派MORSE率领一个小组去协助。MORSE经过多方实地考察，最后提出了两条重要建议： 将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。 起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍) 运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%） 丘吉尔采纳了MORSE的建议，最终成功地打破封锁，并重创了德国潜艇。MORSE同时获得英国和美国的最高勋章。,2019/4/28,管理运筹学课程组,4,英国
3、战斗机中队援法决策（40年代） 第二次世界大战后，德国军队突破了法国的马奇诺防线，法军节节败退。英国为了对抗德国，派遣了十几个战斗机中队，在法国上空与德国军队作战，并且指挥、维护均在法国进行。 英国运筹人员得知此事后，进行了一项研究，其结果表明：在当时情况下，当损失率、补充率为现行水平时，仅仅再进行两周时间左右，英国的援法战斗机就连一架也不存在了。 运筹学家以简明的图表、明确的分析结果说服了丘吉尔，丘吉尔最终决定：不仅不再增加新的战斗机中队，而且还将在法国的英国战斗机中队大部分撤回英国本土，以本土为基地，继续对抗德国。局面有了很大的改观。,2019/4/28,管理运筹学课程组,5,重要事件:,
4、古代朴素的运筹思想 1917年爱尔朗的排队论公式。 1939年英国成立第一个运筹学工作小组，从事防空预警系统的研制（研究如何合理运用雷达），使原先平均击落一架敌机要发2万发炮弹改善为只要发4千发炮弹。 1939年前苏联的康托洛维奇提出类似线性规划模型， 1960年最佳资源利用的经济计算,获诺贝尔奖。 1942年美国成立运筹学工作小组,研究战斗行动效能,行动方式。 1947年美国数学家，提出线性规划模型及单纯形算法 战争结束，Mores和Kimball合著第一部专著“运筹学的方法”。 战后，运筹学的应用领域从军事扩展到其它各领域。,2019/4/28,管理运筹学课程组,6,学会组织,1948年英
5、国成立运筹学学会 1952年美国成立运筹学学会 1956年法国成立运筹学学会 1959年英、美、法成立运筹学联合会 我国50年代引入运筹学，1982年加入世界运筹学联合会(1956年时曾使用“运用学”，57年定名为“运筹学”),2019/4/28,管理运筹学课程组,7,2 运筹学的性质和内容,由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。钱学森,运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、资金等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”英国运
6、筹学会,运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。近代运筹学工作者,1.运筹学的定义,“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。” P.M.Morse与G.E.Kimball,2019/4/28,管理运筹学课程组,8,2.特点,(1)运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行业、部门之限制； (2)运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效； (3)它以
7、整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。,2019/4/28,管理运筹学课程组,9,规划论线性规划、目标规划、非线性规划、 整数规划、动态规划、组合规划等 图与网络 存储论 排队论 对策论 决策论 仿真 马尔科夫过程 可靠性 多目标规划,2019/4/28,管理运筹学课程组,10,3 运筹学的工作步骤,1. 提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数； 2. 建立模型。即把问题中可控变量、参数和目标与约束
8、之间的关系用一定的模型表示出来； 3. 求解。用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出； 4. 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题； 5. 解的实施。是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。,2019/4/28,管理运筹学课程组,11,4 本课程的要求,本课程的授课对象是管理科学与工程类及交通运输类专业,本科生，属管理类专业技术基础必修课。,学生通过学习该课程，应了解管理运筹学对优化决策问题进,行定量研究的特
9、点，,理解,线性规划、整数规划、动态规划、图与,网络、排队论,等分支的基本优化,原理，掌握,其中常用的,模型和算法,，,具有一定的建模能力。,先修课程主要为,线性代数和概率统计,，学生对它们的掌握程,度直接影响本课程的学习，所以要求学生课前要做必要的复习。,学习方法：理解、掌握基本理论和方法的基础上，适当作些,习题。,参考书：其他版本的管理运筹学,二. 线性规划 (LP ) ( Linear Programming),本部分是课程的最重要部分,2019/4/28,管理运筹学课程组,13,1 线性规划问题及其数学模型,第一章 线性规划与单纯形法,2019/4/28,管理运筹学课程组,14,1.1
10、 问题的提出,例1某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和A、B两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？,2019/4/28,管理运筹学课程组,15,利润最大 目标函数 max z = 2x1+ 3x2,2019/4/28,管理运筹学课程组,16,例2: 某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表,40 45 24,3 3 2,2 3 1,A B C,单位产品利润,单位产品橡胶量,单位产品钢消耗量,产品,已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各多少使总利润最大？,2019/4/28,管理运筹学
11、课程组,17,2019/4/28,管理运筹学课程组,18,2019/4/28,管理运筹学课程组,19,2019/4/28,管理运筹学课程组,20,2019/4/28,管理运筹学课程组,21,2019/4/28,管理运筹学课程组,22,2019/4/28,管理运筹学课程组,23,x1,x2,0,4,Q2(4,2),Q1,Q3,Q4,4x1=16,4x2=12,x1+2x2=8,3,Q2,4.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。,解 法 ：,2019/4/28,管理运筹学课程组,24,线性规划问题解的存在情况：,(1)存在唯一最优解,如例1,20
12、19/4/28,管理运筹学课程组,25,（2）有无穷多最优解,若将例1目标函数变为 max z = 2x1+ 4x2，则问题变得存在无穷多最优解。如图,2019/4/28,管理运筹学课程组,26,（3）有无界解( 无有限最优解或无最优解 ),（4）无可行解（可行域为空集）,注意： 没有存在有限多个解的情况 可行域有界时必有最优解，无界时不一定无最优解,2019/4/28,管理运筹学课程组,27,用图解法求下面问题的解,1,2,无界,不可行,2019/4/28,管理运筹学课程组,28,13 线性规划问题的标准形式 为了求解LP问题，必须统一其模型，本课程选用标准型式为,max z =c1x1 +
13、 c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + amnxn = bm x1，x2，xn 0 (1.3) 其中bi 0，（i =1，2，m） 一般m 0。,2019/4/28,管理运筹学课程组,29,标准型的简写形式: max z =c1x1 + c2x2 + cnxn (1.1) s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 (1.2) am1x1 + am2x2 + am
14、nxn = bm x1，x2，xn 0 (1.3),用求和符号表示,2019/4/28,管理运筹学课程组,30,用矩阵描述为： max z =CX AX = b X 0,称 A 为约束条件的m n 阶系数矩阵，一般A的秩为m。,2019/4/28,管理运筹学课程组,31,用向量表示：,向 量 Pj 对 应 的 决 策 变 量 为 xj 。,2019/4/28,管理运筹学课程组,32,(p1,p2, ,pn) Pjxj=b,a11 a12 a1n a21 a22 a2n am1 am2 amn,=,xj0 j=1,n,=,aijxj =bi,i=1,m,AX = b X 0,b,2019/4/2
15、8,管理运筹学课程组,33,2019/4/28,管理运筹学课程组,34,x1 + 2 x2 8 4 x1 16 4 x2 12 x1，x2 0,max z = 2x1+ 3x2 + 0 x3 + 0 x4+ 0 x5,标准型：,例3将例1的数学模型化为标准型。 max z = 2x1+ 3x2,所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有利润，在目标函数中其系数应为零；即c3 ，c4 ，c5 = 0。,x1+ 2 x2 + x3 = 8 4 x1 + x4 =16 4 x2 + x5 =12 x1，x2，x3，x4，x5 0,2019/4/28,管理运筹学课程组,35,x1 + x2 + x3 7 x1 x2 + x3 2 3 x1+ x2 +2 x3 = 5 x1，x2 0，x3为无符号约束,例4将下述线性规划问题化为标准型 min z = x1 +2x2 3x3,解：用x4 - x5 替换x3 ，令z = -z,x1 + x2 + (
