林齐宁-数据、模型与决策一运筹学

运筹学OperationalResearch林齐宁博士，教授北京邮电大学经济管理学院Tel:13621281705E_mail:[e-mail]绪论•一、运筹学的起源与发展•二、运筹学的定义和主要研究分支•三、运筹学的特点及研究对象•四、运筹学解决问题的方法步骤•五、运筹学与其他学科的关系一、运筹学的起源与发展•起源于二次大战的一门新兴交叉学科•与作战问题相关–如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等–英国称为OperationalResearch–美国称为OperationsResearch•战后在经济、管理和机关学校及科研单位继续研究–1952年，Morse和Kimball出版《运筹学方法》–1948年英国首先成立运筹学会–1952年美国成立运筹学会–1959年成立国际运筹学联合会(IFORS)–我国于1982年加入IFORS，并于1999年8月组织了第15届大会一、运筹学的起源与发展1、中国运筹学会简介50年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。1980年4月，中国数学会运筹学分会成立。1991年，中国运筹学会成立。历届学会理事长有，华罗庚、越民义，徐光辉，章祥荪，袁亚湘，2、中国系统工程学会简介1、1979年由钱学森、宋健、关肇直、许国志等21名专家、学者共同倡议并筹备。1980年11月18日在北京正式成立。第一届理事会理事长关肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六届理事长陈光亚。3、运筹学、系统工程主要研究人员构成1）数学：如华罗庚、越民义，徐光辉，章祥荪，袁亚湘，许国志，顾基发等；2）控制论：张仲俊，刘豹，陈珽，郑维敏，赵纯均，陈剑等3）管理等专业相关教学、科研技术人员567一、运筹学的起源与发展4、相关研究机构和高校1）中国科学院数学与系统科学研究院系统科学研究所2）中国科学院数学与系统科学研究院应用数学研究所3）哈工大：胡运权，黄梯云，钱国明等4）天津大学：刘豹，顾培亮，张维，杜纲等5）西安交大：汪应洛，席酉民等6）上海交大：张仲俊，王浣尘等7）清华大学：郑维敏，赵纯均，陈剑等；8）大连理工：王众托，胡祥培等9）北航：顾昌耀，黄海军等10）北理工：吴沧浦，吴祈宗，张强等9二、运筹学的定义和主要研究分支•运筹学的定义–为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse和Kimball–运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会–运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书–现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience10二、运筹学的定义和主要研究分支•运筹学的分支–数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等–图论与网路理论–随机服务理论：排队论–存储理论–网络计划方法–决策理论–对策论–系统仿真：随机模拟技术、系统动力学–可靠性理论–金融工程11三、运筹学的特点及研究对象运筹学的特点：1)优化以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法2定量为所研究的问题提供定量的解决方案。如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源分配方案。运筹学的研究对象：来自生产管理过程中的具体问题，如资源分配、物资调度，生产计划与控制等。12四、运筹学解决问题的方法步骤•1、理清问题、明确目标•2、建立模型•讨论：什么叫模型•3、求解模型。建立模型之后，需要设计相应算法进行求解，实际问题运算量一般都很大，通常需要用计算机求解。•4、结果分析•讨论：模型计算结果与已有的经验或知识进行比较•1）模型计算结果和已有的经验或知识比较一致•2）模型计算结果和已有的经验或知识差异较大•你喜欢那一种情况？13五、运筹学与其他学科的关系•运筹学目标分析、建模、求解和结果分析需要用到很多相关学科的知识，它与如下学科的知识关系比较密切。•1、数学：学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因，有人甚至认为运筹学是一门应用数学；•2、管理学：运筹学研究对象是生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要的涉及管理科学的有关理论；•3、计算机：运筹学所研究的实际问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必须借助计算机来完成。14第一章线性规划•1.1线性规划模型1.1.1问题的提出一、例1、多产品生产问题（Max,）甲电缆乙电缆资源量铜（吨）2110铅（吨）118价格（万元）64需求无限制7另问该工厂应如何安排生产才能使工厂的总收入最大？一、例1、多产品生产问题（Max,）•设x1,x2分别代表甲、乙两种电缆的生产量，f(x)为工厂的总收入，则上述问题可用如下数学模型来表示其中，OBJ（Objective）表示目标，S.t.（Subjectto）表示满足于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目标达到最大。最优解为产量不允许为负值产量约束铅资源约束铜资源约束0,78102..46)(max:212212121xxxxxxxtsxxxfOBJ.36)(max,6,221xfxx二、例2、配料问题（min,)某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料。混合饲料对VA、VB1、VB2和VD的最低含量有一定的要求。已知单位甲、乙两种原料VA、VB1、VB2和VD的含量，单位混合饲料对VA、VB1、VB2和VD的最低含量以及甲、乙两种原料的单位价格如下表所示。问该该加工厂应如何搭配使用甲乙两种原料，才能使混合饲料在满足VA、VB1、VB2和VD的最低含量要求条件下，总成本最小？原料甲原料乙最低含量VA0.50.52VB11.00.33VB20.20.61.2VD0.50.22单价0.30.5二、例2、配料问题（MIN,)设x1,x2分别代表混合单位饲料对甲、乙两种原料的用量，f(x)表示单位混合饲料所需要的成本，则上述问题的线性规划数学模型如下：该数学模型的最优解为该问题的最优解为x1=3.69，x2=0.77，minf(x)=1.49三、线性规划数学模型的特征和定义1、线性规划数学模型的特征：1）有一组决策变量（x1，x2，…，xn）表示某一方案。这一组决策变量的具体值就代表一个具体方案；2）有一个目标函数，该目标函数根据其的具体性质取最大值或最小值。当目标为成本型时取最小，而当目标为效益型时取最大。3）有一组约束方程，包括决策变量的非负约束；4）目标函数和约束方程都是线性的。2、线性规划数学模型的定义定义1.1有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型。四、线性规划数学模型的背景模型和思考1、线性规划数学模型的背景模型：例1.1的多产品生产计划问题的数学模型称为线性规划的背景模型。把该背景模型的条件一般化后可叙述如下：用有限量的几种资源生产若干种产品，如何安排生产，才能使工厂的总收入或利润达到最大。2、背景模型的思考1）讨论：什么叫背景模型能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型。2）背景模型的思考利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运筹学中的一些基础概念和原理是本课程力求在教学中体现的第一个特点，希望大家用心体会。1.1.2线性规划数学模型的一般表示方式技术系数右端项价值系数线性规划问题的规模约束行数变量个数:;:;::;:;:0,,,),(),(),(..)(max(min)21221122222121112121112211ijijnmnmnmmnnnnnnabcmnmnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcxf211、和式njxmibxatsxcxfjinjjijnjjj,,2,1,0,,2,1,..)(max11222、向量式233、矩阵式241.1.3线性规划的图解法1187654322x1876543O109x2ABCEDFGH123f(x)=0f(x)=12.36)(max,6,2:0,78102..46)(max21212212121xfxxxxxxxxxtsxxxf最优解1187654322x1876543O109x2ABCEDFGH123线性规划问题的几个特点：•1、线性规划的可行域为凸集；•讨论：什么叫凸集？•集合中任意两点连线上的一切点仍然在该集合中，在平面上为凸多边形，在空间上为凸几何体；•讨论：最优解在那里取得？•2、线性规划的最优解一定可在其凸集的某一顶点上达到；•讨论：什么情况有最优解？最优解的存在性条件？•3、线性规划若有可行域且其可行域有界，则一定有最优解。•上述3个结论是线性规划的3个基础定理，可以用严格的数学方法进行证明。我们以简单、直观的图解法方式给出，相信大家是可以接受的。•1.3线性规划求解的基础原理和单纯形法1.3.1线性规划问题的标准形一、线性规划模型一般形式二、求解思路1、规定一标准型线性的规划问题数学模型；2、如何把非标准形的线性规划问题数学模型转化为标准形线性规划问题数学模型？3、如何求解标准形线性规划问题数学模型。njxmibxatsxcxfjinjjijnjjj,,2,1),,0(0,,2,1,),(..)(max(min)11不限三、线性规划问题的标准形在上述线性规划标准形中，决策变量的个数取n+m个是习惯表示法。我们知道，对于线性规划背景模型，有m个约束方程，且每个约束方程的不等式均为“”号。如果我们在每个约束方程的左边加上一个大于等于0的变量，则可将各个约束方程的“”号转变为“=”。此时，决策变量就有n+m个。njmixbmibxatsxcxfjiimnjjijmnjjj,,2,1,,2,1,0,,,2,1,..)(max1128四、变换的方法•1、目标函数为min型，价值系数一律反号。令g(x)=-f(x)=-CX,有minf(x)=-max[-f(x)]=-maxg(x)•2、第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向•3、第i个约束为型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0•4、第i个约束为型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0•5、若xj0，令xj=-xj，代入非标准型，则有xj0•6、若xj不限，令xj=xj-xj，xj0，xj0，代入非标准型29五、变换举例：0,,,,,,2004006653004432..0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型1.3.2线性规划问题的解和基础定理本章开始到现在已讨论的内容，相信大部分读者都会感到比较容易理解和掌握。这一节我们将要讨论关于线性规划问题解的一些基础概念和定理，与前面讨论的内容相比，线性规划问题解的一些基础概念略显难一些，其中比较难的概念有线性规划问题的基和基础解等相关概念。为了帮助大家比较容易理解