MBA运筹学培训课程

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学,北京理工大学,管理与经济学院,吴祈宗教授,1,1、绪 论,2、线 性,规,规 划,3、运 输,问,问 题,4、动 态,规,规 划,5、图与网络分,析,析,6、排 队,论,论,7、教学日历,运 筹 学,目录,说,明,明,本教学课件是与,教,教材紧密配合使,用,用的，教材为：,运筹学,杨,杨民助,编,编著,西安交通大学出,版,版社，2000,年,年6月,参考书：,运筹学,清,清华大学出,版,版社,或其他的运筹,学,学方面本科教,材,材的相关内容,下面所标注的页,号,号，均为本课程,教,教材的页号。例,如,如：,p123,表示第123页,p31-34,表示从第31页,到,到第34页,2,绪 论,运筹学（Operational Research) 直译,为,为“运作研究”,运筹学是运用科,学,学的方法（如分,析,析、试验、量化,等,等）来决定如何,最,最佳地运营和设,计,计各种系统的一,门,门学科。运筹学,对,对经济管理系统,中,中的人力、物力,、,、财力等资源进,行,行统筹安排，为,决,决策者提供有依,据,据的最优方案，,以,以实现最有效的,管,管理。,运筹学有广泛应,用,用,（可以自己找一,些,些参考书看）,运筹学的产生和,发,发展,（可以自己找一,些,些参考书看）,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 =50x,1,+ 100x,2,约束条,件,件：s.t.x,1,+x,2,300,2 x,1,+x,2,400,x,2,250,x,1,x,2,0,*看p7-9 例1-1,，,，1-2,例1.,某工厂,在,在计划,期,期内要,安,安排甲,、,、乙两,种,种产品,的,的生产,，,，已知,生,生产单,位,位产品,所,所需的,设,设备台,时,时及A,、,、B两,种,种原材,料,料的消,耗,耗以及,资,资源的,限,限制，,如,如下表,：,：,问题：,工,工厂应,分,分别生,产,产多少,单,单位甲,、,、乙产,品,品才能,使,使工厂,获,获利最,多,多？,12,1、,线,线 性,规,规,划,划 （,续,续1.1）,1.1,线,线性规,划,划的概,念,念,线性规,划,划的组,成,成,：,目标函,数,数Maxf,或,或Minf,约束条,件,件s.t.(subjectto),满,满,足,足于,决策变量,用,用符号,来,来表示可控,制,制的因素,一般形式( p10- p11),目标函数：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- p15 ，例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,*练习：p 68-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,习,习题11-3，1-4,14,1、 线,性,性 规,划,划 （,续,续1.2,）,）,例1.,目标函数,：,：,Maxz= 50 x,1,+ 100 x,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- p45),考虑：,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,= 0j =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,= 0 i= 1,m,i = 1i= 1,a,n+i,i,= 1, a,n+i,j,= 0 ( j,i )i ,j = 1, , m,1、 线 性,规,规 划 （续1.3）,18,1、 线 性,规,规 划 （续1.3单纯形法解,题,题例）,例1。化标准形,式,式：,Maxz = 50x,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, 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,+ M x,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,= 0 j=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,种,种设,备,备上,加,加工,的,的数,量,量。,利润=,（,（销,售,售单,价,价-,原,原料,单,单价,）,）*,产,产,品,品件,数,数,之,之和-,（,（,每,每台,时,时的,设,设备,费,费用*设,备,备实,际,际使,用,用的,总,总台,时,时数,）,）之,和,和。,这样,我,我们,建,建立,如,如下,的,的数,学,学模,型,型:,Max0.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,12,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,Maxz=-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)项,目,目的金,额,额。这,样,样我们,建,建立如,下,下的决,策,策变量,：,：,Ax,11,x,21,x,31,x,41,x,51,Bx,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,第三年：年初的资金为,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,Minf=300y,1,+ 400y,2,+ 250y,3,s.t.x,1,+x,2,300s.t.y,1,+ 2y,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)Max z= c,T,x,(DP)Min f= 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 = 50x,1,+ 100 x,2,s.t.x,1,+x,2,+x,3,= 300,，,， 2x,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、若b,0,，,，则得,到,到最优,解,解，停,止,止；否,则,则，若,有,有 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,b,x 0,最优单,纯,纯形表,中,中含有