(精品)运筹学运筹演示2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,复习第一章、第二章内容,例,1,：某工厂生产,、,两种型号计算机，为了生产一台,型和,型计算机，所需要原料分别为,2,个单位和,3,个单位，需要的工时分别为,4,个单位和,2,个单位，在计划期内可以使用的原料为,100,个单位，工时为,120,个单位。已知生产每台,、,型计算机可获利,6,个单位和,4,个单位，试确定获利最大的生产方案。,原料,工时,利润,型,2,4,6,型,3,2,4,资源限制,100,120,求解线性规划的方法：,1.,图解法,2.,单纯形法,3.,大,M,法,4.,对偶单纯形法,例,2.,minZ,=15x,1,+24x,2,+5x,3,6x,2,+x,3,2,5,x,1,+2x,2,+x,3,1,x,1,，,x,2,，,x,3,0,第三章 运输问题,第一节 平衡运输问题的数学模型,运输问题的提出,例：某公司经销甲产品，该产品有三个加工厂，产量分别为,7,、,4,、,9,吨，该产品有四个销售地点，销售量为,3,、,6,、,5,、,6,吨，已知单位定价，问如何在满足各销售点的需求量的前提下，使花费最小？,销地,产地,B1,B2,B3,B4,产量,A1,A2,A3,3,1,7,11,9,4,3,2,10,10,8,5,7,4,9,销量,3,6,5,6,一般运输问题的提出,:,某种物资有,m,个产地,A,1,、,A,2,A,m,，其产量分别为,a,1,、,a,2,a,m,，有,n,个销地,B,1,、,B,2,B,n,，其销量分别为,b,1,、,b,2,b,m,，现需要把这种物资从各个产地运往各个销地，假设产销平衡,a,i,=,b,j,，且每个产地到每个销地的单位货物运价为,C,ij,，问如何调运，才能使总的运费最省。,已知有,m,个生产地点,A,i,（,i=1,，,2m,），其产量分别为,ai,；有,n,个销售地点,B,j,（,j=1,，,2n,），其销量分别为,b,j,，假设产销平衡，且从,A,i,到,B,j,运输单位物资运价为,C,ij,，可以汇总数据得到产销平衡表：,销地,产地,B,1,B,2,B,n,产量,A,1,A,2,A,m,C,11,C,21,C,m1,C,12,C,22,C,m2,C,1n,C,2n,C,mn,a,1,a,2,a,m,销量,b,1,b,2,b,n,第二节 表上作业法,一、基本概念,1.,闭回路：从起点出发经过另外几个点回到始点的变量集合。,2.,数字格（基格）：在调运方案中，分配运输量的基变量的格。,3.,空格：在调运方案中，没分配运输量的非基变量的格。,4.,性质：运输问题的基变量的个数是约束条件的个数减一，即,m+n-1,个。,二、表上作业法的基本步骤,1.,编制初始方案，确定初始可行解。,使用方法：最小元素法、伏格尔法。,2.,最优性检验,使用方法：闭回路法、位势法。,3.,方案的调整,使用方法：闭回路法,例：某公司经销甲产品，该产品有三个加工厂，产量分别为,7,、,4,、,9,吨，该产品有四个销售地点，销售量为,3,、,6,、,5,、,6,吨，已知单位定价，问如何在满足各销售点的需求量的前提下，使花费最小？,销地,产地,B1,B2,B3,B4,产量,A1,A2,A3,3,1,7,11,9,4,3,2,10,10,8,5,7,4,9,销量,3,6,5,6,最小元素法,销量,产量,B1,B2,B3,B4,销量,A1,10,0,20,11,15,A2,12,7,9,20,25,A3,0,14,16,18,5,产量,5,15,15,10,第二节 产销不平衡的运输问题,1.,产量销量，虚设一个销地,B,n+1,，其销地的销量为,b,n+1,=a-b,，在令各产地到虚拟销地的单位运价为,C,in+1,=0,（,i=1,，,2m,）。,2.,产量,销量，虚设一个产地,A,m+1,，其产地的产量为,a,m+1,=b-a,，在令虚拟产地到各销地的单位运价为,C,m+1j,=0,（,j=1,，,2n,）。,例：,销地,产地,B1,B2,B3,B4,产量,A1,3,2,4,5,20,A2,7,5,2,1,10,A3,9,6,3,6,15,销量,5,10,15,5,例：已知某运输问题，要求,B,地区的,115,个单位必须满足，试求最优的调运方案。,销地,产地,A,B,C,D,E,产量,1,10,15,20,20,40,50,2,20,40,15,30,30,100,3,30,35,40,55,25,130,销量,25,115,60,30,70,例：,某化学公司有,4,个化工厂生产某种产品，产量分别为,200,、,300,、,400,、,100,吨，供应,6,个地区的需要，需求量分别为,200,、,150,、,400,、,100,、,150,、,150,吨，由于工艺技术条件的差别有关数据如表所示，要求第三个地区至少供应,300,单位，第四个地区需要必须满足，试确定该公司获利最大的产品调运方案。,销地,产地,1,2,3,4,5,6,单位成本,1,5,4,3,4,3,1,12,2,3,8,9,5,6,2,14,3,7,7,3,7,4,4,11,4,6,4,2,6,5,8,15,单位售价,20,24,18,22,16,20,运输问题应用：,一、生产计划问题,某拖拉机厂与某单位签订了生产,70,台某种型号拖拉机的合同，按合同规定明年每个季度末分别提供,10,、,15,、,25,、,20,台拖拉机，已知该厂各季度的生产能力及生产每台拖拉机的成本如表所示，如生产出来的拖拉机当季度不交货，每台每积压一个季度需要储存维护费用,0.15,万元，问该厂怎样安排各季度生产计划，既完成合同又使得总费用最少。,季节,生产能力,单位成本（万元）,1,2,3,4,25,35,30,10,10.8,11.1,11,11.3,二、资源短缺问题,销地,产地,B1,B2,B3,B4,产量,A1,16,13,22,17,50,A2,14,13,19,15,60,A3,19,20,23,-,50,最低需求,最高需求,30,50,70,70,0,30,10,不限,第四节 指派问题,一、问题的提出,有,n,个人去完成,n,项任务，每个人只能完成一项任务，且每项任务只能由一个人来完成，每人完成各项任务的效率不同如表,问如何分派任务，才能使总时间最少,?,任务,人,1,2,n,1,C,11,C,12,C,1n,2,C,21,C,22,C,2n,:,n,C,n1,C,n2,C,nn,二、匈牙利法的基本思想,对于同一个人来说，所有的任务的完成效率都提高或降低同一个常数,t,i,，不会影响最优分配，同样对同一个任务来说，让所有人去完成的效率都提高或降低同一常数,d,j,也不会影响其最优分配，从而得到新的效率矩阵为,b,ij,=,c,ij,+t,i,+d,j,。,例,1.,有一份中文说明书，需要翻译成英日德三种文字，记作,E,、,J,、,G,，有甲、乙、丙三个人他们将中文说明书翻译成不同语种的说明书所需要的时间如表所示，问应指派何人去完成何工作，使所需总时间最短？,任务,人,E,J,G,甲,乙,丙,25,15,22,31,20,19,35,24,17,1.,对指派问题的系数矩阵进行变换，使每行每列都出现,0,元素,2.,进行试指派。找出独立的,0,元素。,行搜索：从只有一个,0,元素的行开始，给这个,0,划圈，并划去该元素所在列的其他,0,元素。,列搜索：从只有一个,0,元素的列开始，给这个,0,划圈，并划去该元素所在行的其他,0,元素。,反复行列搜索，直到所有的,0,元素圈上和划去为止。,3.,若独立,0,元素个数,=,方阵的阶数，则已经找到最优方案，反之，转下步。,4.,求覆盖,0,元素的最小直线集合。,（,1,）对没有圈,0,的行的右边打,（,2,）对打的行上所有,0,元素的下方打,（,3,）对打的列上有圈,0,的行的右边打,（,4,）对没有打的行划横线，对打的列划垂线。,5.,确定调整量，在没有被直线覆盖的部分中找到最小元素,Q,，,没有被直线覆盖的元素,-Q,。,一次被直线覆盖的元素不变。,二次被直线覆盖的元素,+Q,。,例,2,施工队,工时,工程,1,2,3,4,5,升板,7,4,5,6,8,滑板,12,10,13,15,9,模板,10,9,8,11,13,多层板,15,17,20,14,11,厂房,16,14,13,18,15,例,3.,矿区,开采量,机器,1,2,3,4,1,10,15,12,5,2,12,17,12,1,3,16,20,6,2,4,4,6,3,1,例,4.,任务,利润,人,甲,乙,丙,丁,A,3,2,-2,1,B,2,-2,0,-,C,-,-1,1,0,例,5.,某公司计划开,5,家商店，为了尽早完成建设，决定由,3,家建筑公司分别承建，已知建筑公司,Ai(i,=1,2,3),对新商店,Bj(j,=1,2,3,4,5),的建造费用的报价。商业公司应对,3,家建筑公司怎样分配建造任务，才能使总的建筑费用最少？（允许每家建筑公司承建,1-2,家商店的建设）,新商店,建筑公司,B 1,B2,B3,B4,B5,A1,4,8,7,15,12,A2,7,9,17,14,10,A3,6,9,12,8,7,0-1,整数规划问题,1.,投资问题，设有,n,个投资项目，其中第,j,个项目需要资金,aj,万元，将来可获得利润,cj,万元，若现在资金总额为,b,万元，则应选择哪些投资项目才能获得利润最大？,2.,背包问题，一个旅行者要在其背包里装一些最有用的旅行物品，背包容积为,a,携带物品总重量最多为,b,现有物品,m,件，第,i,件物品体积为,ai,，重量为,bi,（,i=1,，,2,，,m),为了比较物品的有用程度，假设第,i,件物品的价值为,ci,，若每件物品只能整件携带，每件物品都能放入背包中，并且不考虑物品放入背包的相互间隙，问旅行者应带携带哪些物品，才能使携带物品的总价值最大？,第五章 动态规划,多阶段决策问题：指这样一类决策过程，它可以把复杂问题按照时间或空间分成若干阶段，每个阶段都需要进行决策，以便得到过程的最优结局。,动态规划的基本概念：,1.,阶段：一个问题需要进行决策的步数。,K=1,，,2,，,，,n,2.,状态：是各个阶段之间信息的传递点和结合点。第,k,阶段的状态,x,k,表示。,3.,决策：决策者面临不同选择而作出最后的选择。第,k,阶段,x,k,状态下的决策用,u,k,（,x,k,）表示。,允许决策集合：决策变量的取值往往限制在某一范围内，此范围称为允许决策集合。,4.,状态转移方程：由一个状态到另一个状态的演变过程。,5.,全过程：由第一阶段开始到终点为止。,子过程：由第,k,阶段开始到终点为止。,6.,指标函数：用来衡量过程优劣的效益值。,阶段指标函数：对应某一阶段的效益值,v,k,。,过程指标函数：子过程的效益值,v,k,，,n,。,7.,最优解：第,k,子过程指标函数在,x,k,状态下的最优值。用,f,k,（,x,k,）表示。,最优化原理：作为整个的最优策略具有这样的性质，无论过去的状态和决策如何，对前面形成的状态而言，余下的诸决策必构成最优策略。,动态规划的运算步骤：,1.,将问题按时间和空间的顺序划分若干阶段。,2.,正确选择状态变量。,3.,确定决策变量和允许决策集合。,4.,写出状态转移方程。,5.,建立指标函数。,6.,建立基本方程。,例,：（追加投资问题）某公司有四百万元，可以向,ABC,三个项目追加投资，不同投资额的相应效益如表，问怎样分配资金使总效益值最大？,投资,项目,0,（百万）,1,2,3,4,A,38,41,48,60,66,B,40,42,50,60,66,C,48,64,68,78,79,例：某警卫部门共有,12,只巡逻队负责,4,个要害部位的巡逻，对每个部位可分派,2-4,个巡逻队，并且巡逻队数不同，各部位预期在一段时间内可能造成的损失有差别，问该警卫部门应往各部位分派