运筹学(第3版)全套课件电子教案板.ppt

第,*,页,第,*,页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,第,*,页,第,*,页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,图,第,*,页,第,*,页,第,*,页,第,*,页,运 筹 帷 幄 之 中,决 胜 千 里 之 外,运筹学,（第三版）,第,1,章 绪论,Introduction,运筹学的概况,运筹学的数学,模型,教学计划,与方法,考试与要求,参考文献,第,1,章,绪论,运筹学的由来与发展,运筹学的性质与特点,运筹学的主要内容,运筹学的发展趋势,运筹学的学科地位,1.1,运筹学概况,名称的由来,Operation Research,运筹帷幄“史记”,运作研究,发展历程,运筹学的由来与发展,二战以前,萌芽,二战期间,产生,五六十年代,发展,七八十年代,成熟,引入数学方法解决实际问题,-,定性与定量方法结合,系统与整体性,-,从全局考察问题,应用性,-,源于实践、为了实践、服务于实践,交叉学科,-,涉及经济、管理、数学、工程和系统等 多学科,开放性,-,不断产生新的问题和学科分支,多分支,-,问题的复杂和多样性,运筹学的性质与特点,线性规划,数,学,规,划,非线性规划,整数规划,动态规划,学,科,内,容,多目标规划,双层规划,组,合,优,化,组合优化和最优计数问题,图论和网络优化,排序问题,统筹图,随,机,优,化,对策论,排队论,存储论,投入产出分析,可靠性分析,运筹学的主要内容,运筹学的理论研究将会得到进一步系统地、深入地发展。,运筹学向一些新的研究领域发展。,运筹学分散融化于其他学科，并结合其它学科一起发展。,运筹学沿着原有的学科向前发展。,运筹学中建立的模型将日益受到重视。,运筹学的发展将进一步依赖于计算机的应用和发展。,运筹学的发展趋势,1,在数学学科中的地位,运筹数学,1,在系统科学中的地位,系统工程,1,在管理科学中的地位,管理与运筹学,1,与经济学的关系,问题与方法,1,与工程科学的关系,方法与应用,1,与计算机科学的关系,核心算法与工具,基础理论,应用理论,应用技术,运筹学,运筹学的学科地位,模型要素,变量,可,控因素,目标,优化,的动力和依据,约束,内,部条件和外部约束,研究内容,建模,概念,最优性条件,算法,灵敏度分析,1.2,运筹学的数学模型,实例,问,题,1.,线性规划模型,分,析,线性规划模型,线性规划模型,线性规划带来巨额财富,与其他传统数学学门相比较,线性规划算是非常年轻却非常实用的一门应用数学。根据八十年代的一项调查,在美国财,富,杂志(Fortune)名列前五百名的大公司中,百分八十五均曾应用线性规划的方法来协助公司的营运。由此可见线性规划应用面的宽广与普及。,什么是,线性规,划呢？,根据一般的说法,线性规划问题是由现在美国史丹褔大学任教的,G.B.Dantzig,教授在,1947,年前后孕育出来的。那个时候他,担任美国空军的数学顾问,负责发展一套机械式的方法来做兵力调遣,人员训练,以及后勤补给这些计划方案。由于这类问题牵,涉很广也很复杂,所以,Dantzig,博士先考虑最简单的线性结构,将有关的函数一律简化成线性形式来处理。其结果便在,1948,年以,线性结构的规划,(Programming in Linear Structure),的标题发表。至于线性规划这个名称,则是另一位名家,T.C.Koop-,mans,和,Dantzig,两人于,1948,年夏天在美国加州圣塔摩尼加,(Santa Monica),海滩散步时拟定的。在,1947,到,1949,两年间,线性规划里的一些重要观念,包括最有名的单形法,(Simplex method),都陆续见诸于世。而且从,1947,年开始,T.C.Koopmans,便明确指出线性规划可以做为传统经济分析的利器。,线性规划带来巨额财富,这儿特别要注意的是线性规划的理论基础绝不是一夕生成。早在,1826,年左右法国的大数学家傅立叶便研究过如何解决一组联立线性不等式的问题。这以后还有不少的数学家做过相关的研究工作。到了,1939,年,W.Karush,在芝加哥大学的硕士论文更提出在有限维空间里满足不等式约束的函数其最优化的条件,(optimality conditions),。在同一年里,苏联的,L.V.Kantorovich,更提出一些很特殊的线性规划模式来做简单的生产计划。他甚至还有一套简化的方法来求解呢,!,不幸的是,Kantorovich,的工作始终未为苏联之外的世界所知,一直到了,Dantzig,建立起完整的线性规划理论之后数十年方为世人所知。在,1950,和,1960,年代,线性规划的内容愈变愈丰富,更有许多成功的实用案例,所以愈来愈受世人瞩目。到了,1975,年,瑞典皇家科学院决定将当年的诺贝尔经济奖颁发给前面提到的,L.V.Kantorovich,和,T.C.Koopmans,以表彰他们在资源最佳分配理论的贡献。由于这项最佳分配是藉由线性规划模式来达成,所以线性规划便成了万众瞩目的焦点。,线性规划带来巨额财富,这里我们要特别强调一下单纯形算法的复杂性问题。给定一个问题，电脑最多需要多少次运算才能解决这个问题呢？当然这个运算次数与问题的大小有关。问题越大，变量越多，则所需的运算次数也越多。这种运算次数对问题大小的依赖关系，就可以用来判断一种算法的好与坏。好的算法，其运算次数的增加对问题大小不太敏感。反之，坏的算法，当问题稍微变大一点，运算次数就增加很多，因此就不能解决大的问题。美国华盛顿大学的两位教授在,1971,年得出结论：,单纯形法是一种坏算法,。这在当时的理论界引起了轰动。原来我们使用了如此之久的单纯形算法，竟是一个坏算法！,1979,年,线性规划再次成了报章杂志的头条新闻。这次是因为一位苏联数学家,L.G.Khachian,他利用,N.Z.Shor,D.B.Yudin,以及,A.S.Nemirovskii,的椭球法,(ellipsoid method),概念印证出线性规划问题可在多项式时间内求得解答。,线性规划带来巨额财富,从纯理论的观点而言,Khachian,的椭球法在最恶劣的情况下所需要的计算量要比单形法增长的缓慢。所以有希望用之解决超大型的线性规划问题,包括全球资源的最佳分配在内。这也就是华尔街日报,(Wall Street Journal),将椭球法的发现列为头条新闻的重要原因。不幸的是理论归于理论,在实际计算上,椭球法的一般表现反倒不如传统线性规划,(Linear Programming),的单形法来得有效。于是这方面的学者专家重新构想是否能设计出一套解法无论在理论上和实际计算上均能超越单形法,?,这个问题的答案到了,1984,年由一位美国电话电报公司贝尔实验室的印度裔科学家,N.Karmarkar,揭晓。他设计出一项内点法来解线性规划问题,不但理论上较单形法为优,而且经由实际验证适合解决超大型的问题。从此之后,内点法的研究在最近二十多年来蔚为一时风潮,不断有推陈出新的结果。,线性规划带来巨额财富,不过将卡马卡算法商业化的企图，却遭受了重大失败。贝尔实验室在卡马卡指导下耗资亿万发展的商用软件，因为售价昂贵，只卖出了几套，买方都是军事单位。这样的买主虽然有钱，但实在不多。反观单纯形法，因为从方法到细节都公开，许多大大小小的公司，纷纷用它来制造软件，售价低廉。所以从家庭、课堂到公司，在众多电脑上运行的仍然是单纯形法。在解决中小问题方面，单纯形法非常有效而可靠；在大问题方面，通常也不算太慢。所以它至今仍是最常用的解线性规划的方法。随著强有力的算法之发展与应用，线性规划所能解决的问题也越来越多。在波斯湾战争期间，美国军方利用线性规划，有效地解决了部队给养和武器调运问题，对促进战争的胜利，起了关键的作用。难怪人们说，因为使用炸药，第一次世界大战可说是化学的战争；因为使用原子弹，第二次世界大战可说是物理的战争；因为使用线性规划，波斯湾战争可称为数学的战争。在历史上，没有哪种数学方法，可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史的进程发生如此直接的影响。,线性规划带来巨额财富,第,2,章 线性规划,2.1,线性规划问题,2.2,可行区域与基本可行解,2.3,单纯形方法,2.4,初始解,和,单纯形方法的几点说明,2.5,对偶性及对偶单纯形法,2.6,灵敏度分析,计算软件,案例分析,主,要,内,容,2.1 节 线性规划问题,线性规划实例,生产计划问题,运输问题,线性规划模型,一般形式,规范形式,标准形式,形式转换,概念,某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划。,单位产品所需原料数量（公斤）,产品,Q1,产品,Q2,产品,Q3,原料可用量,（公斤/日）,原料,P1,2,3,0,1500,原料,P2,0,2,4,800,原料,P3,3,2,5,2000,单位产品的利润（千元）,3,5,4,例2.1.1 生产计划问题,问 题 分 析,模 型,计 算 结 果,例2.1.2 运 输 问 题,一般运输问题的数学模型？,2.线性规划模型,目标函数,约束条件,一,般,形,式,矩阵,为,系数矩阵(或约束矩阵),。,其他概念：,2.线性规划模型,标准形式：,2.线性规划模型,规范形式：,2.线性规划模型,显然，标准形式和规范形式是一般形式的特殊情形，下面我们来把一般形式转换成标准形式和规范形式，从而使得这三种形式是等价的。,变量转换,2.线性规划模型,（1）一般形式 规范形式,等式变不等式,变量转换,2.线性规划模型,（2）一般形式 标准形式,不等式变等式,松弛变量,剩余变量,不等式变不等式,2.线性规划模型,目标的转换,例2.1.3,把问题转化为标准形式,2.2,可行区域与基本可行解,图解法,可行域的几何结构,基本可行解与基本定理,本节讨论可行解区域的结构，给出基本可行解的概念及,LP,的一些基本定理,1,、图 解 法,例2.2.1,解线性规划,例2.2.1 解线性规划,例2.2.1 解线性规划,目标函数值可能出现的情况,：,可行域是空集,可行域无界无最优解,最优解存在且唯一，则一定在顶点上达到,最优解存在且不唯一，一定存在顶点是最优解,2.,可行域的几何结构,2.2,可行区域与基本可行解,2.2,可行区域与基本可行解,2.2,可行区域与基本可行解,*问题*,2.2,可行区域与基本可行解,3.,基本可行解与基本定理,2.2,可行区域与基本可行解,2.2,可行区域与基本可行解,2.2,可行区域与基本可行解,线性规划的一些基本定理：,2.2,可行区域与基本可行解,以上问题的回答：,2.2,可行区域与基本可行解,2.3,单纯形方法,(Simplex Method),理论方法,算法步骤,单纯形表,算例,根据前面的定理可知：如果一个,LP,问题有最优解，则一定在某个基本可行解处达到。单纯形方法的主要思想就是,先找一个基本可行解,，判断它是否最优，如若不是，就,找一个更好的基本可行解，再进行判断,。如此迭代下去，直至找到最优基本可行解，或者判定该问题无界！,本节讨,论的主,要内容,2.3,单纯形方法,1.,单纯形方法的理论,2.3,单纯形方法,定 理 2.3.3,2.3,单纯形方法,定理,2.3.4,对于任何非退化的,LP,问题，从任何基本可行解开始，经过有限多次迭代，或得到一个基本可行的最优解，或作出该,LP,问题无界的判断。,算法步骤,:,2.3,单纯形方法,2.,单纯形表,2.3,单纯形方法,2.3,单纯形方法,2.3,单纯形方法,2.3,单纯形方法,2.3,单纯形方法,初始单纯形表,2.3,单纯形方法,迭 代 1,迭 代 2,2.4,初 始 解,两阶段法,大,M,法,说明,1,、两 阶 段 法,基本思想,第一阶段,：,通过求解辅助问题的最优基可行,解得到原问题的初始基可行解。,第二阶段,：,求原问题的最优解,算例,辅 助 问 题,原问题与辅 助问题的关系,求 辅 助 问 题 的 三 种 情 况,算 例,第 1 阶 段,第 1 阶 段,第 1 阶 段,第 1 阶 段,第 1 阶 段,第 2 阶 段,2,、大,M,法,3,、关于单纯形方法的几点说明,2.4,初 始 解,(1),退化问题的处理,摄动方法、字典序方法和,Bland,反循环方法,(2),修正的单纯形算法,(3),特殊问题的处理,运输问题、变量有界线性规划问题等,退化问题,设,X,0,是线性规划问题,LP,的一个基可行解，,如果,X,0,的,所有基变量都取正值,，即,x,0,i,0,，,x,i,是,X,0,的基变量，,则称,X,0,是一个,非退化解,。,如果一个线性规划问题的所有的基可行解都是非退化的解，则称这个线性规划问题是一个,非退化问题,。,由定理,2.3.4,可知，一个非退化的线性规划问题一定可以在有限步内得到最优解或判定无最优解。,但是对于一个,退化问题,，情况又怎样呢？,例,1,取 作为初始可行基。,可见，它是一个,退化的可行基,。,列出它的单纯形表，并进行迭代。,-3/4 150 1/50 6 0 0 0,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,5,x,6,x,7,0,0,1,1/4 -60 -25 9 1 0 0,-90 -1/25 3 0 1 0,0 0 1 0 0 0 1,0,-3/4 150 -1/50 6 0 0 1,x,1,x,6,x,7,0,0,1,1 -240 -4/25 36 4 0 0,0 30 3/50 -15 -2 1 0,0 0 1 0 0 0 1,0,0 -30 -7/50 33 3 0 0,-3/4 150 1/50 6 0 0 0,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,1,x,2,x,7,0,0,1,1 0 8/25 -84 -12 8 0,0 1 1/500 -1/2 -1/15 1/30 0,0 0 1 1 0 0 1,0,0 0 -2/25 18 1 1 0,x,3,x,2,x,7,0,0,1,25/8 0 1 -525/2 -75/2-25 0,-1/160 1 0 1/40 1/120 1/60 0,-25/8 0 0 525/2 75/2 -25 1,0,1/4 0 0 -3 -2 3 6,-3/4 150 1/50 6 0 0 0,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,3,x,4,x,7,0,0,1,-125/2 0 1 0 50 -150 0,-1/4 40 0 1 1/3 -2/3 0,125/2 10500 0 0 -50 150 1,0,-1/2 120 0 0 -1 1 0,x,5,x,4,x,7,0,0,1,-5/4 210 1/50 0 1 -3 0,1/6 -30 -1/150 1 0 1/3 0,0 6 1 0 0 0 1,0,-7/4 330 1/50 0 0 -2 0,-3/4 150 1/50 6 0 0 0,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,5,x,6,x,7,0,0,1,1/4 -60 -1/25 9 1 0 0,-90 -1/50 3 0 1 0,0 6 1 0 0 0 1,0,-150 1/50 6 0 0 0,上述迭代过程中，初始表与最后表完全相同，即迭代,6,次后，又回到初始基。出现了“死循环”，永远也得不到最优解。,注：,在实际计算中，单纯形方法出现死循环的现象是极其少见的。为了解决这个问题，,1952,年，,A.Charnes,提出摄动法，,1954,年，,G.B.Dantzig,提出字典序法。,本节例子是,E.Beale,于,1955,年提出的。,勃兰特法则,1974,年，,R.G.Bland,利用组合方法成功地解决了退化的线性规划问题，并提出了两条简便的规则，称为勃兰特法则：,选取 中下标最小的非基变量 为换入变量，其中,选取最小比数中下标最小的基变量为换出变量。,2.5,对偶理论,对偶线性规划,对偶理论,原始和对偶问题的解及其经济意义,(,注：选讲）,对偶单纯形算法,线性规划问题具有对偶性，即任何一个线性规划问题，都存在另一个线性规划问题问题与之对应。如果把其中一个问题叫做 原问题，则另外一个就叫做它的对偶问题,.,并称这两个相互联系的问题为一对对偶问题。研究对偶问题之间的关系及其性质，就是线性规划的对偶理论,(Duality,Theory),。,1,、对偶线性规划,标准形式线性规划的对偶规划,规范形式线性规划的对偶规划,一般形式线性规划的对偶规划,实例,标准形式的对偶规划,标准形式的对偶规划,规 范 形 式 的 对 偶 规 划,一般形式的对偶规划,实 例,2.,对偶理论,4.,对偶单纯形算法,得到最优解时的单纯形表的情况：,单 纯 形 算 法,对 偶 单 纯 形,正 则 解,正则解,对偶可行解,正则解的单纯性表,规划无可行解,保持正则性,入基变量,否,算 法 过 程,初始正则解,检查可行,是则停止,得最优解,选出基变量,检查,是否无可,行解,是则停止,否,无最优解,选入基变量,计算典式检验数,算 例,迭 代,迭 代,迭 代,2.6,灵敏度分析,概况,改变价值向量,改变右端向量,概 况,信息的不确定性,信息的变化：,价值向量,市,场变化,右端向量资源变化,系数矩阵技术进步,认知的误差,分析方法,静态分析-比较静态分析-动态分析,改变价值向量,一般改变情况,改变非基变量的价值向量,改变基变量的价值向量,算例,一 般 改 变,非 基 变 量,基 变 量,算 例,改变右端向量,基本思想,算例,基,本 思 想,算 例,计 算 软 件,LinDo,LinGo,Matlab,LinDo,输入模型,求解,点击求解按钮 即可,结果,输 入 模 型,!注释内容，可用中文,!,目标函数：,最大-,max,最小-,min,大小写不分,max 3 x1+5 x2+4 x3,!,约束，,以,subject to,开始,subject to,2 x1+3 x2=1500,2 x2+4 x3=800,3 x1+2 x2+5 x3),=,=与,等同,变量非负约束可省略,结束时以,end,标示,结 果,LP OPTIMUM FOUND AT STEP 3,OBJECTIVE FUNCTION VALUE,1)2675.000,VARIABLE VALUE REDUCED COST,X1 375.000000 0.000000,X2 250.000000 0.000000,X3 75.000000 0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 1.050000,3)0.000000 0.625000,4)0.000000 0.300000,LinGo,输入模型,LinDo,模式,LinGo,模式,求解,点击求解按钮 即可,结果,LinDo,输 入 模 式,model,:,MAX,=3*x1+5*x2+4*x3;,2*x1+3*x2=1500;,2*x2+4*x3=800;,3*x1+2*x2+5*x3=2000;,end,注意与,LinDo,的区别,目标函数中加等号,变量与系数之间用“*”,Model:-end,可省略,LinGo,模式,Model:,Sets:,Endsets,Data:,Enddata,调用函数与计算,end,!,定义集合,！,定义数据,集 合 部 分,model,:,！,开始,sets,:,！,定义集合,ve/1.3/:c,x;,co/1.3/:b;,ma(co,ve):a;,endsets,！注：集表达式：名称/成员/：属性,名称（初始集）：属性,定 义 数 据,data,:！,定义数据,c=3 5 4;,b=1500 800 2000;,a=2 3 0,0 2 4,3 2 5;,Enddata,！,注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分号；,调 用 函 数,max,=,sum,(ve(j):c(j)*x(j);,for,(co(i):,sum,(ve(j):a(i,j)*x(j)=b(i);,主要函数：,for(set(set_index_list)|condition:expression),sum(set(set_index_list)|condition:expression),min(max)(set(set_index_list)|condition:expression),结 果,Global optimal solution found at iteration:3,Objective value:2675.000,Variable Value Reduced Cost,C(1)3.000000 0.000000,C(2)5.000000 0.000000,C(3)4.000000 0.000000,X(1)375.0000 0.000000,X(2)250.0000 0.000000,X(3)75.00000 0.000000,B(1)1500.000 0.000000,B(2)800.0000 0.000000,B(3)2000.000 0.000000,A(1,1)2.000000 0.000000,A(1,2)3.000000 0.000000,A(1,3)0.000000 0.000000,A(2,1)0.000000 0.000000,A(2,2)2.000000 0.000000,A(2,3)4.000000 0.000000,A(3,1)3.000000 0.000000,A(3,2)2.000000 0.000000,A(3,3)5.000000 0.000000,Row Slack or Surplus Dual Price,1 2675.000 1.000000,2 0.000000 1.050000,3 0.000000 0.6250000,4 0.000000 0.3000000,Scilab,函数,命令1,：,x,lagr,f=linpro(p,C,b,x0),命令2,：,x,lagr,f=linpro(p,C,b,ci,cs,x0),命令3,：,x,lagr,f=linpro(p,C,b,ci,cs,me,x0),命令4,：,x,lagr,f=linpro(p,C,b,ci,cs,me,x0 ,imp),命令5,：,x1,crit=karmarkar(a,b,c,x0),注意事项,命令1,问题形式,min p*x,s.t.C*x=b,x,lagr,f=linpro(p,C,b,x0）,命 令 2,x,lagr,f=linpro(p,C,b,ci,cs,x0),问题形式,min p*x,s.t.C*x=b,ci=x=cs,命 令 3,x,lagr,f=linpro(p,C,b,ci,cs,me,x0),问题,min p*x,s.t.C(j,:)x=b(j),j=1,.,me,C(j,:)x=b(j),j=me+1,.,me+md,ci=x=cs,命 令 4,x,lagr,f=linpro(p,C,b,ci,cs,me,x0,imp),问题形式,min p*x,s.t.C(j,:)x=b(j),j=1,.,me,C(j,:)x=b(j),j=me+1,.,me+md,ci=x=0,注 意 事 项,命令2和3中,x0,可省略，但命令4和5中不可省略,向量都是列向量，参数的顺序不可换,命令3中等式约束必须在前面,人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表,为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,星期,一,二,三,四,五,六,七,人数,12,15,12,14,16,18,19,模 型 假 设,每天工作8小时，不考虑夜班的情况；,每个人的休息时间为连续的两天时间；,每天安排的人员数不得低于需求量，但可以超过需求量,问 题 分 析,因素,：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；,方案,：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。,变量,：每天开始休息的人数,约束条件,：,1.每人休息时间2天，自然满足。,2.每天工作人数不低于需求量，第,i,天工作的人数就是从第,i,-2,天往前数5天内开始工作的人数，所以有约束：,3.变量非负约束：,目标函数,：,总费用最小，总费用与使,用的总人数成正比。由于每个人必然在,且仅在某一天开始休息，所以总人数等,于,模 型,计 算,注 解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。,定义整数变量用函数,gin,(x1),gin,(x7);,0-1,整数变量为,bin(,x1,),配 料 问 题,某化工厂要用三中原料混合配置,三种不同规格的产品各产品的规格,单价如表1，,产品,规格,单价（元/公斤）,A,原料不少于50%,原料不超过25%,50,B,原料不少于25%,原料不超过50%,35,C,不限,25,问如何安排生产使得生产利润最大？,原料,日最大供应量,单价(元/公斤),100,65,100,25,60,35,原料的单价与每天最大供应量如表2,配 料 问 题 案 例,问题,问题分析,模型,求解,结果分析,问 题 分 析,变量,约束条件,目标函数,变 量,生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的数量。而由于每种产品的数量等于三种原料数量之和，所以只要确定每天生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的原料数，设用于生产第,i,种产品的第,j,种原料数为,约 束 条 件,规格约束,约 束 条 件,资源约束,目标函数,总产值,总成本,总利润=总产值-总成本,模 型,求 解,第,168,页,运 筹 帷 幄 之 中,决 胜 千 里 之 外,第,3,章 整数线性规划,Integer Linear Programming,整数线性规划问题,整数线性规划算法,计算软件,应用案例,第,169,页,第,3,章 整数线性规划,整数规划是的发展也有一段历史啦。它是数学规划的一个重要分支，可分为：纯整数规划（所有变量都限制为整数）、混合整数规划（一部分变量限制为整数）、,0-1,规划（所有变量都限制取,0,或,1,）。,本章讨论纯整数线性规划（,ILP,）及解此规划的割平面法和分枝定界法。,ILP,问题是,NP-,完全问题。,3.1,整数线性规划问题,整数线性规划的模型分类,纯整数规划模型,0-1,整数规划模型,混合整数规划模型,实例 例,3.1.1,投资决策问题,例,3.1.3,旅行售货员问题,其他,背包问题,解整数线性规划的困难性,第,170,页,纯整数规划模型,第,171,页,0-1,整数规划模型,第,172,页,混合整数规划模型,第,173,页,例,3.3.1,投资组合问题,1.,背景：,证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。,项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大,。,某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计,5,年后获利 （）万元，问应如何选择项目使得,5,年后总收益最大？,2.,问题：,变量,每,个项目是否投资,约束,总,金额不超过限制,目标,总收益最大,例,3.3.1,投资组合问题,3.,分析：,第,176,页,例,3.3.1,投资组合问题,4.,数学模型：,例,3.1.3,旅行售货员问题（,TSP,）,旅游线路安排,预定景点走且只走一次,路上时间最短,配送线路,货郎担问题,送货地到达一次,总路程最短,第,177,页,1.,背景,:,例,3.1.3,旅行售货员问题,有一旅行团从 出发要遍游城市,，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？,第,178,页,2.,问题：,3.,分析：,变量,是,否从,i,第个城市到第,j,个城市,约束,每个城市只能到达一次、离开一次,第,179,页,例,3.1.3,旅行售货员问题,目标,总,费用最小,问：是否还需要其他约束条件？,第,180,页,例,3.1.3,旅行售货员问题,4.,数学模型：,此约束是为了避免出现断裂，每个点给个位势，除了初始点外要求前点比后点大,背包问题,背景,案例,模型,第,181,页,背 景,邮递包裹,把形状可变的包裹用尽量少的车辆运走,旅行背包,容量一定的背包里装尽可能的多的物品,第,182,页,某人出国留学打点行李，现有三个旅行包，容积大小分别为,1000,毫升、,1500,毫升和,2000,毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有,7,件，其体积大小分别为,400,、,300,、,150,、,250,、,450,、,760,、,190,、（单位毫升）。尚有,10,件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。,物品,1,2,3,4,5,6,7,8,9,10,体积,200,350,500,430,320,120,700,420,250,100,价格,15,45,100,70,50,75,200,90,20,30,问题分析,第,184,页,变量,对,每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第,i,个物品是否放在第,j,个包裹中,约束,第,185,页,包裹容量限制,必带物品限制,选带物品限制,目标函数,未,带物品购买费用最小,第,186,页,模 型,第,187,页,第,188,页,特征,变,量整数性要求,来源,问题本身的要求,引入的逻辑变量的需要,性质,可,行域是离散集合,2.,解整数线性规划的困难性,与线性规划的关系：,第,189,页,整数规划,可行解是松弛问题的可行解,最优值大于等于松弛问题的最优值,2.,解整数线性规划的困难性,松弛的线性规划问题,第,190,页,2.,解整数线性规划的困难性,最优解不一定在顶点上达到,最优解不一定是松弛问题最优解的邻近整数解,整数可行解远多于松弛问题的顶点，枚举法不可取,解,ILP,问题要远难于解松弛的,LP,问题,如果松弛的,LP,问题无解，显然原,ILP,问题无解。反之，不一定成立。,如果松弛的,LP,问题无界呢？可以证明原,ILP,问题也无界,第,191,页,2.,解整数线性规划的困难性,结,论,整数线性规划算法,3.2,Gomory,割平面算法,3.3,分支定界算法,近似算法,第,192,页,第,193,页,3.2,Gomory,割平面算法,割平面法是求解整数规划的一个最早提出的方法，基本思想是在与整数规划相对应的线性规划中逐步增加线性约束条件（称为割平面），每次增加一个割平面，都使线性规划的可行域缩小，同时保持整数规划的可行解集合不变；然后来求解增加约束后的线性规划，如果得到整数规划的最优解则停止；如果没有找到整数最优解，就再增加割平面，一直到得到或证明无整数最优解为止。,3.2,Gomory,割平面算法,第,194,页,整数规划,松弛的线性规划问题,(P),(P,0,),两个问题具有如下明显关系：,(1)(,P),的可行域,(P0),的可行域,;,(2),若,(P0),无可行解，则,(,P),无可行解；,(3),(P0),的最优值是,(,P),的最优值得一个下界；,(4),若,(P0),的最优解是整数向量，则它也是,(,P),的最优解,.,1.,算法的基本思想：,由松弛问题的可行域向整数规划的可行域逼近,方法,利,用,超平面,切除,要求,整数解保留,松弛问题最优值增加,第,195,页,3.2,Gomory,割平面算法,割平面生成方法,条件,-,保留整数解删除最优解,!,下面是求松弛问题的最后一张单纯形表：,第,196,页,3.2,Gomory,割平面算法,第,197,页,整数可行解,最优基可行解,第,198,页,加入松弛变量,s,割平面,第,199,页,3.2,Gomory,割平面算法,第,200,页,3.2,Gomory,割平面算法,第,201,页,3.2,Gomory,割平面算法,第,202,页,3.2,Gomory,割平面算法,第,203,页,3.2,Gomory,割平面算法,第,204,页,正则解,3.2,Gomory,割平面算法,算 法 步 骤,第,205,页,求松弛问题的,最优基可行解,判断是否,为整数解,是,得到最优解,否,在单纯性表中加入,一列利用,对偶单纯,性算法,求最优解,第,206,页,算 例,(1,1.5),第,207,页,算 例,第,208,页,算 例,第,209,页,算 例,第,210,页,算 例,第,211,页,算 例,第,212,页,算 例,3.3,分支定界法,第,213,页,分枝定界法是一种,隐枚举法,，是一种“巧妙”地枚举整数规划问题的可行解的思想来设计算法的，其关键步骤是,分枝和定界,。,分枝定界法可用于解纯整数或混合的整数规划问题。本世纪六十年代初由,Land Doig,和,Dakin,等人提出。由于这种方法灵活且便于用计算机求解，所以现在它是解整数规划的主要方法。,1.,算法思想,隐枚举法,求解松弛问题,第,214,页,最优值比界坏,最优解为整数最优值比界好,最优解为非整,数最优值比界好,分 支,边 界,分 支,舍 弃,3.3,分支定界法,条件,-,保留整数解删除最优解,!,下面是求松弛问题的最后一张单纯形表：,第,215,页,3.3,分支定界法,2.,分支的方法,:,第,216,页,3.3,分支定界法,3.,分支方法的示意图,:,第,217,页,3.3,分支定界法,定 界,当前得到的最好整数解的目标函数值,分支后计算松弛的线性规划的最优解,整数解且目标值小于原有最好解的值则替代原有最好解,整数解且目标值大于原有最好解的值则 删除该分支其中无最优解,非整数解且目标值小于原有最好解的值则继续分支,非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解,第,218,页,第,219,页,选一分支写出并求解松弛问题，,同时从分支集中删除该分支,判定是否,为整数解,初始分支为可行解集，初始界为无穷大,判定是否,分支集空,是,当前最好解,为最优解,是,否,判定最优值是,否小于当前界,判定最优值是,否小于当前界,按非整数变量分,支并加入分支集,以最优解替代当前最,好解最优值替代当前界,否,是,是,否,算 例,第,220,页,第,221,页,第,222,页,第,223,页,注 释,求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。,第,224,页,对,0-1,整数规划分支时,第,225,页,计 算 软 件,整数变量定义,LinDo,一般整数变量,:GIN,0-1,整数变量,:INT,LinGo,一般整数变量,:GIN(variable_name);,0-1,整数变量：,BIN(variable_name);,算例,第,226,页,算 例,max 3 x1+5 x2+4 x3,subject to,2 x1+3 x2=1500,2 x2+4 x3=800,3 x1+2 x2+5 x3,e,，,1,:,=,k,；,第,2,步,如果,e,j,),(,k,t,，停止迭代，输出,k,t,。,否则，当,0,),(,=,k,t,j,时，停止，,解题失败；,当,0,),(,k,t,j,时，转下一步；,第,3,步,计算,),(,),(,1,k,k,k,k,t,t,t,t,j,