规划理论及模型

下下下下回回回回停停停停一、引言一、引言 二、线性规划模型二、线性规划模型三、整数线性规划模型三、整数线性规划模型第一讲第一讲 规划理论及模型规划理论及模型 四、四、0-1整数规划模型整数规划模型 五、非线性规划模型五、非线性规划模型 六、多目标规划模型六、多目标规划模型 七、动态规划模型七、动态规划模型一、引言一、引言 我们从我们从2005年年“高教社杯高教社杯”全国大学生数模全国大学生数模竞竞谈起谈起.其中第二个问题是一个如何来分配有限资源，其中第二个问题是一个如何来分配有限资源，从而达到人们期望目标的从而达到人们期望目标的优化分配数学模型优化分配数学模型.它它在运筹学中处于中心的地位在运筹学中处于中心的地位.这类问题一般可以这类问题一般可以归结为归结为 数学规划模型数学规划模型.赛的赛的B题题“DVD在线租赁在线租赁”问题的第二问和第三问问题的第二问和第三问 最优化问题概述最优化问题概述最优化问题的定义最优化问题的定义最优化问题的分类及处理方法最优化问题的分类及处理方法最优化模型的基本要素最优化模型的基本要素最优化问题的定义最优化问题的定义最优化问题就是在给定条件下寻找最佳方案的问题，即在资源给定时寻找最好的目标，或在目标确定时使用最少的资源。最优化问题的分类及处理方法最优化问题的分类及处理方法无条件最优化问题：无条件最优化问题：求导法等求导法等约束条件为等式的有约束条件的最优化问题：约束条件为等式的有约束条件的最优化问题：拉拉格朗日乘数法等格朗日乘数法等约束条件为不等式的有约束条件的最优化问题：约束条件为不等式的有约束条件的最优化问题：数学规划数学规划数学规划模型：数学规划模型：目标规划目标规划（一个、多个）、（一个、多个）、动动（静）态规划（静）态规划（与时间是否有关）、（与时间是否有关）、线性规划线性规划（整数规划、（整数规划、0-1规划）、规划）、非线性规划非线性规划最优化（规划）模型的基本要素最优化（规划）模型的基本要素决策变量、目标函数和约束条件：决策变量是问题中有待确定的未知因素。目标函数是指对问题所追求的目标的数学描述。约束条件是指实现问题目标的限制因素。引例引例 某工厂在计划期内要安排生产某工厂在计划期内要安排生产I I、IIII两种产品，该工厂每生产一件产品两种产品，该工厂每生产一件产品I I可可获利获利2 2元，每生产一件产品元，每生产一件产品IIII可获利可获利3 3元。问应如何安排计划使该工厂获利最元。问应如何安排计划使该工厂获利最多？已知生产单位产品所需的设备台时及多？已知生产单位产品所需的设备台时及A A、B B两种原材料的消耗，如下表所两种原材料的消耗，如下表所示示 12kg12kg4 40 0原材料原材料B B16kg16kg0 04 4原材料原材料A A8 8台台时时2 21 1设备设备IIIII I运用规划模型解决最优化问题的一般方法步运用规划模型解决最优化问题的一般方法步骤如下：骤如下：前期分析：分析问题，找出要解决的目标，约束前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。条件，并确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。标函数和约束条件。针对建立的模型，选择合适的求解方法或数学软针对建立的模型，选择合适的求解方法或数学软件。件。编写程序，利用计算机求解。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。法效率与误差等。规划模型的应用极其广泛规划模型的应用极其广泛，其作用已为越来，其作用已为越来来越急速地渗透于工农业生产、商业活动、军事来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量创造的价值无法估量.特别是在数模竞赛过程中特别是在数模竞赛过程中，规划模型是最常，规划模型是最常见的一类数学模型见的一类数学模型.从从92-06年全国大学生数模竞年全国大学生数模竞越多的人所重视越多的人所重视.随着计算机的逐渐普及，它越随着计算机的逐渐普及，它越赛试题的解题方法统计结果来看，规划模型共出赛试题的解题方法统计结果来看，规划模型共出现了现了15次，占到了次，占到了50%，也就是说每两道竞赛题，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解中就有一道涉及到利用规划理论来分析、求解.二、线性规划模型二、线性规划模型 线性规划模型是所有规划模型中最基本、最线性规划模型是所有规划模型中最基本、最例例1.（食谱问题）设有食谱问题）设有 n 种食物，各含种食物，各含 m 种营养种营养素，第素，第 j 种食物中第种食物中第 i 中营养素的含量为中营养素的含量为 aij,n 种种食物价格分别为食物价格分别为c1,c2,cn，请确定食谱中，请确定食谱中n 种食种食物的数量物的数量x1,x2,xn，要求在食谱中，要求在食谱中 m 种营养素种营养素简单的一种简单的一种.2.1 2.1 线性规划模型的标准形式线性规划模型的标准形式 的含量分别不低于的含量分别不低于b1,b2,bm 的情况下，使得总的情况下，使得总总的费用最低总的费用最低.首先根据食物数量及价格可写出食谱费用为首先根据食物数量及价格可写出食谱费用为 其次食谱中第其次食谱中第 i 种营养素的含量为种营养素的含量为 因此上述问题可表述为：因此上述问题可表述为：解解 上述食谱问题就是一个典型的线性规划问题，上述食谱问题就是一个典型的线性规划问题，寻求以线性函数的最大（小）值为目标的数学模寻求以线性函数的最大（小）值为目标的数学模型型.它是指在一组线性的等式或不等式的约束条件下，它是指在一组线性的等式或不等式的约束条件下，例：例：某豆腐店用黄豆制作两种不同口感的豆腐出售。制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。问：应如何安排制作计划才能获得最大收益。一、问题前期分析一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划，使得售出各种豆腐能获得最大收件下合理安排制作计划，使得售出各种豆腐能获得最大收益。益。二、模型假设二、模型假设1 1假设制作的豆腐能全部售出。假设制作的豆腐能全部售出。2 2假设豆腐售价无波动。假设豆腐售价无波动。变量假设：变量假设：设计划制作口感鲜嫩和厚实的豆腐各设计划制作口感鲜嫩和厚实的豆腐各x1x1千克和千克和 x2x2千克，可获得收益千克，可获得收益R R元。元。目标函数：获得的总收益最大。目标函数：获得的总收益最大。总收益可表示为：。总收益可表示为：。受一级黄豆数量限制：。受一级黄豆数量限制：。受二级黄豆数量限制：。受二级黄豆数量限制：。综上分析，得到该问题的线性规划模型：综上分析，得到该问题的线性规划模型：运输问题（常见典型的线性规划问题）运输问题（常见典型的线性规划问题）例例2.2.设要从甲地调出物资设要从甲地调出物资2000吨，从乙地调出物吨，从乙地调出物 资资1100吨，分别供给吨，分别供给A地地1700吨、吨、B地地1100吨、吨、C假定运费与运量成正比假定运费与运量成正比.在这种情况下，采用不在这种情况下，采用不地地200吨、吨、D地地100吨吨.已知每吨运费如表已知每吨运费如表1.1所示所示.同的调拨计划，运费就可能不一样同的调拨计划，运费就可能不一样.现在问：怎现在问：怎样才能找出一个运费最省的调拨计划？样才能找出一个运费最省的调拨计划？1572521甲甲15375151乙乙DCBA表表 1.1销销地地运运费费产产地地假设：假设：假设题目中所给运费已考虑各地间公里数；假设题目中所给运费已考虑各地间公里数；只考虑运量和运费，不考虑车辆调拨等其它相关因素只考虑运量和运费，不考虑车辆调拨等其它相关因素不考虑车辆返空的费用（或：所给运费已包含车辆返空不考虑车辆返空的费用（或：所给运费已包含车辆返空的费用）的费用）变量说明：变量说明：xij:xij:从第从第i i城运往第城运往第j j地的蔬菜数量（地的蔬菜数量（i=1,2,3;j=1,2,3,4i=1,2,3;j=1,2,3,4）乙乙甲甲DCBA解解一般的运输问题可以表述如下：一般的运输问题可以表述如下：数学模型：数学模型：若其中各产地的总产量等于各销地的总销量，若其中各产地的总产量等于各销地的总销量，即即 类似与将一般的线性规划问题转化为其标准类似与将一般的线性规划问题转化为其标准否则，称为不平衡的运输问题，包括：否则，称为不平衡的运输问题，包括：，则称该问题为平衡的运输问题，则称该问题为平衡的运输问题.总产量总产量总销量和总产量总销量和总产量总销量总销量.形式，我们总可以通过引入假想的销地或产地，形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题将不平衡的运输问题转化为平衡的运输问题.从从而，我们的重点就是解决平衡运输问题的求解而，我们的重点就是解决平衡运输问题的求解.显然，运输问题是一个标准的线性规划问题，显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解因而当然可以运用单纯形方法求解.但由于平衡的但由于平衡的运输问题的特殊性质，它还可以用其它的一些特殊运输问题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解很方便地实行了运输问题的求解.关于运输问题及关于运输问题及其解法的进一步介绍参加文献其解法的进一步介绍参加文献2.对于线性规划问题，如果要求其决策变量取对于线性规划问题，如果要求其决策变量取整数值，则称该问题为整数线性规划问题整数值，则称该问题为整数线性规划问题.平面法和分支定界法是两种常用的求解整数线性平面法和分支定界法是两种常用的求解整数线性 对于整数线性规划问题的求解，其难度和运对于整数线性规划问题的求解，其难度和运三、整数线性规划模型三、整数线性规划模型算量远大于同规模的线性规划问题算量远大于同规模的线性规划问题.Gomory割割规划问题的方法（见文献规划问题的方法（见文献1）.此外，同线性此外，同线性规规划模型一样，我们也可以运用划模型一样，我们也可以运用LINGO和和LINDO软软件包来求解整数线性规划模型件包来求解整数线性规划模型.以以1988年美国大学生数学建模竞赛年美国大学生数学建模竞赛B题为例，题为例，说明整数线性规划模型的建立说明整数线性规划模型的建立例例3.有七种规格的包装箱要装到两节铁路平板车有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度（上去。包装箱的宽和高是一样的，但厚度（t，以，以cm 计）及重量（计）及重量（w，以，以kg计）是不同的计）是不同的.表表1给出给出了每种包装箱的厚度、重量以及数量。每节平板了每种包装箱的厚度、重量以及数量。每节平板车有车有10.2m 长的地方可用来装包装箱（像面包片长的地方可用来装包装箱（像面包片那样），载重为那样），载重为40t.由于当地货运的限制，对于由于当地货运的限制，对于C5,C6,C7 类包装箱的总数有一个特别的限制：这类包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过类箱子所占的空间（厚度）不能超过302.7cm.试试把包装箱装到平板车上，使得浪费的空间最小把包装箱装到平板车上，使得浪费的空间最小.种种类类C1C2C3C4C5C6 C7t/cm48.753.061.372.048.752.064.0w/kg2000 3000 10005004000 2000 1000n/件件8796648 为在第为在第 节车上装载第节车上装载第 件包装箱的件包装箱的解解 令令 下面我们建立该问题的整数线性规划模型。下面我们建立该问题的整数线性规划模型。1)约束条件约束条件两节车的装箱数不能超过需要装的件数，即：两节车的装箱数不能超过需要装的件数，即：每节车可装的长度不能超过车能提供的长度：每节车可装的长度不能超过车能提供的长度：每节车可装的重量不超过车能够承受的重量：每节车可装的重量不超过车能够承受的重量：对于对于C5,C6,C7类包装箱的总数的特别限制：类包装箱的总数的特别限制：2)目标函数目标函数浪费的空间最小，即包装箱的总厚度最大：浪费的空间最小，即包装箱的总厚度最大：3)整数线性规划模型整数线性规划模型由上一步中的求解结果可以看出，由上一步中的求解结果可以看出，4)模型求解模型求解运用运用LINGO软件求解得到：软件求解得到：5)最优解的分析说明最优解的分析说明的装车方案，此时装箱的总长度为的装车方案，此时装箱的总长度为1019.7cm，两节车共装箱的总长度为两节车共装箱的总长度为2039.4cm.即为最优即为最优 但是，上述求解结果只是其中一种最优的但是，上述求解结果只是其中一种最优的装车方案，即此答案并不唯一装车方案，即此答案并不唯一.0-1整数规划是整数规划的特殊情形，它要求整数规划是整数规划的特殊情形，它要求线性规划模型中的决策变量线性规划模型中的决策变量xij只能取值为只能取值为0或或1.单隐枚举法，该方法是一种基于判断条件（过滤单隐枚举法，该方法是一种基于判断条件（过滤 0-1整数规划模型的求解目前并没有非常好的整数规划模型的求解目前并没有非常好的四、四、0-1整数规划模型整数规划模型 算法，对于变量比较少的情形，我们可以采取简算法，对于变量比较少的情形，我们可以采取简条件）的穷举法条件）的穷举法.我们也可以利用我们也可以利用LINGO和和LINDO软件包来求软件包来求解解0-1整数规划模型整数规划模型.背包问题背包问题例例4.4.有有 n 个物品，编号为个物品，编号为1,2,n，第，第 i 件物品件物品重重 ai 千克，价值为千克，价值为 ci 元，现有一个载重量不超过元，现有一个载重量不超过大，应如何装载这些物品？大，应如何装载这些物品？a 千克的背包，为了使装入背包的物品总价值最千克的背包，为了使装入背包的物品总价值最用变量用变量 xi 表示物品表示物品 i 是否装包，是否装包，i=1,2,n，并令：并令：解解可得到背包问题的规划模型为：可得到背包问题的规划模型为：指派问题指派问题例例5.5.有有n 项任务，由项任务，由 n 个人来完成，每个人只能个人来完成，每个人只能做一件，做一件，第第 i 个人完成第个人完成第 j 项任务要项任务要 cij 小时，如小时，如何合理安排时间才能使总用时最小？何合理安排时间才能使总用时最小？引入状态变量引入状态变量 xij，并令：，并令：解解则总用时表达式为：则总用时表达式为：可得到指派问题的规划模型为：可得到指派问题的规划模型为：上面介绍的指派问题称为指派问题的标准形上面介绍的指派问题称为指派问题的标准形式，还有许多其它的诸如人数与任务数不等、及式，还有许多其它的诸如人数与任务数不等、及但一般可以通过一些转化，将其变为标准形式但一般可以通过一些转化，将其变为标准形式.某人可以完成多个任务，某人不可以完成任务，某人可以完成多个任务，某人不可以完成任务，某任务必须由某人完成等特殊要求的指派问题某任务必须由某人完成等特殊要求的指派问题.对于标准形式的指派问题，我们可以利用匈对于标准形式的指派问题，我们可以利用匈牙利算法实现求解牙利算法实现求解.它将指派问题中的系数构成它将指派问题中的系数构成一个矩阵，利用矩阵上简单的行和列变换，结合一个矩阵，利用矩阵上简单的行和列变换，结合解的判定条件，实现求解（见文献解的判定条件，实现求解（见文献2）.DVDDVD在线租赁第二个问题的求解在线租赁第二个问题的求解问题二的分析问题二的分析 经营成本和会员的满意度是被考虑的两个相经营成本和会员的满意度是被考虑的两个相互制约的重要因素互制约的重要因素.在忽略邮寄成本的前提下，在忽略邮寄成本的前提下，经营成本主要体现为经营成本主要体现为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.再见再见