运筹学教学演示系统⑴.ppt

运筹学教学Operational Research Teaching,主讲：李中才电话：13616450336邮件：L,教学内容提要,绪论第一章 线性规划及单纯形法第二章 对偶问题及灵敏度分析第三章 运输问题第四章 整数规划第五章 动态规划第六章 图与网络,绪论,第一节 运筹学的简史一、运筹学的产生背景 运筹学英文：Operational Research 中文名称的由来：运筹帷幄 产生的时间：20世纪30年代 产生的背景：二战时期的军事应用(武器利用)1940年英国成立了运筹学小组 1942年美国成立了17人OR小组,绪论运筹学的简史,二、运筹学体系的形成 二战之后，除了继续从事国防战略研究外，转入国民经济各部门的应用研究。20世纪50年代以后，形成了一整套理论。规划论、排队论、存贮论、决策论等。理论体系形成。1957年召开了世界第一次运筹学会议，1959年成立国际运筹学学会联合会（IFORS）International Federation of Operational Research Societies。50年代计算机的问世与发展推动了运筹学的发展。,绪论运筹学的简史,三、运筹学在我国 1956年，中国科学院力学研究所成立了第一个OR小组；1957年运筹学开始应用于建筑业和纺织业；1958年开始在交通、工业、水利、邮电等方面；1960年起开始在石油、钢铁部门开始应用；1965年起统筹法在建筑、大型设备维修得以应用；上世纪70年代后期系统工程的应用得以重视；1980年成立全国运筹学学会；1982年加入国际运筹学联合会。贡献：运输问题、邮递员问题学者：钱学森、管梅谷,绪论运筹学的简史,第二节 运筹学的研究对象 一、什么是运筹学 1、定义：A、运筹学是一种科学的决策方法。B、运筹学是依照给定目标和条件从众多方案中选择最优方案的优化技术。C、运筹学是一门寻求在给定资源条件下，如何设计和运行一个系统的科学决策方法。D、运筹学是近代形成的一门应用学科，它主要用数学方法研究各种管理问题的优化途径及方案，从而为决策者提供科学的决策依据。,绪论运筹学的研究对象,2、运筹学的内涵 它不仅是优化技术或各种决策方法的组合，它是进行科学的定量分析，从而发现问题、解决问题的方法论。它具有多学科交叉的特点，数学、经济学、社会学、心理学等。它与自然科学不同事理科学。即研究如何把事办好。,自然界,绪论运筹学的研究对象,3、运筹学研究的特点A、科学性：表现在方法的科学性；多学科的科学知识。B、实践性：研究的对象实际问题；结果需要实 践来验证，并用于指导实践。C、系统性：着眼于整个系统而不是局部。D、综合性：它是一种综合性的研究，涉及方方面面，应用到多学科知识，需要由各方面专家组成。,绪论运筹学的研究对象,二、运筹学的研究对象,各种有组织的系统（主要是经济系统）的经营管理问题及其 求解的原理和方法。注意：1、运筹学所研究的系统：是指在一定条件下能为人所控制和操作，有两个或两个以上行动方案可供选择而需要人们做出决策的系统。2、运筹学所研究的问题：是能用数量方法表示，且与系统各项活动有关的带有运用、筹划、使用、安排、控制和规划等方面的问题。3、运筹学的任务：在现有条件下，根据要求，建立模型，求解最优途径和方案。,绪论运筹学的研究对象,第三节 模型及其应用步骤 运筹学的核心就是建立和应用模型。一、什么是模型 为了研究某些问题的共性以解决实际问题，经常使用文字、数字、符号、公式、图表及实物，用以描述现实客观事物的某些特征和内在联系，从而表示或解释某一系统的过程。实物模型：制图教具；图表模型：工程进展图；文字模型：程序框图；数字、符号、公式模型。,绪论模型及其应用步骤,二、运筹学模型 运筹学所使用的模型一般为数学模型。数学模型是现实问题中有关因素和参数及其关系的数学表达式。运筹学模型一般有决策变量、约束条件（限制条件）以及目标函数所构成。模型含义：在约束条件所允许的范围内，寻求满足目标要求的最优解。模型的数学形式：,Xi为决策变量；j为已知参数；k为随机参数,绪论模型及其应用步骤,三、为什么要使用模型 抽象研究、共性研究；主要因素分析；试验功能、时效性。四、运筹学模型分析研究问题的步骤 提出及分析问题；建立模型；确定最优方案；检验及灵敏性分析、实施。,绪论模型及其应用步骤,第四节 运筹学的应用领域 市场销售：以竞争性定价为代表；生产计划：生产组织和资源配置；库存管理：存储费用；运输问题：减少折返运输；设备维护：维修及更新；城市管理：交通线路的布置；工程优化：施工过程控制；,绪论运筹学的应用领域,什么是线性规划？线性规划发展的基础：美国学者丹捷格提出的线性规划问题的一般解法单纯形法。线性规划解决的问题：企业经营管理问题管理的职能。线性规划应用的方面：生产组织与计划、资源的合理利用、配料问题、布局问题及运输问题。,第一章 线性规划及单纯形法,第一章线性规划及单纯形法,第一节 实际问题及线性规划模型 一、问题的提出 例1 某厂计划在下一个生产周期内生产甲、乙两种产品，这两种产品分别要经过两种设备加工，有关数据如下表，问应如何安排生产计划使总利润最大？,第一章线性规划及单纯形法,分析该问题 做什么决策？生产计划每种产品的产量 设生产甲、乙两种产品分别为,受到什么限制？设备台时 设备A：设备B：,有多少种可行方案？,哪个方案好呢？,第一章线性规划及单纯形法,判断标准是什么？利润 最大利润如何表示：,问题的数学模型为：,为什么出现,第一章线性规划及单纯形法,例3 教材的例2,假设河流自然净化率20，一厂处理污水成本1000元/万m3，二厂处理污水成本800元/万m3，根据环保要求污水含量不大于0.2，每厂各处理多少污水，使总费用最低。,第一章线性规划及单纯形法,分析问题 决策变量很明显，各厂污水处理量,可用x1,x2 约束条件 A.各段河流的污水含量满足环保要求，如何考虑?一厂:(2-x1)/5000.2%二厂:0.8(2-x1)+(1.4-x2)/(500+200)0.2%B.处理能力与污水排放量的关系 x1 2;x2 1.4 判别依据:处理成本Z最小 Z=1000 x1+800 x2,第一章线性规划及单纯形法,数学模型:,第一章线性规划及单纯形法,例4 假定有一批某型号的圆钢，其长8m，需要截取长为2.5m和1.3m的毛坯各100根和200根，问如何下料使用料最少？分析该问题 每种规格的毛坯单独截取 2.5m的毛坯100根需要多少圆钢 334 100 1.3m的毛坯200根需要多少圆钢 634 200 则共需要圆钢68根 下面我们考虑一下用67根圆钢能否截取2.5m和1.3m的毛坯各100根和200根呢？如何截?,混合截取 混合截取有哪些方式？,如何假设决策变量 设Xj表示第j种方式所用的原材料根数(j=1,2,3,4),例5 某厂有5种合金，其成份及成本如下表，将5种合金混合成一种含铅30、含锌20、含锡50的新合金，问如何混合使成本最省？,如何选定决策变量 各种合金需要量,分别用x1,x2,x3,x4,x5表示 约束条件 含铅30,含锌20、含锡50可以类推 目标函数：总成本 如果决策变量不采用上面的假设，而是各种合金所占的比重，那么，是否也可以解决这个问题？,例6 某物资共有三个产地A、B、C，三个销地、，产地的产量、销地的需要量、单位运价如下表，如何调运使总运费最少？,决策变量是什么？,表示产地 i 运往销地 j 的产品数量,如上表所示,约束条件是什么？每一产地运出的产品数量不大于产地产量 每一销地接收的产品数量不小于销地需要量 其数学模型如下:,二、线性规划模型的一般形式 综上所述，各种数学模型具有一些共同的特点：求一组决策变量的值，使目标函数达到最大或最小；存在一组约束条件，这些约束条件都是线性等式或线性不等式；目标函数是决策变量的线性函数。因此，线性规划问题就是求一个线性目标函数在一组线性约束条件下的极值问题。模型的一般形式可描述为：,第一章线性规划及单纯形法,第一章线性规划及单纯形法,三、线性规划问题的图解法 线性规划问题就是求一个线性目标函数在一组线性约束条件下的极值问题。因此，决策变量的取值首先要满足这些约束条件。反过来说 首先要确定满足约束条件的解，然后在这些解中找到最优的解。对只有两个变量的线性规划问题，可以采用图解法。例7 用图解法求解下列线性规划问题,第一章线性规划及单纯形法,解：图解法应注意的问题 每一个约束条件，在平面上有一定的区域与之对应 等式是一条直线，不等式是一个区域 对于不等式，首先作等式直线，然后确定区域 分析规划 由于xij0,因此满足约束条件的区域在第一象限 作图,第一章线性规划及单纯形法,图中阴影重叠区域中的每一个点都满足约束条件，该阴影区域称为可行域(OABC)，记为D;可行域中的每一点称为可行解。,第一章线性规划及单纯形法,目标函数值的问题 怎样确定最优的目标函数值呢？可行域中不同的点，将得到不同的Z值。先看两个Z值的情况(z=60 x1+50 x2)Z=0 Z=500 根据Z值作目标函数线,第一章线性规划及单纯形法,按照平行的方向，移动目标函数线与边界上B点相交，则B为最优解。,例8 用图解法求解下列线性规划问题,第一章线性规划及单纯形法,平移的结果是与BC线重合，也就是BC线段上任一点都是最优解，则为无穷多最优解。,例9 用图解法求解下列线性规划问题,可行域无界，平移可使目标函数值达到无穷大，称这种情况为无界解或无有限最优解。,例10 用图解法求解下列线性规划问题,可行域无界，但由于求目标函数的最小值，向下平移目标函数线，在B点达到最优值。,例11 用图解法求解下列线性规划问题,无可行域，无可行解，不存在最优解。,几点结论：若线性规划问题有可行解，则可行域是一个凸多边形。可行域有可能有界，也可能无界。若线性规划问题有最优解，则这个最优解一定在可行域的顶点或边界得到。若可行域无界，也可能存在最优解。线性规划问题的解有四种情况 惟一解；无穷多个解 无界解或无有限最优解；无可行解,第一章线性规划及单纯形法,四、线性规划模型的标准形式 标准形式的目的是将各种问题统一起来。1.线性规划问题的标准形式,第一章线性规划及单纯形法,2.线性规划问题标准型的矩阵描述,其中：,若记：,则：,第一章线性规划及单纯形法,3.如何将非标准的线性规划模型转化成标准型 目标函数的最小变最大 如何将求最小所得到的结果和求最大所得到的结果是一致的。方法为：,约束方程的常数项为负值 约束方程两边乘以（-1）不等式变等式 引入大于等于零的松弛变量,第一章线性规划及单纯形法,决策变量的无约束 引入两个非负变量，两个非负变量之差就具有无约束的特征。,将下列模型转化成标准型,第一章线性规划及单纯形法,第二节 线性规划问题解的基本性质 一、解的基本概念 对于线性规划问题的标准形式,m为约束方程的个数，n为决策变量的个数。一般只讨论 mn 的情况。定义1：满足约束条件的解，称为线性规划问题的可行解，可行解的集合称为可行域，记为：,第一章线性规划及单纯形法,定义2：使线性规划的目标函数达到最大值的可行解称为最优解,即用数学语言来描述如下：,定义3：线性规划模型约束方程组的系数矩阵A的任一个mm阶的非奇异子方阵B，称为线性规划问题的一个基或基阵。不失一般性,第一章线性规划及单纯形法,注意的概念：基向量 非基向量 基变量 非基变量,定义4：对于选定的基B，令非基变量的取值为零，所得到的一组解称为线性规划问题的一个基本解。,第一章线性规划及单纯形法,注意几个问题：决策变量不用矩阵描述，怎么表示基本解 可行解与基本解的关系 基本解的个数:不大于Cnm个 基本解在图形中的位置 定义5：满足非负条件的基本解称为基可行解，相应的基B称为可行基。基可行解一定在可行域内吗？下面看一个的例子,第一章线性规划及单纯形法,标准型,基有多少种情况：,第一章线性规划及单纯形法,二、解的几何意义 定义6：存在集合K，若对于任意的X(1)K；X(2)K，其连线上的一切点有 X(1)+(1-)X(2)K则称K为凸集。(01)凸集的几何意义是集合中任两点的连线仍在该集合中。,凸集的特殊情况：一条线、一个点、空集 两点连线的任一点能够表示，如何表示三角形中的任一点呢？如何表示多维空间中的任一点呢？这就是凸组合的概念！即：,第一章线性规划及单纯形法,定义7：设K为凸集，若X（XK）不能用不同的两点X(1)K和X(2)K的线性组合表示为 X=X(1)+(1-)X(2)(01)则称X为K的一个顶点（极点）。,第一章线性规划及单纯形法,定理1：若线性规划问题存在可行域，则其可行域为凸集。证明的思路：什么是线性规划问题的可行域？在可行域中取任意的两个点 目的是证明两点连线的任一点都属于可行域，则可行域为凸集。,第一章线性规划及单纯形法,定理1的证明如下证明：设线性规划模型如下：,从其可行域中任取两点X（1）、X（2），且X（1）X（2），则其连线上任意点X为：X=X（1）+（1-）X（2）其中：0 1因为X（1），X（2）属于可行域中的两点，则满足：AX（1）=b，X（1）0AX（2）=b，X（2）0,下面证明X是否为可行域的点。把X代入约束条件中，即AX=AX（1）+（1-）X（2）=AX（1）+A（1-）X（2）=AX（1）+（1-）AX（2）=b+（1-）b=b因为：0 1，则0 1-1又因为：X（1）0、X（2）0所以：X=X（1）+（1-）X（2）0 所以X仍为可行域中的一点所以线性规划的可行域为凸集,引理1：线性规划问题的任意一个可行解为基可行解的充分必要条件是该可行解的正分量所对应的系数列向量是线性无关（线性独立）的。下面对引理进行简单的证明,第一章线性规划及单纯形法,若证明引理1，首先了解这样几个问题：可行解的正分量（非零分量）必要条件 若可行解为基可行解，则线性无关 充分条件 若线性无关，则可行解为基可行解 线性无关（线性独立）,定理2：线性规划问题的基可行解对应于可行域顶点。证明的思路：顶点不能用不同的两点连线表示；基可行解必须保证向量线性无关。定理3：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。结论：可行域是凸集；基可行解是凸集的顶点；若存在最优解，最优解一定可在某个基可行解上取得。,第一章线性规划及单纯形法,定理2的证明证：不失一般性，假设基可行解X的前m个分量为正，则：,现分两步讨论，分别用反证证明（1）若X不是基可行解，则它一定不是可行域的顶点。根据引理1可知，若X不是基可行解，则其正分量所对应的系数列向量p1,p2,pm线性相关，则存在一组不全为0的数i(I=1,2,m)，使下式成立：,用一个0的数乘（2）式后分别与（1）式相加减得：,（2）若X不是可行域的顶点，则它一定不是可行基。因为X不可行域的顶点，则可在可行域内找到不同的两点,假设X是基可行解，则对应的向量p1,p2,pm线性独立。且当jm时有：,将上两式相减得：,定理3的证明证：设X(1),X(2),X(k)是可行域的顶点,X(0)不是顶点,且目标函数在X(0)处达到最大值，即：Z*=CX(0)为目标函数的最大值,将X(0)代入目标函数,即,在所有顶点中,我们一定可从中找到一点X(m),使其目标函数C X(m)为这些顶点的最大,即可得到下式:,所以要使目标函数取得最大值,X(0)只能为某个顶点。,第三节 线性规划问题的单纯形法 单纯形法的基本思路：从一个顶点开始，在顶点中逐步选优，使目标函数达到最优或判定规划问题无解。一、单纯形法的引入 先用一个例子说明单纯形法的过程 例1 求下列问题的最优解,第一章线性规划及单纯形法,解：化标准型,确定初始基可行解并判别是否为最优解,第一章线性规划及单纯形法,为了方便求解,用非基变量表示基变量,即,目标函数用非基变量表示为,令非基变量为0得一基可行解为,第一章线性规划及单纯形法,从上述目标函数Z可知，只要目标函数中变量（非基变量）的取值不为零，目标函数值将增大。因此，该基可行解不是最优解。如何使非基变量取值不为零？非基变量取非零的值，意味着非基变量成为基变量。而基变量的个数一定，则只能将非基变量和基变量进行替换。这一替换将得到第二个基可行解。,第一章线性规划及单纯形法,迭代确定第二个基可行解 所谓迭代，就是一个非基变量和一个基变量的交换。选哪个非基变量成为基变量呢？从目标函数看：,选X2进基，X1仍然为非基变量，必须解决两个问题：哪个出基呢？哪个成为非基变量？X2=?，当然越大越好，应考虑什么？还是从约束条件来解决这个问题。,第一章线性规划及单纯形法,考查约束条件,第一章线性规划及单纯形法,仍按上述方法,用非基变量来表示基变量如下,目标函用非基变量表示为:,令非基变量为零,得基解为,第一章线性规划及单纯形法,从上述目标函数Z可知，目标函数中x1的系数为2,当其取值不为零，目标函数值将增大。因此，该基可行解仍不是最优解。还需要迭代。只要目标函数中变量X1（非基变量）的取值不为零，目标函数值将增大。因此，该基可行解不是最优解。,迭代确定第三个基可行解,二、单纯形法的基本原理 单纯形法是以基可行解的迭代及判别为核心内容。1.初始基可行解的确定 初始基可行解与初始可行基是对应的，找初始可行基的方法有：若线性规划模型约束方程的系数矩阵中，存在一个m阶的单位矩阵，该单位矩阵所对应的系数列向量就是一个初始可行基。若原线性规划模型的所有约束方程都是“”号的不等式，则引入的松弛变量的系数列向量就是一个初始可行基。非以上两种情况，应采用特殊的方法来确定初始可行基。,第一章线性规划及单纯形法,2.存在初始可行基的线性规划模型表示方法 若A中存在一个初始可行基，不妨假设由A的前m列组成，即：,若目标函数仅包含非基变量，则线性规划模型可表示为：,第一章线性规划及单纯形法,该表示法往往称为线性规划关于基B的典式。目标函数中，非基变量的系数称为检验数。3.最优性检验与解的判别 解的情况：唯一最优解，无穷最优解，无界解，无可行解。建立解的判断准则。我们先推导一下检验数j计算公式,第一章线性规划及单纯形法,根据线性规划的引入，可知对于线性规划标准模型，经变换总可以把基变量用非变量表示成下列形式：,将上式代入目标函数得：,第一章线性规划及单纯形法,最优解判别定理 若X为对应于基B的基可行解，其检验数,则，X为最优解。,上式的j即为基变量xj的检验数，因此检验数计算公式为：,根据基变量的检验数，我们可以进行解的判别。最优解的类别准则如下：,第一章线性规划及单纯形法,无穷多最优解判别定理 若X为对应于基B的基可行解，其检验数,则线性规划问题存在无穷多最优解。无界解判别定理 若X为对应于基B的基可行解，存在某个检验数,则线性规划问题具有无界解（无有限最优解）。问题是如何判别无最优解的情况呢？注：上述判断都针对目标函数为求最大的情况，如果目标函数为求最小时，可以将其转化为求最大的情况，然后管好上述准则进行判断。但也可不转化，把判断准则取反极可。,4.基变换 换入变量的确定最大法则：目标函数系数，对于经过变换的模型就是检验数。,换出变量的确定最小比值法则：各约束方程的常数和换入变量系数的比值。,5.迭代 所谓迭代就是将换入变量的系数列向量变成换出变量系数列向量（单位向量）的过程。,第一章线性规划及单纯形法,三、单纯形法的计算步骤 1.单纯形表 构造单纯形表的要点包括：化标准型 确定初始基可行解 确定初始基可行解所对应的检验数 下面构造单纯形表,第一章线性规划及单纯形法,将目标函数与约束方程组成n+1变量，m+1个约束条件,为了便于迭代,将上述方程组写成增广矩阵的形式,第一章线性规划及单纯形法,将Z看作不参变换的基变量,它与X的系数构成一个基,采用矩阵的初等变换,使基变为单位矩阵,得:,第一章线性规划及单纯形法,根据上述增广矩阵设单纯形表如下:,m+1,n,第一章线性规划及单纯形法,例2 用单纯形表求解下列规划问题,化标准型,第一章线性规划及单纯形法,第一章线性规划及单纯形法,第一章线性规划及单纯形法,检验数全部小于等于零，得到最优解，且是惟一最优解，即：,第一章线性规划及单纯形法,2.单纯形表的计算步骤 找出初始可行基，列出初始单纯形表；检验各非基变量的检验数，若检验数全部小于等于零，则已经得到最优解，否则继续下一步；在所有正的检验数中，若某检验数所对应的系数分量小于等于零，则此问题无界，否则转入下一步；根据最大法则确定进基变量，根据最小比值法则确定出基变量；以进基变量与出基变量交叉的元素（主元、旋转元素）进行行初等变换，得到新的单纯形表；重复，直至结束。,第一章线性规划及单纯形法,3.几种特殊情况 例3 求解下列模型,该模型的初始单纯形表及某步的单纯形表为：,第一章线性规划及单纯形法,该模型的初始单纯形表及某步的单纯形表为：,可以看出，已经得到最优解，但存在一个非基变量的检验数为零。若以该非基变量为进基变量，再迭代，将得到下面的单纯形表。,因此，该线性规划已经得到了两个最优解，那么这两点连线中的任一点都是最优解，即存在无穷多最优解。无穷多最优解的表示方法为：,第四节 人工变量法确定初始可行基 单纯形表是从一个初始基可行解开始的，如果在线性规划问题的系数矩阵中不存在一个 m阶单位矩阵，也即很难找到一个初始可行基怎么办？一、人工变量的引入 设线性规划问题为：,第一章线性规划及单纯形法,若A中不存在m阶单位矩阵，为了形成一个m阶单位矩阵，可给每个约束方程人为地加上一个人工变量，则模型调整为：,新规划与原规划是否一致呢？什么样情况下一致呢？人工变量等于零！,二、大M法 为了对人工变量进行处理，在模型的目标函数中也引入人工变量，其系数为（-M）（M为任意大的正数），即,M很大很大，-M就很小很小。显然，若人工变量不为零，目标函数不可能得到最大值，也不可能获得最优解。一般称M为惩罚因子。例4 用大M法求解下列规划问题（书上的例子）,解题应注意的问题；引入几个人工变量 如何确定初始单纯形表的检验数 若存在最优解，最终表的目标函数值不可能包含M 三、两阶段法 始终包含一个M进行单纯形表的运算是不方便的。两阶段法就是将引入人工变量后的规划问题分为两个阶段来求解：利用辅助规划，判断原规划是否存在基可行解，并给出基可行解。从求得的基可行解出发，对原问题继续迭代，求最优解。,两阶段法的辅助规划为：,例5 用两阶段法求解下列线性规划问题，注意其改进！,