规划理论及模型课件.ppt

规划理论及模型第1页，此课件共111页哦第一章第一章 规划理论及模型规划理论及模型一、一、引言引言二、线性规划模型二、线性规划模型三、整数线性规划模型三、整数线性规划模型四、四、0-10-1整数规划模型整数规划模型 五、五、非线性规划模型非线性规划模型六、六、多目标规划模型多目标规划模型目录下页返回上页结束七、动态七、动态规划模型规划模型第2页，此课件共111页哦一、引言一、引言目录下页返回上页结束 我们从我们从2005年年“高教社杯高教社杯”全国大学生数模竞全国大学生数模竞赛的赛的B题题“DVD在线租赁在线租赁”问题的第二问和第三问问题的第二问和第三问 谈起谈起.其中第二个问题是一个如何来分配有限资源，其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的优化分配数学模型从而达到人们期望目标的优化分配数学模型.它它在运筹学中处于中心的地位在运筹学中处于中心的地位.这类问题一般可以这类问题一般可以归结为归结为数学规划模型数学规划模型.第3页，此课件共111页哦目录下页返回上页结束 规划模型的应用极其广泛，其作用已为越来规划模型的应用极其广泛，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量创造的价值无法估量.特别是在数模竞赛过程中，规划模型是最常特别是在数模竞赛过程中，规划模型是最常见的一类数学模型见的一类数学模型.从从92-06年全国大学生数模竞年全国大学生数模竞越多的人所重视越多的人所重视.随着计算机的逐渐普及，它越随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出赛试题的解题方法统计结果来看，规划模型共出现了现了15次，占到了次，占到了50%，也就是说每两道竞赛题，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解中就有一道涉及到利用规划理论来分析、求解.第4页，此课件共111页哦目录下页返回上页结束二、线性规划模型二、线性规划模型二、线性规划模型二、线性规划模型 线性规划模型是所有规划模型中最基本、最线性规划模型是所有规划模型中最基本、最例例1（食谱问题）设有食谱问题）设有 n 种食物，各含种食物，各含 m 种营养种营养素，第素，第 j 种食物中第种食物中第 i 中营养素的含量为中营养素的含量为 aij,n 种种食物价格分别为食物价格分别为c1,c2,cn，请确定食谱中，请确定食谱中n 种食种食物的数量物的数量x1,x2,xn，要求在食谱中，要求在食谱中 m 种营养素种营养素简单的一种简单的一种.2.1 线性规划模型的标准形式线性规划模型的标准形式 的含量分别不低于的含量分别不低于b1,b2,bm 的情况下，使得总的情况下，使得总总的费用最低总的费用最低.第5页，此课件共111页哦目录下页返回上页结束 首先根据食物数量及价格可写出食谱费用为首先根据食物数量及价格可写出食谱费用为 其次食谱中第其次食谱中第 i 种营养素的含量为种营养素的含量为 因此上述问题可表述为：因此上述问题可表述为：解解第6页，此课件共111页哦目录下页返回上页结束 上述食谱问题就是一个典型的线性规划问题，上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模型寻求以线性函数的最大（小）值为目标的数学模型.它是指在一组线性的等式或不等式的约束条件下，它是指在一组线性的等式或不等式的约束条件下，第7页，此课件共111页哦目录下页返回上页结束 线性规划模型的三种形式线性规划模型的三种形式线性规划模型的三种形式线性规划模型的三种形式 系系数数矩矩阵阵目标函数目标函数 价值向量价值向量 价值系数价值系数 决策变量决策变量右端向量右端向量非负约束非负约束自由变量自由变量 一般形式一般形式第8页，此课件共111页哦目录下页返回上页结束 规范形式规范形式 标准形式标准形式 三种形式的三种形式的LP问题全都是等价的，即一种形问题全都是等价的，即一种形式的式的LP可以简单的变换为另一种形式的可以简单的变换为另一种形式的LP，且它们，且它们有相同的解有相同的解.以下我们仅将一般形式化成规范形式和标准形式以下我们仅将一般形式化成规范形式和标准形式.第9页，此课件共111页哦目录下页返回上页结束目标函数的转化目标函数的转化 xoz-z第10页，此课件共111页哦目录下页返回上页结束约束条件和变量的转化约束条件和变量的转化 为为了了把把一一般般形形式式的的LP问问题题变变换换为为规规范范形形式式，我我们们必必须须消消除除等等式式约约束束和和符符号号无无限限制制变变量量.在在一一般般形形式式的的LP中，一个等式约束中，一个等式约束可用下述两个不等式约束去替代可用下述两个不等式约束去替代 第11页，此课件共111页哦目录下页返回上页结束这样就把一般形式的这样就把一般形式的LP变换为规范形式变换为规范形式.对对于于一一个个无无符符号号限限制制变变量量 ，引引进进两两个个非非负负变量变量 和和 ，并设，并设第12页，此课件共111页哦目录下页返回上页结束为了把一般形式的为了把一般形式的为了把一般形式的为了把一般形式的LPLPLPLP问题变换为标准形式，必须问题变换为标准形式，必须问题变换为标准形式，必须问题变换为标准形式，必须消除其不等式约束和符号无限制变量消除其不等式约束和符号无限制变量消除其不等式约束和符号无限制变量消除其不等式约束和符号无限制变量.对于一个不等式约束对于一个不等式约束代替上述的不等式约束代替上述的不等式约束.对符号无限制变量的处理可按上述方法进行对符号无限制变量的处理可按上述方法进行.可引入一个可引入一个剩余变量剩余变量 ，第13页，此课件共111页哦目录下页返回上页结束 对于不等式约束对于不等式约束 代替上述的不等式约束代替上述的不等式约束 这样就把一般形式的这样就把一般形式的LP变换为标准形式变换为标准形式.可引入一个可引入一个松弛变量松弛变量，用，用第14页，此课件共111页哦目录下页返回上页结束 针对标准形式的线性规划问题，其解的理论针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算分析已经很完备，在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也单纯形方法是线性规划问题的最为基础、也法法单纯形方法及其相应的变化形式（两阶段单纯形方法及其相应的变化形式（两阶段2.2 线性规划模型的求解线性规划模型的求解 法，对偶单纯形法等）法，对偶单纯形法等）.是最核心的算法。它是一个迭代算法，先从一个是最核心的算法。它是一个迭代算法，先从一个特殊的可行解（极点）出发，通过判别条件去判特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不断该可行解是否为最优解（或问题无界），若不第15页，此课件共111页哦目录下页返回上页结束是最优解，则根据相应规则，迭代到下一个更好的可行是最优解，则根据相应规则，迭代到下一个更好的可行解（极点），直到最优解（或问题无界）解（极点），直到最优解（或问题无界）.关于线性规关于线性规划问题解的理论和单纯形法具体的求解过程可参见文献划问题解的理论和单纯形法具体的求解过程可参见文献1.然后在实际应用中，特别是数学建模过程中，遇到然后在实际应用中，特别是数学建模过程中，遇到线性规划问题的求解，我们一般都是利用现有的软件进线性规划问题的求解，我们一般都是利用现有的软件进行求解，此时通常并不要求线性规划问题是标准形式行求解，此时通常并不要求线性规划问题是标准形式.比较常用的求解线性规划模型的软件包有比较常用的求解线性规划模型的软件包有LINGO和和LINDO.第16页，此课件共111页哦目录下页返回上页结束运输问题运输问题例例2 2 设要从甲地调出物资设要从甲地调出物资20002000吨，从乙地调出物吨，从乙地调出物 资资1100吨，分别供给吨，分别供给A地地1700吨、吨、B地地1100吨、吨、C假定运费与运量成正比假定运费与运量成正比.在这种情况下，采用不在这种情况下，采用不地地200吨、吨、D地地100吨吨.已知每吨运费如表已知每吨运费如表1.1所示所示.同的调拨计划，运费就可能不一样同的调拨计划，运费就可能不一样.现在问：怎现在问：怎样才能找出一个运费最省的调拨计划？样才能找出一个运费最省的调拨计划？第17页，此课件共111页哦目录下页返回上页结束1572521甲甲15375151乙乙DCBA表表 1.1销销地地运运费费产产地地第18页，此课件共111页哦目录下页返回上页结束解解乙乙甲甲DCBA第19页，此课件共111页哦目录下页返回上页结束第20页，此课件共111页哦目录下页返回上页结束一般的运输问题可以表述如下：一般的运输问题可以表述如下：第21页，此课件共111页哦目录下页返回上页结束数学模型：数学模型：第22页，此课件共111页哦目录下页返回上页结束 类似与将一般的线性规划问题转化为其标准类似与将一般的线性规划问题转化为其标准 若其中各产地的总产量等于各销地的总销量，若其中各产地的总产量等于各销地的总销量，即即否则，称为不平衡的运输问题，包括：否则，称为不平衡的运输问题，包括：，则称该问题为平衡的运输问题，则称该问题为平衡的运输问题.总产量总产量总销量总销量 和和 总产量总产量总销量总销量.形式，我们总可以通过引入假想的销地或产地，形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题将不平衡的运输问题转化为平衡的运输问题.从从而，我们的重点就是解决平衡运输问题的求解而，我们的重点就是解决平衡运输问题的求解.第23页，此课件共111页哦目录下页返回上页结束 显然，运输问题是一个标准的线性规划问题，因而显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解当然可以运用单纯形方法求解.但由于平衡的运输问题但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解质结合起来，很方便地实行了运输问题的求解.关关于运输问题及其解法的进一步介绍参加文献于运输问题及其解法的进一步介绍参加文献2.第24页，此课件共111页哦目录下页返回上页结束 对于线性规划问题，如果要求其决策变量取对于线性规划问题，如果要求其决策变量取整数值，则称该问题为整数线性规划问题整数值，则称该问题为整数线性规划问题.平面法和分支定界法是两种常用的求解整数线性平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解，其难度和运对于整数线性规划问题的求解，其难度和运三、整数线性规划模型三、整数线性规划模型算量远大于同规模的线性规划问题算量远大于同规模的线性规划问题.Gomory割割规划问题的方法（见文献规划问题的方法（见文献1）.此外，同线性规此外，同线性规划模型一样，我们也可以运用划模型一样，我们也可以运用LINGO和和LINDO软软件包来求解整数线性规划模型件包来求解整数线性规划模型.第25页，此课件共111页哦目录下页返回上页结束 以以1988年美国大学生数学建模竞赛年美国大学生数学建模竞赛B题为例，说明整题为例，说明整数线性规划模型的建立及用数线性规划模型的建立及用LINGO软件包如何求解整软件包如何求解整数线性规划模型数线性规划模型.例例3 有七种规格的包装箱要装到两节铁路平板车有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度（上去。包装箱的宽和高是一样的，但厚度（t，以，以cm 计）及重量（计）及重量（w，以，以kg计）是不同的计）是不同的.表表1给出给出了每种包装箱的厚度、重量以及数量了每种包装箱的厚度、重量以及数量.每节平板每节平板车有车有10.2 m 长的地方可用来装包装箱（像面包片长的地方可用来装包装箱（像面包片那样），载重为那样），载重为40t.由于当地货运的限制，对于由于当地货运的限制，对于第26页，此课件共111页哦目录下页返回上页结束C5,C6,C7 类包装箱的总数有一个特别的限制：这类包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过类箱子所占的空间（厚度）不能超过302.7cm.试试把包装箱装到平板车上，使得浪费的空间最小把包装箱装到平板车上，使得浪费的空间最小.种种类类C1C2C3C4C5C6 C7t/cm48.753.061.372.048.752.064.0w/kg2000 3000 10005004000 2000 1000n/件件8796648第27页，此课件共111页哦目录下页返回上页结束 为在第为在第 节车上装载第节车上装载第 件包装箱的件包装箱的解解 令令 下面我们建立该问题的整数线性规划模型。下面我们建立该问题的整数线性规划模型。第28页，此课件共111页哦目录下页返回上页结束1)约束条件约束条件两节车的装箱数不能超过需要装的件数，即：两节车的装箱数不能超过需要装的件数，即：每节车可装的长度不能超过车能提供的长度：每节车可装的长度不能超过车能提供的长度：每节车可装的重量不超过车能够承受的重量：每节车可装的重量不超过车能够承受的重量：第29页，此课件共111页哦目录下页返回上页结束对于对于C5,C6,C7类包装箱的总数的特别限制：类包装箱的总数的特别限制：2)目标函数目标函数浪费的空间最小，即包装箱的总厚度最大：浪费的空间最小，即包装箱的总厚度最大：第30页，此课件共111页哦目录下页返回上页结束3)整数线性规划模型整数线性规划模型第31页，此课件共111页哦目录下页返回上页结束4)模型求解模型求解运用运用LINGO软件求解得到：软件求解得到：5)最优解的分析说明最优解的分析说明优的装车方案，此时装箱的总长度为优的装车方案，此时装箱的总长度为1019.7cm，两节车共装箱的总长度为两节车共装箱的总长度为2039.4cm.由上一步中的求解结果可以看出，由上一步中的求解结果可以看出，即为最即为最 但是，上述求解结果只是其中一种最优的装但是，上述求解结果只是其中一种最优的装车方案，即此答案并不唯一车方案，即此答案并不唯一.第32页，此课件共111页哦目录下页返回上页结束 0-1整数规划是整数规划的特殊情形，它要求整数规划是整数规划的特殊情形，它要求线性规划模型中的决策变量线性规划模型中的决策变量 xij 只能取值为只能取值为0或或1.单隐枚举法，该方法是一种基于判断条件（过滤单隐枚举法，该方法是一种基于判断条件（过滤 0-1整数规划模型的求解目前并没有非常好的整数规划模型的求解目前并没有非常好的四、四、0-1整数规划模型整数规划模型 算法，对于变量比较少的情形，我们可以采取简算法，对于变量比较少的情形，我们可以采取简条件）的穷举法条件）的穷举法.我们也可以利用我们也可以利用LINGO和和LINDO软件包来求软件包来求解解0-1整数规划模型整数规划模型.第33页，此课件共111页哦目录下页返回上页结束例例4 有有 n 个物品，编号为个物品，编号为 1,2,n，第，第 i 件物品件物品重重 ai 千克，价值为千克，价值为 ci 元，现有一个载重量不超过元，现有一个载重量不超过大，应如何装载这些物品？大，应如何装载这些物品？a 千克的背包，为了使装入背包的物品总价值最千克的背包，为了使装入背包的物品总价值最用变量用变量 xi 表示物品表示物品 i 是否装包，是否装包，i=1,2,n，并令：并令：解解第34页，此课件共111页哦目录下页返回上页结束可得到背包问题的规划模型为：可得到背包问题的规划模型为：第35页，此课件共111页哦目录下页返回上页结束例例5 有有n 项任务，由项任务，由 n 个人来完成，每个人只能个人来完成，每个人只能做一件，做一件，第第 i 个人完成第个人完成第 j 项任务要项任务要 cij 小时，如小时，如何合理安排时间才能使总用时最小？何合理安排时间才能使总用时最小？引入状态变量引入状态变量 xij，并令：，并令：解解则总用时表达式为：则总用时表达式为：第36页，此课件共111页哦目录下页返回上页结束可得到指派问题的规划模型为：可得到指派问题的规划模型为：第37页，此课件共111页哦目录下页返回上页结束 上面介绍的指派问题称为指派问题的标准形上面介绍的指派问题称为指派问题的标准形式，还有许多其它的诸如人数与任务数不等、及式，还有许多其它的诸如人数与任务数不等、及但一般可以通过一些转化，将其变为标准形式但一般可以通过一些转化，将其变为标准形式.某人可以完成多个任务，某人不可以完成任务，某人可以完成多个任务，某人不可以完成任务，某任务必须由某人完成等特殊要求的指派问题某任务必须由某人完成等特殊要求的指派问题.对于标准形式的指派问题，我们可以利用匈对于标准形式的指派问题，我们可以利用匈牙利算法实现求解牙利算法实现求解.它将指派问题中的系数构成它将指派问题中的系数构成一个矩阵，利用矩阵上简单的行和列变换，结合一个矩阵，利用矩阵上简单的行和列变换，结合 解的判定条件，实现求解（见文献解的判定条件，实现求解（见文献2）.第38页，此课件共111页哦目录下页返回上页结束DVDDVD在线租赁第二个问题的求解在线租赁第二个问题的求解问题二的分析问题二的分析 经营成本和会员的满意度是被考虑的两个相互制约的经营成本和会员的满意度是被考虑的两个相互制约的重要因素重要因素.在忽略邮寄成本的前提下，经营成本主要体现在忽略邮寄成本的前提下，经营成本主要体现为为DVD的数量的数量.我们主要考虑在会员向网站提供需求我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量信息，且满足一定要求的前提下，对给定数量DVD进进行分配决策，使得行分配决策，使得DVD的的数量尽量小，会员满意度最数量尽量小，会员满意度最大大.第39页，此课件共111页哦目录下页返回上页结束 假设按照公历月份进行的租赁业务，即会员无论两假设按照公历月份进行的租赁业务，即会员无论两次租赁还是一次租赁，必须在当月内完成次租赁还是一次租赁，必须在当月内完成DVD的租与还的租与还.同时假设网站对其会员进行一次租赁业务时，只能向其提同时假设网站对其会员进行一次租赁业务时，只能向其提供供3张该会员已经预定的张该会员已经预定的DVD，否则不进行租赁，否则不进行租赁.经观察，可以认为在线订单中每个会员的预定经观察，可以认为在线订单中每个会员的预定DVD的的表示偏好程度的数字反映了会员对所预定不同表示偏好程度的数字反映了会员对所预定不同DVD的满意的满意程度，且当会员租到其预定排序为程度，且当会员租到其预定排序为1，2，3的三张的三张DVD时，时，满意度达到满意度达到100%.会员没有预定的会员没有预定的DVD对其满意度的贡对其满意度的贡献为献为0.第40页，此课件共111页哦目录下页返回上页结束 利用层次分析法，对此满意指数的合理性进利用层次分析法，对此满意指数的合理性进行了简单分析行了简单分析.该问题要求根据现有的该问题要求根据现有的100种种DVD的数量和当前的数量和当前需要处理的需要处理的1000位会员的在线订单，制定分配策略，位会员的在线订单，制定分配策略，使得会员达到最大的满意度使得会员达到最大的满意度.因而我们认为只需因而我们认为只需对这些对这些DVD进行一次性分配，使得会员的总体满意度达进行一次性分配，使得会员的总体满意度达到最大到最大.为此考虑建立优化模型，进行求解为此考虑建立优化模型，进行求解.第41页，此课件共111页哦目录下页返回上页结束问题二的模型及求解问题二的模型及求解 经营成本和会员的满意度是被考虑的两个相互制经营成本和会员的满意度是被考虑的两个相互制约的重要因素约的重要因素.在忽略邮寄成本的前提下，经营成本在忽略邮寄成本的前提下，经营成本主要体现为主要体现为DVD的数量的数量.我们主要考虑在会员向网站我们主要考虑在会员向网站提供需求信息，且满足一定要求的前提下，对给定数量提供需求信息，且满足一定要求的前提下，对给定数量DVD进行分配决策，使得进行分配决策，使得DVD的数量尽量小，会员满的数量尽量小，会员满意度最大意度最大.第42页，此课件共111页哦目录下页返回上页结束第43页，此课件共111页哦目录下页返回上页结束第44页，此课件共111页哦目录下页返回上页结束第45页，此课件共111页哦目录下页返回上页结束由此，可得问题二的由此，可得问题二的0-1整数线性规划模型如下：整数线性规划模型如下：第46页，此课件共111页哦目录下页返回上页结束 根据所得的根据所得的0-1整数线性规划模型，利用整数线性规划模型，利用LINGO软软件进行求解，我们得到了一组最优件进行求解，我们得到了一组最优分配方案分配方案.该组最优解其目标函数会员总体最大满意度为该组最优解其目标函数会员总体最大满意度为91.56%，只有，只有6人未成功租赁（如人未成功租赁（如：前：前30名会员中名会员中C0008被分配到被分配到DVD），其余），其余994个会员全都得到了个会员全都得到了3张预定的张预定的DVD.第47页，此课件共111页哦目录下页返回上页结束五、非线性规划模型五、非线性规划模型五、非线性规划模型五、非线性规划模型 前面介绍了线性规划问题，即目标函数和约束前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作中，条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，其中目还常常会遇到另一类更一般的规划问题，其中目标函数和约束条件至少有一个是非线性函数的规标函数和约束条件至少有一个是非线性函数的规划问题，即非线性规划问题划问题，即非线性规划问题.第48页，此课件共111页哦目录下页返回上页结束 事实上，客观世界中的问题许多是非线性事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的的，给予线性大多是近似的，是在作了科学的假设和简化后得到的假设和简化后得到的.为了利用线性的知识，为了利用线性的知识，许多非线性问题常进行线性化处理许多非线性问题常进行线性化处理.但在实际问但在实际问题中，有一些是不能进行线性化处理的，否则将严题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型重影响模型对实际问题近似的可依赖型.第49页，此课件共111页哦目录下页返回上页结束 由由于于非非线线性性规规划划问问题题在在计计算算上上常常是是困困难难的的，理理论论上上的的讨讨论论也也不不能能像像线线性性规规划划那那样样给给出出简简洁洁的的结结果果形形式式和和全全面面透透彻彻的的结结论论.这这点点又又限限制制了了非非线线性性规规划划的的应应用用，所所以以，在在数数学学建建模模时时，要要进进行行认认真真的的分分析析，对对实实际际问问题题进进行行合合理理的的假假设设、简简化化，首首先先考考虑虑用用线线性性规规划划模模型型，若若线线性性近近似似误误差差较较大大时时，则则考考虑虑用用非非线线性性规规划划.第50页，此课件共111页哦目录下页返回上页结束非线性规划问题的标准形式为：非线性规划问题的标准形式为：非线性规划问题的标准形式为：非线性规划问题的标准形式为：第51页，此课件共111页哦目录下页返回上页结束非线性规划模型按约束条件可分为以下三类：非线性规划模型按约束条件可分为以下三类：等式约束非线性规划模型等式约束非线性规划模型：无约束非线性规划模型：无约束非线性规划模型：第52页，此课件共111页哦目录下页返回上页结束 不等式约束非线性规划模型：不等式约束非线性规划模型：1)无约束的非线性规划问题无约束的非线性规划问题.针对上述三类非线性规划模型，其常用求解的基本针对上述三类非线性规划模型，其常用求解的基本思路可归纳如下：思路可归纳如下：第53页，此课件共111页哦目录下页返回上页结束(表示函数的梯度）求出最表示函数的梯度）求出最优优解解 ，但求解但求解 往往是很困难的往往是很困难的.若目若目标标函数函数的形式的形式简单简单，可以通，可以通过过求解方程求解方程（下降迭代法）（下降迭代法）寻寻找，找，该该方法的基本步方法的基本步骤骤如下：如下：所以往往根据目标函数的特征采用搜索的方法所以往往根据目标函数的特征采用搜索的方法第54页，此课件共111页哦目录下页返回上页结束检验检验 是否是否满满足停止迭代的条件，如是，足停止迭代的条件，如是，则则停停 止迭代，用止迭代，用 来近似来近似问题问题的最的最优优解，否解，否则转则转至至.从从 出出发发，沿方向，沿方向 ，按某种方法确定步，按某种方法确定步长长 ，使得：，使得：令令 ，然后置，然后置 ，返回，返回适当适当选选取初始点取初始点，令，令按某种按某种规则规则确定确定处处的搜索方向的搜索方向.第55页，此课件共111页哦目录下页返回上页结束 在下降迭代算法中，搜索方向起着关键的作用，在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好坏的重要而当搜索方向确定后，步长又是决定算法好坏的重要因素因素.非线性规划只含一个变量，即一维非线性规划可非线性规划只含一个变量，即一维非线性规划可以用一维搜索方法求得最优解，一以用一维搜索方法求得最优解，一维维搜索方法主要有搜索方法主要有进进退法和黄金分割法退法和黄金分割法.二二维维的非的非线线性性规规划也可以像解划也可以像解线线性性规规划那划那样样用用图图形求解形求解.对对于二于二维维非非线线性性规规划，使用搜索方法是要用到梯度的概念，最常用划，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降法的搜索方法就是最速下降法.第56页，此课件共111页哦目录下页返回上页结束2)只有等式约束的非线性规划问题通常可用消元法、只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为无约束问题拉格朗日乘子法或反函数法，将其化为无约束问题求解求解.3)具有不等式约束的非线性规划问题解起来很复杂，具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等式约束，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无约束问题，用线性逼近的方再将约束问题化为无约束问题，用线性逼近的方法将非线性规划问题化为线性规划问题法将非线性规划问题化为线性规划问题.第57页，此课件共111页哦 下面介绍一个简单的非线性规划问题的例子，其中下面介绍一个简单的非线性规划问题的例子，其中的一些约束条件是等式，这类非线性规划问题可用拉格的一些约束条件是等式，这类非线性规划问题可用拉格朗日方法求解朗日方法求解.第58页，此课件共111页哦目录下页返回上页结束例例7 7（石油最优储存方法）有一石油运输公司，为（石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间了减少开支，希望作了节省石油的存储空间.但要求但要求存储的石油能满足客户的要求存储的石油能满足客户的要求.为简化问题，假设只为简化问题，假设只经营两种油，各种符号表示的意义如表经营两种油，各种符号表示的意义如表4 4所示所示.其中其中供给率指石油公司供给客户的速度供给率指石油公司供给客户的速度.第59页，此课件共111页哦目录下页返回上页结束表表表表4 4 各种符号表示意义表各种符号表示意义表各种符号表示意义表各种符号表示意义表第第i种油的存种油的存储储量量第第i种油的价格种油的价格第第i种油的供种油的供给给率率第第i种油的每种油的每单单位的存位的存储费储费用用第第i种油的每种油的每单单位的存位的存储储空空间间总总存存储储公式公式第60页，此课件共111页哦目录下页返回上页结束由历史数据得到的经验公式为由历史数据得到的经验公式为:且提供数据如表且提供数据如表5 5所示：所示：第61页，此课件共111页哦目录下页返回上页结束表表5 数据表数据表已知已知总总存存储储空空间间石油的石油的种类种类1930.5022450.24第62页，此课件共111页哦目录下页返回上页结束代入数据后得到的模型为：代入数据后得到的模型为：模型求解：模型求解：拉格朗日函数的形式为：拉格朗日函数的形式为：第63页，此课件共111页哦目录下页返回上页结束即即即即:对对 求各个求各个变变量的偏量的偏导导数，并令它数，并令它们们等于等于零，得零，得:第64页，此课件共111页哦目录下页返回上页结束 解这个线性方程组得：解这个线性方程组得：解这个线性方程组得：解这个线性方程组得：从而可得最小从而可得最小值值是是12.71.表示当表示当约约束条件右束条件右边边的的值值增大一个增大一个单单位后，相位后，相应应目目标标函数函数值值的增加的增加值值。比如。比如说说：如：如总总存存储储空空间间由由24变变为为25时时，最，最优值优值会由会由12.71变为变为第65页，此课件共111页哦目录下页返回上页结束六、多目标规划模型六、多目标规划模型六、多目标规划模型六、多目标规划模型 在许多实际问题中，衡量一个方案的好坏标准在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高又要燃料最省，还要精度最高.这一类问题统称为多这一类问题统称为多目标最优化问题或多目标规划问题目标最优化问题或多目标规划问题.我们先来看一我们先来看一个生产计划的例子个生产计划的例子.第66页，此课件共111页哦目录下页返回上页结束能耗不得超过能耗不得超过160t标准煤标准煤其它数据如下表其它数据如下表：布料布料生产数量生产数量（m/h）利润利润（元（元/m）最大销售量最大销售量（m/周）周）能耗能耗（t/km）A14004000.150.1540000400001.21.2A25105100.130.1351000510001.31.3A33603600.200.2030000300001.41.4问每周应生产三种布料各多少问每周应生产三种布料各多少m，才能使该厂，才能使该厂的利润最高，而能源消耗最少？的利润最高，而能源消耗最少？，该厂两班生产，每周生产时间为，该厂两班生产，每周生产时间为80h，例例8 8（生产计划问题）某厂生产三种布料（生产计划问题）某厂生产三种布料第67页，此课件共111页哦目录下页返回上页结束 ，总利润为，总利润为 （元），总能耗为（元），总能耗为解解 设该厂每周生产布料设该厂每周生产布料 的小时数为的小时数为（t标准煤），其中标准煤），其中 ，则上述问题的数学模型为则上述问题的数学模型为第68页，此课件共111页哦目录下页返回上页结束其中，其中，.有有显然这是一个多目标线性规划问题显然这是一个多目标线性规划问题.一般的多目标规一般的多目标规划问题都可写成如下的形式：划问题都可写成如下的形式：第69页，此课件共111页哦目录下页返回上页结束 多目标规划问题的解法大致可分为两类：直接解法和多目标规划问题的解法大致可分为两类：直接解法和间接解法间接解法.到目前为止，常用的多为间接解法，即根据问到目前为止，常用的多为间接解法，即根据问题的实际背景和特征，设法将多目标优化问题转化为单目题的实际背景和特征，设法将多目标优化问题转化为单目标优化问题，从而得到满意解的方法标优化问题，从而得到满意解的方法.许解许解.多目标规划问题与前面讲的规划问题的主多目标规划问题与前面讲的规划问题的主要区别在于：目标函数不止一个，而是要区别在于：目标函数不止一个，而是p个（个（）.称为多目标规划问称为多目标规划问题的可行集或容许集，题的可行集或容许集，称为可行解或容称为可行解或容第70页，此课件共111页哦目录下页返回上页结束在多目标优化问题中，若能从在多目标优化问题中，若能从p个目标中，确定个目标中，确定一个目标为主要目标，例如一个目标为主要目标，例如 ，1)主要目标法主要目标法而把其余目标作为次要目标，并根据实际情况，确而把其余目标作为次要目标，并根据实际情况，确定适当的界限值，这样就可以把次要目标作为约束定适当的界限值，这样就可以把次要目标作为约束来处理，而将多目标优化问题转化为求解如下的线来处理，而将多目标优化问题转化为求解如下的线性或非线性规划问题：性或非线性规划问题：第71页，此课件共111页哦把多目标规划问题中的把多目标规划问题中的p个目标按其重要程度排个目标按其重要程度排一个次序，假设一个次序，假设 最重要，最重要，次之，次之，目录下页返回上页结束令令 ，其中界限值取为，其中界限值取为 ，再次之，再次之，L，最后一个目标，最后一个目标 .先求出以第一个目标先求出以第一个目标 为目标函数为目标函数而原问题而原问题则此非线性规划问题得最优解必为原问题的弱有效解则此非线性规划问题得最优解必为原问题的弱有效解.因此，用主要目标法求得的解必是多目标优化问题的因此，用主要目标法求得的解必是多目标优化问题的弱有效解或有效解弱有效解或有效解.2）分层序列法）分层序列法第72页，此课件共111页哦目录下页返回上页结束变的问题变的问题 ：的最优解的最优解 及最优值及最优值 ，再求问题再求问题 ：的最优解的最优解 及最优值及最优值 ，即，即 ，其中：其中：为问题为问题 的可行域的可行域.第73页，此课件共111页哦目录下页返回上页结束再求解问题再求解问题 ：得最优解得最优解 及最优值及最优值 ，L，如此继续下去，如此继续下去，直到求出第直到求出第p个问题个问题 ：得最优解得最优解 及最优值及最优值 ，则，则 就是就是原多目标规划原多目标规划问题在分层序列意义下得最优解，问题在分层序列意义下得最优解，为其最优值为其最优值.第74页，此课件共111页哦目录下页返回上页结束，其最优解是唯一的，则问题，其最优解是唯一的，则问题 的最优解的最优解也是唯一的，且也是唯一的，且 。因此常将分层因此常将分层序列法修改如下：序列法修改如下：选取一组适当的小正数选取一组适当的小正数，成为宽容值，把上述的问题，成为宽容值，把上述的问题 修改如下：修改如下：再按上述方法依次求解各问题再按上述方法依次求解各问题 .容易看出，在使用分层序列法时，若对某个问题容易看出，在使用分层序列法时，若对某个问题p.第75页，此课件共111页哦目录下页返回上页结束对多目标规划问题中的对多目标规划问题中的p p个目标按期重要程度给个目标按期重要程度给以适当的权系数以适当的权系数 ，且且 ，然后用用 作为新的目作为新的目得最优解 ，取 作为多目标规划问多目标规划问题的解题的解.3）线性加权求和法）线性加权求和法标函数，成为评价（目标）函数，再求解问题标函数，成为评价（目标）函数，再求解问题第76页，此课件共111页哦目录下页返回上页结束 在一定条件下，用线性加权求和法求得的最优在一定条件下，用线性加权求和法求得的最优解必是原多目标规划问题的有效解或弱有效解解必是原多目标规划问题的有效解或弱有效解.例例9 9求解引言中求解引言中DVDDVD在在线线租租赁赁的第三个的第三个问题问题.下面以引言中下面以引言中2005年全国大学生数模年全国大学生数模竞赛竞赛“DVD在在线线租租赁赁”问题问题第三第三问为问为例，介例，介绍绍多目多目标线标线性性规规划模型以及利用主要目划模型以及利用主要目标标法求解法求解该该模型模型.第77页，此课件共111页哦目录下页返回上页结束此问是在现有的在线订单基础上，为满足一个此问是在现有的在线订单基础上，为满足一个月内月内95%的会员得到他想看的的会员得到他想看的DVD，我们进行购买量，我们进行购买量预算和分配决策，使得会员的满意度最大预算和分配决策，使得会员的满意度最大.预算购买量的预算购买量的目的是在尽可能地减少目的是在尽可能地减少DVD购买量的前提下，满足要购买量的前提下，满足要求，进行合理分配使得会员的满意度最大求，进行合理分配使得会员的满意度最大.问题三的分析问题三的分析第78页，此课件共111页哦 我们假