MBA运筹学127页ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,北京理工大学,管理与经济学院,吴祈宗教授,1,1、绪,论,论,2、线,性,性 规,划,划,3、运,输,输 问,题,题,4、动,态,态 规,划,划,5、图与网,络,络分析,6、排,队,队 论,7、教学日,历,历,运 筹,学,学,目录,说,明,明,本教学课件,是,是与教材紧,密,密配合使用,的,的，教材为,：,：,运筹学,杨,杨民助编,著,著,西安交通大,学,学出版社，2000年6月,参考书：,运筹学,清,清,华,华大学出版,社,社,或其他的,运,运筹学方,面,面本科教材,的,的相关内容,下面所标注,的,的页号，均,为,为本课程教,材,材的页号。,例,例如：,p123,表示第123页,p31-34,表示从第31页到第34页,2,绪,论,论,运筹学（OperationalResearch),直,直译为“,运,运作研究”,运筹学是运,用,用科学的方,法,法（如分析,、,、试验、量,化,化等）来决,定,定如何最佳,地,地运营和设,计,计各种系统,的,的一门学科,。,。运筹学对,经,经济管理系,统,统中的人力,、,、物力、财,力,力等资源进,行,行统筹安排,，,，为决策者,提,提供有依据,的,的最优方案,，,，以实现最,有,有效的管理,。,。,运筹学有广,泛,泛应用,（可以自己,找,找一些参考,书,书看）,运筹学的产,生,生和发展,（可以自己,找,找一些参考,书,书看）,3,运筹学解决,问,问题的过程,1）提出问,题,题：认清问,题,题,2）寻求可,行,行方案：建,模,模、求解,3）确定评,估,估目标及方,案,案的标准或,方,方法、途径,4）评估各,个,个方案：解,的,的检验、灵,敏,敏性分析等,5）选择最,优,优方案：决,策,策,6）方案实,施,施：回到实,践,践中,7）后评估,：,：考察问题,是,是否得到完,满,满解决,1）2）3,）,）：形成问,题,题；4）5,）,）分析问题,：,：定性分析,与,与定量分析,。,。构成决策,。,。,4,运筹学的,分,分支,线性规划,非线性规,划,划,整数规划,动态规划,多目标规,划,划,随机规划,模糊规划,等,等,图与网络,理,理论,存储论,排队论,决策论,对策论,排序与统,筹,筹方法,可靠性理,论,论等,5,运筹学在,工,工商管理,中,中的应用,生产计划,：,：生产作,业,业的计划,、,、日程表,的,的编排、,合,合理下,料、配料,问,问题、物,料,料管理等,库存管理,：,：多种物,资,资库存量,的,的管理，,库,库存方式,、,、库存,量等,运输问题,：,：确定最,小,小成本的,运,运输线路,、,、物资的,调,调拨、,运输工具,的,的调度以,及,及建厂地,址,址的选择,等,等,人事管理,：,：对人员,的,的需求和,使,使用的预,测,测，确定,人,人员编,制、人员,合,合理分配,，,，建立人,才,才评价体,系,系等,市场营销,：,：广告预,算,算、媒介,选,选择、定,价,价、产品,开,开发与,销售计划,制,制定等,财务和会,计,计：预测,、,、贷款、,成,成本分析,、,、定价、,证,证券管,理、现金,管,管理等,*,设,设备维修,、,、更新，,项,项目选择,、,、评价，,工,工程优化,设,设计与管,理,理等,6,运筹学方,法,法使用情,况,况(美1983),（,（%）,7,运筹学方,法,法在中国,使,使用情况(随机抽,样,样)（%,）,）,8,运筹学的,推,推广应用,前,前景,据美劳工,局,局1992年统计,预,预测:,运,运筹学应,用,用分析人,员,员需求从1990,年,年到2005年的,增,增长百分,比,比预测为73%,增,增长速度,排,排到各项,职,职业的前,三,三位.,结论:,运筹学在,国,国内或国,外,外的推广,前,前景是非,常,常广阔的,工商企业,对,对运筹学,应,应用和需,求,求是很大,的,的,在工商企,业,业推广运,筹,筹学方面,有,有大量的,工,工作要做,9,学习运筹,学,学要把重,点,点放在分,析,析、理解,有,有关的概,念,念、思路,上,上。在自,学,学过程中,，,，应该多,向,向自己提,问,问，如一,个,个方法的,实,实质是什,么,么，为什,么,么这样做,，,，怎么做,等,等。,自学时要,掌,掌握三个,重,重要环节,：,：,1、认真,阅,阅读教材,和,和参考资,料,料，以指,定,定教材为,主,主，同时,参,参考其他,有,有关书籍,。,。一般每,一,一本运筹,学,学教材都,有,有自己的,特,特点，但,是,是基本原,理,理、概念,都,都是一致,的,的。注意,主,主从，参,考,考资料会,帮,帮助你开,阔,阔思路，,使,使学习深,入,入。但是,，,，把时间,过,过多放在,参,参考资料,上,上，会导,致,致思路分,散,散，不利,于,于学好。,2、要在,理,理解了基,本,本概念和,理,理论的基,础,础上研究,例,例题，注,意,意例题是,为,为了帮助,你,你理解概,念,念、理论,的,的。作业,练,练习的主,要,要作用也,是,是这样，,它,它同时还,有,有让你自,己,己检查自,己,己学习的,作,作用。因,此,此，做题,要,要有信心,，,，要独立,完,完成，不,要,要怕出错,。,。因为，,整,整个课程,是,是一个整,体,体，各节,内,内容有内,在,在联系，,只,只要学到,一,一定程度,，,，知识融,会,会贯通起,来,来，你做,题,题的正确,性,性自己就,有,有判断。,3、要学,会,会做学习,小,小结。每,一,一节或一,章,章学完后,，,，必须学,会,会用精炼,的,的语言来,该,该书所学,内,内容。这,样,样，你才,能,能够从较,高,高的角度,来,来看问题,，,，更深刻,的,的理解有,关,关知识和,内,内容。这,就,就称作“,把,把书读薄,”,”，若能,够,够结合自,己,己参考大,量,量文献后,的,的深入理,解,解，把相,关,关知识从,更,更深入、,广,广泛的角,度,度进行论,述,述，则称,之,之为“把,书,书读厚”,在建数学,模,模型时要,结,结合实际,应,应用，要,学,学会用计,算,算机软件,解,解决问题,。,如何学习,运,运筹学课,程,程,返回目录,10,各章节的,重,重点、难,点,点及注,意,意事项,11,1、 线,性,性 规,划,划,线性规划,模,模型：,目标函数,：,：Maxz =50 x,1,+ 100 x,2,约束条件,：,：s.t.x,1,+x,2,300,2 x,1,+x,2,400,x,2,250,x,1,x,2, 0,*看p 7-9 例1-1，1-2,例1.,某工厂在,计,计划期内,要,要安排甲,、,、乙两种,产,产品的生,产,产，已知,生,生产单位,产,产品所需,的,的设备台,时,时及A、B两种原,材,材料的消,耗,耗以及资,源,源的限制,，,，如下表,：,：,问题：工,厂,厂应分别,生,生产多少,单,单位甲、,乙,乙产品才,能,能使工厂,获,获利最多,？,？,12,1、 线,性,性 规,划,划 （,续,续1.1,）,）,1. 1,线,线性,规,规划的概,念,念,线性规划,的,的组成,：,目标函数Maxf,或,或Minf,约束条件s.t.(subjectto),满,满足于,决策变量,用,用,符,符号来表,示,示可控制,的,的因素,一般形式 (p10-p 11),目标函数：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,标准形式 (p11-p 15,，,，例1-3),目标函数：Maxz =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,*练习：p68-70 习题11-1,，,，1-2,13,1、 线 性,规,规 划 （,续,续1.2）,1. 2,线,线性规划问题,解,解的概念及性,质,质,熟悉下列一些,解,解的概念（p15-16,）,）,可行解、可行,解,解集（可行域,）,），最优解、,最,最优值，基、,基,基变量、非基,变,变量，基本解,、,、基本可行解,，,，可行基、最,优,优基。,图解方法及各,有,有关概念的意,义,义（p16-20）,看：图解法步,骤,骤，例1-4,，,，1-5，1-6，1-7,，,，1-8，1-9,下一页是一个,图,图解法解题的,一,一个例子，右,图,图中的阴影部,分,分为可行域。,单纯形法的理,论,论基础（p20-30）,1.2.3段,要,要求看懂，了,解,解如何直接通,过,过对约束矩阵,的,的分析求出基,本,本可行解,1.2.4,1.2.5,两,两段应注重结,论,论的了解，如,单,单纯形法思想,和,和关于线性规,划,划解的四个,定理，而对证,明,明过程则可根,据,据自己的数学,基,基础来掌握：,基础很好，可,要,要求掌握；否,则,则，也可略去,不,不看。,*习题：p70 习题1 1-3，1-4,14,1、 线 性,规,规 划 （,续,续1.2）,例1.,目标函数：,Maxz = 50 x,1,+ 100x,2,约束条件：,s.t.,x,1,+x,2, 300 (A),2 x,1,+x,2, 400 (B),x,2, 250 (C),x,1, 0(D),x,2, 0(E),得到最优解：,x,1,= 50，x,2,= 250,最优目标值z =27500,15,1、 线 性,规,规 划 （,续,续1.3）,1. 3,单,单纯形法,利用单纯形表,的,的方法求解线,性,性规划重,点,点 (p30-451.3.1, 1.3.2, 1.3.3),此项内容是本,章,章的重点，学,习,习中应注意掌,握,握表格单纯形,法,法求解线性规,划,划问题的基本,过,过程。要通过,读,读懂教材内容,以,以及大量练习,来,来掌握。,16,1、 线 性,规,规 划 （,续,续1.3）,表格单纯形法( p40- p 45),考虑：,b,i, 0i =1 , , m,Maxz = 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,加入松弛变量,：,：,Maxz = 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,+ x,n+1,= b,1,a,21,x,1,+,a,22,x,2,+ +,a,2n,x,n,+ x,n+2,= b,2,a,m1,x,1,+,a,m2,x,2,+ +,a,mn,x,n,+ x,n+m,= b,m,x,1,，x,2,， ，x,n,，x,n+1,， ，x,n+m, 0,17,显然，,x,j,= 0 j= 1, , n;x,n+i,= b,i,i = 1, ,m是基本可行解,对应的基是单,位,位矩阵。,以下是初始单,纯,纯形表：,mm,其中：f =,- c,n+i,b,i,j,=,c,j,- c,n+i,a,ij,为检验数,c,n+i,= 0i= 1,m,i = 1i =1,a,n+i,i,= 1, a,n+i,j,= 0 (ji )i, j =1, , m,1、 线 性,规,规 划 （,续,续1.3）,18,1、 线 性,规,规 划 （,续,续1.3单纯,形,形法解题例）,例1。化标准,形,形式：,Maxz = 50 x,1,+ 100x,2,s.t.x,1,+x,2,+x,3,= 300,2 x,1,+x,2,+x,4,= 400,x,2,+x,5,= 250,x,1, x,2, x,3, x,4, x,5, 0,最优解 x,1,= 50x,2,= 250x,4,= 50（,松,松弛标量，表,示,示原料A有50个单位的剩,余,余）,19,注意：单纯形,法,法中，,1、每一步运,算,算只能用矩阵,初,初等行变换；,2、表中第3,列,列的数总应保,持,持非负（0）；,3、当所有检,验,验数均非正（, 0）时，,得,得到最优单纯,形,形表。,1、 线 性,规,规 划 （,续,续1.3）,20,1、 线 性,规,规 划 （,续,续1.3）,一般情况的处,理,理及注意事项,的,的强调（p45-55）,1.3.4段,主,主要是讨论初,始,始基本可行解,不,不明显时，常,用,用的方法。要,弄,弄清它的原理,，,，并通过例1-14 ,例,例1-17掌,握,握这些方法，,同,同时进一步熟,悉,悉用单纯形法,解,解题。,考虑一般问题,：,：,b,i, 0i =1 , , m,Maxz = 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,21,1、,线,线,性,性,规,规,划,划,（,（,续,续1.3,）,）,大M,法,法：,引入,人,人工,变,变量x,n+i,0i=1,m;,充,充分,大,大正,数,数M,。,。,得,得到,，,，,Maxz=c,1,x,1,+c,2,x,2,+,+c,n,x,n,+Mx,n+1,+,+Mx,n+m,s.t.,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,+x,n+1,=b,1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,+x,n+2,=b,2,a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,+x,n+m,=b,m,x,1,，x,2,，,，,，x,n,，x,n+1,，,，,，x,n+m,0,显然,，,，,x,j,=0j=1,n;x,n+i,=b,i,i=1,m是基,本,本可,行,行解,对应,的,的基,是,是单,位,位矩,阵,阵。,结论,：,：若,得,得到,的,的最,优,优解,满,满足,x,n+i,=0i=1,m则是,原,原问,题,题的,最,最优,解,解；,否,否则,，,，原,问,问题,无,无可,行,行解,。,。,22,1、,线,线,性,性,规,规,划,划,（,（,续,续1.3,）,）,两阶,段,段法,：,：,引入,人,人工,变,变量x,n+i,0，i=1,m；,构,构造,，,，,Maxz=-x,n+1,-x,n+2,-,-x,n+m,s.t.,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,+x,n+1,=b,1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,+x,n+2,=b,2,a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,+x,n+m,=b,m,x,1,，x,2,，,，,，x,n,，x,n+1,，,，,，x,n+m,0,第一,阶,阶段,求,求解,上,上述,问,问题,：,：,显然,，,，,x,j,=0j=1,n;x,n+i,=b,i,i=1,m是基,本,本可,行,行解,对应,的,的基,是,是单,位,位矩,阵,阵。,结论,：,：若,得,得到,的,的最,优,优解,满,满足,x,n+i,=0i=1,m则是,原,原问,题,题的,基,基本,可,可行,解,解；,否,否则,，,，原,问,问题,无,无可,行,行解,。,。,得到,原,原问,题,题的,基,基本,可,可行,解,解后,，,，第,二,二阶,段,段求,解,解原,问,问题,。,。,23,1、,线,线,性,性,规,规,划,划,（,（,续,续1.3,）,）例,题,题,例：,（,（LP）Maxz=5x,1,+2x,2,+3x,3,-x,4,s.t.x,1,+2x,2,+3x,3,=15,2x,1,+x,2,+5x,3,=20,x,1,+2x,2,+4x,3,+x,4,=26,x,1,x,2,x,3,x,4,0,大M,法,法问,题,题（LP-M,）,）,Maxz=5x,1,+2x,2,+3x,3,-x,4,-Mx,5,-Mx,6,s.t.x,1,+2x,2,+3x,3,+x,5,=15,2x,1,+x,2,+5x,3,+x,6,=20,x,1,+2x,2,+4x,3,+x,4,=26,x,1,x,2,x,3,x,4,x,5,x,6,0,两阶,段,段法,：,：,第,第一,阶,阶段,问,问题,（,（LP-1）,Maxz=-x,5,-x,6,s.t.x,1,+2x,2,+3x,3,+x,5,=15,2x,1,+x,2,+5x,3,+x,6,=20,x,1,+2x,2,+4x,3,+x,4,=26,x,1,x,2,x,3,x,4,x,5,x,6,0,24,1,、,、,线,线,性,性,规,规,划,划,（,（,续,续1.3,）,）,大,大M,法,法,例,例,大M,法,法,（LP-M,）,）,得,到,到,最,最,优,优,解,解,：,：(25/3,，,，10/3,，,，0,，,，11),T,最,优,优,目,目,标,标,值,值,：,：112/3,25,1,、,、,线,线,性,性,规,规,划,划,（,（,续,续1.3,）,）,两,两,阶,阶,段,段,法,法,例,例,第,一,一,阶,阶,段,段,（LP-1,）,）,得,到,到,原,原,问,问,题,题,的,的,基,基,本,本,可,可,行,行,解,解,：,：(0,，,，15/7,，,，25/7,，,，52/7),T,26,1,、,、,线,线,性,性,规,规,划,划,（,（,续,续1.3,）,）,两,两,阶,阶,段,段,法,法,例,例,第,二,二,阶,阶,段,段,把,基,基,本,本,可,可,行,行,解,解,填,填,入,入,表,表,中,中,得,到,到,原,原,问,问,题,题,的,的,最,最,优,优,解,解,：,：(25/3,，,，10/3,，,，0,，,，11),T,最,优,优,目,目,标,标,值,值,：,：112/3,27,1,、,、,线,线,性,性,规,规,划,划,（,（,续,续1.3,）,）,1.3.5,矩,矩,阵,阵,描,描,述,述,此,此,段,段,为,为,选,选,读,读,，,，,有,有,困,困,难,难,者,者,可,可,不,不,看,看,。,。,1.3.6,段,段,单,单,纯,纯,形,形,迭,迭,代,代,过,过,程,程,中,中,的,的,几,几,点,点,注,注,意,意,事,事,项,项,是,是,对,对,有,有,关,关,内,内,容,容,的,的,强,强,调,调,和,和,补,补,充,充,，,，,要,要,认,认,真,真,学,学,习,习,、,、,理,理,解,解,。,。,*,习,习,题,题,：,：p70-71,习,习,题,题11-5,，,，1-6,28,1.4,线,线,性,性,规,规,划,划,应,应,用,用,建,建,模,模,（,（p55-68,）,）,本,节,节,介,介,绍,绍,了,了,些,些,线,线,性,性,规,规,划,划,应,应,用,用,的,的,例,例,子,子,，,，,这,这,些,些,例,例,子,子,从,从,多,多,个,个,方,方,面,面,介,介,绍,绍,建,建,模,模,对,对,未,未,来,来,是,是,很,很,有,有,用,用,的,的,，,，,应,应,认,认,真,真,对,对,待,待,。,。,除了教,材,材上的,例,例子之,外,外，还,有,有许多,其,其它应,用,用：,* 合,理,理利用,线,线材问,题,题：如,何,何下料,使,使用材,最,最少,* 配,料,料问题,：,：在原,料,料供应,量,量的限,制,制下如,何,何获取,最,最大利,润,润,* 投,资,资问题,：,：从投,资,资项目,中,中选取,方,方案，,使,使投资,回,回报最,大,大,* 产,品,品生产,计,计划：,合,合理利,用,用人力,、,、物力,、,、财力,等,等，使,获,获利最,大,大,* 劳,动,动力安,排,排：用,最,最少的,劳,劳动力,来,来满足,工,工作的,需,需要,* 运,输,输问题,：,：如何,制,制定调,运,运方案,，,，使总,运,运费最,小,小,*下,面,面是一,些,些建模,的,的例子,，,，有兴,趣,趣者，,可,可作为,练,练习。,这,这些例,子,子有一,定,定的难,度,度，做,起,起来会,有,有一些,困,困难。,*习,题,题：p72-73,习,习,题,题11-7，1-8,，,，1-9，1-10,1、,线,线 性,规,规,划,划 （,续,续1.4）,返回目,录,录,29,例某,昼,昼夜服,务,务的公,交,交线路,每,每天各,时,时间段,内,内所需,司,司机和,乘,乘务人,员,员数如,下,下：,设司机,和,和乘务,人,人员分,别,别在各,时,时间段,一,一开始,时,时上班,，,，并连,续,续工作,八,八小时,，,，问该,公,公交线,路,路怎样,安,安排司,机,机和乘,务,务人员,，,，既能,满,满足工,作,作需要,，,，又配,备,备最少,司,司机和,乘,乘务人,员,员?,例：人,力,力资源,分,分配的,问,问题,30,解：设,x,i,表示第i班次,时,时开始,上,上班的,司,司机和,乘,乘务人,员,员数,这,这样我,们,们建立,如,如下的,数,数学模,型,型。,目标函,数,数：Min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,+,x,6,约束条,件,件：s.t.,x,1,+,x,6, 60,x,1,+,x,2, 70,x,2,+,x,3, 60,x,3,+,x,4, 50,x,4,+,x,5, 20,x,5,+,x,6, 30,x,1,x,2,x,3,x,4,x,5,x,6, 0,例：人,力,力资源,分,分配的,问,问题（,续,续）,31,例、,明,明兴,公,公司生,产,产甲、,乙,乙、丙,三,三种产,品,品，都,需,需要经,过,过铸造,、,、机加,工,工和装,配,配三个,车,车间。,甲,甲、乙,两,两种产,品,品的铸,件,件可以,外,外包协,作,作，亦,可,可以自,行,行生产,，,，但产,品,品丙必,须,须本厂,铸,铸造才,能,能保证,质,质量。,数,数据如,下,下表。,问,问：公,司,司为了,获,获得最,大,大利润,，,，甲、,乙,乙、丙,三,三种产,品,品各生,产,产多少,件,件？甲,、,、乙两,种,种产品,的,的铸造,中,中，由,本,本公司,铸,铸造和,由,由外包,协,协作各,应,应多少,件,件？,例：生,产,产计划,的,的问题,32,解：设,x,1,x,2,x,3,分别为,三,三道工,序,序都由,本,本公司,加,加工的,甲,甲、乙,、,、丙三,种,种产品,的,的件数,，,，,x,4,x,5,分别为,由,由外协,铸,铸造再,由,由本公,司,司机加,工,工和装,配,配的甲,、,、乙两,种,种产品,的,的件数,。,。,求,x,i,的利润,：,：利润=,售,售价- 各,成,成本之,和,和,可得到,x,i,（i=1,2,3,4,5,）,）的利,润,润分别,为,为15,、,、10,、,、7、13、9元。,这样我,们,们建立,如,如下的,数,数学模,型,型。,目标函,数,数：Max15,x,1,+ 10,x,2,+ 7,x,3,+ 13,x,4,+ 9,x,5,约束条,件,件：s.t.5,x,1,+ 10,x,2,+ 7,x,3, 8000,6,x,1,+4,x,2,+ 8,x,3,+ 6,x,4,+ 4,x,5, 12000,3,x,1,+2,x,2,+ 2,x,3,+ 3,x,4,+ 2,x,5, 10000,x,1,x,2,x,3,x,4,x,5,0,例：,生,生产,计,计划,的,的问,题,题（,续,续）,33,例、,永,永,久,久机,械,械厂,生,生产,、,、,三,种,种产,品,品，,均,均要,经,经过A、B,两,两道,工,工序,加,加工,。,。假,设,设有,两,两种,规,规格,的,的设,备,备A,1,、A,2,能完,成,成A,工,工序,；,；有,三,三种,规,规格,的,的设,备,备B,1,、B,2,、B,3,能完,成,成B,工,工序,。,。,可,可在A、B的,任,任何,规,规格,的,的设,备,备上,加,加工,；,；,可,可,在,在任,意,意规,格,格的A设,备,备上,加,加工,，,，但,对,对B,工,工序,，,，只,能,能在B,1,设备,上,上加,工,工；,只,能,能在A,2,与B,2,设备,上,上加,工,工；,数,数据,如,如下,表,表。,问,问：,为,为使,该,该厂,获,获得,最,最大,利,利润,，,，应,如,如何,制,制定,产,产品,加,加工,方,方案,？,？,例：,生,生产,计,计划,的,的问,题,题（,续,续）,34,解：设,x,ijk,表示第 i,种,种产品，,在,在第 j,种,种工序上的,第,第 k 种,设,设备上加工,的,的数量。,利润 =（销售单,价,价 - 原,料,料单价）*,产,产品件数之和 -,（,（每台时,的,的设备费用*设备实际,使,使用的总台,时,时数）之和,。,。,这样我们建,立,立如下的数,学,学模型:,Max 0.75,x,111,+0.7753,x,112,+1.15,x,211,+1.3611,x,212,+1.9148,x,312,-0.375,x,121,-0.5,x,221,-0.4475,x,122,-1.2304,x,322,-0.35,x,123,s.t.5,x,111,+ 10,x,211, 6000,（,（ 设备A,1,）,7,x,112,+ 9,x,212,+ 12,x,312, 10000,（,（ 设备A,2,）,6,x,121,+ 8,x,221, 4000,（,（ 设备B,1,）,4,x,122,+ 11,x,322, 7000,（,（ 设备B,2,）,7,x,123, 4000,（,（ 设备B,3,）,x,111,+,x,112,-,x,121,-,x,122,-,x,123,= 0 （,产品在A,、,、B工序加,工,工的数量相,等,等）,x,211,+,x,212,-,x,221,= 0 （,产品在A,、,、B工序加,工,工的数量相,等,等）,x,312,-,x,322,= 0 （,产品在A,、,、B工序加,工,工的数量相,等,等）,x,ijk, 0, i =1,2,3; j= 1,2; k =1,2,3,例：生产计,划,划的问题（,续,续）,35,例、某工厂,要,要做100,套,套钢架，每,套,套用长为2.9 m,2.1 m,1.5m的圆钢各,一,一根。已知,原,原料每根长7.4 m,，,，问：应如,何,何下料，可,使,使所用原料,最,最省？,解： 设,计,计下列 5,种,种下料方,案,案,假设,x,1,x,2,x,3,x,4,x,5,分别为上面,前,前 5 种,方,方案下料的,原,原材料根数,。,。这样我们,建,建立如下的,数,数学模型。,目标函数：Min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,约束条件：s.t.,x,1,+ 2,x,2,+,x,4, 100,2,x,3,+ 2,x,4,+,x,5, 100,3,x,1,+,x,2,+ 2,x,3,+ 3,x,5, 100,x,1,x,2,x,3,x,4,x,5, 0,例：套裁下,料,料问题,36,例6某工,厂,厂要用三种,原,原料1、2,、,、3混合调,配,配出三种不,同,同规格的产,品,品甲、乙、,丙,丙，数据如,下,下表。问：,该,该厂应如何,安,安排生产，,使,使利润收入,为,为最大？,例：配料问,题,题,37,例：配料问,题,题（续）,解： 设,x,ij,表示第 i,种,种（甲、,乙,乙、丙）产,品,品中原料j 的含量,。,。这样我们,建,建立数学模,型,型时，要考,虑,虑：,对于甲：,x,11,，,x,12,，,x,13,；,对于乙：,x,21,，,x,22,，,x,23,；,对于丙：,x,31,，,x,32,，,x,33,；,对于原料1,：,：,x,11,，,x,21,，,x,31,；,对于原料2,：,：,x,12,，,x,22,，,x,32,；,对于原料3,：,：,x,13,，,x,23,，,x,33,；,目标函数：,利,利润最大,，,，利润 =,收,收入 -,原,原料支出,约束条件：,规,规格要求4 个；,供应量限制3 个。,38,Max z= -15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,s.t. 0.5,x,11,-0.5,x,12,-0.5,x,13, 0 （原材,料,料1不少于50%）,-0.25,x,11,+0.75,x,12,-0.25,x,13, 0 （原材,料,料2不超过25%）,0.75,x,21,-0.25,x,22,-0.25,x,23, 0 （原材,料,料1不少于25%）,-0.5,x,21,+0.5,x,22,-0.5,x,23, 0 （原材,料,料2不超过50%）,x,11,+,x,21,+,x,31, 100(供应量限制,）,）,x,12,+,x,22,+,x,32, 100(供应量限制,）,）,x,13,+,x,23,+,x,33, 60(供应量限制,）,）,x,ij, 0 ,i = 1,2,3; j =1,2,3,例：配料问题（,续,续）,39,例8某部门现,有,有资金200万,元,元，今后五年内,考,考虑给以下的项,目,目投资。已知：,项,项,目A：从第一年,到,到第五年每年年,初,初都可投资，当,年,年末能收回本利110%；项目B：从第,一年到第四年每,年,年年初都可投资,，,，次年末能收回,本,本利125%，,但,但规定每年最大,投,投资额,不能超过30万,元,元；项目C：需,在,在第三年年初投,资,资，第五年末能,收,收回本利140%，但规,定最大投资额不,能,能超过80万元,；,；项目D：需在,第,第二年年初投资,，,，第五年末能收,回,回本,利155%，但,规,规定最大投资额,不,不能超过100,万,万元；,据测定每万元每,次,次投资的风险指,数,数如右表：,问：,a）应如何确定,这,这些项目的每年,投,投资额，使得第,五,五年年末拥有资,金,金的本利金额为,最,最大？,b）应如何确定,这,这些项目的每年,投,投资额，使得第,五,五年年末拥有资,金,金的本利在330万元的基础上,使,使得其投资总的,风,风险系数为最小,？,？,解： 1）,确定决策变量：,连,连续投资问题,设,x,ij,( i = 1- 5，j= 1、2、3,、,、4)表示第i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项,目,目的金额。这样,我,我们建立如下的,决,决策变量：,A x,11,x,21,x,31,x,41,x,51,B x,12,x,22,x,32,x,42,C,x,33,D,x,24,例：投资问题,40,2）约束条件：,第一年：A当年,末,末可收回投资，,故,故第一年年初应,把,把全部资金投出,去,去，于是,x,11,+,x,12,= 200；,第二年：B次当,年,年末才可收回投,资,资故第二年年初,的,的资金为,x,11,，于是,x,21,+,x,22,+,x,24,= 1.1,x,11,；,第三年：年初的,资,资金为,x,21,+,x,12,，于是,x,31,+,x,32,+,x,33,= 1.1,x,21,+ 1.25,x,12,；,第四年：年初的,资,资金为,x,31,+,x,22,，于是,x,41,+,x,42,= 1.1,x,31,+ 1.25,x,22,；,第五年：年初的,资,资金为,x,41,+,x,32,，于是,x,51,= 1.1,x,41,+ 1.25,x,32,；,B、C、D的,投,投资限制：,x,i2, 30 (I =1、2、3、4)，,x,33, 80，,x,24, 100,3）目标函数,及,及模型：,a),Max z= 1.1,x,51,+ 1.25,x,42,+ 1.4,x,33,+ 1.55,x,24,s.t.,x,11,+,x,12,= 200,x,21,+,x,22,+,x,24,= 1.1,x,11,；,x,31,+,x,32,+,x,33,= 1.1,x,21,+ 1.25,x,12,；,x,41,+,x,42,= 1.1,x,31,+ 1.25,x,22,；,x,51,= 1.1,x,41,+ 1.25,x,32,；,x,i2, 30 (I =1、2、3、4)，,x,33, 80，,x,24, 100,x,ij, 0 (i = 1,、,、2、3、4,、,、5；j =1、2、3,、,、4）,b),Min f= (,x,11,+,x,21,+,x,31,+,x,41,+,x,51,)+3(,x,12,+,x,22,+,x,32,+,x,42,)+4,x,33,+5.5,x,24,s.t.,x,11,+,x,12,= 200,x,21,+,x,22,+,x,24,= 1.1,x,11,；,x,31,+,x,32,+,x,33,= 1.1,x,21,+ 1.25,x,12,；,x,41,+,x,42,= 1.1,x,31,+ 1.25,x,22,；,x,51,= 1.1,x,41,+ 1.25,x,32,；,x,i2, 30 (I =1、2、3、4)，,x,33, 80，,x,24, 100,1.1,x,51,+ 1.25,x,42,+ 1.4,x,33,+ 1.55,x,24, 330,x,ij, 0 (i = 1,、,、2、3、4,、,、5；j =1、2、3,、,、4）,例：投资问题,（,（续）,41,2、线性规划,问,问题的进一步,研,研究（2.1,）,）,2. 1,对,对偶原理,1、对偶问题,：,：考虑前文例1,若设备和原料,都,都用于外协加,工,工，工厂收取,加,加工费。试问,：,：设备工时和,原,原料A、B,各,各如何收费才,最,最有竞争力？,设 y,1,，y,2,，y,3,分别为每设备,工,工时、,原料 A、B,每,每单位的收取,费,费用,Maxz = 50 x,1,+ 100x,2,Min f= 300y,1,+ 400y,2,+ 250y,3,s.t.x,1,+x,2, 300s.t.y,1,+ 2 y,2,+ 50,2 x,1,+x,2, 400（不少于甲产,品,品的利润）,x,2, 250y,1,+ y,2,+ y,3, 100,x,1,x,2,0y,1,y,2,y,3,0,42,2、,对,对偶,定,定义,对称,形,形式,：,：,互,互为,对,对偶,(LP)Maxz=c,T,x,(DP)Minf=b,T,y,s.t.Ax,bs.t.A,T,y,c,x,0y,0,“Max-,”,”,“,“Min-,”,一般,形,形式,：,：,若一,个,个问,题,题的,某,某约,束,束为,等,等式,，,，那,么,么对,应,应的,对,对偶,问,问题,的,的相,应,应变,量,量无,非,非负,限,限制,；,；反,之,之，,若,若,一,一个,问,问题,的,的某,变,变量,无,无非,负,负限,制,制，,那,那么,对,对应,的,的对,偶,偶问,题,题的,相,相应,约,约束,为,为等,式,式。,2、,线,线性,规,规划,问,问题,的,的进,一,一步,研,研究,（,（2.1,）,）,43,3、,对,对偶,定,定理,（,（,原,原问,题,题与,对,对偶,问,问题,解,解的,关,关系,）,）,考虑,（,（LP）,和,和（DP,）,）,定理2-1,（,（弱,对,对偶,定,定理,）,）若x,y,分,分别,为,为（LP,）,）和,（,（DP）,的,的可,行,行解,，,，那,么,么c,T,x,b,T,y,。,。,推论,若,若,（,（LP）,可,可行,，,，那,么,么（LP,）,）无,有,有限,最,最优,解,解的,充,充分,必,必要,条,条件,是,是（LD,）,）无,可,可行,解,解。,定理2-2,（,（最,优,优性,准,准则,定,定理,）,）若x,y,分,分别,为,为（LP,）,）和,（,（DP）,的,的可,行,行解,，,，且c,T,x=b,T,y,，,，那,么,么x,y,分,分别,为,为（LP,）,）和,（,（DP）,的,的最,优,优解,。,。,定理2-3,（,（主,对,对偶,定,定理,）,）若,（,（LP）,和,和（DP,）,）均,可,可行,，,，那,么,么（LP,）,）和,（,（DP）,均,均有,最,最优,解,解，,且,且最,优,优值,相,相等,。,。,以上,定,定理,、,、推,论,论对,任,任意,形,形式,的,的相,应,应线,性,性规,划,划的,对,对偶,均,均有,效,效,*,习,习题,：,：p99,习,习,题,题22-1,2、,线,线性,规,规划,问,问题,的,的进,一,一步,研,研究,（,（2.1,）,）,44,4、,影,影子,价,价格,是,是,一,一个,向,向量,，,，它,的,的分,量,量表,示,示最,优,优目,标,标值,随,随相,应,应资,源,源数,量,量变,化,化的,变,变化,率,率。,若x,*,y,*,分别,为,为（LP,）,）和,（,（DP）,的,的最,优,优解,，,，,那么，c,T,x,*,= b,T,y,*,。,根据f =b,T,y,*,= b,1,y,1,*,+ b,2,y,2,*,+,+ b,m,y,m,*,可知,f /,b,i,=y,i,*,y,i,*,表示 b,i,变化1个,单,单位对目,标,标 f,产,产生的影,响,响，称y,i,*,为 b,i,的影子价,格,格。,注意：若B 是,最,最优基，y,*,= (B,T,),-1,c,B,为影子价,格,格向量。,2、线性,规,规划问题,的,的进一步,研,研究（2.1）,45,5、由最,优,优单纯形,表,表求对偶,问,问题最优,解,解,第1章例1。化标,准,准形式：,Maxz= 50 x,1,+ 100 x,2,s.t.x,1,+x,2,+x,3,=300,，,，2 x,1,+x,2,+x,4,=400,x,2,+x,5,=250,，,，x,1, x,2, x,3, x,4, x,5, 0I,O,B=(p,1, p,4, p,2,),(B,T,),-1,c,B,B,-1,最优解x,1,= 50x,2,= 250x,4,= 50（松弛,标,标量，表,示,示原料A,有,有50个,单,单位的剩,余,余）,影子价格y,1,= 50y,2,= 0y,3,= 50 ,B,-1,对应的检,验,验数 (B,T,),-1,c,B,。,2、线性,规,规划问题,的,的进一步,研,研究（2.1）,46,2. 2,对,对偶单,纯,纯形法,对偶单纯,形,形法在什,么,么情况下,使,使用 ：,应用前提,：,：有一个,基,基，其对,应,应的基本,解,解满足, 单纯,形,形表的检,验,验数行全,部,部非正（,对,对偶可行,）,）；, 变量,取,取值可有,负,负数（非,可,可行解）,。,。,*注：,通,通过矩阵,行,行变换运,算,算，使所,有,有相应变,量,量取值均,为,为非负数,即,即得到最,优,优单纯性,表,表。,2、线性,规,规划问题,的,的进一步,研,研究（2.2）,47,2、线性,规,规划问题,的,的进一步,研,研究（2.2）,对偶单纯,形,形法求解,线,线性规划,问,问题过程,：,：,1、建立,初,初始对偶,单,单纯形表,，,，对应一,个,个基本解,，,，所有检,验,验数均非,正,正，转2,；,；,2、若b0,，,，则得到,最,最优解，,停,停止；否,则,则，若有b,k, 0,则,则选 k,行,行的基,变,变量为出,基,基变量，,转,转3；,3、若所,有,有 a,kj,0 (j =1,2,n)，则原,问,问题无可,行,行解，停,止,止；否则,，,，若有a,kj, 0,则,则选, =min,j,/ a,kj,a,kj, 0,c,s,Min,j,/ a,sj,a,sj, 0,例:MaxZ =2x,1,+ 3x,2,+ 0x,3,+ 0x,4,+ 0x,5,S.t.x,1,+ 2x,2,+ x,3,= 8,4x,1,+ x,4,=16,4x,2,+x,5,=12,x,1, x,2, x,3, x,4, x,5, 0,2、线性,规,规划问题,的,的进一步,研,研究（2.3）,55,例、下表,为,为最优单,纯,纯形表，,考,考虑基变,量,量系数c,2,发生变化,从表中看,到,到 ,j,= C,j,- （C,1,* a,1j,+ C,5,* a,5j,+ （C,2,+,C,2,）* a,2j,） j= 3,、,、4,可得到-3, C,2,1,时,时，,原,原最优解,不,不变。,2、线性,规,规划问题,的,的进一步,研,研究（2.3）,56,右端项b 发生,变,变化,设分量b,r,变化为b,r,+,b,r,，根据第1章的讨,论,论，最优,解,解的基变,量,量 x,B,= B,-1,b，那么,只,只要保持B,-1,(b +,b,) 0 ，则,最,最优基不,变,变，即基,变,变量保持,，,，只有值,的,的变化；,否,否则，需,要,要利用对,偶,偶单纯形,法,法继续计,算,算。,对于问题(LP)Maxz =c,T,x,s.t.Ax