运筹学全套课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,Operational Research,目 录,绪 论,第一章 线性规划,第二章,对偶理论与灵敏度分析,第三章 运输问题,第四章 整数规划,第五章 动态规划,第六章 图与网路分析,第七章 随机服务理论概述,第八章 生灭服务系统,第九,章 存储,理论,第十章,网络计划方法,绪 论,一、运筹学的起源与发展,二、运筹学的定义和主要研究分支,三、运筹学的特点及研究对象,四、运筹学解决问题的方法步骤,五、,运筹学与其他学科的关系,一、运筹学的起源与发展,起源于二次大战的一门新兴交叉学科,与作战问题相关,如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等,英国称为,Operational Research,美国称为,Operations Research,战后在经济、管理和机关学校及科研单位继续研究,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,）管理等专业相关教学、科研技术人员,一、运筹学的起源与发展,4,、相关研究机构和高校,1,）中国科学院数学与系统科学研究院系统科学研究所,2,）中国科学院数学与系统科学研究院应用数学研究所,3,）哈工大：胡运权，黄梯云，钱国明等,4,）天津大学：刘豹，顾培亮，张维，杜,纲,等,5,）西安交大：汪应洛，席酉民等,6,）上海交大：张仲俊，王浣尘等,7,）清华大学：郑维敏，赵纯均，陈剑等；,8,）大连理工：王众托，胡祥培等,9,）北航：顾昌耀，黄海军等,10,）北理工：,吴沧浦,，吴祈宗，张强等,7,二、运筹学的定义和主要研究分支,运筹学的定义,为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法,Morse,和,Kimball,运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策,英国运筹学会,运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理,中国百科全书,现代运筹学涵盖了一切领域的管理与优化问题，称为,Management Science,8,二、运筹学的定义和主要研究分支,运筹学的分支,数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等,图论与网路理论,随机服务理论：排队论,存储理论,网络计划方法,决策理论,对策论,系统仿真：随机模拟技术、系统动力学,可靠性理论,金融工程,9,三、运筹学的特点及研究对象,运筹学的特点：,1),优化,以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来协调各部门之间的利害冲突，从而求出问题的最优解。所以运筹学可看成是一门优化技术，为解决各类问题提供优化方法,2,定量,为所研究的问题提供定量的解决方案。如采用运筹学研究资源分配问题时，其求解结果是一个定量的最优资源分配方案。,运筹学的研究对象：,来自生产管理过程中的具体问题，如资源分配、物资调度，生产计划与控制等。,10,四、运筹学解决问题的方法步骤,1,、理清问题、明确目标,2,、建立模型,讨论：什么叫模型,3,、求解模型。建立模型之后，,需要设计相应算法进行求解，实际问题,运算量一般都很大，通常需要用计算机,求解,。,4,、结果分析,讨论：模型计算结果与已有的经验或知识进行比较,1,）模型计算结果和已有的经验或知识比较一致,2,）模型计算结果和已有的经验或知识差异较大,你喜欢那一种情况？,11,五、,运筹学与其他学科的关系,运筹学,目标分析、,建模,、,求解,和结果分析需要用到很多相关学科的知识，它与如下学科的知识关系比较密切。,1,、数学：,学习、应用运筹学应该具备较广的数学知识，许多运筹学者来自数学专业就是这个原因，有人甚至认为运筹学是一门应用数学,；,2,、管理学：运筹学研究对象是,生产管理过程的具体问题，在利用运筹学理论和方法解决具体问题时，需要的涉及管理科学的有关理论,；,3,、计算机：,运筹学所研究的实际问题通常都是比较复杂，而且规模比较大，在求解这些问题时，必须借助计算机来完成,。,12,第一章 线性规划,1.1,线性规划模型,1.1.1,问题的提出,一、,例1、多产品生产问题,（,Max,）,甲电缆,乙电缆,资源量,铜（吨）,2,1,10,铅（吨）,1,1,8,价格（万元）,6,4,需求,无限制,7,另,问该工厂应如何安排生产才能使工厂的总收入最大？,一、,例1、多产品生产问题,（,Max,）,设,x,1,x,2,分别代表甲、乙两种电缆的生产量，,f(x),为工厂的总收入，则上述问题可用如下数学模型来表示,其中，,OBJ,（,Objective,）表示目标，,S.t.,（,Subject to,）表示满足于。表示在满足铜、铅资源和需求等约束条件下使工厂的总收入这一目标达到最大,。最优解为,二、例,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,的最低含量要求条件下，总成本最小？,二、例,2,、配料问题（,MIN,),设,x,1,x,2,分别代表混合单位饲料对甲、乙两种原料的用量，,f(x),表示单位混合饲料所需要的成本，则上述问题的线性规划数学模型如下：,该数学模型的最优解为该问题的最优解为,x,1,=3.69,，,x,2,=0.77,，,minf(x)=1.49,三、线性规划数学模型的特征和定义,1,、,线性规划数学模型,的特征,：,1,）,有一组决策变量（,x,1,，,x,2,，,，,x,n,）表示某一方案。这一组决策变量的具体值就代表一个具体方案；,2,）,有一个目标函数，该目标函数根据其的具体性质取最大值或最小值。当目标为成本型时取最小，而当目标为效益型时取最大。,3,）,有一组约束方程，包括决策变量的非负约束；,4,）,目标函数和约束方程都是线性的。,2,、,线性规划数学模型的定义,定义,1.1,有一个目标函数和一组约束方程，且目标函数和约束方程都是线性的数学模型称为线性规划数学模型。,四、线性规划数学模型的背景模型和思考,1,、,线性规划数学模型,的背景模型,：,例,1.1,的多产品生产计划问题的数学模型称为线性规划的背景模型。把该背景模型的条件一般化后可叙述如下：用有限量的几种资源生产若干种产品，如何安排生产，才能使工厂的总收入或利润达到最大。,2,、背景模型的思考,1,）讨论：什么叫背景模型,能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型。,2,）背景模型的思考,利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运筹学中的一些,基础,概念和原理是,本课程,力求在,教学,中体现的第一个特点，,希望大家,用心体会,。,1.1.2,线性规划数学模型的一般表示方式,19,1,、,和式,20,2,、,向量式,21,3,、,矩阵式,22,1.1.3,线性规划的图解法,f,(,x,)=36,线性规划问题的几个特点：,1,、线性规划的可行域为凸集,；,讨论：什么叫凸集？,集合中任意两点连线上的一切点仍然在该集合中，在平面上为凸多边形，在空间上为凸几何体；,讨论：最优解在那里取得？,2,、线性规划的最优解一定可在其凸集的某一顶点上达到；,讨论：什么情况有最优解？最优解的存在性条件？,3,、线性规划若有可行域且其可行域有界，则一定有最优解。,上述,3,个结论是线性规划的,3,个,基础,定理，可以用严格的数学方法进行证明,。,我们以简单、直观的图解法方式给出，相信大家是可以接受的。,1.3,线性规划求解的,基础,原理和单纯形法,1.3.1,线性规划问题的标准形,一、线性规划模型一般形式,二、求解思路,1,、,规定一标准型线性的规划问题数学模型；,2,、,如何把非标准形的线性规划问题数学模型转化为标准形线性规划问题数学模型？,3,、,如何求解标准形线性规划问题数学模型。,三、,线性规划问题的标准形,在上述线性规划标准形中，决策变量的个数取,n+m,个是习惯表示法。我们知道，对于线性规划背景模型，有,m,个约束方程，且每个约束方程的不等式均为,“,”,号。如果我们在每个约束方程的左边加上一个大于等于,0,的变量，则可将各个约束方程的,“,”,号转变为,“,=,”,。此时，决策变量就有,n+m,个。,26,四、,变换的方法,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,，,代入非标准型,27,五、,变换举例：,1.3.2,线性规划问题的解和,基础,定理,本章开始到现在已讨论的内容，相信大部分读者都会感到比较容易理解和掌握。这一节我们将要讨论关于线性规划问题解的一些,基础,概念和定理，与前面讨论的内容相比，线性规划问题解的一些,基础,概念略显难一些，其中比较难的概念有线性规划问题的基和基础解等相关概念。为了帮助大家比较容易理解这些概念，我们先从大家熟悉的两个变量两个线性方程组这一简单问题入手，然后逐步过渡到我们所要讨论的线性规划问题的基和基础解等相关概念。,著名数学家笛卡尔曾说过，他最擅长做的两件事是：,1),第一做简单事；,2),第二是将复杂事变为简单事。,本,课程,将从大家熟悉的一些简单问题入手，然后逐步过渡到运筹学一些相对比较抽象和难的概念和原理。这是本,课程教学,力求的另一特点。,一、线性方程组的解,考虑如下线性方程组的解：,再考虑如下线性方程组的解：,一、线性方程组的解,类似地，如果将方程组（,3,）中的变量,x2,或,x,1,当成常数，分别移到其方程的右边后采用消元法进行求解，则也可得到如下两组,通,解,及其特解,：,一、线性方程组的解,仔细观察和思考方程组（,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,的系数列向量是线性无关。显然，这三个条件是等价的。,一、线性方程组的解,同样，由于方程组组（,3,）中的变量,x,1,和,x,3,的系数矩阵行列式,|B,2,|,不等于,0,与,变量,x,2,和,x,3,的系数矩阵行列式,|B,3,|,不等于,0,，,即,才能得到方程组（,3,）的通解或特解（,6,）或（,7,）,与,通解或特解（,8,）或（,9,）,。,将上面讨论的方程组（,3,）加上一目标函数和变量非负约束条件后就变成一标准型线性规划。如：,一、线性方程组的解,对于,上述标准型线性规划（,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,）的基础可行解。,二、,标准型线性规划解的若干基础概念,标准型有,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,),最多有 个基,二、标准型线性规划解的若干基础概念,可行解,与,非可行解,满足约束条件和非负条件的解,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,个约束条件。,二、标准型线性规划解的若干基础概念,基础可行解,与,基础非可行解,基础解,X,B,的非零分量都,0,时，称为,基础可行解,，否则为,基础非可行解。,退化,解,基础可行解,的非零分量个数,f,(X,(0),)=0,（,五,）最优检验,将（,5,）式代入,(1),的目标函数后可得,f,(X)=30+x,2,-3x,3,（,6,）,从目标函数（,6,）可知，非基变量,x,2,的系数是正数，,所以,X,(1),不是最优解。,（,六,）求另一个更好的,基础,可行解,48,1,、确定换入变量及其值,从从目标函数（,6,）可知，,只有,非基变量,x,2,的系数,为正,，所以，可确定,x,2,为换入变量,。,由于,所以，,当另一个非基变量,x,3,仍然为,0,时，由,（,7,）,式可得到换入变量,x,1,的值为,x,2,=Min5/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,P2,P,5,),X,B2,=,（,x,1,，,x,2,，,x,5,),T,，,X,N2,=,（,x,3,，,x,4,),T,49,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,三、求初始基础可行解（背景模型，,MAX,),50,设线性规划问题为,另设,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,，,则得,初始本可行解,四、最优检验,51,对于标准化线性规划问题,(2),，经过若干次迭代后，如果对,x,j,及,a,ij,重新编号，则约束方程可化为,其中，,b,i,和,a,ij,表示经过若干次迭代后，当前的右端系数和技术系数，以便区别于原始的右端系数,b,i,和技术系数,a,ij,。将,上,式代入,（,2,）的,目标函数后可得,机会成本,52,在一般情况下，目标函数值,OBJ,计算公式和机会成本计算公式可写成,四、最优检验,其中，,I,为基变量的下标集。,最优检验条件为,其中，,J,表示非基变量的下标集。,对于,基变量,的,检验数为,因为,基变量的技术系数满足：,a,ij,=1,当,i=j,a,ij,=0,当,i,j,五、求另一个更好的,基础可行解,53,若某一,基础,可行解经过最优检验表明不是最优解，则需要设法求得另一个更好的,基础,可行解。求另一个更好的,基础,可行解的主要步骤如下：,1,、确定换入变量；,2,、确定换出变量；,3,、通过基变换或初等变换求得另一个更好的,基础,可行解。,我们已在前面例子中说明了这种初等变换方法的,基础,思路。下一小节我们将用单纯形表进一步说明这种初等变换方法。,54,1.3.4,单纯形法表及单纯形法,55,例,试列出下面线性规划问题的初始单纯型表,单纯形法,步骤,56,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,。,57,表,1.2.4,例,1.2.2,单纯型表的迭代过程,答：最优解为,x,1,=20,x,2,=20,x,3,=0,OBJ=1700,58,单纯型表中元素的几点说明,任何时候，各基变量对应的列都构成一个单位矩阵,当前表中的,b,列表示当前基变量的解值，通过变换,B,1,b,得到,(,资源已变成产品,),当前非基变量对应的向量可通过变换,B,1,A,N,得到，,表示第,j,个变量对第,i,行对应的基变量的消耗率,非基变量的机会成本为,59,1.4,单纯形法的进一步讨论,1.4.1,人工变量法,上一节我们涉及的线性规划模型都是线性规划的背景模型，即目标函数为最大，每个约束方程都是“,”型，右端系数都是大于等于,0,。对于这样一类的线性规划，每个约束方程引入一个松弛变量将其标准化后，约束方程的系数矩阵含有单位矩阵，以此单位矩阵作为初始可行基，很容易得到一个初试,基础,可行解。但是，对于下面的线性规划，将其标准化后，其约束方程的系数矩阵不存在单位矩阵。因此无法直观和方便地得到一个初始,基础,可行解,例,1.4.1,解 令,g(x)=-f(x),，第,1,和,2,个约束方程分别减去一个剩余变量,x,4,和,x,5,，则可将上述线性规划转化为如下标准形线性规划。1.4.1,人工变量法,60,变量,x,6,称为人工变量。这样，变量,x,3,和,x,6,系数矩阵可构成一个单位矩阵，即可构成一个初始可行基，以变量,x,3,和,x,6,为初始基变量，其它变量为非基变量,0,，则可得一初始,基础,可行解,X,(0),=(0,，,0,，,4,，,0,，,0,，,6),T,这种在约束方程中加人工变量来得到初始基础可行解的方法称为人工变量法。,61,我们知道，对于任何一个基础可行解，非基变量都是等于,0,，所以，人工变量在初始基础可行解中虽然不等于,0,，但如果在后面迭代过程中，能把所有人工变量转变为非基变量，则所有人工变量都将等于,0,，这样，原有的约束方程就不会被破坏。但如果在迭代过程中，已得到最优解（即满足最优解检验条件），而基变量中还有人工变量，或最优解时所有人工变量不全部等于,0,，则原线性规划无解，即不存在满足所有约束方程的可行解。,将人工变量从初始基础可行解中转变为非基变量的方法主要有：（,1,）大,M,法；（,2,）两阶段法。下面我们分别讨论。,1.4.1,人工变量法,62,1.4.2,大,M,法,例,1.4.1,63,表,1.4.1,例,1.4.1,的单纯型表迭代过程,答：最优解为,x,1,=2,x,2,=2,x,3,=0,OBJ=36,64,大,M,法的一些说明,大,M,法实质上与原单纯型法一样，,M,可看成一个很大的常数,人工变量被迭代出去后一般就不会再成为基变量,当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题,无可行解,大,M,法手算很不方便,因此提出了二阶段法,计算机中常用大,M,法,二阶段法手算可能容易,65,1.4.3,两阶段法,第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解,第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解,若第一阶段结束时，人工变量仍在基变量中，则原问题无解,为了简化计算，在第一阶段重新定义价值系数如下：,66,用二阶段法求解例,1.4.1,的第一阶段,67,用二阶段法求解例,1.4.1,的第二阶段,最优解对应的,B,1,在哪？68,1.4.4,单纯型法的一些具体问题,一、,无界解,可行区域不闭合,(,约束条件有问题,),单纯型表中入变量,x,j*,对应的列中所有,69,例,1.4.2,的单纯型表及其迭代过程,70,二、,退化解,退化问题的原因很复杂，当原问题存在平衡约束时,当单纯型表中同时有多个基变量可选作出变量时,退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法,71,三、多重解,多个基础可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行,最优单纯型表中有非基变量的检验数为,0,最优解的线性组合仍是最优解，即,X,=,aX,1,+,bX,2,，,a,+,b,=1,72,例,1.4.4,的单纯型表及其迭代过程,73,四、,无可行解,约束条件互相矛盾，无可行域,单纯型表达到最优解检验条件时，人工变量仍在基变量中,74,例,1.4.5,第一阶段的单纯型表,1.5,修正单纯形法,1.5.1,单纯形法的矩阵描述,75,其中，,X,S,=(x,s 1,，,x,s 2,，,，,x,s m,),为,松弛变量,，,I,为,m,m,阶单位矩阵。目标函数中松弛变量,X,S,的系数,0,是一列,0,矩阵。,以,X,S,对应的系数矩阵单位阵,I,做为初始可行基,B,，对应的松弛变量,X,S,为初始基变量，记为,X,B,，其余变量为初始非基变量，记为,X,N,。,令,X,N,=0,，则可得到对应于初始可行基,B,（为单位阵）的初始基础可行解,X=(X,B,X,N,)=(b,0),，对应目标函数值为,f(X)=0,。并以该初始基础可行解,X=(X,B,X,N,)=(b,0),为切入点开始进行迭代运算。,1.5.1,单纯形法的矩阵描述,76,一般地，对于任一标准型线性规划，在某一步迭代运算中，设,B,是其可行基，则该标准型线性规划可用矩阵形式表示如下：,其中,，,X,=(,X,B,X,N,),T,，,C=,(,C,B,，,C,N,）,，,A=,(,B,，,A,N,）。,由于,B,是可行基，,B,-1,存在，所以，上述线性规划的约束方程可写成,X,B,=,B,-1,(,b,-,A,N,XN,),将上式,X,B,代入,上述,线性规划的目标函数，并整理后可得，,f,(,X,)=,C,B,B,-1,b,+(,C,N,-,C,B,B,-1,A,N,),X,N,令,X,N,=0,，,X=(X,B,X,N,)=(B,-1,b,0),，,f(X)=C,B,B,-1,b,对应某一可行基,B,的最优检验条件用矩阵形式可表示如下：,N,=,(,C,N,-C,B,B,-1,A,N,),0,（,2,）,77,1.5.1,单纯形法的矩阵描述,若非基变量,X,N,的系数向量,(C,N,-C,B,B,-1,A,N,),有一些分量大于,0,，则取其中数值最大的一个分量,k,所对应的非基变量分量,x,k,做为换入变量分量。,对于某一非最优可行基,B,，确定换出变量时，可用如下矩阵形式表示：,其中，,P,k,为标准型线性规划（,1,）技术系数矩阵,A,中换入变量,x,k,的系数列向量。,根据公式（,3,）的计算结果，基变量向量,X,B,中的第,i*,分量,x,l,为换出变量。当然，如果公式（,3,）的计算结果为空集，则为无界解。,确定了换入变量,x,k,和换出变量,x,l,，就可以得到新的可行基和对应的基变量和非基变量,等,，并按公式,(,2,),进行最优检验。,78,1.5.2,改进单纯形法,原单纯型法迭代所需存储量大，原单纯型法有不必要的计算量,由于改进单纯形算法通过矩阵运算求解线性规划，其关键是计算某一可行基,B,的逆矩阵,B,-1,。,可,按,如下初等变换进行：,(,B,I,),(,I,B,-1,),例,1.5.1,用改进单纯形算法求解如下线性规划,79,解,（一）列出技术系数矩阵,A,，,选择,初始基,、初始基变量等,（二）最优检验,由于,B,0,是单位阵，其逆矩阵,B,0,-1,也是单位阵。,X,B0,=,（,x,3,，,x,4,，,x,5,),T,，,X,N0,=,（,x,1,，,x,2,),T,C,B0,=,（,0,，,0,，,0,）,，,C,N0,=,（,2,，,3,），,A,N0,=(P,1,，,P,2,),所以，初始基,B,0,不是最优基。,由于,检验数向量第,2个分量值最大，所以对应初始非基变量,X,N0,=,（,x,1,，,x,2,),T,的第,2,个分量,x,2,为换入变量。即,x,k,=x,2,。,80,（三）确定换出变量，得到新的可行基及对应的基变量等,i,*,=3,，对应基变量,X,B0,=,（,x,3,，,x,4,，,x,5,),T,的第,3,个分量,x,5,为换出变量，根据换出变量,x,5,、换入变量,x,2,和初始基,B,0,=(P,3,，,P,4,，,P,5,),，得到新的可行基,及其,基变量,等,B,1,=(P,3,，,P,4,，,P,2,),，,X,B1,=,（,x,3,，,x,4,，,x,2,),T,，,C,B1,=,（,00,，,3,），,X,N1,=,（,x,1,，,x,5,),T,，,C,N1,=,（,2,，,0,），,A,N1,=(P,1,，,P,5,),。,（四）最优检验,由于可行基,B,1,的非基变量检验数向量,所以，可行基,B,1,不是最优基。,由于,检验数向量第,1,个分量值最大，所以对应非基变量,X,N1,=,（,x,1,，,x,5,),T,的第,1,个分量,x,1,为换入变量。,81,（五）确定换出变量，得到新的可行基及对应的基变量等,i,*,=1,，对应基变量,X,B1,=,（,x,3,，,x,4,，,x,2,),T,的第,1,个分量,x,3,为换出变量,根据换出变量,x,3,、换入变量,x,1,和可行基,B,1,=(P,3,，,P,4,，,P,2,),，得到新的可行基,及其,基变量,等,B,2,=(P,1,，,P,4,，,P,2,),，,X,B2,=,（,x,1,，,x,4,，,x,2,),T,，,C,B2,=,（,2,，,0,，,3,），,X,N2,=,（,x,3,，,x,5,),T,，,C,N2,=,（,0,，,0,），,A,N2,=(P,3,，,P,5,),。,（六）最优检验,由于可行基,B,2,的非基变量检验数向量,所以，可行基,B,2,不是最优基。,检验数向量第,2,个分量值最大，所以对应非基变量,X,N2,=,（,x,2,，,x,5,),T,的第,2,个分量,x,5,为换入变量。,82,（,七,）确定换出变量，得到新的可行基及对应的基变量等,i,*,=2,，对应基变量,X,B2,=,（,x,1,，,x,4,，,x,2,),T,的第,2,个分量,x,4,为换出变量，根据换出变量,x,4,、换入变量,x,5,和可行基,B,2,=(P,1,，,P,4,，,P,2,),，得到新的可行基,及其,基变量,等,B,3,=(P,1,，,P,5,，,P,2,),，,X,B3,=,（,x,1,，,x,5,，,x,2,),T,，,C,B3,=,（,2,，,0,，,3,），,X,N3,=,（,x,3,，,x,4,),T,，,C,N3,=,（,0,，,0,），,A,N3,=P,3,，,P,4,),。,（八）最优检验,由于可行基,B,3,的非基变量检验数向量,所以，可行基,B,3,是最优基。对应的最优解为,1.6,线性规划建模案例分析,1.6.1,线性规划建模,基础,步骤,83,一、建模前需要考虑的问题,1,）所讨论问题的目标是否可用一线性函数来描述；,2,）所讨论问题是否存在多种解决方案及其相关数据；,3,）所要达到的目标是在一定约束条件下可以实现，且这些约束条件可以线性方程来表示。,二、,建立线性规划模型的,基础,步骤,1,、确定一目标；,2,、选择一组决策变量；,3,、列出目标函数和所有的约束方程。,上面三个步骤中，步骤一和步骤二尤其重要。其中步骤一要确定一适当的目标并能够用恰当的方式进行表示，有时直接表示问题的目标有困难时，可用等价方式表示；步骤二要求选择一组合理的决策变量，用这些变量能够方便地列出步骤三的目标函数和所有约束方程。,84,案例,1,某工厂生产用,2,单位,A,和,1,单位,B,混合而成的成品出售，市场无限制。,A,和,B,可在该工厂的,3,个车间中的任何车间生产，生产每单位的,A,和,B,在各车间消耗的工时如下表。试建立使产品数最大的线性规划模型。,消耗工时,车间,1,车间,2,车间,3,A,2,1,1,5,B,1,2,1,5,可用工时,100,120,100,解：上述问题看似比较简单，目标是使产品数最大，决策变量分别是车间,1,、车间,2,和车间,3,生产产品零件,A,和,B,的数量。但是，一个产品是由,2,个,A,零件和,1,个,B,零件组成，所以直接表示产品数最大有一定困难，为此，我们考虑如下等价表示方式：,1,）产品数最大等价于：零件,B,数最大，且零件,A,的总数满足是零件,B,的总数两倍；,2),产品数最大等价于：零件,A,数最大，且零件,B,的总数满足是零件,A,的总数,1/2,倍,85,案例,1,解：设车间,1,生产,x,1A,单位,A,、生产,x,1B,单位,B,；,设车间,2,生产,x,2A,单位,A,、生产,x,2B,单位,B,；,设车间,3,生产,x,3A,单位,A,、生产,x,3B,单位,B,；,则有生产安排最优化的模型如下：,讨论：,第,4,个约束方程取“”,好,，,还,是,取,“,=,”,好呢？,86,案,例,2,某饮料工厂按照一定的配方将,A,、,B,、,C,三种原料配成三种饮料出售。配方规定了这三种饮料中,A,和,C,的极限成分，具体见下表，,饮料品种,规格,每升售价（元）,需求量,甲（,1,）,A,60%,C,20%,6.80,1500,乙（,2,）,A,15%,C,60%,5.70,3000,丙（,3,）,C,50%,4.50,无限制,A,、,B,、,C,三种原料每月的供应量和每升的价格如下表。,供应量（升,/,月）,价格（元,/,升）,A,2000,7,00,B,2500,5,00,C,1200,4,00,饮料甲、乙和丙分别由不同比例的,A,、,B,、,C,调兑而成，设调兑后不同成分的体积不变，求最大收益的生产方案的线性规划模型。,87,案,例,2,解：问题是要确定原料,A,，,B,和,C,的购买量和饮料甲、乙和丙的生产量，使得在满足规定约束条件下，饮料厂的总收益最大。,建立该问题的线性规划模型的主要问题是如何选择决策变量，如果直接选择,A,，,B,和,C,的购买量和饮料甲、乙和丙的生产量六个变量做为决策变量，那将无法表示饮料甲、乙和丙中的,A,和（或）,C,的规格要求。为此，我们设：,x,1A,为饮料甲中,A,的总含量,(,升,),；,x,2A,为饮