（基础数学专业论文）规划模型及其应用.pdf

摘要 本文主要阐述了三类最常用规划即整数规划、非线性规划、多目标规划的相 关概念，并分别辅以实际例子，重点介绍了三类规划模型在实际问题中的应用。 文中应用整数规划、非线性规划、多目标规划分别解决了三个问题：奥运会临时 超市网点设计、钢管的订购与运输以及城市公交车调度。在应用整数规划模型时， 我们主要还结合了h u f f 概率法则以及最短路准则。在非线性规划模型中，我们 主要运用了f l o y d 算法进行求解。在最后建立的多目标规划模型中，我们主要运 用了非经典启发式算法遗传算法并进行了仿真求解。 关键词：整数规划非线性规划多目标规划 a b s t r a c t i nt h i sp a p e r , w eh a v em a i n l yi n t r o d u c e dr e l e v a n tc o n c e p t so nt h et h r e ek i n d so f t h em o s t p o p u l a rp r o g r a m m i n g , w h i c hi si n t e g e rp r o g r a m m i n g , n o n l i n e a r p r o g r a m m i n ga n dm u l t io b j e c t i v ep r o g r a m m i n g w ef o c u so nt h ea p p l i c a t i o no ft h e t h r e ep r o g r a m m i n gm o d e mi n t op r a c t i c a lp r o b l e m s w eh a v es o l v e dt h r e ep r o b l e m s b ya p p l y i n gt h et h r e ep r o g r a m m i n gm o d e l sr e s p e c t i v e l y ：m o d e ld e s i g nf o rt h e n e t w o r ko ft r a n s i e n ts u p e r m a r k e t si no l y m p i c sg a m e s ，s c h e d u l eo ft h eo r d e ra n d t r a n s p o r t a t i o nf o rs t e e lp i p e ，b u sd i s p a t c hi nc i t i e s w 1 1 i l es o l v i n gt h ei n t e g e r p r o g r a m m i n gm o d e l ，w eh a v ee m p l o y e dt h eh u f fp r o b a b i l i t ya n dt h es h o r t e s tp a t h c r i t e r i o n s i nt h en o n l i n e a rp r o g r a m m i n gm o d e l ，w em a i n l ya p p l yt h ef l o y d a l g o r i t h m t os o l v et h em o d e l i nt h el a s tp r o b l e m , w em a i n l yu s et h eg e n e t i ca l g o r i t h ma n d s i m u l a t i o na l g o r i t h mt os o l v et h em o d e l k e y w o r d si n t e g e rp r o g r a m m i n g n o n l i n e a r p r o g r a m m i n g m u l t i o b j e c t i v e p r o g r a m m i n g n 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝婆盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解滥望盘鲎有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年 月 日 签字日期：年 月 e t 浙江大学硕士学位论文 规划模型及其应用 第一章整数规划 1 1 相关概念 1 1 1 发展历程 整数规划是指一类要求问题中的全部或部分变量为整数的数学规划。是近 三十年来发展起来的、规划论的一个分支整数规划问题是要求决策变量取整数 值的线性规划或非线性规划问题。 一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规 划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数， 但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工 作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非 整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应 该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数， 则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数 规划的一种特殊情形是旺1 规划，它的变数仅限于0 或1 。 整数规划是从1 9 5 8 年由i l e 戈莫里提出割平面法之后形成独立分支的，3 0 多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个 相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于 求解的松弛问题( 衍生问题称为松弛问题的源问题) 。通过松弛问题的解来确定 它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问 题来替代它。随即，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重 复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是 分枝定界法和割平面法，它们都是在上述框架下形成的。 旺1 规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指 派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整 数规划都与旺1 规划等价，用旺l 规划方法还可以把多种非线性规划问题表示 成整数规划问题，所以不少人致力于这个方向的研究。求解旺1 规划的常用方 法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙 利方法就比较方便。 1 1 2 常用算法 求解整数规划的一种自然的想法是，能否用整数规划的线性松弛模型的最优 解经过四舍五入得到整数规划的最优解呢? 回答是否定的，因为这样四舍五入的 浙江大学硕士学位论文 规划模型及其应用 结果甚至不是可行解。 整数规划比通常的线性规划更加难以求解，迄今求解整数规划其基本求解思 路都是按一定的搜索规则，在整数规划的线性松弛模型的可行域内寻找出整数最 优解( 或确认无整数最优解) ，因此求整数规划的解需要更多的时间，现通用的 解法，主要有分支定界法、割平面法和穷举法等。下面简要介绍一下割平面法以 及分支定界法的基本思想。 割平面法的思想及过程：在整数规划对应的线性松弛模型中逐次增加一个新约束 ( 即割平面) ，割去原可行域中一部分不含整数解的区域，逐次切割直至最终得 到松弛问题可行域的一个最优解顶点为整数解为止。 新增约束必须满足的条件： ( 1 ) 不能割去满足条件的整数点； ( 2 ) 必须将前一次模型的最优解割去。 分枝界限法的基本思想 1 、基本思想 分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同 类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问 题的所有可行解( 数目有限) 空间进行搜索。该算法在具体执行时，把全部可行 的解空间不断分割为越来越小的子集( 称为分支) ，并为每个子集内的解的值计 算一个下界或上界( 称为定界) 。在每次分支后，对凡是界限超出已知可行解值 那些子集不再做进一步分支。这样，解的许多子集( 即搜索树上的许多结点) 就 可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止， 该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。 将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。 2 、分枝节点的选择 对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行 解最小下界的任何子集( 节点) ，都有可能作为分枝的选择对象( 对求最小值问 题而言) 。怎样选择搜索树上的节点作为下次分枝的节点呢? 有两个原则： 1 ) 从最小下界分枝( 队列式f i f o 分枝限界法) ：每次算完界限后，把搜索 树上当前所有叶节点的界限进行比较。找出限界最小的节点，此结点即为下次分 枝的结点。 优点：检查子问题较少，能较快地求得最佳解； 缺点：要存储很多叶节点的界限及对应的耗费矩阵，花费很多内存空间。 2 ) 从最新产生的最小下界分枝( 优先队列式分枝限界法) ：从最新产生的各 子集中选择具有最小的下界的结点进行分枝。 优点：节省了空间；缺点：需要较多的分枝运算，耗费的时间较多。 2 浙江大学硕士学位论文规划模型及其应用 这两个原则更进一步说明了，在算法设计中的时空转换概念。 分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担 问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。对于不同 的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。 1 2 模型的具体应用 下面具体介绍一个整数规划的实际应用 1 2 1 问题介绍 2 0 0 8 年北京奥运会已经取得了圆满成功。在奥运会的场馆建设规划阶段， 曾计划在比赛主场馆的周边地区需要建设由小型商亭构建的临时商业网点，称为 迷你超市( m i n is u p e r m a r k e t ，以下记做m s ) 网，以满足观众、游客、工作人员 等在奥运会期间的购物需求，主要经营食品、奥运纪念品、旅游用品、文体用品 和小日用品等。在比赛主场馆周边地区设置的这种m s ，在地点、大小类型和总 量方面有三个基本要求：满足奥运会期间的购物需求、分布基本均衡和商业上赢 利。 作为真实地图的简化，比赛主场馆的规划图如图l 所示，图中仅保留了与本 问题有关的地区及相关部分：道路( 白色为人行道) 、公交车站、地铁站、出租 车站、私车停车场、餐饮部门等，其中标有a 1 a 1 0 、b 1 b 6 、c 1 c 4 的黄色区域 是规定的设计m s 网点的2 0 个商区。 为了得到人流量的规律，一个可供选择的方法，是在已经建设好的某运动场 通过对预演的运动会的问卷调查，了解观众( 购物主体) 的出行和用餐的需求方 式和购物欲望。 浙江大学硕士学位论文 规划模型及其应用 暖暮搿 44- 图11 ：比赛主场馆及相关设施建模结构图 按步骤对图2 的2 0 个商区设计m s 网点，需要解决如下三个问题： 问题一：根据附录中给出的问卷调查数据，找出观众在出行、用餐和购物等方面 所反映的规律。 问题二：假定奥运会期间( 指某一天) 每位观众平均出行两次，一次为进出场馆， 一次为餐饮，并且出行均采取最短路径。依据1 的结果，测算图2 中2 0 个商区 的人流量分布( 用百分比表示) 。 问题三：如果有两种大小不同规模的m s 类型供选择，给出图2 中2 0 个商区内 m s 网点的设计方案( 即每个商区内不同类型m s 的个数) ，以满足上述三个基 本要求。 1 2 2 模型建立 问题一；根据相关问卷调查数据，找出观众在出行、用餐和购物等方面所反映的 规律。 在大量的0 0 6 0 0 份) 问卷调查的基础上，归纳出观众在出行，用餐和购物等方面所 反映的规律。经过对三次问卷调查，共1 0 6 0 0 份问卷结果的统计分析，我们得出以 下规律： 1 年龄结构： 表l1 ：年龄结构统计表 l 总人数2 0 岁以下 2 0 一3 0 岁3 0 一5 0 岁 5 0 岁以上 l 第一次调查 3 5 0 00 1 0 9 1 4 305 7 9 7 1 402 0 3 1 4 3 0 1 0 8 0 l 第二次调查 3 2 0 00 1 0 7 7 1 405 2 0 2 8 60 1 8 6 5 7 1 0 0 9 9 7 1 4 3 r i 季匕 l l l l 崔匕l拳摧 圳刚a昴酬矧吲删划矧虱 浙江大学硕士学位论文 规划模型及其应用 第三次调查 3 9 0 00 1 1 8 5 7 10 6 5 7 1 4 30 2 2 1 4 2 90 1 1 7 1 4 3 平均 3 5 3 30 1 1 0 7 5 50 5 8 0 18 90 2 0 1 7 9 20 1 0 7 2 6 4 从表中可以看出：年龄在2 0 3 0 岁的人群占绝对多数，为5 8 0 2 ；2 0 岁以下的青 少年，儿童与5 0 岁以上老人的比例占相当少数，分别为1 1 1 0 7 5 5 和1 0 7 2 6 4 2 性别比例：男( 5 2 1 7 ) 女( 4 7 8 3 ) 比例基本持平 3 出行方式： 表1 2 ：出行方式统计表： 公交( 南公交( 东 北)西) 出租 私车地铁( 东) 地铁( 西) 2 0 岁以下 0 0 2 7 20 0 1 4 90 0 1 8 5 0 0 1 0 70 0 2 0 50 0 1 9 l 2 m 一3 0 岁 0 0 9 9 50 0 8 5 70 1 1 1 70 0 5 3 6 o 1 1 4 6o 1 1 5 1 3 m 一5 0 岁 0 0 2 5 20 0 4 2 70 0 4 0 4 0 0 1 8 50 0 3 6 90 0 3 8 l 5 0 岁以上 0 0 1 5 50 0 2 9 2o 0 1 9 1 0 0 0 7 60 0 1 7 30 0 1 8 7 总计 0 1 6 7 4o 1 7 2 50 1 8 9 60 0 9 0 40 1 8 9 20 1 9 0 9 从表中可以看出，公交车和地铁是大多数人群的出行首选，分别占总人口数的 3 3 9 9 ( 1 6 7 4 + 1 7 2 5 ) 和3 8 0 1 ( 1 8 9 2 + 1 9 0 9 ) ；其次为选乘出租车的人群， 占总人口数的1 8 9 6 ；只有很少部分( 9 4 ) 人使用私家车，而出行方式与年龄结 构之间相关性并不明显。 4 餐饮方式： 表1 3 ：餐饮方式统计表 中餐 西餐商场( 餐饮) 2 0 岁以下o 0 1 1 60 0 5 2 10 0 4 7 1 2 岫0 岁 0 0 9 3 6 0 3 5 9 30 1 2 7 3 3 m 一5 0 岁 0 0 7 6 10 0 8 4 30 0 4 1 3 5 0 岁以上0 0 4 3 40 0 2 9 40 0 3 4 4 总计 0 2 2 4 7 0 5 2 5 20 2 5 0 1 从表中可以看出，西餐是大多数人的餐饮首选，占总人口的5 2 5 2 。商场 ( 餐饮) 和中餐分别占总人口的2 2 4 7 和2 5 0 1 ，餐饮方式与年龄结构之间的 相关性也不明显。 5 消费额度： 表1 4 ：消费额度统计表 m 一1 0 01 0 咐0 02 0 m 3 0 03 0 0 4 0 04 0 m 一5 0 05 0 0 以上 第一次调查 0 1 9 5 10 2 3 8 00 4 5 4 30 0 8 9 4 0 0 1 3 40 0 0 9 7 第二次调查 0 1 9 6 6 0 2 5 5 00 4 3 5 00 0 8 4 10 0 1 8 80 0 1 0 6 5 浙江大学硕士学位论文 规划模型及其应用 第三次调查 0 1 9 1 8o 2 5 1 30 4 3 2 30 1 0 2 8o 0 1 2 80 0 0 9 0 平均 0 1 9 4 50 2 4 8 10 4 4 0 50 0 9 2 1o 0 1 5 00 0 0 9 7 从表中可以看出，多数观众消费额度在1 0 0 3 0 0 元之间，占6 8 8 6 。消费 额度在5 0 0 以上的仅占总人口的0 9 7 。在各次调查中，观众的消费额度结构保 持稳定。 问题二根据问题一的结果，测算图一中2 0 个商区的人流量分布( 用百分比表示) 观众吸引力模型 进一步确定观众在出行时( 一次为进出场馆，一次为餐饮) 前往各个交通餐 饮设施的可能性。联想商圈的确定理论上著名的顾客吸引力模型，该模型是由美 国加利福尼亚大学的经济学者h u f f d 在1 9 6 4 年提出的在城市区域内商圈规模预 测的空间影响模型，该模型最大的特点是更接近于实际，他将商圈理论具体到以 商店街、百货店、超级市场为单位，综合考虑人口、距离、零售面积规模等多种 因素，将各个商圈地带的引力强弱、购物比率发展成为概率模型的理论。假定营 业能力，竞争力，美誉度相同的数个网点集中一地时，居民利用那一点接受服务 的概率是由该区域网点面积和居民到服务点所花的时间决定的，h u f f 概率准则 模型为： ：坠塑l0 - 1 ) i s , ( 乃) 五】 = l 式中只为消费者从住所前往商区的可能性；s ，为某类商品在商业区内的总营业 面积；根据集中吸引原则消费者总是倾向于总营业面积较大的商业区( 商店较集 中) 以便进行挑选和价格比较，因此s ，可以用来衡量消费者倾向于不同商业区 的概率；瓦为消费者从住所到商业区所需花费的时间；五指数用来衡量顾客因 购物类型不同而对路途时间的重视程度不同，五需要通过实际调研或运用计算 机程序加以确定日常服务中，五= 1 2 。1 1 为不同商业区的数量。 类似地，建立观众吸引力模型，用表示观众从比赛场馆前往各个交通餐 饮设施的可能性；s ；表示观众主观倾向：即观众在选择不同的交通工具和餐饮 方式时，受主观喜好，个人习惯，美誉度等多种主观因素影响主观上倾向于各种 交通工具和餐饮方式的概率。乃为观众从比赛场馆前往各交通餐饮设施所需花费 的时间，五指数用来衡量观众路途时间的重视程度，在本模型中取五= l 。运用 6 浙江大学硕士学位论文规划模型及其应用 h u f f 准则建立观众吸引力模型为： 昂：半坦卫 晦饵) 。 ，- 】 可见，二者在形式上是完全一样的。 ( 1 五) 主观俩向s ， 观众在选择不同的交通工具和餐饮方式时往往受主观倾向和距离远近的左 右，问题一的统计结果在很大程度上可以反映0 8 奥运会时观众在出行、用餐和 购物等方面的规律。图- 是已经建设好的某运动场比赛主场馆及相关设施简化 图，在该图中，各交通餐饮设施目标点与主场馆的距离相差很小，可咀视为相等。 因而，问题一的统计结果可以反映出在不受距离远近困素影响的情况下观众的选 择倾向，即 主观倾向s 瞄鎏l 。瞳邕璧翘 。隧- - 。o _ 舞 一 鉴箍妒| 懑 零罂暨：t 蠹参1 2 一+ 。蕾鐾目髓墨高 w 1 圈e 誓量。 一鼙三二墅塑霎粤 i一瑚二。_ 三 瞳熊霉 瞳崮i 盈l 凰12 某运动场比赛主场馆及相关设施简化图 对交通设施餐饮设施标号：= 公交( 南北) = 公交( 东西) = 出租= 私车 = 地铁( 西) 护地铁( 东) = 中餐 = 西餐g - 商场( 键饮) 根据问题一的结果，观众在选择交通工具和餐饮方式的主观倾向为： 表l f i ：主观倾向统计衰 浙江大学硕士学位论文规划模型及其应用 商场公交公交 地铁地铁 中餐西餐( 餐( 南( 东出租私车 ( 东)( 西) 北)西)饮) s j墨 是墨 蜀s 瓯 s ， 最s 主 观 0 1 6 7 40 1 7 2 5o 1 8 9 60 0 9 0 4o 1 8 9 20 1 9 0 90 2 2 4 70 5 2 5 20 2 5 0 1 倾 向 墨表示观众总体主观上以怎样的概率倾向于各种交通工具和餐饮方式。因此有： s l + s 2 + s 3 + s 4 + s 5 + s 6 = 1 s 1 + s s + s 9 = 1 ( 1 - 3 ) ( 1 - 4 ) 最短时间乃： 观众从比赛场馆前往各交通餐饮设施所需花费的时间与比赛场馆到各交通 餐饮设施的最短距离d ：f 有关。因为观众吸引力模型为比例式，最短时间乃可以 用亩来衡量。通过图论中有关最短路径的知识和对图形一进行网格划分( 女口图三 所示) ，可以估算出出行时所经得最短路径d 矗( 用格子数来表示) ，该最短路径如 果经过该商区记为“1 ”，不经过该商区记为“0 ”。如果同时存在n 条最短路径 ( n 2 ) ，记为“二”，这里如果存在两条路径格子数仅差l 2 个，便可以视为同 刀 为最短路径。 8 浙江大学硕士学位论文规划模型及其应用 图1 3 ：比赛主场馆及相关设施建模网格圈 三个场馆的每个看台出口对准一个商区，因此最短距离即为观众所在看台对 应商区到各个交通餐饮设施的最短路径。依据上述统计方法，商业规划区 斗公 变( 南北) 的最短路径1 7 ，同时存在两条：分别为4 斗4 一 斗4 斗4 斗4 斗 公交( 南北) 和4 _ _ + 4 - + 4 斗4 斗 - - ) 公交( 南北) 。因此记为 表16 = 最短路径 l 起点终点距离 a 8 a 1 0 l l a 1 05o5o50 50 , 5 i l 起点 终点距离b 3c 1c 2c 4 l l a l 00 00 l 同理可以统计所有商区到交通餐饮设施的最短路径以及沿途经过商区，进一 步可以求出只。 为简化起见，假定国家体育场( 鸟巢) 容量为1 0 万人，国家体育馆容量为 6 万人，国家游泳中心( 水立方) 容量为4 万人。三个场馆的每个看台容量均为 1 万人，出口对准一个商区，各商区面积相同。奥运会时，各场馆的上座率均为 1 0 0 。 第i 个商区选择第j 个交通餐饮设施的潜在人流量为： 川= 弓x 1 0 0 0 0 ( 1 - 5 ) 浙江大学硕士学位论文规划模型及其应用 因为观众往返路线相同，经过每个商区次数为2 ，所以经过第i 个商区的潜在人 流量为： 对数据进行处理，可得图一中2 0 个商区的潜在人流量分布为： 表1 7 ：潜在人流量分布 ( 1 - 6 ) 商区a 1 _ a 2 a 3 a 4 a 5a 6a 7a 8a 9a 1 0 人数 0 9 3 6 10 5 3 5 20 5 6 9 50 6 5 2 90 7 4 8 01 3 0 1 60 4 9 7 10 4 1 0 30 4 6 9 9o a 7 6 5 ( 万) 百分比0 0 8 6 8 o 0 4 9 60 0 5 2 80 0 6 0 50 0 6 9 3 0 1 2 0 60 0 4 6 l0 0 3 8 00 0 4 3 60 0 4 4 2 商区 b 1b 2 b 3 b 4b 5b 6 c lc 2c 3c 4 人数 0 4 5 8 00 3 6 5 60 5 0 6 10 3 2 4 30 3 6 3 30 8 1 1 50 2 1 6 2o 3 1 8 30 2 6 5 20 5 6 3 2 ( 万) 百分比0 0 4 2 50 0 3 3 90 0 4 6 90 0 3 0 10 0 3 3 70 0 7 5 20 0 2 0 00 0 2 9 50 0 2 4 60 0 5 2 2 问题三基于上述两个问题的分析：如果有两种大小不同规模的m s 类型供选择， 给出图2 中2 0 个商区内m s 网点的设计方案( 即每个商区内不同类型m s 的个 数) ，以满足地点、大小类型和总量方面的三个基本要求：满足奥运会期间的购 物需求、分布基本均衡和商业上赢利。 所谓商圈，是指“经营某种产品或服务的某家或某类企业的顾客分布的地理 区域”，商业上用“商圈”来描述商店的覆盖范围。应用g i s 原理进行店址选择和 优化连锁零售企业网络布局。影响商店选址的主要因素是商圈内的人流量及购物 欲望。统计各个商业规划区内不同消费档次的人数( 万) 和潜在期望消费总额如 下表所示： 表1 8 ：不同消费档次的人数( 万) 和潜在期望消费总额 m 1 0 0 1 0 m 一2 0 02 0 m 一3 0 03 0 0 4 0 0 4 0 m 一5 0 05 0 0 以上总额( 元) a 11 8 8 8 32 4 5 6 04 0 1 3 80 8 1 2 7 o 1 1 4 70 0 7 5 7 18 4 3 9 6 0 0 a 21 0 4 9 01 3 6 5 32 3 4 0 50 4 7 3 30 0 7 6 0o 0 4 7 510 6 8 3 5 0 0 a 31 0 9 3 91 4 1 7 32 5 2 5 70 5 1 3 l0 0 8 9 90 0 5 5 5l1 4 9 2 8 0 0 a 4 1 2 4 0 4 1 5 9 2 92 9 2 0 80 5 9 4 30 1 1 1 20 0 6 9 613 2 7 4 8 0 0 a 51 4 0 9 4 1 7 9 8 43 3 6 6 5o 6 8 6 40 1 3 4 30 0 8 4 81 5 2 9 1 7 0 0 a 6 2 4 3 0 0 3 0 9 3 85 8 8 7 41 2 0 9 40 2 4 2 20 1 5 2 72 6 7 3 6 8 5 0 a 7 0 9 3 2 11 1 9 8 42 2 3 6 10 4 6 3 6 0 0 8 7 10 0 5 4 01 0 1 6 5 4 5 0 1 0 2 ” ，芦 = 浙江大学硕士学位论文规划模型及其应用 a 80 7 7 9 71 0 1 5 21 8 2 5 00 3 7 8 70 0 6 4 80 0 3 9 38 3 0 8 3 5 0 a 90 9 0 3 81 1 8 2 02 0 7 3 70 4 2 9 60 0 6 8 80 0 4 1 59 4 5 0 6 0 0 a 1 00 9 4 4 91 2 3 1 72 0 6 3 30 4 2 4 30 0 6 1 70 0 3 9 49 4 5 7 6 5 0 b 10 9 1 3 81 1 3 9 72 0 1 8 10 3 9 9 80 0 6 4 3o 0 4 4 99 1 4 7 3 0 0 b 20 7 2 8 30 9 2 2 31 5 9 9 20 3 2 5 30 0 4 8 10 0 3 2 77 2 8 0 4 5 0 b 3 1 0 0 8 8 1 3 0 3 62 1 9 1 1 0 4 5 7 60 0 6 0 20 0 3 9 710 0 2 8 4 0 0 b 40 6 4 5 00 8 1 5 61 4 1 8 7 0 2 9 1 1o 0 4 2 90 0 2 9 86 4 6 8 4 5 0 b 50 7 3 2 00 9 0 2 11 5 8 8 0 o 3 1 7 40 0 5 4 20 0 4 0 07 2 6 3 9 5 0 b 61 6 3 0 31 9 8 8 23 5 7 0 30 7 0 5 3o 1 2 6 8 0 0 9 3 816 2 7 8 2 5 0 c l0 4 3 5 90 5 4 3 40 9 3 2 00 1 9 2 20 0 3 3 80 0 2 5 24 3 2 6 4 5 0 c 20 6 1 6 90 8 0 0 91 3 7 8 10 3 1 1 0 o 0 4 6 30 0 2 9 66 4 1 4 7 0 0 c 3o 5 2 0 20 6 5 7 31 1 6 2 40 2 4 6 70 0 3 9 1 0 0 2 6 55 3 3 7 2 0 0 ( 3 41 1 2 7 21 4 0 2 82 4 5 9 80 4 9 5 10 0 8 5 20 0 6 1 811 2 7 3 4 5 0 从附表可以看出：观众每次出行平均要穿过5 个不同的商业规划区，往返平 均要穿过l o 个不同的商业规划区，而在途中每个商业区消费的概率是相等的， 因此每个商业区的实际期望消费总额应为潜在期望消费总额的1 1 0 。 整数规划模型 为了确定2 0 个商区内m s 网点的设计方案( 即每个商区内不同类型m s 的个数) 建立整数规划模型进行求解： 目标函数： 卫 朋级( q 一巨吩一易) ( 1 - 7 ) 其中， q ：f 表示商业区的实际期望消费总额，乓，最分别为大、小超市的平均日 经营成本。 ，分别表示第i 个商区内大小超市的数量。这个目标函数保证了赢利最大。 约束条件： 1 毛吩+ 毛砚q其中忍、e 分别表示大小超市的日营业额上限( 受存储量 和上货速度等因素的影响) ，这个约束条件保证了基本满足观众的购物需求。 2 q 一巨吩一易他0 这个约束条件保证了在整个奥运临时超市网络赢利最大 的同时，每个商业规划区赢利。 3 h + m s - n j - m j d 其中，f 歹；d 表示为了保证均衡性任意两个不同商区大 浙江大学硕士学位论文规划模型及其应用 小超市的总数目允许相差的阀值。这个约束条件保证了超市的分布基本均衡。 由此可得整数规划模型： im a x z ( q i 一巨吩- e 2 m , ) 1 扭1 j s 丁e 3 n , + e 4 m , q f iq i 一巨一岛0 0 n i + 一n j 一l d ( 1 8 ) 其中n i 、他均为整数。 1 2 3 模型的求解 查阅相关数据，对模型进行试验求解： 取巨= 2 5 ( 万元) ，易= 5 ( 万元) 9 3 = 5 0 ( 万元) ，日= 1 0 ( 万元) ，d = 3 。 利用l i n g o 软件求得2 0 个商区内m s 网点的优化设计方案为： 表1 9 ：优化设计方案 商区 a la 2a 3a 4a 5a 6a 7a 8a 9a l o 大超市数量n i 3 1l225ll1l 小超市数量 4 6 7462 6 4 55 总计 7786877566 商区 b lb 2b 3b 4b 5b 6c 1c 2c 3c 4 大超市数量惕 l0l00300ol 小超市数量 5867825767 总计 6877855768 可见分布基本均衡。最大赢利为1 0 2 1 1 9 9 万元。 1 2 浙江大学硕士学位论文规划模型及其应用 第二章非线性规划 2 1 相关概念 2 1 1 发展历程 具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。非 线性规划研究一个n 元实函数在一组等式或不等式的约束条件下的极值问题， 且目标函数和约束条件至少有一个是未知量的非线性函数。目标函数和约束条件 都是线性函数的情形则属于线性规划。 非线性规划是2 0 世纪5 0 年代才开始形成的- i 7 新兴学科。1 9 5 1 年h w 库 恩和a w 塔克发表的关于最优性条件( 后来称为库恩一塔克条件) 的论文是非线 性规划正式诞生的一个重要标志。在5 0 年代还得出了可分离规划和二次规划的 n 种解法，它们大都是以g b 丹齐克提出的解线性规划的单纯形法为基础的。5 0 年代末到6 0 年代末出现了许多解非线性规划问题的有效的算法，7 0 年代又得到 进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的 应用，为最优设计提供了有力的工具。 2 1 2 相关模型及求解算法 建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与 决策变量之间的函数关系，称之为目标函数。然后将各种限制条件加以抽象，得出 决策变量应满足的一些等式或不等式，称之为约束条件。非线性规划问题的一般 数学模型可表述为求未知量x 1 ，x 2 ，x n ，使满足约束条件： g i ( x l ，则i = 1 ，m h j ( x l ，x n ) = 0j = 1 ，p 并使目标函数胀1 ，x n ) 达到最小值( 或最大值) 。其中f ，诸西和诸均都 是定义在n 维向量空间r n 的某子集d ( 定义域) 上的实值函数，且至少有一个是非 线性函数。 上述模型可简记为： m i n f 辑) s t g i ( x ) 却i = 1 ，m h j ( x ) = 0 j = 1 ，p 其中x - - ( x l ，x n ) 属于定义域d ，符号r a i n 表示“求最小值”，符号s t 表示 “受约束于”。 定义域d 中满足约束条件的点称为问题的可行解。全体可行解所成的集合 称为问题的可行集。对于一个可行解x ，如果存在x 宰的一个邻域，使目标函数在 1 3 浙江大学硕士学位论文规划模型及其应用 x 处的值坟妒) 优于( 指不大于或不小于) 该邻域中任何其他可行解处的函数值， 则称x 唯为问题的局部最优解( 简称局部解) 。如果取木) 优于一切可行解处的目标 函数值，则称x 为问题的整体最优解( 简称整体解) 。实用非线性规划问题要求整 体解，而现有解法大多只是求出局部解。 一维最优化方法指寻求一元函数在某区间上的最优值点的方法。这类方法 不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用 的一维最优化方法有黄金分割法、切线法和插值法。 黄金分割法又称0 6 1 8 法。它适用于单峰函数。其基本思想是：在初 始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出 近似最优值点。 切线法又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个 猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点， 逐步迭代去逼近最优点。 插值法又称多项式逼近法。其基本思想是用多项式( 通常用二次或三 次多项式) 去拟合目标函数。 此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。 无约束最优化方法指寻求n 元实函数f 在整个i 1 维向量空间r n 上的最优 值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多 约束最优化方法可将有约束问题转化为若干无约束问题来求解。 无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两 类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函 数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利 搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同样手续， 如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以 有各种算法。属于解析型的算法有：梯度法：又称最速下降法。这是早期的解 析法，收敛速度较慢。牛顿法：收敛速度快，但不稳定，计算也较困难。共 轭梯度法：收敛较快，效果较好。变尺度法：这是一类效率较高的方法。其中 达维登一弗莱彻一鲍威尔变尺度法，简称d f p 法，是最常用的方法。属于直接型 的算法有交替方向法( 又称坐标轮换法) 、模式搜索法、旋转方向法、鲍威尔共 轭方向法和单纯形加速法等。 约束最优化方法指前述一般非线性规划模型的求解方法。常用的约束最优 化方法有4 种。拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻 点。制约函数法：又称系列无约束最小化方法，简称s u m t 法。它又分两类， 一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是 将原问题转化为一系列无约束问题来求解。可行方向法：这是一类通过逐次选 1 4 浙江大学硕士学位论文规划模型及其应用 取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克一沃尔夫法、 投影梯度法和简约梯度法都属于此类算法。近似型算法：这类算法包括序贯线 性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者 将原问题化为一系n - 次规划问题求解。 凸规划这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f 是凸函数，诸西都是凹函数，诸场都是一次函数，则称之为凸规划。所谓f 是凸 函数，是指f 有如下性质：它的定义域是凸集，且对于定义域中任意两点x 和y 及 任一小于1 的正数a ，下式都成立： 坟( 1 - a ) x + 叫) o 【g1 - 叻f i x ) + 畈y ) 将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下 性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。 对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必 为整体解，而且凸规划的可行集和最优解集都是凸集。 二次规划一类特殊的非线性规划。它的目标函数是二次函数，约束条件是 线性的。求解二次规划的方法很多。较简便易行的是沃尔夫法。它是依据库恩一 塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、 毕尔法、凯勒法等。 几何规划一类特殊的非线性规划。它的目标函数和约束函数都是正定多项 式( 或称正项式) 。几何规划本身一般不是凸规划，但经适当变量替换，即可变 为凸规划。几何规划的局部最优解必为整体最优解。求解几何规划的方法有两类。 一类是通过对偶规划去求解；另一类是直接求解原规划，这类算法大多建立在根 据几何不等式将多项式转化为单项式的思想上。 应用问题在经营管理、工程设计、科学研究、军事指挥等方面普遍地存在 着最优化问题。例如：如何在现有人力、物力、财力条件下合理安排产品生产， 以取得最高的利润；如何设计某种产品，在满足规格、性能要求的前提下，达到 最低的成本；如何确定一个自动控制系统的某些参数，使系统的工作状态最佳； 如何分配一个动力系统中各电站的负荷，在保证一定指标要求的前提下，使总耗 费最小；如何安排库存储量，既能保证供应，又使储存费用最低；如何组织货源， 既能满足顾客需要，又使资金周转最快等。对于静态的最优化问题，当目标函数 或约束条件出现未知量的非线性函数，且不便于线性化，或勉强线性化后会招致 较大误差时，就可应用非线性规划的方法去处理。 2 2 模型的具体应用 下面具体介绍一个非线性规划( - - 次规划) 的实际应用。 浙江大学硕士学位论文 规划模型及其应用 2 2 1 问题介绍： 要铺设一条4 4j 一4 ，的输送天然气的主管道，管道铺设与交通网络图如 图2 1 所示。经筛选后可以生产这种主管道钢管的钢厂有s ，是，岛。一个钢厂如 果承担制造这种钢管，至少需要生产5 0 0 个单位。钢厂墨在指定期限内能生产该 钢管的最大数量为岛个单位，钢管出厂销价1 单位钢管为p , t y 元，如下表： 表2 1 ：钢管出厂销价 l l234567 s f 8 0 08 0 01 0 0 02 0 0 02 0 0 02 0 0 03 0 0 0 p i 1 6 01 5 51 5 51 6 01 5 51 5 01 6 0 l 单位钢管的铁路运价如下表： 表2 2 ：单位钢管的铁路运价 里程( k m ) 3 0 03 0 1 3 5 03 5 l - 4 0 04 0 l - - - 4 5 04 5 1 5 0 0 运价( 万元) 2 02 32 62 93 2 里程( k m ) 5 0 1 6 0 06 0 1 7 0 07 0 1 8 0 08 0 1 9 0 09 0 1 1 0 0 0 运价( 万元) 3 7 4 4 5 05 56 0 1 0 0 0 k m 以上每增加1 至1 0 0 k m 运价增加5 万元。 公路运输费用为1 单位钢管每公里o 1 万元( 不足整公里部分按整公里计算) 。 钢管可由铁路、公路运往铺设地点( 不只是运到点4 , a 2 ，4 s ，而是管道全线) 。 ( 1 ) 请制定一个主管道钢管的订购和运输计划，使总费用最小( 给出总费用) 。 ( 2 ) 请就( 1 ) 的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影 响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并 给出相应的数字结果。 ( 3 ) 如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成 网络，请就这种更一般的情形给出一种解决办法，并对图二按( 1 ) 的要求给出 模型和结果。 1 6 浙江大学硕士学位论文 规划模型及其应用 。粗线表 示铁路，单细线表示公路，双细线表示 要铺设的管道( 假设沿管道或者原来有 公路，或者建有施工公路) ，圆圈表示火 车站，每段铁路、公路和管道旁的阿拉 伯数字表示里程( 单位l ( m ) 。 图2 1 ：管道铺设与交通网络示意图( 铺设管道直线情形) 粗线表 线表示 来有公 路，或者建有施工公路) ，圆圈表示火车 站，每段铁路、公路和管道旁的阿拉伯 数字表示里程( 单位k m ) 。 图2 2 ：管道铺设与交通网络示意图( 铺设管道树形图情形) 1 7 浙江大学硕士学位论文规划模型及其应用 2 2 2 模型建立： 决策变量：要铺设一条4 4 专寸4 ，的输送天然气的主管道，设从钢厂s 订购并运往铺设节点4 的钢管量表示为彰，其中往正方向铺设的部分表示为 彰+ ，往负方向铺设的部分表示为彰一。 目标函数： 本题要求制定一个主管道钢管的订购和运输计划，使总费用最小。而总费用由三 部分组成，即：订购费用，运输费用和铺设费用。 订购费用e x p e n