线性规划整数规划规划.pptx

《线性规划整数规划规划.pptx》由会员分享，可在线阅读，更多相关《线性规划整数规划规划.pptx（54页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一、引言 我们从2005年“高教社杯”全国大学生数模竞谈起.其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型.这类问题一般可以归结为数学规划模型.赛的B题“DVD在线租赁”问题的第二问和第三问 第1页/共54页 规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量.特别是在数模竞赛过程中，规划模型是最常见的一类数学模型.从历年全国大学生数模竞赛越多的人所重视.随着计算机的逐渐普及，它越试题的解题方法统计结果来看，每年至少有一道题涉及到利用规划理论来分析、求解.第2页/共54页

2、二、线性规划模型 线性规划模型是所有规划模型中最基本、最例1.（食谱问题）设有 n 种食物，各含 m 种营养素，第 j 种食物中第 i 中营养素的含量为 aij,n 种食物价格分别为c1,c2,cn，请确定食谱中n 种食物的数量x1,x2,xn，要求在食谱中 m 种营养素简单的一种.2.1 线性规划模型的标准形式 的含量分别不低于b1,b2,bm 的情况下，使得总总的费用最低.第3页/共54页 首先根据食物数量及价格可写出食谱费用为 其次食谱中第 i 种营养素的含量为 因此上述问题可表述为：解第4页/共54页 上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模型

3、.它是指在一组线性的等式或不等式的约束条件下，第5页/共54页线性规划模型的三种形式 一般形式 目标函数价值向量价值系数决策变量右端向量系数矩阵非负约束自由变量第6页/共54页规范形式标准形式 三种形式的LP问题全都是等价的，即一种形式的LP可以简单的变换为另一种形式的LP，且它们有相同的解.以下我们仅将一般形式化成规范形式和标准形式.第7页/共54页目标函数的转化 xoz-z第8页/共54页约束条件和变量的转化为了把一般形式的LP问题变换为规范形式，我们必须消除等式约束和符号无限制变量.在一般形式的LP中，一个等式约束可用下述两个不等式约束去替代第9页/共54页这样就把一般形式的LP变换为规

4、范形式.对于一个无符号限制变量，引进两个非负变量和，并设第10页/共54页为了把一般形式的为了把一般形式的LPLP问题变换为标准形问题变换为标准形式，必须消除其不等式约束和符号无限制变式，必须消除其不等式约束和符号无限制变量量.对于一个不等式约束代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行.可引入一个剩余变量，用第11页/共54页 对于不等式约束代替上述的不等式约束这样就把一般形式的LP变换为标准形式.可引入一个松弛变量，用第12页/共54页 针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也法单纯形方法及其

5、相应的变化形式（两阶段2.2 线性规划模型的求解 法，对偶单纯形法等）.是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不第13页/共54页是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无界）.关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献1.在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式.比较常用的求解线性规划模型的软件包有LINGO和LINDO.第14页/共54页运输问题例2.设要从甲

6、地调出物资2000吨，从乙地调出物 资1100吨，分别供给A地1700吨、B地1100吨、C假定运费与运量成正比.在这种情况下，采用不地200吨、D地100吨.已知每吨运费如表1.1所示.同的调拨计划，运费就可能不一样.现在问：怎样才能找出一个运费最省的调拨计划？第15页/共54页1572521甲15375151乙DCBA表1.1销地运费产地第16页/共54页乙甲DCBA解第17页/共54页第18页/共54页一般的运输问题可以表述如下：第19页/共54页数学模型：第20页/共54页 若其中各产地的总产量等于各销地的总销量，即 类似与将一般的线性规划问题转化为其标准否则，称为不平衡的运输问题，包

7、括：，则称该问题为平衡的运输问题.总产量总销量和总产量bj 的运输问题，得到的数学模i=1j=1型为第23页/共54页m nminf=cij xiji=1j=1ns.t.xijaii=1,2,mj=1mxij=bj j=1,2,ni=1xij0(i=1,2,m;j=1,2,n)第24页/共54页只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xi,n+1i=1,2,m 即可，变为：nxij+xin+1=aii=1,2,m j=1然后，需设一个销地Bn+1,它的销量为：m nbn+1=ai-bji=1j=1第25页/共54页这里，松弛变量xi n+1可以视为从产地A i运往销地B

8、n+1的运输量，由于实际并不运送，它们的运费为 ci n+1=0i=1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。第26页/共54页2.销量大于产量的情况m n考虑aibj 的运输问题，得到的数学模型为i=1j=1m nMinf=cij xiji=1j=1 n s.t.xij=aii=1,2,mj=1m xijbjj=1,2,ni=1xij0(i=1,2,m;j=1,2,n)第27页/共54页只要在模型中的产量限制约束（后n个不等式约束）中引入n个松弛变量xm+1jj=1,2,n即可，变为：mxij+xm+1j=bjj=1,2,mi=1然后，需设一个产地A m+1,它的销量为：n

9、 m am+1=bj-aij=1 i=1第28页/共54页这里，松弛变量x m+1,j可以视为从产地A m+1运往销地Bj的运输量，由于实际并不运送，它们的运费为c m+1,j=0j=1,2,n。于是，这个运输问题就转化成了一个产销平衡的问题。第29页/共54页 显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解.但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解.关于运输问题及其解法的进一步介绍参考文献2.第30页/共54页 对于线性规划问题，如果要

