简介与线性规划(第一、二、三章)

,运筹学OperationResearchUndergraduateCourseEconomicsandManagementSchoolofWuhanUniversityDr.MingxiaLiuTele.87383479(H)E-mail:susan6662005年,CourseRequirement,ClassTime:54hoursTeachingArrangement:Teaching:51hoursCaseAnalysis:3hoursResultProportionAttendence:10%CaseandProject:20%MidtermTest:20%FinalTest:50%,Textbook,Operation(al)Research（简写OR）直译为：作战研究、运用研究日本：运用学中国：运筹学（意译）Textbook管理运筹学，韩伯棠，高等教育出版社，2000年References管理科学导论（中文版数据、模型与决策），DavidR.Anderson,et.机械工业出版社，1998年管理运筹学薛声家、左小德编，暨南大学出版社运筹学，清华大学出版社,TheNatureoftheCourse,管理学科的专业基础课定量化的管理技术（理性的分析与推理）辅助决策制定,应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。,TeachingpurposeandMethod,教学目的介绍运筹学各分支体系的基本模型、基本算法与实际应用；引导并锻练学生运用运筹学知识更优地决策或解决实际问题的能力(根据实际问题拿出一个最好的解决方案)。如优化系统的方案、成本最小的方案、收入或利润最大的方案。教学方法以各种实际问题为背景，引出各分支基本概念、基本模型和基本算法，侧重各运筹学方法的实际应用。介绍运筹学方面的软件，并让学生掌握这类软件。强调运用软件的“两头”：input和output课堂讲授与课后练习相结合分组进行案例分析与讨论,资源利用,目标实现,低浪费,高成就,效果(Effect),效率（Efficiency）,管理水平的体现：投入产出,Contents,运筹学简介（Introduction）对运筹学的一般认识，包括它的发展、性质和特点、解决程序、应用情况等。线性规划(LinearProgramming)应用相当广泛的一种解决问题的方法，根据其模型中目标函数和约束条件均为线性表达式而称之为线性规划。整数规划(IntegerProgramming)针对实际问题要求整数解的一种处理方法，它是一种特殊的线性规划。目标规划(Goalprogramming)多个目标情形下的线性规划，即，存在多目标时解决问题的一种方法。动态规划(DynamicProgramming)一种解决多阶段决策问题的方法,网络规划(NetworkModels)把实际问题转换为一个图来加以解决的方法存贮论(InventoryModels)研究存贮系统的决策问题，如什么时间订货？订多少？排队论(WaitingLineModels)研究排队系统中队列、“顾客”等待、“服务器”数量等问题，帮助决策者设计和改造系统。对策论(Gametheory)研究存在竞争对抗时的最优策略决策论(DecisionAnalysis)研究在一定环境下如何选择方案排序：零部件的加工顺序项目管理：如何制定和控制项目进度,ChapterOneIntroduction,运筹学的发展：三个来源运筹学的性质和特点运筹学的模型运筹学的工作步骤运筹学在工商管理中的应用,运筹学的发展：三个来源,军事管理经济,军事：运筹学的主要发源地,古代军事运筹学思想中国古代的“孙子兵法”在质的论断中渗透着量的分析（1981年美国军事运筹学会出版了一本书，书中第一句话就是说孙武子是世界上第一个军事运筹学的实践家），中国古代运筹学思想的例子还有：田忌赛马、围魏救赵、行军运粮，等等。国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。,运筹学的正式产生：第二次世界大战鲍德西（Bawdsey）雷达站的研究1939年，以Blackett为首的一个研究小组（代号“Blackett马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。Blackett备忘录1941年12月，Blackett应盟国政府的要求，写了一份题为“ScientistsattheOperationalLevel”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。大西洋反潜战：研究如何打破德国对英吉利海峡的海上封锁英国战斗机中队援法的决策,管理,泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图”、吉尔布雷思夫妇的动作研究等爱尔朗（Erlong）的排队论公式19091920年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是1909年的论文“概率与电话通话理论”，开创了运筹学的重要分支排队论。,经济（数理经济学）,VonNeumann与对策论1932年，VonNeumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的对策论与经济行为开创了对策论分支。康托洛维奇与“生产组织与计划中的数学方法”30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。,运筹学的性质和特点,应用科学“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。运筹学的特点定量化分析(QuantitativeAnalysis)多学科交叉，如综合利用了心理学、经济学、物理、化学等方法最优决策,定量分析(QuantitativeAnalysis),模型(Model)：现实情况的简化描述代表一种现实情况经过简化，只保留相关的部分用模型的特性代表现实情况中的特性数据(data)数据准备是进行定量分析的一个非常重要的工作统计方法是获取数据的一种方法从管理信息系统中获取一些数据,Model,模型的种类形象模型，如模型汽车（有车轮、发动机等）模拟模型，如用钟表上的指针表示时间、用水银柱的高度表示温度、用速度仪指针表示速度，等等。符号模型：如用数学方程式、图等符号表示的模型比如，总利润单位利润*售出数量，表示：P10 x模型的作用：实验推导得出关于真实情形的有用信息用模型实验，所花的时间少、费用少基于模型得出的结论和决策，其价值取决于模型代表现实情况是否精确,运筹学中的模型,环境因素（不可控）,决策变量可控）,运筹学的工作步骤(Steps),提出和形成问题实际问题决策目标问题中的变量可能的方案以及行动步骤问题的来龙去脉建立模型辩认并确定相关的变量确定变量之间的关系,3.测试模型把以前的数据代入模型，看它所预言的结果与实际结果是否接近修改模型时，分析模型中是否有不相关的变量、是否忽视了相关的变量、变量间的函数关系是否正确4.得到问题的解决方案用相应算法求解软件求解5.方案实施与控制外在因素变化时，调整模型或方案以适应变化,运筹学在工商管理中的应用,生产计划库存管理运输问题人事管理市场营销财务与会计,运筹学方法的使用情况,各个工商企业使用运筹学方法的频率不同，有的经常使用，有的只是偶尔使用。大公司大企业使用运筹学方法的百分比高。据统计，88%的美国大公司使用预测方法，超过50%的大公司用运筹学方法制定生产计划、存储控制、资金预算、运输方案等。各种运筹学方法的使用程度也是不同的，统计、线性规划、网络计划、计算机模拟、决策论、排队论使用的频率高。如制造业中最经常使用的是网络计划，其次是统计、模拟、线性规划。,中国使用运筹学方法的情况,90年以前的一些经典应用,90年代以来的一些应用举例,ChapterTwoLinearProgramming,线性规划问题线性规划模型线性规划的求解图解法单纯形法线性规划的应用,线性规划问题（生产计划）某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗，以及资源的限制，如下表所示。该工厂每生产一单位产品I可获利50元，每生产一单位产品可获利100元，工厂应分别生产多少产品I、才能使工厂获得最多？,建立模型,第一步：确定决策变量(要决定的未知量)第二步：确定追求目标、目标与决定变量之间的函数关系(目标函数)第三步：确定约束条件(决策变量受到的约束),生产计划问题的模型1.确定决策变量：x1,x2(x1=产品I的生产数量,x2=产品II的生产数量)2.确定目标函数：Z=50 x1+100 x23.寻找约束条件：设备限制：x1+x2300原料A的限制：2x1+x2400原料B的限制：x2250非负条件：x10，x20,市场调查公司（MSI）专门评定消费者对新产品、服务和广告活动的反应。一个客户要求MSI帮助确定消费者对一种近期推出的家居产品的反应。客户要求采取个人入户调查（分为日间调查和晚间调查），以从有孩家庭和无孩家庭获得回答。客户的合同要求依据以下条款进行1000个访问：1）至少访问400个有孩家庭；2）至少访问400个无孩家庭；3）晚间访问的总数量至少等于日间访问的数量；4）至少40%有孩家庭必须在晚间访问；5）至少60%无孩家庭必须在晚间访问。访谈成本见表所示。怎样安排，才能既满足合同要求，又成本最低？,决策变量：对有孩家庭日间访问的数量x1、对有孩家庭晚间访问的数量x2、对无孩家庭日间访问的数量x3、对无孩家庭晚间访问的数量x4目标函数：minz=20 x1+25x2+18x3+20 x4约束条件：x1+x2+x3+x41000 x1+x2400 x3+x4400 x2+x4x1+x3即-x1+x2-x3+x40 x20.4（x1+x2）即-0.4x1+0.6x20 x40.6（x3+x4）即-0.6x3+0.4x40 x1、x2、x3、x40,如何化标准形？,当碰到最大化问题，即maxz=CX化标准形的方法：令z=-z(z=-CX)，minz=-CX与maxz=CX最优解相同，最优值反号当约束条件是不等式不等式左边加减一个非负变量(称松驰变量)化为标准形当某个bi=0，替代xk,LP问题的解的概念,可行解：满足约束条件的解X=(x1，x2，xn)最优解：使目标函数达到最优值的可行解基：已知A是约束条件的mn系数矩阵，其秩为m。若B是A中mm阶非奇异子矩阵(即/B/0),则称B是LP问题的一个基基向量：基B中的一个列向量pi基变量：与基向量Pi对应的变量xi称为基变量(个数为m)，其它变量称为非基变量(n-m个)基解：由一个基所求出的解称为基解，基解有可行的基解(称基可行解)，也有非可行的基解(称基不可行解),LP问题的求解：图解法,例：maxz=50 x1+100 x2s.t.x1+x2300 x1+x2400 x2250 x10 x20,200,300,400,100,200,300,400,100,x1+x2300,2x1+x2400,x2250,X20,x10,B(50,250),Z=050 x1+100 x2,Z=2750050 x1+100 x2,可行域,最优解,线性规划问题的最优解一定是在可行域的顶点上,基本定理,只要存在可行解，就一定存在顶点若目标函数有最优值，则最优值必至少在某一顶点上达到顶点的个数是有限的，为(n!/m!(n-m)!)线性规划问题的基可行解对应于可行域的顶点,LP问题的求解：单纯形法,基本思路：从一个基可行解转换到另一个“更好”的基可行解上(“更好”：目标函数值得到改善)，直到找到最优解或者获得无最优解的信息,单纯形法的步骤,将所给问题化为标准形找出一个初始基可行解,建立初始单纯形表检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步)考察是否无解(若是,计算停止,否则继续下一步)确定入基变量,出基变量对初始单纯形表进行单纯形变换,最优判别定理1：若所有检验数0，则x是最优解。定理2：若存在这样一个检验数，它所对应的列向量的全部分量均0，则所给问题的目标函数值无下界，因而无最优解。入基变量的确定正检验数中，最大的检验数对应的变量先入基出基变量的确定最小比值法：bi/aij(aij0)，最小比值对应的变量,例：maxz=5x1+4x2s.t.3x1+5x2152x1+x252x1+2x211x1,x20,化标准形：minz1=-5x1-4x2s.t.3x1+5x2+x3=152x1+x2+x4=52x1+2x2+x5=11x1,x2,x3,x4,x50,变量行,检验数行,基变量,人工变量法,若约束条件全是型，化标准形时每个不等式都加上一个松驰变量，化为等式，而每个等式中的松驰变量正好构成一组基变量，于是可以直接用单纯形法,若约束条件不全是型，即：含有或=时，不能找到一组基变量(或基变量个数不够)，就必须用人工变量法,人工变量法有两种：大M法、两阶段法,大M法,构造辅助问题：Minz=cjxj+MR1+MR2+MRms.t.aijxj+Ri=bi,i=1,2,mxj0,j=1,2,n,定理：若辅助问题有最优解，则当辅助问题的最优解中人工变量取值全部为0时，原问题才有最优解(辅助问题最优解去掉人工变量值),否则原问题无可行解。若辅助问题无最优解，则原问题也无最优解。,例:minz=x1+3x2s.t.2x1+x2=43x1+4x26x1+3x23x1,x20,化标准形：minz=x1+3x2s.t.2x1+x2=43x1+4x2-s2=6x1+3x2+s3=3x1,x2,s2,s30,构造辅助问题：minz=x1+3x2+MR1+MR2s.t.2x1+x2+R1=43x1+4x2-s2+R2=6x1+3x2+s3=3x1,x2,s2,s3，R1，R20,*M,(同上),(同上),故原问题的最优解为(2，0),两阶段法,构造辅助问题：Minf=R1+R2+Rms.t.aijxj+Ri=bi,i=1,2,mxj0,j=1,2,n,定理：若辅助问题的f*0，则原问题无可行解；若f*=0，则原问题有可行解,例:minz=x1+3x2s.t.2x1+x2=43x1+4x26x1+3x23x1,x20,化标准形：minz=x1+3x2s.t.2x1+x2=43x1+4x2-s2=6x1+3x2+s3=3x1,x2,s2,s30,构造辅助问题：minf=R1+R2s.t.2x1+x2+R1=43x1+4x2-s2+R2=6x1+3x2+s3=3x1,x2,s2,s3，R1，R20,*1,(同上),故原问题的最优解为(2，0),minz=2,观察最后一行：0=0，说明这个方程是多余的，可以去掉，进行第二阶段的求解,第一阶段的求解，如果最后一个表如下：,第一阶段的求解，如果最后一个表如下：,去掉人工变量列，进行第二阶段的求解,多重最优解：在最优表中，若非基变量的检验数为0,第三章对偶问题和灵敏度分析,原问题,对偶问题,对偶性质,原问题与对偶问题互为对偶原问题与对偶问题或都有最优解(最优值相同),两最优解之间存在一定的关系,或都没有最优解可知:研究对偶问题可以简化计算(当原问题很复杂时,可先求解对偶问题,再根据一定的关系得出原问题的最优解提出了新的求解方法:对偶单纯形法,对偶单纯形法,从单纯形表来看，最优必须同时满足两个条件：1.可行性条件(右端列中的所有bi0)2.最优性条件(全部检验数j0),单纯形法的基本思想是保证可行性条件的基础上，逐步通过迭代去满足最优性条件。而对偶单纯形法则是走另外一条路径，即始终保持最优性条件，而通过迭代逐步去满足可行性条件。,对偶单纯形法的步骤,把所给LP问题化为标准形找出一个满足所有检验数0的一组基变量，作单纯形表。若表中所有右端常数0，则已是最优表，计算终止。否则，进行下一步。换基：任何一个取负值的基变量(通常取负得最多的一个)都可为出基变量。用最小比值确定入基变量(比值：检验数/出基变量行的负系数)对上述单纯形表进行单纯形变换，再转第三步。,比较,灵敏度分析,确定参数Ci、bj的变化范围,即保持某LP问题的最优解或最优基变量不变的条件下该参数单独变化的最大范围一个参数的变化范围越小,最优解对这一参数的变化就越敏感,最优解对该参数而言就越不稳定当两个或更多的参数同时发生变化时，不能直接从输出部分找到灵敏度分析，可用100%法则进行灵敏度分析。对于所有变化的目标函数系数，当其所有允许增加百分比与允许减少百分比之和不超过100%时，最优解不变。对于所有变化的约束右端常数，当其所有允许增加百分比与允许减少百分比之和不超过100%时，对偶价格不变。,参数单独变化的灵敏度分析,目标函数系数发生变化(cj变)基变量系数发生变化非基变量系数发生变化右端常数发生变化(bi变)系数矩阵中的系数发生变化(aij变)基变量系数发生变化非基变量系数发生变化,举例,maxz=5x1+4x2s.t.3x1+5x2152x1+x252x1+2x211x1,x20,maxz=5x1+(4+q)x2s.t.3x1+5x2152x1+x252x1+2x211x1,x20,对偶变量的经济解释,对偶变量yi在经济上表示原问题第i种资源的边际贡献,即当第i种资源增加一个单位时,相应的目标值z的增量对偶问题的最优解yi*是原问题第i种资源的影子价格应用:1.出租资源或设备时,租金价格的设定(至少高于该资源在企业内的影子价格)2.企业内资源I的存量设定(当资源I的影子价格=市场价格时,可买进该资源;否则卖出)3.调整资源