规划理论及模型(数模).ppt

单击此处编辑母版标题样式,下,回,停,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,一、引言,二、线性规划模型,三、整数线性规划模型,第一讲 规划理论及模型,四、,0-1,整数规划模型,五、非线性规划模型,六、多目标规划模型,七、动态规划模型,一、引言,我们从,2005,年“高教社杯”全国大学生数模竞,谈起,.,其中第二个问题是一个如何来分配有限资源，,从而达到人们期望目标的优化分配数学模型,.,它,在运筹学中处于中心的地位,.,这类问题一般可以,归结为,数学规划模型,.,赛的,B,题“,DVD,在线租赁”问题的第二问和第三问,规划模型的应用极其广泛，其作用已为越来,来越急速地渗透于工农业生产、商业活动、军事,行为核科学研究的各个方面，为社会节省的财富、,创造的价值无法估量,.,特别是在数模竞赛过程中，规划模型是最常,见的一类数学模型,.,从,92-06,年全国大学生数模竞,越多的人所重视,.,随着计算机的逐渐普及，它越,赛试题的解题方法统计结果来看，规划模型共出,现了,15,次，占到了,50%,，也就是说每两道竞赛题,中就有一道涉及到利用规划理论来分析、求解,.,二、线性规划模型,线性规划模型是所有规划模型中最基本、最,例,1.,（,食谱问题）设有,n,种食物，各含,m,种营养,素，第,j,种食物中第,i,中营养素的含量为,a,ij,n,种,食物价格分别为,c,1,c,2,c,n,，,请确定食谱中,n,种食,物的数量,x,1,x,2,x,n,，,要求在食谱中,m,种营养素,简单的一种,.,2.1,线性规划模型的标准形式,的含量分别不低于,b,1,b,2,b,m,的情况下，使得总,总的费用最低,.,首先根据食物数量及价格可写出食谱费用为,其次食谱中第,i,种营养素的含量为,因此上述问题可表述为：,解,上述食谱问题就是一个典型的线性规划问题，,寻求以线性函数的最大（小）值为目标的数学模,型.,它是指在一组线性的等式或不等式的约束条件下，,线性规划模型的三种形式,一般形式,目标函数,价值向量,价值系数,决策变量,右端向量,系,数,矩,阵,非负约束,自由变量,规范形式,标准形式,三种形式的,LP,问题全都是等价的，即一种形式的,LP,可以简单的变换为另一种形式的,LP,，,且它们有相同的解,.,以下我们仅将一般形式化成规范形式和标准形式,.,目标函数的转化,x,o,z,-z,约束条件和变量的转化,为了把一般形式的,LP,问题变换为规范形式，我们必须消除等式约束和符号无限制变量,.,在一般形式的,LP,中，一个等式约束,可用下述两个不等式约束去替代,这样就把一般形式的,LP,变换为规范形式,.,对于一个无符号限制变量 ，引进两个非负变量 和 ，并设,为了把一般形式的,LP,问题变换为标准形式，必须消除其不等式约束和符号无限制变量,.,对于一个不等式约束,代替上述的不等式约束,.,对符号无限制变量的处理可按上述方法进行,.,可引入一个,剩余变量,，,用,对于不等式约束,代替上述的不等式约束,这样就把一般形式的,LP,变换为标准形式,.,可引入一个,松弛变量,，用,针对标准形式的线性规划问题，其解的理论,分析已经很完备，在此基础上也提出了很好的算,单纯形方法是线性规划问题的最为基础、也,法,单纯形方法及其相应的变化形式（两阶段,2.2,线性规划模型的求解,法，对偶单纯形法等）,.,是最核心的算法。它是一个迭代算法，先从一个,特殊的可行解（极点）出发，通过判别条件去判,断该可行解是否为最优解（或问题无界），若不,是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无界）,.,关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献,1.,然后在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式,.,比较常用的求解线性规划模型的软件包有,LINGO,和,LINDO.,运输问题,例,2.,设要从甲地调出物资,2000,吨，从乙地调出物,资,1100,吨，分别供给,A,地,1700,吨、,B,地,1100,吨、,C,假定运费与运量成正比,.,在这种情况下，采用不,地,200,吨、,D,地,100,吨,.,已知每吨运费如表,1.1,所示,.,同的调拨计划，运费就可能不一样,.,现在问：怎,样才能找出一个运费最省的调拨计划？,15,7,25,21,甲,15,37,51,51,乙,D,C,B,A,表,1.1,销,地,运,费,产,地,乙,甲,D,C,B,A,解,一般的运输问题可以表述如下：,数学模型：,若其中各产地的总产量等于各销地的总销量，即,类似与将一般的线性规划问题转化为其标准,否则，称为不平衡的运输问题，包括：,，则称该问题为平衡的运输问题,.,总产量,总销量和总产量,总销量,.,形式，我们总可以通过引入假想的销地或产地，,将不平衡的运输问题转化为平衡的运输问题,.,从,而，我们的重点就是解决平衡运输问题的求解,.,显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解,.,但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解,.,关于运输问题及其解法的进一步介绍参加文献,2.,对于线性规划问题，如果要求其决策变量取,整数值，则称该问题为整数线性规划问题,.,平面法和分支定界法是两种常用的求解整数线性,对于整数线性规划问题的求解，其难度和运,三、整数线性规划模型,算量远大于同规模的线性规划问题,.,Gomory,割,规划问题的方法（见文献,1,）,.,此外，同线性规,划模型一样，我们也可以运用,LINGO,和,LINDO,软,件包来求解整数线性规划模型,.,以,1988,年美国大学生数学建模竞赛,B,题为例，说明整数线性规划模型的建立及用,LINGO,软件包如何求解整数线性规划模型。,例,3.,有七种规格的包装箱要装到两节铁路平板车,上去。包装箱的宽和高是一样的，但厚度（,t,，以,cm,计）及重量（,w,，以,kg,计）是不同的,.,表,1,给出,了每种包装箱的厚度、重量以及数量。每节平板,车有,10.2,m,长的地方可用来装包装箱（像面包片,那样），载重为,40,t,.,由于当地货运的限制，对于,C,5,C,6,C,7,类包装箱的总数有一个特别的限制：这,类箱子所占的空间（厚度）不能超过,302.7,cm,.,试,把包装箱装到平板车上，使得浪费的空间最小,.,种类,C,1,C,2,C,3,C,4,C,5,C,6,C,7,t,/,cm,48.7,53.0,61.3,72.0,48.7,52.0,64.0,w,/,kg,2000,3000,1000,500,4000,2000,1000,n,/,件,8,7,9,6,6,4,8,为在第 节车上装载第 件包装箱的,解,令,下面我们建立该问题的整数线性规划模型。,1),约束条件,两节车的装箱数不能超过需要装的件数，即：,每节车可装的长度不能超过车能提供的长度：,每节车可装的重量不超过车能够承受的重量：,对于,C,5,C,6,C,7,类包装箱的总数的特别限制：,2),目标函数,浪费的空间最小，即包装箱的总厚度最大：,3),整数线性规划模型,由上一步中的求解结果可以看出，,4),模型求解,运用,LINGO,软件求解得到：,5),最优解的分析说明,的装车方案，此时装箱的总长度为,1019.7,cm,，,两节车共装箱的总长度为,2039.4,cm,.,即为最优,但是，上述求解结果只是其中一种最优的,装车方案，即此答案并不唯一,.,0-1,整数规划是整数规划的特殊情形，它要求,线性规划模型中的决策变量,x,ij,只能取值为,0,或,1.,单隐枚举法，该方法是一种基于判断条件（过滤,0-1,整数规划模型的求解目前并没有非常好的,四、,0-1,整数规划模型,算法，对于变量比较少的情形，我们可以采取简,条件）的穷举法,.,我们也可以利用,LINGO,和,LINDO,软件包来求,解,0-1,整数规划模型,.,背包问题,例,4.,有,n,个物品，编号为,1,2,n,，第,i,件物品,重,a,i,千克，价值为,c,i,元，现有一个载重量不超过,大，应如何装载这些物品？,a,千克的背包，为了使装入背包的物品总价值最,用变量,x,i,表示物品,i,是否装包，,i,=,1,2,n,，,并令：,解,可得到背包问题的规划模型为：,指派问题,例,5.,有,n,项任务，由,n,个人来完成，每个人只能,做一件，第,i,个人完成第,j,项任务要,c,ij,小时，如,何合理安排时间才能使总用时最小？,引入状态变量,x,ij,，并令：,解,则总用时表达式为：,可得到指派问题的规划模型为：,上面介绍的指派问题称为指派问题的标准形,式，还有许多其它的诸如人数与任务数不等、及,但一般可以通过一些转化，将其变为标准形式,.,某人可以完成多个任务，某人不可以完成任务，,某任务必须由某人完成等特殊要求的指派问题,.,对于标准形式的指派问题，我们可以利用匈,牙利算法实现求解,.,它将指派问题中的系数构成,一个矩阵，利用矩阵上简单的行和列变换，结合,解的判定条件，实现求解（见文献,2,）,.,DVD,在线租赁第二个问题的求解,问题二的分析,经营成本和会员的满意度是被考虑的两个相互制约的重要因素,.,在忽略邮寄成本的前提下，经营成本主要体现为,DVD,的数量,.,我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量,DVD,进行分配决策，使得,DVD,的数量尽量小，会员满意度最大,.,假设按照公历月份进行的租赁业务，即会员无论两次租赁还是一次租赁，必须在当月内完成,DVD,的租与还,.,同时假设网站对其会员进行一次租赁业务时，只能向其提供,3,张该会员已经预定的,DVD,，否则不进行租赁,.,经观察，可以认为在线订单中每个会员的预定,DVD,的表示偏好程度的数字反映了会员对所预定不同,DVD,的满意程度，且当会员租到其预定排序为,1,，,2,，,3,的三张,DVD,时，满意度达到,100%.,会员没有预定的,DVD,对其满意度的贡献为,0.,利用层次分析法，对此满意指数的合理性进,行了简单分析,.,该问题要求根据现有的,100,种,DVD,的数量和当前需要处理的,1000,位会员的在线订单，制定分配策略，使得会员达到最大的满意度,.,因而我们认为只需对这些,DVD,进行一次性分配，使得会员的总体满意度达到最大,.,为此考虑建立优化模型，进行求解,.,问题二的模型及求解,经营成本和会员的满意度是被考虑的两个相互制约的重要因素,.,在忽略邮寄成本的前提下，经营成本主要体现为,DVD,的数量,.,我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量,DVD,进行分配决策，使得,DVD,的数量尽量小，会员满意度最大,.,由此，可得问题二的,0-1,整数线性规划模型如下：,根据所得的,0-1,整数线性规划模型，利用,LINGO,软件进行求解，我们得到了一组最优分配方案（见表,3,）,.,该组最优解其目标函数会员总体最大满意度为,91.56%,，只有,6,人未成功租赁（如：前,30,名会员中,C0008,被分配到,DVD,），其余,994,个会员全都得到了,3,张预定的,DVD,.,再见,