资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管理与人文学院 忻展红,1999,，,4,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,Operational Research,Tel:,E_mail:,1,绪 论,一、运筹学的起源与发展,二、运筹学的定义和主要研究分支,三、运筹学的特点及研究对象,四、运筹学解决问题的方法步骤,五、,运筹学与其他学科的关系,2,一、运筹学的起源与发展,起源于二次大战的一门新兴交叉学科,与作战问题相关,如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等,英国称为,Operational Research,美国称为,Operations Research,战后在经济、管理和机关学校及科研单位继续研究,1952,年，,Morse,和,Kimball,出版,运筹学方法,1948,年英国首先成立运筹学会,1952,年美国成立运筹学会,1959,年成立国际运筹学联合会,(IFORS),我国于,1982,年加入,IFORS,，并于,1999,年,8,月组织了第,15,届大会,3,一、运筹学的起源与发展,1,、中国运筹学会简介,50,年代中期，我国著名科学家钱学森、许国志等教授将运筹学从西方引入国内。,1980,年,4,月，中国数学会运筹学分会成立。,1991,年，中国运筹学会成立,。历届学会理事长有，华罗庚、越民义，徐光辉，,章祥荪,，,袁亚湘,，,2,、中国系统工程学会简介,1,、,1979,年由钱学森、宋健、关肇直、许国志等,21,名专家、学者共同倡议并筹备。,1980,年,11,月,18,日在北京正式成立。 第一届理事会理事长关肇直，第二、三届理事长许国志。第四、五届理事长顾基发、第六届理事长陈光亚。,3,、运筹学、系 统工程 主要研究人员构成,1,）数学：如华罗庚、越民义，徐光辉，,章祥荪,，,袁亚湘,，许国志，顾基发等；,2,）控制论：张仲俊，刘豹，陈珽，郑维敏，赵纯均，陈剑等,3,）管理等专业相关教学、科研技术人员,4,5,6,7,一、运筹学的起源与发展,4,、相关研究机构和高校,1,）中国科学院数学与系统科学研究院系统科学研究所,2,）中国科学院数学与系统科学研究院应用数学研究所,3,）哈工大：胡运权，黄梯云，钱国明等,4,）天津大学：刘豹，顾培亮，张维，,杜,纲,等,5,）西安交大：汪应洛，席酉民等,6,）上海交大：张仲俊，王浣尘等,7,）清华大学：郑维敏，赵纯均，陈剑等；,8,）大连理工：王众托，胡祥培等,9,）北航：顾昌耀，黄海军等,10,）北理工 ：,吴沧浦,，吴祈宗，张强等,8,二、运筹学的定义和主要研究分支,运筹学的定义,为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法,Morse,和,Kimball,运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策,英国运筹学会,运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理,中国百科全书,现代运筹学涵盖了一切领域的管理与优化问题，称为,Management Science,9,二、运筹学的定义和主要研究分支,运筹学的分支,数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等,图论与网路理论,随机服务理论：排队论,存储理论,网络计划方法,决策理论,对策论,系统仿真：随机模拟技术、系统动力学,可靠性理论,金融工程,10,11,三、运筹学的特点及研究对象,运筹学的特点：,1),优化,以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法,2,定量,为所研究的问题提供定量的解决方案。如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源分配方案。,运筹学的研究对象：,来自生产管理过程中的具体问题，如资源分配、物资调度，生产计划与控制等。,11,四、运筹学解决问题的方法步骤,1,、理清问题、明确目标,2,、建立模型,讨论：什么叫模型,3,、求解模型。建立模型之后，,需要设计相应算法进行求解，实际问题,运算量一般都很大，通常需要用计算机,求解,。,4,、结果分析,讨论：模型计算结果与已有的经验或知识进行比较,1,）模型计算结果和已有的经验或知识比较一致,2,）模型计算结果和已有的经验或知识差异较大,你喜欢那一种情况？,12,五、,运筹学与其他学科的关系,运筹学,目标分析、,建模,、,求解,和结果分析需要用到很多相关学科的知识，它与如下学科的知识关系比较密切。,1,、数学：,学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因，有人甚至认为运筹学是一门应用数学,；,2,、管理学：运筹学研究对象是,生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要的涉及管理科学的有关理论,；,3,、计算机：,运筹学所研究的实际问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必须借助计算机来完成,。,13,第一章 线性规划,1.1,线性规划模型,1.1.1,问题的提出,一、,例1、多产品生产问题,（,Max,）,甲电缆,乙电缆,资源量,铜（吨）,2,1,10,铅（吨）,1,1,8,价格（万元）,6,4,需求,无限制,7,另,问该工厂应如何安排生产才能使工厂的总收入最大？,14,一、,例1、多产品生产问题,（,Max,）,设,x,1, x,2,分别代表甲、乙两种电缆的生产量，,f(x),为工厂的总收入，则上述问题可用如下数学模型来表示,其中，,OBJ,（,Objective,）表示目标，,S.t.,（,Subject to,）表示满足于。表示在满足铜、铅资源和需求等约束条件下，使工厂的总收入这一目标达到最大,。最优解为,15,二、例,2,、配料问题（,min,),某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料。混合饲料对,VA,、,VB,1,、,VB,2,和,VD,的最低含量有一定的要求。已知单位甲、乙两种原料,VA,、,VB,1,、,VB,2,和,VD,的含量，单位混合饲料对,VA,、,VB,1,、,VB,2,和,VD,的最低含量以及甲、乙两种原料的单位价格如,下,表所示。,问该该加工厂应如何搭配使用甲乙两种原料，才能使混合饲料在满足,VA,、,VB,1,、,VB,2,和,VD,的最低含量要求条件下，总成本最小？,16,二、例,2,、配料问题（,MIN,),设,x,1, x,2,分别代表混合单位饲料对甲、乙两种原料的用量，,f(x),表示单位混合饲料所需要的成本，则上述问题的线性规划数学模型如下：,该数学模型的最优解为该问题的最优解为,x,1,=3.69,，,x,2,=0.77,，,minf(x)=1.49,17,三、线性规划数学模型的特征和定义,1,、,线性规划数学模型,的特征,：,1,）,有一组决策变量（,x,1,，,x,2,，,，,x,n,）表示某一方案。这一组决策变量的具体值就代表一个具体方案；,2,）,有一个目标函数，该目标函数根据其的具体性质取最大值或最小值。当目标为成本型时取最小，而当目标为效益型时取最大。,3,）,有一组约束方程，包括决策变量的非负约束；,4,）,目标函数和约束方程都是线性的。,2,、,线性规划数学模型的定义,定义,1.1,有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型。,18,四、线性规划数学模型的背景模型和思考,1,、,线性规划数学模型,的背景模型,：,例,1.1,的多产品生产计划问题的数学模型称为线性规划的背景模型。把该背景模型的条件一般化后可叙述如下：用有限量的几种资源生产若干种产品，如何安排生产，才能使工厂的总收入或利润达到最大。,2,、背景模型的思考,1,）讨论：什么叫背景模型,能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型。,2,）背景模型的思考,利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运筹学中的一些,基础,概念和原理是,本课程,力求在,教学,中体现的第一个特点，,希望大家,用心体会,。,19,1.1.2,线性规划数学模型的一般表示方式,20,1,、,和式,21,2,、,向量式,22,3,、,矩阵式,23,1.1.3,线性规划的图解法,f,(,x,)=36,24,线性规划问题的几个特点：,1,、线性规划的可行域为凸集,；,讨论：什么叫凸集？,集合中任意两点连线上的一切点仍然在该集合中，在平面上为凸多边形，在空间上为凸几何体；,讨论：最优解在那里取得？,2,、线性规划的最优解一定可在其凸集的某一顶点上达到；,讨论：什么情况有最优解？最优解的存在性条件？,3,、线性规划若有可行域且其可行域有界，则一定有最优解。,上述,3,个结论是线性规划的,3,个,基础,定理，可以用严格的数学方法进行证明,。,我们以简单、直观的图解法方式给出，相信大家是可以接受的。,25,1.3,线性规划求解的,基础,原理和单纯形法,1.3.1,线性规划问题的标准形,一、线性规划模型一般形式,二、求解思路,1,、,规定一标准型线性的规划问题数学模型；,2,、,如何把非标准形的线性规划问题数学模型转化为标准形线性规划问题数学模型？,3,、,如何求解标准形线性规划问题数学模型。,26,三、,线性规划问题的标准形,在上述线性规划标准形中，决策变量的个数取,n+m,个是习惯表示法。我们知道，对于线性规划背景模型，有,m,个约束方程，且每个约束方程的不等式均为“,”号。如果我们在每个约束方程的左边加上一个大于等于,0,的变量，则可将各个约束方程的“,”号转变为“,=,”。此时，决策变量就有,n+m,个。,27,四、,变换的方法,1,、目标函数为,min,型，价值系数一律反号。令,g(,x,) = -,f,(,x,) = -,CX,有,min,f,(,x,) = - max -,f,(,x) = - max g,(,x),2,、第,i,个约束的,b,i,为负值，则该行左右两端系数同时反号，同时不等号也要反向,3,、第,i,个约束为, 型，在不等式左边增加一个非负的变量,x,n+i,，,称为松弛变量；同时令,c,n+i,= 0,4,、第,i,个约束为, 型，在不等式左边减去一个非负的变量,x,n+i,，,称为剩余变量；同时令,c,n+i,= 0,5,、若,x,j,0,，令,x,j,= -,x,j,，代入非标准型，则有,x,j, 0,6,、若,x,j,不限，令,x,j,=,x,j,-,x,j,，,x,j, 0,，,x,j, 0,，,代入非标准型,28,五、,变换举例：,29,1.3.2,线性规划问题的解和,基础,定理,本章开始到现在已讨论的内容，相信大部分读者都会感到比较容易理解和掌握。这一节我们将要讨论关于线性规划问题解的一些,基础,概念和定理，与前面讨论的内容相比，线性规划问题解的一些,基础,概念略显难一些，其中比较难的概念有线性规划问题的基和基础解等相关概念。为了帮助大家比较容易理解这些概念，我们先从大家熟悉的两个变量两个线性方程组这一简单问题入手，然后逐步过渡到我们所要讨论的线性规划问题的基和基础解等相关概念。,著名数学家笛卡尔曾说过，他最擅长做的两件事是：,1),第一做简单事；,2),第二是将复杂事变为简单事。,本,课程,将从大家熟悉的一些简单问题入手，然后逐步过渡到运筹学一些相对比较抽象和难的概念和原理。这是本,课程教学,力求的另一特点。,30,一、线性方程组的解,考虑如下线性方程组的解：,再考虑如下线性方程组的解：,31,一、线性方程组的解,类似地，如果将方程组（,3,）中的变量,x,2,或,x,1,当成常数，分别移到其方程的右边后采用消元法进行求解，则也可得到如下两组,通,解,及其特解,：,32,一、线性方程组的解,仔细观察和思考方程组（,3,）的三组通解（,4,）、（,6,）和（,8,）或三组特解（,5,）、（,7,）和（,9,）是如何得到的，以及能够得到这些通解或特解的条件是什么？根据求解线性方程组克莱姆条件可知，能够得到方程组（,3,）的通解（,4,）或特解（,5,）的条件是方程组（,3,）中的变量,x,1,和,x,2,的系数矩阵行列式不等于,0,，即,或变量,x,1,和,x,2,的系数矩阵,B,1,是非奇异矩阵或变量,x,1,和,x,2,的系数列向量是线性无关。显然，这三个条件是等价的。,33,一、线性方程组的解,同样，由于方程组组（,3,）中的变量,x,1,和,x,3,的系数矩阵行列式,|B,2,|,不等于,0,与,变量,x,2,和,x,3,的系数矩阵行列式,|B,3,|,不等于,0,，,即,才能得到方程组（,3,）的通解或特解（,6,）或（,7,）,与,通解或特解（,8,）或（,9,）,。,将上面讨论的方程组（,3,）加上一目标函数和变量非负约束条件后就变成一标准型线性规划。如：,34,一、线性方程组的解,对于,上述标准型线性规划（,10,）,称,B,1,、,B,2,和,B,3,为线性规划（,10,）的基。因利用其中任何一个基,B,1,或,B,2,或,B,3,，都能得到线性规划（,10,）的一组通解和特解（见式（,4,）,-,（,9,）。,变量,x,1,和,x,2,为基变量，变量,x,3,为非基变量，令,x,3,=0,，,得,解（,5,）为线性规划（,10,）的基础解，但,因,该基础解中,x,1,= -10,，不满足线性规划（,10,）的变量非负约束条件，因此，该基础解（,5,）,是线性规划（,10,）的基础非可行解。,变量,x,1,和,x,3,为基变量，变量,x,2,为非基变量，令,x,2,=0,，,得,解（,7,）为线性规划（,10,）的基础解,。,该基础解中,x,1,和,x,3,均大于,0,，满足线性规划（,10,）的变量非负约束条件，因此，该基础解（,7,）,是线性规划（,10,）的基础可行解。,变量,x,2,和,x,3,为基变量，变量,x,1,为非基变量，令,x,1,=0,，,得,解（,9,）为线性规划（,10,）的基础解,.,该基础解中,x,2,和,x,3,均大于,0,，满足线性规划（,10,）的变量非负约束条件，因此，该基础解（,9,）,是线性规划（,10,）的基础可行解。,35,二、,标准型线性规划解的若干基础概念,标准型有,n+m,个变量，,m,个约束行,“,基,”的概念,在标准型中，技术系数矩阵有,n+m,列，即,A,= (,P,1,P,2, ,P,n+m,),A,中线性独立的,m,列，构成该标准型的一个,基,，即,B,= (,P,1,P,2, ,P,m,),，,|,B |, 0,P,1,P,2, ,P,m,称为,基向量,与,基向量,对应的变量称为,基变量,，记为,X,B,= (,x,1,x,2, ,x,m,),T,，其余的变量称为,非基变量,，记为,X,N,= (,x,m,+1,x,m,+2, ,x,m+n,),T,，,故有,X,=,（,X,B,，,X,N,),最多有 个基,36,二、标准型线性规划解的若干基础概念,可行解,与,非可行解,满足约束条件和非负条件的解,X,称为,可行解,，不满足约束条件或非负条件的解,X,称为,非可行解,基础解,对应某一基,B,且令其,非基变量,X,N,=,0,，求得,基变量,X,B,的值。称,X = (X,B, X,N,),T,为,基础解。,其中,，,X,B,=,B,1,b,，,X,N,=,0,X,B,是,基础解,必须满足如下条件：,1,）,非,0,分量的个数,m,；,2,、,m,个基变量所对应的系数矩阵为非奇异的；,3,、满足,m,个约束条件。,37,二、标准型线性规划解的若干基础概念,基础可行解,与,基础非可行解,基础解,X,B,的非零分量都,0,时，称为,基础可行解,，否则为,基础非可行解。,退化,解,基础可行解,的非零分量个数,f,(X,(0),)=0,（,五,）最优检验,将（,5,）式代入,(1),的目标函数后可得,f,(X)=30+x,2,-3x,3,（,6,）,从目标函数（,6,）可知，非基变量,x,2,的系数是正数，,所以,X,(1),不是最优解。,49,（,六,）求另一个更好的,基础,可行解,1,、确定换入变量及其值,从从目标函数（,6,）可知，,只有,非基变量,x,2,的系数,为正,，所以，可确定,x,2,为换入变量,。,由于,所以，,当另一个非基变量,x,3,仍然为,0,时，由,（,7,）,式可得到换入变量,x,1,的值为,x,2,=Min10/0.5,，,3/0.5,，,7/1=6,2,、确定换出变量,从（,7,）式可知，当,x,2,=6,时，,x,4,=0,，所以,x,4,为换出变量。由此得到线性规划（,1,）的一个新的基,B,2,和,一组新的基变量与非基变量。,B,2,=(P,1,P,2,P,5,), X,B2,=,（,x,1,，,x,2,，,x,5,),T,，,X,N2,=,（,x,3,，,x,4,),T,50,3,、求另一个更好的,基础,可行解,将,（,1),约束方程中对应于基,B,2,的非基变量,x,3,和,x,4,移到方程的右边后可得,令非基变量,x,3,=x,4,=0,，可得,另,一,基础,可行解,X,(2),= (2,，,6,，,0,，,0,，,1),T,此时，对应于,X,(2),的目标函数,f,(X,(2),)=6x,1,+4x,2,=36,f,(X,(1),)=30,（,七,）最优检验,将（,8,）式代入,(1),的目标函数后可得,f,(X)=36-2x,3,-2x,4,（,9,）,从目标函数（,9,）可,知,，非基变量,x,3,和,x,4,的系数都是,负,数，,所以,X,(2),是最优解。即,X,*,= X,(2),= (2,，,6,，,0,，,0,，,1),T,f,(X,*,)=36,51,三、求初始基础可行解（背景模型，,MAX, ),设线性规划问题为,另设,b,i,0 (i=1,2,m),。标准化后，若对,x,j,和,a,ij,重新编号，则约束方程可化为,变量,x,1,，,x,2,，,，,x,m,作为初始基变量，其余变量作为初始非基变量,，并,令,x,m+1,=x,m+1,=x,n+m,=0,，,则得,初始本可行解,52,四、最优检验,对于标准化线性规划问题,(2),，经过若干次迭代后，如果对,x,j,及,a,ij,重新编号，则约束方程可化为,其中，,b,i,和,a,ij,表示经过若干次迭代后，当前的右端系数和技术系数，以便区别于原始的右端系数,b,i,和技术系数,a,ij,。将,上,式代入,（,2,）的,目标函数后可得,机会成本,53,在一般情况下，目标函数值,OBJ,计算公式和机会成本计算公式可写成,四、最优检验,其中，,I,为基变量的下标集。,最优检验条件为,其中，,J,表示非基变量的下标集。,对于,基变量,的,检验数为,因为,基变量的技术系数满足：,a,ij,=1,当,i=j,a,ij,=0,当,i,j,54,五、 求另一个更好的,基础,可行解,若某一,基础,可行解经过最优检验表明不是最优解，则需要设法求得另一个更好的,基础,可行解。求另一个更好的,基础,可行解的主要步骤如下：,1,、确定换入变量；,2,、确定换出变量；,3,、通过基变换或初等变换求得另一个更好的,基础,可行解。,我们已在前面例子中说明了这种初等变换方法的,基础,思路。下一小节我们将用单纯形表进一步说明这种初等变换方法。,55,1.3.4,单纯形法表及单纯形法,56,例,试列出下面线性规划问题的初始单纯型表,57,单纯形法,步骤,1,、求初始,基础,可行解,将线性规划模型标准化，建立初始单纯形表，求初始,基础,可行解。,2,、最优检验：对任一基础可行解,X,，若其所有检验数,j,=c,j,z,j,0,，,j,J,则,X,为最优解，即,X,*,=X,，计算最优解所对应的最优目标函数值,f(X,*,),，算法停止。否则转,3,。,3,、求另一个更好的,基础,可行解,1,）,确定入变量,x,k,若,则,x,k,为换入变量；,2,）,确定换出变量,x,l*,计算,若,l,为空集，则为无界解，算法停止。否则与右端系数,b,l,同一行的基变量,x,l*,为换出变量。转,3,）,3,）初等变换，得到另一个更好的,基础,可行解,将入变量,x,k,所在列,k,，出变量,x,l*,所在行,l,的主元技术系数,a,l,k,变换为,1,，主元,a,l,k,所在列的其余元变换为,0,。更换基变量（用入变量,x,k,替换出变量,x,l*,）及其价值系数，得到另一个更好的,基础,可行解。转,2,。,58,
展开阅读全文