运筹学胡运权第五版课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运 筹,学,(,Operations Research,),一、古代朴素的运筹学思想,例如：田忌赛马,二、运筹学的起源,国外,英文原名,Operations Research,简称,“,O.R.”,直译为：运用研究或作业研究,正式出现于,1938,年,7,月英国一份关于防空作战系统运行的研究报告中,二战后运筹学的发展经历了三个阶段,绪 论,国内,1956,年成立第一个运筹学小组,1957,年从,“,夫运筹策帷幄之中，决胜于千里之外,”,中摘取,“,运筹,”,二字，将,O.R.,正式翻译为,“,运筹学,”,三运筹学的定义,研究工具：数学，计算机科学及其他相关科学,研究目的：对有限资源进行合理规划、使用，并提供,优化决策方案。,研究对象：复杂系统的组织和管理,参考,大英百科全书,、,辞海,、,中国企业管理百科全书,等。,四、运筹学研究的基本特点,系统的整体优化,多学科的配合,模型方法的应用,五、运筹学研究的基本步骤,分析与表述问题,建立数学模型,对问题求解,对模型和模型导出的解进行检验,建立对解的有效控制,方案的实施,六、本课程的主要学习内容,第一章 线性规划及单纯形法,第二章 线性规划的对偶理论,第三章 运输问题,第四章 整数规划与分配问题,第六章 图与网络分析,第一章 线性规划及单纯形法,Linear Programming and Simplex Method,x,a,此为无约束的极值问题,1.1,一般线性规划问题的数学模型,1-1,问题的提出,例,1,用一块边长为,a,的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？,解：如图设四个角上减去的小正方形边长为,x,，则容器体积为：,时，容积最大,例,2,常山机器厂生产,I,、,II,两型产品。这两型产品都分别要在,A,、,B,、,C,三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：,如何安排生产才能使总的利润最大？,单位产品消耗设备工时,I,II,设备工时限量（小时）,设备,A,设备,B,设备,C,2,4,0,2,0,5,12,16,15,单位利润（元）,2,3,解：设计划期内两种产品的数量分别为,x,1,，,x,2,，则总利润为：,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,简记为：,s.t,.,（约束于：）,z,=2,x,1,+3,x,2,在满足限制条件下求,z,的最大值。,此为有约束极值问题,1-2,线性规划问题的数学模型,原型,模型,数学模型,提炼,数学工具,1,、,原型,：现实世界中人们关心、研究的实际对象。,模型,：将某一部分信息简缩、提炼而构造的原型替代物。,数学模型,：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。,3,、规划问题数学模型的三要素,（,2,）,目标函数,：问题要达到的目标要求，表示为决策变量的函数。用,z,=,f,(,x,1,，,x,2,，,，,x,n,),表示。,（,1,）,决策变量,：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用,x,1,，,x,2,，,，,x,n,表示。,（,3,）,约束条件,：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,2,、规划问题,即求目标函数在若干约束条件下的最值。4,、线性规划问题（,Linear Programming,）的数学模型,（,2,）,一般形式,：,（,1,）,条件,：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为,“,L.P.”,max,(,或,min,)z=c,1,x,1,+c,2,x,2,+,+,c,n,x,n,s.t,.,a,11,x,1,+a,12,x,2,+a,1n,x,n,（,=,，,）,b,1,a,21,x,1,+a,22,x,2,+a,2n,x,n,（,=,，,）,b,2,a,m1,x,1,+a,m2,x,2,+,a,mn,x,n,（,=,，,）,b,m,x,1,x,2,x,n,0,（,3,）,其他形式,连加形式,向量形式,其中,称为,价值行向量,；,决策列向量,系数列向量,右端列向量,矩阵形式,其中,称为价值行向量；,决策列向量,右端列向量,约束矩阵或系数矩阵,1-3,线性规划问题的标准形式,1,、标准形式,或,2,、条件,目标函数求极大值,约束条件全是等式（线性方程组）,决策变量全非负,右端常数全非负,3,、标准化方法,（,1,）若目标函数求极小值，即,则令,转化为,（,2,）若约束条件为不等式，,则依次引入松弛变量或剩余变量（统称为松弛变量），,转化为等式约束条件。,注意,：松弛变量在目标函数中系数全为,0,。,约束为不等式，减去松弛变量，化为等式约束条件；,约束为不等式，加上松弛变量，化为等式约束条件。,多退少补,例：,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t,.,标准化,（,3,）若决策变量,x,j,0,，则令,（,4,）若决策变量,x,j,取值无限制，则令,（,5,）若约束等式的右端常数,b,i,0,，则等式两边同时乘以“,-1,”,。,其中,（“一分为二”）,例：,将下列线性规划模型化为标准形式。,则问题化为标准形式：,并引入松弛变量,x,4,x,5,1-4,线性规划问题的解,已知线性规划的标准形式：,或,1,、,求解线性规划问题,：,从满足（,2,）、（,3,）的方程组中找出一个解使目标函数（,1,）达到最大值。,2,、,可行解,：,所有可行解的集合。,可行域,：,满足约束条件（,2,）、（,3,）的解。,记做,最优解,：,使目标函数达到最大值的可行解。,（,1,）,基,：设,A,为线性规划问题约束条件的,m,n,系数矩阵,（,m0,，,有如下结论：,(1),若对所有,j,m+1,，有,j,0,，则,z,（,1,）,z,（,0,）,，即,z,（,0,）,为最优函数值，,X,（,0,）,为,唯一最优解,；,(2),若对所有,j m+1,，,有,j,0,，且,存在某个非基变量的检验数,k,=,0,，则将,P,k,作为新的基向量得出新的基可行解,X,（,1满足,z,（,1,）,=,z,（,0,）,，故,z,（,1,）,也,为最优函数值，从而,X,（,1,）,也,为最优解，,X,（,0,）,、,X,（,1,）,连线上所有点均为最优解，因此该线性规划模型具有,无穷多最优解,；,(3),若存在某个,j,0,，但对应的第,j,列系数全非正，即,a,ij,0,，则当,+,时，有,z,（,1,）,+,，,该线性规划模型具有,无界解,。,1.4,单纯形法的计算步骤,1,、前提：标准化的线性规划问题的系数矩阵含有单位子矩阵。,不妨假设,A,中前,m,列对应的子矩阵是单位矩阵，取其为基,B,，得到初始基可行解,m+,3,行,n+,4,列,第,1,行：价值行,c,j,第,2,行：变量行,x,j,最后一,行：检验数行,j,第,1,列：基价值列,C,B,第,2,列,：基变量列,X,B,第,3,列,：基解列,b,最后一,列：,比值,列,主体：系数矩阵,A,m,n,2,、单纯形表的结构,3,、初始单纯形表：含初始基可行解的单纯形表,最优单纯形表：含最优解的单纯形表,4,、单纯形法（,Simplex Method,）：,利用单纯形表求解线性规划问题的方法。,5,、单纯形法的计算步骤,(1),化,L.P.,问题为标准形式,建立初始单纯形表；,(3),计算,以,a,lk,为主元素,(,简称主元，用,表示,),，进行线性方程组 的初等行变换，将主元列,P,k,化为单位向量得到新的单纯形表，转入,(2),。,（最大正检验数决定换入变量）,（最小比值,决定换出变量,）,例：用单纯形法求解下列线性规划问题,.,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t,.,解：先标准化,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0,4 0 0 1 0,0 5 0 0 1,再列初始单纯形表：,6,-,3,2 3 0 0 0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0 6,4 0 0 1 0 -,0 5 0 0 1 3,2 3 0 0 0,以,5,为主元进行初等行变换,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,3,X,2,6,16,3,2 0 1 0 -2/5 3,4 0 0 1 0 4,0 1 0 0 1/5 -,2 0 0 0 -3/5,x,1,为换入变量,下面开始单纯形法迭代：,x,5,为换出变量,x,2,为换入变量,以,2,为主元进行初等行变换,x,3,为换出变量,主元化为,1,，主元列的其他元素化为,0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,4,3,X,2,3,4,3,1 0,0 -1/5,0 0 -2 1 4/5,0 1 0 0 1/5,0 0 -1 0 -1/5,此时得到唯一最优解,X,*,=(3,3),T,Z,max,=15,。,6,、单纯形法中存在的问题,（,1,）存在两个以上的最大正检验数。,任取一个最大正检验数对应的变量作为换入变量。,（,2,）,出现两个以上相同的最小值。,任取一个最小,对应的变量作为换出变量。,此时,L.P.,问题出现退化现象。,练习 用单纯形法求解下列线性规划问题,解：先标准化,2 1 0 0,5,4,x,3,x,4,0,0,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,24,15,3,5,1,0,6,2,0,1,0 0,x,3,x,1,0,2,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,4,3,0,1,4,1,0,1/3,-1/2,1/6,1/3,-1/3,3/4,12,0 0 -1/12 -7/24,x,2,x,1,1,2,x,1,x,2,x,3,x,4,b,x,B,c,B,2 1 0 0,c,j,15/4,3/4,0,1,1/4,-1/8,1,0,-1/12,5/24,唯一最优解,5-1,人工变量法（大,M,法）,1.5,单纯形法的进一步讨论,例：用单纯形法求解下列线性规划问题。,解：先标准化为,系数矩阵,但是,A,中没有单位矩阵，在,A,中人为的增加两列,此时,对应的约束方程组为,：,该问题新增加了两个变量：,x,4,x,5,（称为人工变量）,A,有单位子矩阵，选择这个单位矩阵作为基（称为人工基）。,为使,必须保证在可行解中人工变量,x,4,=x,5,=,0,，,故令,x,4,，,x,5,在目标函数中的系数为,M,（其中,M,表示任意大的正数），,这种添加人工变量求解,LP,的方法称为,人工变量法,计算过程中出现了,M,，这种方法也称为,大,M,法,等价于,于是，这个线性规划问题转化为：,以下可用单纯形法继续求解。,C,j,x,1,x,2,x,3,x,4,X,B,b,C,B,1 1 -1 1 0 1 2 0 0 1,-2 -3 0 -,M,-,M,34,x,4,x,5,-,M,-M,c,j,-,z,j,-2+2M,-3+3M,-M,0,3/1=3,4/2=2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x,4,x,2,12,c,j,-,z,j,-1/2+M/2,0,-,M,0,3/2-3M/2,-,M-,3,24,1 0 -2 2 -1 0 1 1 -1 1,x,1,x,2,21,c,j,-,z,j,0 0 -1 1-M,1-M,-2-3,x,5,0,唯一最优解,故,z,min,=,7,注意：此时人工变量,x,4,=,x,5,=0,说明：,若表中所有,j,0,，但存在非,0,的人工变量，则该模型,无可行解,。,采用大,M,法求解线性规划模型时，如果模型中各个系数与,M,的值非常接近或相差很大，若用手工计算不会出现问题。但是若利用计算机求解，则容易引起混淆，使得机器判断出错，从而使大,M,法失效。,在这种情况下，可采用下面的两阶段法进行计算。,5-2,两阶段法,(,将,L.P.,问题分成两个阶段来考虑,),第一阶段,:,判断原,L.P.,问题是否存在可行解。,给原,L.P.,问题加入人工变量，并构造仅含人工变量的目标函数,w,（,人工变量在,w,中的系数一般取为,1,）并求,w,的最小值；然后用单纯形法求解。若求得,w,min,=0,，则该问题有可行解，进入第二阶段，否则该问题无可行解，结束。,第二阶段：将第,一,阶段得到的最终表去掉人工变量，并将目标函数还原为原,L.P.,问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。,例：用两阶段法求解下列线性规划问题。,标准化,引入人工变量,z,(1),第一阶段，构造判断是否存在可行解的模型：,用单纯形法求解这个问题，先标准化为；,C,j,x,1,x,2,x,3,x,4,X,B,b,C,B,1 1 -1 1 0 1 2 0 0 1,0 0 0 -,1,-,1,34,x,4,x,5,-,1,-1,c,j,-,z,j,2,3,-1,0,3/1=3,4/2=2,1/2 0 -1 1 -1/2 1/2 1 0 0 1/2,x,4,x,2,12,c,j,-,z,j,1/2,0,-1,0,-3/2,-1,0,24,1 0 -2 2 -1 0 1 1 -1 1,x,1,x,2,21,c,j,-,z,j,0 0 0 -1,-1,0 0,x,5,0,最优解,本问题有可行解，进入第二阶段,(2),第二阶段,先在第一阶段的最终单纯形表去掉人工变量，再还原原目标函数，即,max z,=-2,x,1,-3,x,2,+0,x,3,，,继续迭代：,C,j,x,1,x,2,x,3,X,B,b,C,B,1 0 -2 0 1 1,-2 -3 0,21,x,1,x,2,-2,-3,c,j,-,z,j,0,0,-1,唯一最优解,故,z,min,=,7,注意：两阶段法中不再出现大,M,，但需要解两个线性规划问题，要注意目标函数系数的变化。,5-3,关于解的判别,用最终单纯形表判断线性规划问题解的类型：,解的类型,最终表的特征,无可行解,有非,0,的人工变量,有,可,行,解,唯一最优解,无,非,0,的人,工变量，非基变量的检验数全为负数,无穷多最优解,无非,0,的人工,变量，非基变量的检验数全非正，且有某个非基变量的检验数为,0,无界解,无非,0,的,人工变量，有某个非基变量的检验数为正数，但该变量对应的系数全为非正数,已知线性规划问题形如：,5-4,单纯形法计算的向量、矩阵描述,引入松弛变量,x,s,记,X=,(,X,B,X,N,X,S,),T,其中，,X,S,为松弛变量，在初始表中是基变量；,X,B,为,最终表中基变量；,X,N,表示,既不是初始表的基变量又不是最终表的基变量。,注意：,X,S,和,X,B,允许有公共变量。,（,2,）,A=,(,B,N,I,),B,N,I,分别为,X,B,、,X,N,、,X,S,在初始表中,对应,的矩阵。,则（,1,）,C=,(C,B,C,N,0),C,B,C,N,0,分别为,X,B,、,X,N,、,X,S,在目标函数中的系数。,（,3,）,A,=,(,I,N,B,-1,),I,N,B,-1,分别为,X,B,、,X,N,、,X,S,在最终表中,对应,的矩阵。,约束方程组两端同时左乘,B,-1,，则可得如下表达式：,初始单纯形表,最终单纯形表,用单纯形表表示如下：,X,S,b,B N I,X,B,b,I N,B,-1,初始表,X,B,X,N,X,S,c,j,-,z,j,0,0,N,S,=,（,-y,1,-y,2,-,y,m,）,=-Y,T,最终表,X,B,X,N,X,S,c,j,-,z,j,B,N,0,0,比较得：,b,=B,-1,b,N,=B,-1,N,或者,P,jB,-1,P,j,S,=-C,B,B,-1,=-Y,T,N,=C,N,-C,B,B,-1,N,=C,N,-Y,T,N,或者,j,=C,j,-C,B,B,-1,P,j,其中,B,-1,为初始表中基变量在最终表对应的系数矩阵，,B,为最终表中基变量在初始表对应的系数矩阵。,例：用单纯形法求解下列线性规划问题,.,max,z,=2,x,1,+3,x,2,2,x,1,+2,x,2,12,4,x,1,16,5,x,2,15,x,1,0,，,x,2,0,s.t,.,解：先标准化,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,0,X,3,0,X,4,0,X,5,12,16,15,2 2 1 0 0,4 0 0 1 0,0 5 0 0 1,得到初始单纯形表：,6,-,3,2 3 0 0 0,C,j,2 3 0 0 0,C,B,X,B,b,X,1,X,2,X,3,X,4,X,5,2,X,1,0,X,4,3,X,2,3,4,3,1 0,0 -1/5,0 0 -2 1 4/5,0 1 0 0 1/5,0 0 -1 0 -1/5,最终单纯形表：,X,4,0,1,0,X,4,0,1,0,可以验证：,三要素,决策变量,约束条件,目标函数,两,个,三个,以上,x,j,0,x,j,无,约束,x,j,0,b,i,0,b,i,0,=,maxZ,minZ,x,s,x,a,标准化,图解法、,单纯形法,单纯形法,不,处,理,令,x,j,=,x,j,-,x,j,x,j,0,x,j,0,令,x,j,=-,x,j,不,处,理,约束条件两端同乘以,-1,加松弛变量,x,s,加人工变量,x,a,减,去,x,s,加入,x,a,不,处,理,令,z,=-,Z,0,-M,根据上表可以列出初始单纯形表,5-5,单纯形法小结,个数,取值限制,右端常数,约束方向,要求,系数,列初始表,1.7,应用举例,一般而言，一个经济、管理问题要满足以下条件，才能建立线性规划模型：,.,需要求解问题的目标能用数值指标来反映，且能用线性函数来描述目标的要求；,.,为达到这个目标存在多种方案；,.,要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式来描述。,（一）、混合配料问题,例：某糖果厂用原料,A,、,B,、,C,加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中各种原料的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如下表所示。问该厂每月生产这三种牌号糖果各多少千克，能使该厂获利最大。请建立这个问题的线性规划模型。,甲,乙,丙,原料成本（元,/kg,）,每月限制用量（,kg,）,A,B,C,60,20,30,50,60,2.00,1.50,1.00,2000,2500,1200,加工费（元,/kg,）,0.50,0.40,0.30,售价（元,/kg,）,3.40,2.85,2.25,解：,用,i,=1,2,3,表示原料,A,、,B,、,C,；,用,j,=1,2,3,表示糖果甲、乙、丙；,设,x,ij,为生产第,j,种糖果使用的第,i,种原料的质量，,则该问题的数学模型为：,s.t,.,原料供应限制,含量要求条件,用单纯形法求得：,即每月生产甲糖果,kg,，乙糖果,kg,，不生产丙糖果，可获得最大利润为,5450,元。,（二）、投资项目组合问题,例：兴安公司有一笔,30,万元的资金，考虑今后三年内用于下列项目的投资：,1,、三年内每年年初均可投资，每年获利为投资额的,20%,，其本利可一起用于下一年投资；,2,、只允许第一年初投入，于第二年末收回，本利合计为投资额的,150%,但此类投资限额不超过,15,万元；,3,、允许于第二年初投入，于第三年末收回，本利合计为投资额的,160%,，但限额投资,20,万元；,4,、允许于第三年初投入，年末收回，可获利,40%,，但限额为,10,万元,.,试为该公司确立一个使第三年末本利和最大的投资组合方案，,请建立这个问题的线性规划模型。,解：用,x,ij,表示第,i,年初投放到第,j,个项目的资金数，则建立如下线性规划模型：,1,2,3,4,一,二,三,第,i,年初,投入第,j,个项目,用单纯形法求得：,1,2,3,4,一,166666.7,133333.3,二,0,200000,三,100000,100000,第三年末本利和,=580000,综上投资组合方案如下：,