10、求其决策变量取整数值，则称该问题为整数线性规划问题.平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解，其难度和运三、整数线性规划模型算量远大于同规模的线性规划问题.Gomory割规划问题的方法（见文献1）.此外，同线性规划模型一样，我们也可以运用LINGO和LINDO软件包来求解整数线性规划模型.第31页/共54页 以1988年美国大学生数学建模竞赛B题为例，说明整数线性规划模型的建立及用LINGO软件包如何求解整数线性规划模型。例3.有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以cm 计）及重量（w，以kg计）是不同的.表1给出了每种

11、包装箱的厚度、重量以及数量。每节平板车有10.2m 长的地方可用来装包装箱（像面包片那样），载重为40t.由于当地货运的限制，对于第32页/共54页C5,C6,C7 类包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm.试把包装箱装到平板车上，使得浪费的空间最小.种类种类C1C2C3C4C5C6 C7t/cm48.753.061.372.048.752.064.0w/kg2000 3000 10005004000 2000 1000n/件件8796648第33页/共54页 为在第 节车上装载第 件包装箱的解 令 下面我们建立该问题的整数线性规划模型。第34页/共54

12、页1)约束条件两节车的装箱数不能超过需要装的件数，即：每节车可装的长度不能超过车能提供的长度：每节车可装的重量不超过车能够承受的重量：第35页/共54页对于C5,C6,C7类包装箱的总数的特别限制：2)目标函数浪费的空间最小，即包装箱的总厚度最大：第36页/共54页3)整数线性规划模型第37页/共54页由上一步中的求解结果可以看出，4)模型求解运用LINGO软件求解得到：5)最优解的分析说明的装车方案，此时装箱的总长度为1019.7cm，两节车共装箱的总长度为2039.4cm.即为最优 但是，上述求解结果只是其中一种最优的装车方案，即此答案并不唯一.第38页/共54页 0-1整数规划是整数规划

13、的特殊情形，它要求线性规划模型中的决策变量xij只能取值为0或1.单隐枚举法，该方法是一种基于判断条件（过滤 0-1整数规划模型的求解目前并没有非常好的四、0-1整数规划模型 算法，对于变量比较少的情形，我们可以采取简条件）的穷举法.我们也可以利用LINGO和LINDO软件包来求解0-1整数规划模型.第39页/共54页背包问题例4.有 n 个物品，编号为1,2,n，第 i 件物品重 ai 千克，价值为 ci 元，现有一个载重量不超过大，应如何装载这些物品？a 千克的背包，为了使装入背包的物品总价值最用变量 xi 表示物品 i 是否装包，i=1,2,n，并令：解第40页/共54页可得到背包问题的

14、规划模型为：第41页/共54页指派问题例5.有n 项任务，由 n 个人来完成，每个人只能做一件，第 i 个人完成第 j 项任务要 cij 小时，如何合理安排时间才能使总用时最小？引入状态变量 xij，并令：解则总用时表达式为：第42页/共54页可得到指派问题的规划模型为：第43页/共54页 上面介绍的指派问题称为指派问题的标准形式，还有许多其它的诸如人数与任务数不等、及但一般可以通过一些转化，将其变为标准形式.某人可以完成多个任务，某人不可以完成任务，某任务必须由某人完成等特殊要求的指派问题.对于标准形式的指派问题，我们可以利用匈牙利算法实现求解.它将指派问题中的系数构成一个矩阵，利用矩阵上简

15、单的行和列变换，结合解的判定条件，实现求解（见文献2）.第44页/共54页DVDDVD在线租赁第二个问题的求解问题二的分析 经营成本和会员的满意度是被考虑的两个相互制约的重要因素.在忽略邮寄成本的前提下，经营成本主要体现为DVD的数量.我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量DVD进行分配决策，使得DVD的数量尽量小，会员满意度最大.第45页/共54页 假设按照公历月份进行的租赁业务，即会员无论两次租赁还是一次租赁，必须在当月内完成DVD的租与还.同时假设网站对其会员进行一次租赁业务时，只能向其提供3张该会员已经预定的DVD，否则不进行租赁.经观察，可以认为在线

16、订单中每个会员的预定DVD的表示偏好程度的数字反映了会员对所预定不同DVD的满意程度，且当会员租到其预定排序为1，2，3的三张DVD时，满意度达到100%.会员没有预定的DVD对其满意度的贡献为0.第46页/共54页 利用层次分析法，对此满意指数的合理性进行了简单分析.该问题要求根据现有的100种DVD的数量和当前需要处理的1000位会员的在线订单，制定分配策略，使得会员达到最大的满意度.因而我们认为,只需对这些DVD进行一次性分配，使得会员的总体满意度达到最大.为此考虑建立优化模型，进行求解.第47页/共54页问题二的模型及求解 经营成本和会员的满意度是被考虑的两个相互制约的重要因素.在忽略

17、邮寄成本的前提下，经营成本主要体现为DVD的数量.我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量DVD进行分配决策，使得DVD的数量尽量小，会员满意度最大.第48页/共54页第49页/共54页第50页/共54页第51页/共54页由此，可得问题二的0-1整数线性规划模型如下：第52页/共54页 根据所得的0-1整数线性规划模型，利用LINGO软件进行求解，我们得到了一组最优分配方案（见表3）.该组最优解其目标函数会员总体最大满意度为91.56%，只有6人未成功租赁（如：前30名会员中C0008被分配到DVD），其余994个会员全都得到了3张预定的DVD.第53页/共54页感谢您的观看！第54页/共54页