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