运筹学胡运权第四版和答案.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版标题样式,*,*,运筹学(胡运权第四版和答案),联系方式,办公室：,QL643 87313663,手机：,13600512360,邮箱：,xxdhz,绪 论,绪论,什么是运筹学？,运筹学发展历史,运筹学主要内容,运筹学的基本特征与基本方法,绪论,什么是运筹学？,定义：,为决策机构在对其控制下业务活动进行,决策,时，提供以,数量化,为基础的科学方法。,西蒙：管理就是决策,决策,定性,管理者的判断和经验,定量,运筹,学,绪论,运筹学发展历史,古代运筹思想：田忌赛马、,丁渭修皇宫,二战期间的,Operational Research,研究成果被应用到生产经济领域，且研究不断深,化，逐步形成,“,运筹学,”,绪论,绪论,运筹学的主要内容有哪些？,线性规划,运输问题,整数规划,目标规划,动态规划,图与网络模型,排序与统筹方法,存储论,排队论,对策论,决策分析,预测,绪论,运筹学研究的基本特征,系统的整体观念,多学科的综合,模型方法的应用,绪论,运筹学研究的基本方法,分析和表述问题,建立模型,求解模型和优化方案,测试模型及对模型进行必要的修正,建立对解的有效控制,方案的实施,第一章：线性规划及单纯形法,第一章：线性规划及单纯形法,线性规划问题及其数学模型,线性规划图解法,单纯形法原理,单纯形法计算步骤,单纯形法的进一步讨论,第一章：线性规划及单纯形法,例题：某工厂在计划期内要安排,、,两种产品的生产，生产单位产品所需的设备台时及,A,、两种原材料的消耗以及资源的限制如表所示,工厂每生产一单位产品,可获利,50,元，每生产一单位产品,可获利,100,元，问工厂应分别生产多少单位产品,和产品,才能获利最多？,资源限制,设备,1,1,300,台时,原料,A,2,1,400KG,原料,B,0,1,250KG,第一章：线性规划及单纯形法,线性规划问题的数学模型,目标函数：,maxz=50 x,1,+100 x,2,x,1,+x,2,300,2x,1,+x,2,400,x,2,250,x,1,0,，,x,2,0,概念：可行解、最优解、最优值,约束条件：,非负约束：,第一章：线性规划及单纯形法,500,万,m,3,练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天,500,万,m,3,，,在两个工厂之间有一条流量为每天,200,万,m,3,支流，第一化工厂每天排放含有某种有害物质的工业污水,2,万,m,3,，第二化工厂每天排放这种工业污水,1.4,万,m,3,。从第一化工厂排出的工业污水流到第二化工厂以前，有,20%,可自净化。根据环保要求，河流中工业污水的含量应不大于,0.2%,，这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的成本是,1000,元,/,万,m,3,。第二化工厂处理污水的的成本是,800,元,/万,m,3,。现问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。,200,万,m,3,工厂,1,工厂,2,第一章：线性规划及单纯形法,线性规划问题的数学模型,目标函数：,minz=1000 x,1,+800 x,2,约束条件：,(2-x,1,)/5000.2%,0.8(2-x,1,)+(1.4-x,2,)/700 0.2%,x,1,2,x,2,1.4,非负约束：,x,1,0,，,x,2,0,线性规划的一般模式,目标函数：,max(min)Z=c,1,x,1,+c,2,x,2,+c,3,x,3,+,+c,n,x,n,约束条件：,a,11,x,1,+a,12,x,2,+a,13,x,3,+,+a,1n,x,n,(=)b,1,a,21,x,1,+a,22,x,2,+a,23,x,3,+,+a,2n,x,n,(=)b,2,a,m1,x,1,+a,m2,x,2,+a,m3,x,3,+,+a,mn,x,n,(=)b,n,非负性约束：,x,1,0,x,2,0,x,n,0,第,一,章：线性规划及单纯形法,解得：,最大利润：,27500,X,1,=50 X,2,=250,代入得：,设备台时：,300,原料,A,：,350,原料,B,：,250,概念：松弛变量 剩余变量,第,一,章：线性规划及单纯形法,线性规划的标准型,maxZ=c,1,x,1,+c,2,x2,+,+c,n,x,n,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,j,0,j,=1,2,n,第,一,章：线性规划及单纯形法,标准型的四个标准：求最大值、约束条件为等式、,bj 0.x,j,0,化非标准形线性规划为标准形式,minz=x,1,+2x,2,+3x,3,-2,x,1,+x,2,+x,3,9,-3x,1,+x,2,+2x,3,400,4x,1,-2x,2,-3x,3,=-6,x,1,0,x,2,0,x,3,取值无约束,第,一,章：线性规划及单纯形法,练习：将下面线性规划问题化为标准形式,minz=2x,1,-2x,2,+3x,3,-,x,1,+x,2,+x,3,=4,-2x,1,+x,2,-x,3,6,x,1,0,x,2,0,x,3,取值无约束,第,一,章：线性规划及单纯形法,第一章：线性规划及单纯形法,线性规划问题及其数学模型,线性规划图解法,单纯形法原理,单纯形法计算步骤,单纯形法的进一步讨论,400,200,100,100,200,300,400,300,0,x,1,x,2,第,一,章：线性规划及单纯形法,2x,1,+x,2,=400,x,2,=250,x,1,+x,2,=300,目标函数maxz=50 x,1,+100 x,2,约束条件：,x,1,+x,2,300,2x,1,+x,2,400,x,2,250,非负约束：,x,1,0,，,x,2,0,400,200,100,100,200,300,400,300,0,x,1,x,2,2x,1,+x,2,=400,x,2,=250,x,1,+x,2,=300,第,一,章：线性规划及单纯形法,可行域,400,200,100,100,200,300,400,300,0,x,1,x,2,2x,1,+x2=400,x,2,=250,x,1,+x,2,=300,Z=0=50 x,1,+100 x,2,Z=1000=50 x,1,+100 x,2,Z=20000=50 x,1,+100 x,2,Z=27500=50 x,1,+100 x,2,第,一,章：线性规划及单纯形法,等值线,线性规划问题解的几种情况,线性规划存在唯一最优解,线性规划存在有无穷多个最优解的情况,线性规划可能存在无界解,线性规划存在无可行解的情况,第,一,章：线性规划及单纯形法,练习：,P43,：,1.1,（,1,）（,2,）,第,一,章：线性规划及单纯形法,第一章：线性规划及单纯形法,线性规划问题及其数学模型,线性规划图解法,单纯形法原理,单纯形法计算步骤,单纯形法的进一步讨论,基本概念：,可行解,最优解,基,基解,基可行解,可行基,第一章：线性规划及单纯形法,解的几何意义,例,:,线性规划问题基本可行解的意义：,第一章：线性规划及单纯形法,解的几何意义,第一章：线性规划及单纯形法,解的几何意义,第一章：线性规划及单纯形法,解的几何意义,第一章：线性规划及单纯形法,解的几何意义,第一章：线性规划及单纯形法,解的几何意义,第一章：线性规划及单纯形法,解的几何意义,第一章：线性规划及单纯形法,算法思路,求一个初始基本可行解,是,判断基本可行解是否最优,结 束,不是,求使目标得到改善的基本可行解,是否存在？,如何得到？,是否唯一？,如何判断？,如何改善？,如何判断没有有限最优解？,第一章：线性规划及单纯形法,基本定理,定理,1,若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。,定理,2,线性规划问题的基可行解,x,对应线性规划问题可行域,(,凸集,),的顶点,定理,3,若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解，如果在几个顶点上都出现最优解，则这些顶点的每个凸组合上也达到最优。,第一章：线性规划及单纯形法,凸集的概念,1,、基本概念：,凸集,设,K,是,n,维欧氏空间的一个点,集，若任意两点,X,（,1,）,K,，,X,（,2,）,K,的,连线上的一切点：,X,（,1,）,+,（,1-,）,X,（,2,）,K,（,01,），则称,K,为,凸集,。,第一章：线性规划及单纯形法,凸集的概念,凸组合,设,X,（,1,）,，,X,（,2,）,，,，,X,（,k,）,是,n,维欧氏空间中的,K,个点，若存在,k,个数,1,，,2,，,，,k,满足,0,i,1,i=1,2,k,；,则称,X=,1,X,（,1,）,+,2,X,（,2,）,+,+,k,X,(k),为,X,（,1,）,，,X,（,2,）,，,，,X,（,k,）,的,凸组合,。,顶点,设,K,是凸集，,X,K,；若,K,中不存在两个不同的点,X,（,1,）,K,，,X,（,2,）,K,使,X=X,（,1,）,+,（,1-,）,X,（,2,）,（,00,d,1,+,0,d,2,-,=0,d,2,-,0,(810,1476),目标规划的这种求解方法可以表述如下：,1,确定解的可行区域。,2,对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。,3,对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。,4.,重复第,3,步，直至所有优先权的目标求解完。,目标规划模型的标准化,例,6,中对两个不同优先权的目标单独建立线性规划进行求解。为简,便，把它们用一个模型来表达，如下：,Min P,1,（,d,1,+,）,+P,2,（,d,2,-,）,s.t.,20 x,1,50 x,2,90000,0.5x,1,+0.2x,2,-d,1,+,+d,1,-,=700,3x,1,+4x,2,-d,2,+,+d,2,-10000,x,1,x,2,d,1,+,d,1,-,d,2,+,d,2,-,0,复杂情况下的目标规划,例,7,一工艺品厂商手工生产某两种工艺品,A,、,B,，已知生产一件产品,A,需要耗费人力,2,工时，生产一件产品,B,需要耗费人力,3,工时。,A,、,B,产品的单位利润分别为,250,元和,125,元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于,600,工时，但也不能超过,680,工时的极限；次要任务是要求每周的利润超过,70000,元；在前两个任务的前提下，为了保证库存需要，要求每周产品,A,和,B,的产量分别不低于,200,和120,件，因为,B,产品比,A,产品更重要，不妨假设,B,完成最低产量,120,件的重要性是,A,完成,200,件的重要性的,1,倍。,试求如何安排生产？,解：本问题中有,3,个不同优先权的目标，不妨用,P,1,、,P,2,、,P,3,表,示从高至低的优先权。,对应,P,1,有两个目标：每周总耗费人力资源不能低于,600,工,时,也不能超过,680,工时；,对应,P,2,有一个目标：每周的利润超过,70000,元；,对应,P,3,有两个目标：每周产品,A,和,B,的产量分别不低于,200,和,120,件。,采用简化模式，最终得到目标线性规划如下：,Min P,1,(d,1,+,)+P,1,d,2,)+P,2,(d,3,-,)+P,3,(d,4,-,)+P,3,(2d,5,-,),s.t.,2x,1,+3x,2,-d,1,+,+d,1,-,=680,对应第,1,个目标,2x,1,+3x,2,-d,2,+,+d,2,-,=600,对应第,2,个目标,250 x,1,+125x,2,-d,3,-,+d,3,+,70000,对应第,3,个目标,x,1,-d,4,+,+d,4,-,=200,对应第,4,个目标,x,2,-d,5,+,+d,5,-,=120,对应第,5,个目标,x,1,x,2,d,1,+,d,1,-,d,2,+,d,2,-,d,3,+,d,3,-,d,4,+,d,4,-,d,5,+,d,5,-,0,使用运筹学软件求解可得：,x,1,=250,；,x,2,=60,；,d,1,+,=0,；,d,1,-,=0,；,d,2,+,=80,；,d,2,-,=0,；,d,3,+,=0,；,d,3,-,=0,；,d,4,+,=50,；,d,4,-,=0,；,d,5,+,=0,；,d,5,-,=60,，目标函数,d,4,-,+2d,5,-,=120,。,可见，目标,1,、目标,3,和目标,4,达到了，但目标,2,、目标,5,都有一些偏差。,加权目标规划,加权目标规划,是另一种解决多目标决策问题的方法，其基本方法是通过,量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总,的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加,权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的,要求，那么，整个问题都可以描述为一个线性规划的问题。,如果在例,7,中我们对每周总耗费的人力资源超过,680,工时或低于,600,工时,的每工时罚数权重定为,7,；每周利润低于,70000,元时，每元的罚数权重为,5,；每周产品,A,产量低于,200,件时每件罚数权重为,2,，而每周产品,B,产量低,于,120,件时每件罚数权重为,4,。,则其目标函数化为：,min7d,1,+,+7d,2,-,+5d,3,-,+2d,4,-,+4d,5,-,这就变成了一个普通的单一目标的线性规划问题,min7d,1,+,+7d,2,-,+5d,3,-,+2d,4,-,+4d,5,-,s.t.2x,1,+3x,2,-d,1,+,+d,1,-,=680,2x,1,+3x,2,-d,2,-,+d,2,+,=680,250 x,1,+125x,2,-d,3,-,+d,3,+,=70000,x,1,-d,4,+,+d,4,-,=200,x,2,-d,5,+,+d,5,-,=120,x,1,x,2,d,1,+,d,1,-,d,2,-,d,2,+,d,3,+,d,3,-,d,4,+,d,4,-,d,5,+,d,5,-,0,。,第八章 整数规划,在整数规划中，如果所有的变量都为非负整数，则称为,纯整数规划问题,；如果有一部分变量为负整数，则称之,为,混合整数规划问题,。在整数规划中，如果变量的取值,只限于,0,和,1,，这样的变量我们称之为,0-1,变量,。在纯整数,规划和混合整数规划问题中，如果所有的变量都为,0-1,变,量，则称之为,0-1,规划,。,第五章 整数规划,整数规划的图解法,例,:,某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。,甲种货物至多托运,4,件，问两种货物各托运多少件，可使获得利润最大。,解：设,x,1,、,x,2,分别为甲、乙两种货物托运的件数，建立模型,目标函数：,Max z=2x,13 x,2,约束条件：,195,x,1,+273 x,2,1365,4,x,1,+40 x,2,140,x,1,4,x,1,，,x,2,0,为整数。,如果去掉最后一个约束，就是一个线性规划问题。利用图解法，,货物,每件体积,（立方英尺）,每件重量,（百千克）,每件利润,（百元）,甲,乙,195,273,4,40,2,3,托运限制,1365,140,得到线性规划的最优解为,x,1,=2.44,x,2,=3.26,目标函数值为,14.66,。由图表可,看出，整数规划的最优解为,x,1,=4,x,2,=2,目标函数值为,14,。性质,1,：任何求最,大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相,应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混,合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数,值。,1,2,3,4,1,2,3,2x,1,+3x,2,=14.66,x,1,x,2,2x,1,+3x,2,=14,2x,1,+3x,2,=6,整数规划的图解法,例,2,：,Max z=3,x,1,+,x,2,+3,x,3,s.t.,-,x,1,+2,x,2,+,x,3,4,4,x,2,-3,x,3,2,x,1,-3,x,2,+2,x,3,3,x,1,x,2,x,3,0,为整数,例,3,：,Max z=3x,1,+x,2,+3x,3,s.tx,1,+2x,2,+x,3,4,4x,2,-3x,3,2,x,1,-3x,2,+2x,3,3,x,3,1,x,1,x,2,x,3,0,x,1,，,x,3,为整数,x,3,为,0-1,变量,用,管理运筹学,软件求解得：,x,1,=5,x,2,=2,x,3,=2,用,管理运筹学,软件求解得：,x,1,=4,x,2,=1.25,x,3,=1,z=16.25,整数规划的计算机求解,整数规划的应用,投资场所的选择,例,4,、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有,10,个位置,A,j,(j,1,，,2,，,3,，,，,10),可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：,在东区由,A,1,，,A,2,，,A,3,三个点至多选择两个；,在西区由,A,4,，,A,5,两个点中至少选一个；,在南区由,A,6,，,A,7,两个点中至少选一个；,在北区由,A,8,，,A,9,，,A,10,三个点中至少选两个。,A,j,各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示,(,单位：万元,),。但投资总额不能超过,720,万元，问应选择哪几个销售点，可使年利润为最大,?,解：,设：,0-1,变量,x,i,=1(A,i,点被选用）或,0,(,A,i,点没被选用）。这样我们可建立如下的数学模型：,Max z=36,x,1,+40,x,250,x,3,+22,x,4,+20,x,5,+30,x,6,+25,x,7,+48,x,8,+58,x,9,+61,x,10,s.t.,100,x,1,+120,x,2,+150,x,3,+80,x,4,+70,x,5,+90,x,6,+80,x,7,+140,x,8,+160,x,9,+180,x,10,720,x,1,+,x,2,+,x,3,2,x,4,+,x,5,1,x,6,+,x,7,1,x,8,+,x,9,+,x,10,2,x,i,0,且,x,i,为,0-1,变量,，,i,=1,2,3,10,固定成本问题,例,5,高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金,属板劳动力和机器设备，制造一个容器所需的各种资源的数量如表所,示。不考虑固定费用，每种容器售出一只所得的利润分别为,4,万元、,5,万,元、,6,万元，可使用的金属板有,500,吨，劳动力有,300,人,/,月，机器有,100,台,/,月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小,号是,l00,万元，中号为,150,万元，大号为,200,万元。现在要制定一个生产计,划，使获得的利润为最大。,解：这是一个整数规划的问题。,设,x,1,，,x,2,，,x,3,分别为小号容器、中号容器和大号容器的生产数量。各,种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的,这种性质设,y,i,=1(,当生产第,i,种容器,即,x,i,0,时,),或,0（,当不生,产第,i,种容器即,x,i,=0,时）。引入约束,x,i,M,y,i,，,i=1,，,2,，,3,，,M,充分大，以保证当,y,i,=0,时，,x,i,=0,。,这样我们可建立如下的数学模型：,Max z=4,x,1,+5,x,2,+6,x,3,-100y,1,-150y,2,-200y,3,s.t.2,x,1,+4,x,2,+8,x,3,500,2,x,1,+3,x,2,+4,x,3,300,x,1,+2,x,2,+3,x,3,100,x,i,M,y,i,，,i=1,，,2,，,3,，,M,充分大,x,j,0,y,j,为,0-1,变量,，,i,=1,2,3,指派问题,有,n,项不同的任务，恰好,n,个人可分别承担这些任务，但由于每人,特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人,去完成一项任务，怎样把,n,项任务指派给,n,个人，使得完成,n,项任,务的总的效率最高，这就是,指派问题。,例,6,有四个工人，要分别指派他们完成四项不同的工作，每人做各项,工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时,间为最少。,解：引入,0,1,变量,x,ij,，,并令,x,ij,=1(,当指派第,i,人去完成第,j,项工作,时,),或,0,（当不指派第,i,人去完成第,j,项工作时,),这可以表示为一个,0-1,整数规划问题：,Minz=15,x,11,+18,x,12,+21,x,13,+24,x,14,+19,x,21,+23,x,22,+22,x,23,+18,x,24,+26,x,31,+17,x,32,+16,x,33,+19,x,34,+19,x,41,+21,x,42,+23,x,43,+17,x,44,s.t.,x,11,+,x,12,+,x,13,+,x,14,=1 (,甲只能干一项工作,),x,21,+,x,22,+,x,23,+,x,24,=1 (,乙只能干一项工作,),x,31,+,x,32,+,x,33,+,x,34,=1 (,丙只能干一项工作,),x,41,+,x,42,+,x,43,+,x,44,=1 (,丁只能干一项工作,),x,11,+,x,21,+,x,31,+,x,41,=1 (A,工作只能一人干,),x,12,+,x,22,+,x,32,+,x,42,=1 (B,工作只能一人干,),x,13,+,x,23,+,x,33,+,x,43,=1 (C,工作只能一人干,),x,14,+,x,24,+,x,34,+,x,44,=1 (D,工作只能一人干,),x,ij,为,0-1,变量,，,i,j,=1,2,3,4,*,求解可用,管理运筹学,软件中整数规划方法。,分布系统设计,例,7,某企业在,A,1,地已有一个工厂，其产品的生产能力为,30,千箱，为了,扩大生产，打算在,A,2,，,A,3,，,A,4,，,A,5,地中再选择几个地方建厂。已知在,A,2,，,A,3,，,A,4,，,A,5,地建厂的固定成本分别为,175,千元、,300,千元、,375,千元、,500,千元，另外，,A,1,产量及,A,2,，,A,3,，,A,4,，,A,5,建成厂的产量，那时销地的销量,以及产地到销地的单位运价,(,每千箱运费,),如下表所示。,a),问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小,?,b),如果由于政策要求必须在,A,2,，,A,3,地建一个厂，应在哪几个地方建厂,?,解：,a),设,x,ij,为从,A,i,运往,B,j,的运输量,(,单位千箱,),，,y,k,=1(,当,A,k,被选中时,),或,0,（当,A,k,没被选中时,),k,=2,3,4,5,这可以表示为一个整数规划问题：,Min z=175,y,2,+300,y,3,+375,y,4,+500,y,5,+8,x,11,+4,x,12,+3,x,13,+5,x,21,+2,x,22,+3,x,23,+4,x,31,+,3,x,32,+4,x,33,+9,x,41,+7,x,42,+5,x,43,+10,x,51,+4,x,52,+2,x,53,其中前,4,项为固定投资额，后面的项为运输费用。,s.t.,x,11,+,x,12,+,x,13,30 (A,1,厂的产量限制,),x,21,+,x,22,+,x,23,10,y,2,(A,2,厂的产量限制,),x,31,+,x,32,+,x,33,20,y,3,(A,3,厂的产量限制,),x,41,+,x,42,+,x,43,30,y,4,(A,4,厂的产量限制,),x,51,+,x,52,+,x,53,40,y,5,(A,5,厂的产量限制,),x,11,+,x,21,+,x,31,+,x,41,+,x,51,=30 (B,1,销地的限制,),x,12,+,x,22,+,x,32,+,x,42,+,x,52,=20 (B,2,销地的限制,),x,13x,23,+,x,33,+,x,43,+,x,53,=20 (B,3,销地的限制,),x,ij,0,，,i,=1,2,3,4,5,；,j,=1,2,3,，,y,k,为,0-1,变量，,k,=2,3,4,5,。,*求解可用,管理运筹学,软件中整数规划方法。,投资问题,例,8,某公司在今后五年内考虑给以下的项目投资。已知：,项目,A,：,从第一年到第四年每年年初需要投资，并于次年末回收本利,115%,，,但要求第一年投资最低金额为,4,万元，第二、三、四年不限；,项目,B,：,第三年初需要投资，到第五年末能回收本利,128,，但规定最低投资,金额为,3,万元，最高金额为,5,万元；,项目,C第二年初需要投资，到第五年末能回收本利,140%,，但规定其投资额,或为,2,万元或为,4,万元或为,6,万元或为,8,万元。,项目,D,：,五年内每年初可购买公债，于当年末归还，并加利息,6%,，此项投资,金额不限。,该部门现有资金,10,万元，问它应如何确定给这些项目的每年投资额，,使到第五年末拥有的资金本利总额为最大,?,解：,1),设,x,iA,、,x,iB,、,x,iC,、,x,iD,(i,1,，,2,，,3,，,4,，,5),分别表示第,i,年年初给项,目,A,，,B,，,C,，,D,的投资额；设,y,iA,，,y,iB,，是,0,1,变量，并规定取,1,时分别表,示第,i,年给,A,、,B,投资，否则取,0,（,i=1,2,3,4,5,）。,设,y,iC,是非负整数变量，并规定：第,2,年投资,C,项目,8,万元时,，,取值为,4,；,第,2,年投资,C,项目,6,万元时，取值,3,；第,2,年投资,C,项目,4,万元时，取值,2,；第,2,年,投资,C,项目,2,万元时，取值,1,；第,2,年不投资,C,项目时，取值,0,；,这样我们建立如下的决策变量：,第,1,年 第,2,年 第,3,年 第,4,年 第,5,年,A,x,1A,x,2A,x,3A,x,4A,B,x,3B,C x,2C,=20000y,2C,D x,1D,x,2D,x,3D,x,4D,x,5D,2,）约束条件：,第一年：年初有,100000,元，,D,项目在年末可收回投资，故第一年年初应把全部资金投,出去，于是,x,1A,+,x,1D,=100000,；,第二年：,A,的投资第二年末才可收回，故第二年年初的资金为,1.06,x,1D,，于是,x,2A,+,x,2C,+,x,2D,=1.06,x,1D,；,第三年：年初的资金为,1.15,x,1A,+1.06,x,2D,，于是,x,3A,+,x,3B,+,x,3D,=1.15,x,1A,+1.06,x,2D,；,第四年：年初的资金为,1.15,x,2A,+1.06,x,3D,，于是,x,4A,+,x,4D,=1.15,x,2A,+1.06,x,3D,；,第五年：年初的资金为,1.15,x,3A,+1.06,x,4D,，于是,x,5D,=1.15,x,3A,+1.06,x,4D,。,关于项目,A,的投资额规定,:,x,1A,40000,y,1A,，,x,1A,200000,y,1A,，,200000,是足,够大的数；保证当,y,1A,=0,时，,x,1A,=0,；当,y,1A,=1,时，,x,1A,40000,。,关于项目,B,的投资额规定,:,x,3B,30000,y,3B,，,x,3B,50000,y,3B,；,保证当,y,3B,=0,时，,x,3B,=0,；当,y,3B,=1,时，,50000,x,3B,30000,。,关于项目,C,的投资额规定,:,x,2C,=20000,y,2C,，,y,2C,=0,，,1,，,2,，,3,，,4,。,3,）,目标函数及模型：,Max z=1.15,x,4A,+1.40,x,2C,+1.28,x,3B,+1.06,x,5D,s.t.,x,1A,+,x,1D,=100000,；,x,2A,+,x,2C,+,x,2D,=1.06,x,1D,；,x,3A,+,x,3B,+,x,3D,=1.15,x,1A,+1.06,x,2D,；,x,4A,+,x,4D,=1.15,x,2A,+1.06,x,3D,；,x,5D,=1.15,x,3A,+1.06,x,4D,；,x,1A,40000y,1A,，,x,1A,200000,y,1A,，,x,3B,30000,y,3B,，,x,3B,50000,y,3B,；,x,2C,=20000,y,2C,，,y,iA,，,y,iB,=0,或,1,，,i=1,2,3,4,5,y,2C,=0,，,1,，,2,，,3,，,4,x,iA,，,x,iB,，,x,iC,，,x,iD,0 (i=1,、,2,、,3,、,4,、,5,）,第八章 图与网络分析,图论中图是由点和边构成，可以反映一些对象之间的关系。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图,11-1,就是一个表示这种关系的图。,(v,1,),赵,(v,2,),钱,(v,3),孙,(v,4,),李,(v,5,),周,(v,6,),吴,(v,7,),陈,e,2,e,1,e,3,e,4,e,5,图与网络的基本概念,当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图,11-2,来表示，可见图论中的图与几何图、工程图是不一样的。,(v,1,),赵,(v,2,),钱,孙,(v,3,),李,(v,4,),周,(v,5,),吴,(v,6,),陈,(v,7,),e,2,e,1,e,3,e,4,e,5,图,11-2,图与网络的基本概念,图与网络的基本概念,a,1,a,2,a,3,a,4,a,14,a,7,a,8,a,9,a,6,a,5,a,10,a,12,a,11,a,13,a,15,(v,1,),赵,(v,2,),钱,(v,3,),孙,(v,4,),李,(v,5,),周,(v,6,),吴,(v,7,),陈,图,11-3,如果我们把上面例子中的,“,相互认识,”,关系改为,“,认识,”,的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图,11-3,就是一个反映这七人,“,认识,”,关系的图。相互认识用两条反向的弧表示。,无向图：由点和边构成的图，记作,G=,（,V,，,E,）。,有向图：由点和弧构成的图，记作,D=,（,V,，,A,）。,连通图：对无向图,G,，若任何两个不同的点之间，至少存在一条链，则,G,为连通图。,回路：若路的第一个点和最后一个点相同，则该路为回路。,赋权图：对一个无向图,G,的每一条边,(v,i,v,j,),，相应地有一个数,w,ij,，则称图,G,为赋权图，,w,ij,称为边,(v,i,v,j,),上的权。,网络：在赋权的有向图,D,中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把,D,中的每一条弧的赋权数称为弧的容量，,D,就称为网络。,图与网络的基本概念,最短路问题,最短路问题：对一个赋权的有向图,D,中的指定的两个点,V,s,和,V,t,找到一条从,V,s,到,V,t,的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从,V,s,到,V,t,的最短路。这条路上所有弧的权数的总和被称为从,V,s,到,V,t,的距离。,一、求解最短路的,Dijkstra,算法,(,双标号法）,步骤：,1.,给出点,V,1,以标号,(0,s),2.,找出已标号的点的集合,I,，没标号的点的集合,J,以及弧的集合,3.,如果上述弧的集合是空集，则计算结束。如果,v,t,已标号（,l,t,k,t,），则,v,s,到,v,t,的距离为,l,t,，而从,v,s,到,v,t,的最短路径，则可以从,k,t,反向追踪到起点,v,s,而得到。如果,v,t,未标号，则可以断言不存在从,v,s,到,v,t,的有向路。如果上述的弧的集合不是空集，则转下一步。,4.,对上述弧的集合中的每一条弧，计算,s,ij,=l,i,+c,ij,。在所有的,s,ij,中，找到其值为最小的弧。不妨设此弧为（,V,c,V,d,），则给此弧的终点以双标号（,s,cd,c,）,返回步骤,2,。,最短路问题,例,1,求下图中,v,1,到,v,6,的最短路,解：采用,Dijkstra,算法，可解得,最短路径为,v,1,v,3,v,4,v,6,各点的标号图如下：,v,2,3,5,2,7,5,3,1,5,1,2,v,1,v,6,v,5,v,3,v,4,(31),v,2,3,5,2,7,5,3,1,5,1,2,V,1,（,0,s),v,5,(8,4),v,6,(2,1),v,3,(3,3),v,4,例,2,电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架,设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示,两地间公路的长度（单位：公里）。,解：这是一个求无向图的最短路的问题。可以把无向图的每一边,（,v,i,v,j,）都用方向相反的两条弧（,v,i,v,j,）和（,v,j,v,i,）代替，就化为,有向图，即可用,Dijkstra,算法来求解。也可直接在无向图中用,Dijkstra,算,法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已,标号的点到未标号的点的边的集合即可。,V,1,（甲地）,15,17,6,2,4,4,3,10,6,5,v,2,V,7,（乙地）,v,3,v,4,v,5,v,6,例,2,最终解得：,最短路径,v,1,v,3,v,5,v,6,v,7,，每点的标号见下图,（,0,s,）,V,1,（甲地）,15,17,6,2,4,4,3,10,6,5,(13,3),v,2,(22,6),V,7,（乙地）,V,5,(14,3),V,6,(16,5),V,3,(10,1),V,4,(18,5),例,3,设备更新问题。某公司使用一台设备，在每年年初，公司就,要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就,要支付一定的购置费，当然新设备的维修费用就低。如果继续使用,旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之,内的更新设备的计划，使得五年内购置费用和维修费用总的支付费,用最小。已知：设备每年年初的价格表,设备维修费如下表,年份,1,2,3,4,5,年初价格,11,11,12,12,13,使用年数,0-1,1-2,2-3,3-4,4-5,每年维修费用,5,6,8,11,18,例,3,的解：将问题转化为最短路问题，如下图：,用,v,i,表示,“,第,i,年年初购进一台新设备,”,弧（,v,i,v,j,）表示第,i,年年初购进的,设备一直使用到第,j,年年初。,把所有弧的权数计算如下表：,v,1,v,2,v,3,v,4,v,5,v,6,1,2,3,4,5,6,1,16,22,30,41,59,2,16,22,30,41,3,17,23,31,4,17,23,5,18,6,(,继上页,),把权数赋到图中，再用,Dijkstra,算法求最短路。,最终得到下图，可知，,v,1,到,v,6,的距离是,53,，最短路径有两条：,v,1,v,3,v,6,和,v,1,v,4,v,6,v,1,v,2,v,3,v,4,v,5,v,6,16,22,30,41,59,16,22,30,41,31,23,17,18,17,23,V,1,（,0,s,）,v,3,v,4,(41,1),v,5