管理运筹学教案1-绪论及线性规划模型复习过程.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,管理运筹学课程组,*,Click to edit Master title style,管理运筹学教案1-绪论及线性规划模型,大西洋反潜战（1942年）,应英国要求，美国派MORSE率领一个小组去协助。MORSE经过多方实地考察，最后提出了两条重要建议：,将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷深水炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍),运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%）,丘吉尔采纳了MORSE的建议，最终成功地打破封锁，并重创了德国潜艇。MORSE同时获得英国和美国的最高勋章。,2,管理运筹学课程组,英国战斗机中队援法决策（40年代）,第二次世界大战后，德国军队突破了法国的马奇诺防线，法军节节败退。英国为了对抗德国，派遣了十几个战斗机中队，在法国上空与德国军队作战，并且指挥、维护均在法国进行。,英国运筹人员得知此事后，进行了一项研究，其结果表明：在当时情况下，当损失率、补充率为现行水平时，仅仅再进行两周时间左右，英国的援法战斗机就连一架也不存在了。,运筹学家以简明的图表、明确的分析结果说服了丘吉尔，丘吉尔最终决定：不仅不再增加新的战斗机中队，而且还将在法国的英国战斗机中队大部分撤回英国本土，以本土为基地，继续对抗德国。局面有了很大的改观。,3,管理运筹学课程组,重要事件:,古代朴素的运筹思想,1917年爱尔朗的排队论公式。,1939年英国成立第一个运筹学工作小组，从事防空预警系统的研制（研究如何合理运用雷达），使原先平均击落一架敌机要发2万发炮弹改善为只要发4千发炮弹。,1939年前苏联的康托洛维奇提出类似线性规划模型，,1960年最佳资源利用的经济计算,获诺贝尔奖。,1942年美国成立运筹学工作小组,研究战斗行动效能,行动方式。,1947年美国数学家，提出线性规划模型及单纯形算法,战争结束，Mores和Kimball合著第一部专著“运筹学的方法”。,战后，运筹学的应用领域从军事扩展到其它各领域。,12/19/2024,4,管理运筹学课程组,学会组织,1948年英国成立运筹学学会,1952年美国成立运筹学学会,1956年法国成立运筹学学会,1959年英、美、法成立运筹学联合会,我国50年代引入运筹学，1982年加入世界运筹学联合会(1956年时曾使用“运用学”，57年定名为“运筹学”),12/19/2024,5,管理运筹学课程组,2 运筹学的性质和内容,由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。钱学森,运用科学方法来解决工业、商业、政府、国防等部门里有关人力、机器、物资、资金等大型系统的指挥或管理中所出现的复杂问题的一门学科。其目的是“帮助管理者以科学方法确定其方针和行动”英国运筹学会,运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。近代运筹学工作者,1.运筹学的定义,“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”P.M.Morse与G.E.Kimball,12/19/2024,6,管理运筹学课程组,2.特点,(,1)运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行业、部门之限制；,(2)运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；,(3)它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。,12/19/2024,7,管理运筹学课程组,规划论线性规划、,目标规划、非线性规划、,整数规划、动态规划、,组合规划,等,图与网络,存储论,排队论,对策论 决策论 仿真 马尔科夫过程 可靠性 多目标规划,12/19/2024,8,管理运筹学课程组,3 运筹学的工作步骤,1.提出和形成问题。,即要弄清问题的目标，可能的约束，问题的可控变量以及有关参数；,2.建立模型。,即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示出来；,3.求解。,用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出；,4.解的检验。,首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题；,5.解的实施。,是指将解用到实际中必须考虑到实施的问题，如向实际部门讲清楚用法、在实施中可能产生的问题和修改。,12/19/2024,9,管理运筹学课程组,4 本课程的要求,本课程的授课对象是管理科学与工程类及交通运输类专业,本科生，属管理类专业技术基础必修课。,学生通过学习该课程，应了解管理运筹学对优化决策问题进,行定量研究的特点，,理解,线性规划、整数规划、动态规划、图与,网络、排队论,等分支的基本优化,原理，掌握,其中常用的,模型和算法,，,具有一定的建模能力。,先修课程主要为,线性代数和概率统计,，学生对它们的掌握程,度直接影响本课程的学习，所以要求学生课前要做必要的复习。,学习方法：理解、掌握基本理论和方法的基础上，适当作些,习题。,参考书：其他版本的管理运筹学,12/19/2024,10,管理运筹学课程组,二.线性规划 (LP)(Linear Programming),本部分是课程的最重要部分,1 线性规划问题及其数学模型,第一章 线性规划与单纯形法,12,管理运筹学课程组,1.1 问题的提出,例1某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和,A、B,两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？,12/19/2024,13,管理运筹学课程组,利润最大 目标函数 max,z,=2,x,1,+3,x,2,12/19/2024,14,管理运筹学课程组,例2:某工厂用钢与橡胶生产3种产品A、B、C，有关资料如下表,40,45,24,3,3,2,2,3,1,A,B,C,单位产品利润,单位产品橡胶量,单位产品钢消耗量,产品,已知每天可获得100单位的钢和120单位橡胶，问每天生产A、B、C各多少使总利润最大？,解,：设x,1,，x,2，,x,3,分别为A、B、C日产量，则有,约束条件,2 x,1,+3x,2,+x,3,100,3x,1,+3x,2,+2x,3,120,x,1,0，x,2,0，x,3,0称x,1,，x,2，,x,3,0为决策变量,目标函数：max z=40 x,1,+45x,2,+24x,3,12/19/2024,15,管理运筹学课程组,2万m,3,1.4万m,3,12/19/2024,16,管理运筹学课程组,2万m,3,1.4万m,3,12/19/2024,17,管理运筹学课程组,12/19/2024,18,管理运筹学课程组,19,管理运筹学课程组,20,管理运筹学课程组,21,管理运筹学课程组,x,1,x,2,0,4,Q,2,(4,2),Q,1,Q,3,Q,4,4,x,1,=16,4,x,2,=,12,x,1,+2,x,2,=8,2x,1,+3x,2,=0,3,Q,2,4.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。,解 法：,22,管理运筹学课程组,线性规划问题解的存在情况：,(1)存在唯一最优解,x,1,x,2,0,4,Q,2,(4,2),Q,1,Q,3,Q,4,4,x,1,=16,4,x,2,=,12,x,1,+2,x,2,=8,2x,1,+3x,2,=0,3,Q,2,如例1,23,管理运筹学课程组,（2）有无穷多最优解,若将例1目标函数变为 max,z,=2,x,1,+4,x,2,，则问题变得存在无穷多最优解。如图,x,1,x,2,0,4,Q,2,(4,2),Q,1,Q,3,Q,4,4,x,1,=16,4,x,2,=,12,x,1,+2,x,2,=8,2x,1,+,4,x,2,=0,3,Q,2,24,管理运筹学课程组,（3）有无界解(无有限最优解或无最优解),z,（4）无可行解（可行域为空集）,注意：,没有存在有限多个解的情况,可行域有界时必有最优解，无界时不一定无最优解,25,管理运筹学课程组,用图解法求下面问题的解,1,2,无界,不可行,26,管理运筹学课程组,13 线性规划问题的标准形式,为了求解LP问题，必须统一其模型，本课程选用标准型式为,max,z,=,c,1,x,1,+,c,2,x,2,+,+,c,n,x,n,(1.1),s.t.,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,=,b,1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,=,b,2,(1.2),a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,=,b,m,x,1,，,x,2,，,，,x,n,0 (1.3),其中,b,i,0，（,i,=1，2，,，,m,）,一般,m 0,。,27,管理运筹学课程组,标准型的简写形式:,max,z,=,c,1,x,1,+,c,2,x,2,+,+,c,n,x,n,(1.1),s.t.,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,=,b,1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,=,b,2,(1.2),a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,=,b,m,x,1,，,x,2,，,，,x,n,0 (1.3),用求和符号表示,28,管理运筹学课程组,用矩阵描述为：,max,z,=,CX,AX=b,X,0,=(,P,1,，,P,2,，,，,P,n,)；,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,A=,称,A,为约束条件的m,n,阶系数矩阵，一般A的秩为m。,0,=,0,0,0,29,管理运筹学课程组,用向量表示：,X,=,x,1,x,2,x,n,P,j,=,a,1j,a,2j,a,mj,b,=,b,1,b,2,b,m,向 量,P,j,对 应 的 决 策 变 量 为,x,j,。,30,管理运筹学课程组,b,1,b,2,b,m,(p,1,p,2,p,n,),P,j,x,j,=b,a,11,a,12,a,1n,a,21,a,22,a,2n,a,m1,a,m2,a,mn,x,1,x,2,x,n,=,x,j,0 j=1,n,x,1,x,2,x,n,Max,z=,x,1,x,2,x,n,(c,1,c,2,c,n,),=,c,j,x,j,=,CX,=,a,ij,x,j,=b,i,i=1,m,AX=b,X,0,b,31,管理运筹学课程组,32,管理运筹学课程组,x,1,+2,x,2,8,4,x,1,16,4,x,2,12,x,1,，,x,2,0,max,z,=2,x,1,+3,x,2,+0,x,3,+0,x,4,+0,x,5,标准型：,例3将例1的数学模型化为标准型。,max,z,=2,x,1,+3,x,2,所加松弛变量,x,3,，,x,4,，,x,5,表示没有被利用的资源，当然也没有,利润，在目标函数中其系数应为零；即,c,3,，,c,4,，,c,5,=0。,x,1,+2,x,2,+,x,3,=8,4,x,1,+x,4,=,16,4,x,2,+,x,5,=12,x,1,，,x,2,，,x,3,，,x,4,，,x,5,0,33,管理运筹学课程组,x,1,+,x,2,+,x,3,7,x,1,x,2,+,x,3,2,3,x,1,+,x,2,+2,x,3,=5,x,1,，,x,2,0，,x,3,为无符号约束,例4将下述线性规划问题化为标准型,min,z,=,x,1,+2,x,2,3,x,3,解：用,x,4,-,x,5,替换,x,3,，令z,=-,z,x,1,+,x,2,+,(,x,4,-,x,5,)+,x,6,=7,x,1,x,2,+,(,x,4,-,x,5,),-,x,7,=2,3,x,1,+,x,2,+2,(,x,4,-,x,5,)=5,x,1,，,x,2,，,x,4,，,x,5,，,x,6,，,x,7,0,max z,=,x,1,2,x,2,+,3,(,x,4,-,x,5,)+0,x,6,+0,x,7,用标准型求最优解后，再回到原变量。,34,管理运筹学课程组,复习线性代数内容:,列向量,x=(x,1,，x,2,，x,n,）,T,为n维列向量。x,R,n,行向量,x=(x,1,，x,2,，x,n,）,为n维列向量。x,R,n,矩阵(向量)运算规则,加减乘、求逆运算,结合律 分配律,交换律,乘法无交换律,线性相关,一组向量v,1,v,n,如果有一组不全为零的,系数,1,n,使得:,1,v,1,+,n,v,n,=0,则称v,1,v,n,是线性相关的.,线性无关,一组向量v,1,v,n,如果对于任何数,1,n,若要满足:,1,v,1,+,n,v,n,=0,则必有系数,1,=,n,=0,(全为零)则称v,1,v,n,线性无关.,矩阵A的秩,设A为一个mn阶矩阵(mn)若矩阵中最大线性,无关列向量个数为k,则称矩阵A的秩为k,记,为rank(A)=k.,12/19/2024,35,管理运筹学课程组,练习:,将下列线性规划问题化成标准型,1、min,Z=5x,1,+x,2,+x,3,3x,1,+x,2,-x,3,7,-3x,1,+x,2,6,s.t x,1,+2x,2,4,x,2,-3,x,1,无限制,x,3,0,2、max,Z=-x,1,+4 x,2,s.t x,1,-2x,2,+4x,3,-6,x,2,+3x,3,=3,x,1,x,2,0,x,3,无限制,36,管理运筹学课程组,Thank You!,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,