0绪论1线性规划

,单击此处编辑母版标题样式,李明超 副教授,运 筹 学,Operations Research,课程说明,1,、教材与参考书,教材,钱颂迪主编，运筹学,(,第三,/,四版,),，清华大学出版社，,2005/2012,参考书,胡运权主编，运筹学教程,(,第三版,),，清华大学出版社，,2007,Hillier, F.S. Introduction to Operations Research, 8e. McGraw-Hill, 2005,2,、先修课程,微积分、,线性代数,、概率论,3,、学习与考试方式,学习,课堂听课、课下习题、,案例分析、程序编制,课程资料,本科教学课程信息运筹学,课程资料,考试,闭卷考试,+,平时成绩,课程说明,运筹学讨论学习：,QQ,群：,305522490,/,运筹学,2014,需要验证：,所在班级,+,姓名,（例如：水电,1,班柴朝政、,水港,2,班闫小龙）,进群后要求将,群名片修改为：班级,+,姓名,。,（,例如：,水,1,柴,朝政,、港,2,闫,小龙,）,课程说明,4,、课程内容（,32,学时）,课程说明,绪论（,1,学时）,第一章 线性规划（,6,学时）,第二章 对偶理论与灵敏度分析（,4,学时）,第三章 整数规划（,2,学时）,第四章 动态规划,（,4,学时）,第五章 图与网络分析,（,6,学时）,第六章 排队论（,4,学时）,第七章 决策论（,2,学时）,复习（,1,学时）,考试（,2,学时）,绪论,Introduction,运 筹 学,Operations Research,绪论,一、运筹学的产生与发展,运筹学的萌芽,可以追朔到,20,世纪初期，但主要产生于,20,世纪,40,年代中期的二战期间。,创建阶段（,19451951,）,1947年美国Dantzig提出了,单纯形法,1948,年英国,运筹学会（,OR Club,）,成立,1950,年英国伯明翰大学正式开设,运筹学课程,运筹学季刊,在英国创刊,1951,年美国,Morse,等著的,运筹学方法,一书出版,绪论,绪论,成长阶段（,19521959,）,计算机技术,的发展促进了运筹学的推广应用,美国已有约半数的大公司应用运筹学,解决管理运营中的生产计划,、,资源分配,等问题,更多,学会和刊物,的出现：,10,个国家、,6,种刊物,1957,年英国牛津大学召开第一次,国际运筹学会议,1959,年成立,国际运筹学联合会,（,International Federation of Operational Research,Societies,，,IFORS,，,http,:/,）,绪论,普及发展阶段（,1960,）,进一步细分为各个分支：线性规划、动态规划,专业学术团体、期刊、书籍迅速增多,运筹学课程更多地被纳入教学计划,运筹学的广泛实际背景促使其不断发展并在经济管理、系统工程和工程建设等多领域中发挥着令人瞩目的重要作用。,绪论,我国运筹学的发展,2,0,世纪,50年代中期由,钱学森,等引入，1957年正式定名为,运筹学,（,“,夫运筹帷幄之中，决胜千里之外”,史记,）,。,1970年后，在,华罗庚,的直接指导下，全国范围内推广统筹法和优选法，并取得了卓著成效。,1980年,，,中国运筹学会,于成立，1982年作为正式成员加入了国际运筹学联合会（IFORS）,。,绪论,二、运筹学的特性,运筹学是一门以,定量方法,为,管理决策,提供科学依据的,应用科学,。,基本特性,以管理决策为基点,以科学方法论为依据,以系统观点为指导,以数学模型为主要工具,绪论,三、运筹学的应用与软件,运筹学在水利水电和港口工程中的应用,土石方调配,水文计算,混凝土浇筑,施工场地布置,场内交通分析,水库调度,绪论,运筹学常用软件,MS Excel Solver,LINDO,、,LINGO,CPLEX,运筹学软件包,Matlab,第一章 线性规划,Linear Programming,运 筹 学,Operations Research,1.1,线性规划模型,1.2,图解法,1.3,单纯形法,1.1,线性规划模型,一、线性规划问题,第一章 线性规划,在生产和经营等管理工作中，需要经常进行计划或规划，共同需要解决的问题可归结为：,在现有各项资源条件的限制下，如何确定相应的方案，合理利用资源，使预期目标达到最优。,第一章 线性规划,例,1,某工厂要生产甲、乙两种产品，需消耗,A,、,B,、,C,三种资源。现将有关数据列表如下：,试拟订使总,利润,最大的生产计划方案,。,第一章 线性规划,解：,设安排甲、乙产量分别为,x,1,、,x,2,，总收入为,z,，则模型为：,第一章 线性规划,例,2,某施工工地有,3,个不同土区，按工期要求和碾压条件所限，各土区所需土料和装运费情况如下表：,求,使,装运费用,最,节省,的,土方调配,方案,。,第一章 线性规划,解：设,3,个土区每天取土次数分别为,x,1,、,x,2,、,x,3,，总费用为,z,，则模型为：,第一章 线性规划,例,3,某,工厂要为生产产品需购买材料来获取,A、B、C、D四种,物质，市场上可选择的材料有,M、N两种。有关数据如下,表：,材料,售价,（元,/kg,）,每,kg,含物质,A B C D,M,10,0.1 0 0.1 0.2,N,4,0 0.1 0.2 0.1,每件产品需要量,0.4 0.6 2.0 1.7,试决定买M与N二种,材料,料各多少,k,g,而使支出的总费用为最少？,第一章 线性规划,解：设,M,、,N,材料分别购买,x,1,、,x,2,（,kg,）,，总费用为,z,，则模型为：,第一章 线性规划,练习,1,A,、,B,两水电站均属调节电站， 同时从,C,水库引水发电，枯水期平均流量,0.52 m,3,/s,，按规定,A,、,B,两站厂用电量不得超过,0.9,万,kWh,，其它有关指标如下：,项目,单位,A,电站,B,电站,装机,kW,4000,400,单位千瓦耗水,m,3,/s,0.00024,0.0004,厂用电率,%,0.75,0.60,可调小时,h/,月,600,600,求枯水期上网电量,最大的,电站出力调度,方案,。,第一章 线性规划,解：设,A,、,B,电站出力分别为,x,1,、,x,2,（,kW,）,，总上网电量为,z,，则模型为：,第一章 线性规划,练习,2,某港口,某年生产经营指标如下表,。,该年吞吐量不超过,880,万吨，其中：煤炭吞吐量至少,630,万吨；木材需求在,10,万吨以上，二码头通过能力难以突破,32,万吨；矿石吞吐量至少,130,万吨，化肥货源预计在,45,万吨以下，三码头实际通过能力难以突破,300,万吨。,以码头通过能力和货源预测为约束条件求得最佳货种搭配，以取得最大营业收入,。,码头,一码头,二码头,三码头,货物,煤炭,木材,石油,矿石,化肥,其他,单位收入,(,万元,/,万吨,),1.8,5,7.3,2,20.3,18.5,第一章 线性规划,第一章 线性规划,二、线性规划数学模型,一般形式如下（以,max,型、,约束为例,）：,第一章 线性规划,矩阵形式：,X,决策变量向量,C,价格系数向量,A,技术系数矩阵,b,资源限制向量,？为什么将,A,称为技术系数矩阵？,技术系数：生产一定量某种产品所需要的各种生产要素的配合比例。,第一章 线性规划,第一章 线性规划,线性规划模型的一个基本特点：,目标和约束均为变量的,线性,表达式,若模型中出现非线性表达式，如：,则不属于线性规划，而是非线性规划。,1.2,图解法,第一章 线性规划,图解法是用画图的方式求解线性规划的一种方法。它虽然只能,用于解二维（两个变量）的问题,，但其主要作用并不在于求解，而是在于能够,直观地说明线性规划解的一些重要性质,。,分三步进行：,第一章 线性规划,1,、作约束的图形,先做,非负约束,的图形；,再做,资源约束,的图形。,以例,1,为例，其约束为：,x,1,x,2,0,3,4,4,8,可行域,第一章 线性规划,2,、作目标的图形,对于目标函数：,x,2,x,1,0,3,4,4,8,任给两个不同的,z,值，可作相应的两条直线，用虚线表示。,z,6,z,12,可以看出,z,增大的方向。,第一章 线性规划,3,、求最优解,将目标直线,向使目标优化的方向,移，直至,可行域的边界,为止，这时其与可行域的“切”点,X,*,即最优解。,例,1,中的最优解：,X,*,（,4,，,2,）,T,x,1,x,2,0,3,4,4,8,X,*,第一章 线性规划,由图解法的结果得到例,1,的最优解，即：,x,1,4,，,x,2,2,。,将其代入目标函数求得相应的最优目标值：,z,14,。,说明该厂最优生产计划方案为：,当生产甲产品,4,件，乙产品,2,件时，可获得最大的利润,14,元。,第一章 线性规划,练习,用图解法求解下列线性规划问题：,x,1,0,0.5,1,x,2,1,1.5,0.375,X,*,（,0.5,，,0,）,T,，,z,*=3,X,*,第一章 线性规划,思考,线性规划的可行域是什么,形状？,多边形，而且是“凸”形的,多边形。,最优解在什么位置获得？,在边界，而且是在某个顶,点获得。,第一章 线性规划,由图解法得到线性规划解的一些特性：,（,1,）线性规划的约束集（即可行域）是一个凸多面体。,凸多面体是凸集的一种,，所谓凸集是指：,集中任两点的连线仍属此集,。试判断下面的图形是否凸集：,凸集中的“,极点,”，又称,顶点或角点,，是指它属于凸集，但不能表示成,集中某二点连线的内点,，,如多边形顶点。,第一章 线性规划,（,2,）线性规划的最优解（若存在的话）必能在可行域的顶点获得。,由图解法可知，只有当目标直线平移到边界时，才能使目标,z,达到最大限度的优化。,问题：本性质有何重要意义？,第一章 线性规划,（,3,）线性规划解的几种情形,a,）唯一解,c,）无可行解,注：出现,c,）、,d,）情况时，建模有问题。,b,）无穷多最优解（多重最优解）,d,）无界解（无有限最优解）,矛盾的,约束条件,缺乏必要的,约束条件,1.3,单纯形法,第一章 线性规划,单纯形法是求解线性规划的主要算法，,1947,年由,美国斯坦福大学教授丹捷格,（,G.B.Dantzig,）提出。,尽管在其后的几十年中，又有一些算法问世，但单纯形法以其,简单实用,的特色始终保持着绝对的“市场”占有率。,第一章 线性规划,一、,预备知识,1,、线性规划问题的标准型式,标准型式特点：,max,型、等式约束、非负约束,A,m,n,的秩为,m,(,m,n,),，,b,0,第一章 线性规划,标准模型是基于,理性决策的假设,前提得到的。,什么是理性决策（,Making Rational Decisions,）？,人是,目标最大化,的经济动物，即决策者是理性的（好事越多越好，坏事越少越好）；,每个可行决策方案可能产生的,结果,，或者至少是结果的概率和收益都,已知,；,决策者有着明确的偏好顺序，能够对,结果进行排序,（从最好到最坏）。,第一章 线性规划,线性规划问题的一般型式如何转化为标准型式？,引入符号和变量,（,1,）目标函数：,min,型,max,型，引入负号,（,2,）约束条件：不等式，引入松弛变量或剩余变量,x,3,称为松弛变量。,问：其实际意义是什么？,第一章 线性规划,（,3,）对于取值无约束的变量,x,k,：,（,4,）对于右端项,b,i, 0,的情况：,等式两端同时乘以,1,即可。,（,5,）对于,x,i,0,，则转入下一步。,问题：,计算上一步所求得,X,0,的每个,x,j,的检验数，,并判断,X,0,是否为最优解？,第一章 线性规划,3,、寻找更优的基本可行解,由于基本可行解与基对应，即寻找一个新的基可行解，相当于从上一个基,B,0,变换为下一个新的基,B,1,，因此，本步骤也称为,基变换,。,第一章 线性规划,寻找方法：,i,称为检验比。,问题：,接上一步，确定进基、出基，换基计算下一个基本可行解、再检验，直至最优。,当模型规模较大时，计算量很大。,事实上，单纯形法的实现是在单纯形表上完成的。,第一章 线性规划,线性规划解的相关概念,可行域、可行解、最优解、最优值,基、可行基,基向量、基变量、非基变量,基解、基可行解,第一章 线性规划,【,例,6】,令,P,= (,P,3,P,4,P,5,) =,P,3, P,4, P,5,是三个,基向量,与,P,3, P,4, P,5,相对应的三个变量,x,3, x,4, x,5,是,基变量,X,B,= ,x,3, x,4, x,5,T,X,N,= ,x,1, x,2,T,得到,X,B,= ,x,3, x,4, x,5,T,= 8, 16, 12,T,其也是,基可行解,此时，,z,= 0,P,是一个,基,(1),令,X,N,= ,x,1, x,2,T,=,0, 0,T,x,1, x,2,是,非基变量,对应的,可行基,为,P,= (,P,3,P,4,P,5,),则,为,基解,第一章 线性规划,P,= (,P,3,P,4,P,2,) =,X,B, = ,x,3, x,4, x,2,T,X,N, = ,x,1, x,5,T,得到,X,B, = ,x,3, x,4, x,2,T,= 8, 10, 3,T,其也是,基可行解,此时，,z,= 15,x,2,进基,，,x,5,出基,(2),令,X,N, = ,x,1, x,5,T,=,0, 0,T,x,1, x,5,是,非基变量,对应的,可行基,为,P,= (,P,3,P,4,P,2,),则,为,基解,第一章 线性规划,用,P,2,替换,P,5,，则,P,3, P,4, P,2,是三个,基向量,P,是一个,基,则,为,最优解,，,z,=15,为,最优值,第一章 线性规划,三、单纯形表,单纯形表是基于单纯形法的,计算步骤设计的计算格式,，是单纯形法的具体实现,。,过程,：,单纯形表的主体内容是：,B,-1,(,b A,),，即,第一章 线性规划,问题,：,（,1,）第一张表的,B,-1,=,？,（,2,）检验数的公式是什么？,（,3,）,B,-1,P,j,在表格哪里？,单纯形表的结构形式：,第一章 线性规划,例,7,采用单纯形表求解例,1,的线性规划问题。,初始单纯形表：,初始基本可行解,X,0,=,？,z,0,=,？,2,3,0,0,0,4,3,4,第一章 线性规划,以,4,为主元素进行初等行变换：,新的基本可行解,X,1,=,？,z,1,=,？,1,2,0,0,0,3/4,2,4,3,x,2,1/2,0,1/4,0,0,1,第一章 线性规划,以,1,为主元素进行初等行变换：,新的基本可行解,X,2,=,？,z,2,=,？,0,0,2,0,1/4,4,12,2,x,1,2,第一章 线性规划,以,2,为主元素进行初等行变换：,最优解,X*,=,？,z*,=,？,0,0,3/2,1/8,0,0,x,5,第一章 线性规划,单纯形表中的信息分析：,（,1,）每一列的含义；,（,2,）,表中的,B,和,B,-1,的查找；,（,3,）终表分析,最优基,B*,和,(B*),-1,的查找。,第一章 线性规划,四、人工变量法（大,M,法）,例,8,采用单纯形法求解下列线性规划问题。,第一章 线性规划,问题：,方法：,增加人工变量,X,R,=,（,x,n+1,，,，,x,n+m,）,T,X,R,在目标函数中的系数为,M,（,M,为充分大正数）,。,于是原问题化为：,求解：单纯形法,最优基变量中不含,X,R,，则所得解的前,n,个分量即为,X*,，否则无解。,A,中不含,I,。,第一章 线性规划,解：,增加人工变量,x,5,、,x,6,，,模型标准化为,第一章 线性规划,单纯形表：,5,7M,3,5M,2,4M,4,10M,0,0,5/4,5,8,5/2,4/3M,5/2,15/4M,3/2,11/4M,0,-1/2-5/4M,0,10,2,15/4,第一章 线性规划,第一章 线性规划,五、单纯形法总结,（,1,）,Min,型单纯形表与,Max,型的区别仅在于：,令,k,=min,j,0,的,x,k,进基，当所有,j,0,时最优,。,（,2,）解的几种情况及其在单纯形表上的体现（,Max,型）,唯一,最优解,j,0,非基,0,但,B,-1,P,k, 0,无可行解,用大,M,法求解，最优基中含有,X,R,退化解,最优解中某基变量为,0,线性规划与单纯形法小结,线性规划问题建模,图解法,最优解必在顶点,模型标准型式,基本可行解,单纯形法,单纯形表,