CPLEX在优化调度中的应用

福 建 电 脑福 建 电 脑 !""#年第 $$期 !"#$%在优化调度中的应用 孙 岚 !福州大学数学与计算机学院 福建 福州 !"###$" !摘 要" %&’( )*&+, 是目前国际上流行的优化软件包#是一种高性能$健壮$灵活的优化软件#它包括 )*&+, 接口和 )*&+, 算法% %&’( )*&+, 被广泛应用于物流行业$制造业$通信业$油田地面工程等#使得一些复杂的问题求 解变得相对简单$高效% 本文着重描述 )*&+, 在水电调度中的应用#并以美国 -. 公司的实际调度数据构造算法实例 进行验证#得到了较好的效果% !关键词" )*&+,#水电调度#混合整数规划% 一#引言 %&’(是全球领先的软件组件开发商 ! %&’( ’)*+,+-.*+/0 12+*3 则是由 %&’( 公司开发的一个优化组件系列" 它以 %&’( 1/4536 与 %&’( 78&9: 作为基础"允许开发人员为资源优化#排 序#物流# 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 与配置创建强大的解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ! %&’( 78&9: 由 78&9: 接口和 78&9: 算法组成! 78&9: 接口又由组件库和交互优化程序两部分组成! 组件库允许开发 人员将 %&’( 78&9: 引擎完整#有效地整合到应用程序中$交互 优化程序提供了开发和部署应用程序过程中的各种不同的连接 方式!灵活的接口能够使其用于大多数开发环境及很多种平台" 提供了真正的可移植性! 78&9: 本身并不是一种算法"但是却 包含一系列可配置的算法"也称为优化选择"这些优化选择主要 包括单一优化程序#界限优化程序和混合整数优化程序!用户可 以根据实际问题的不同特点"选用不同的优化程序来解决!特别 地"%&’( 78&9: 混合整数优化程序应用一种前沿的策略的划 分范围技术%%%;2**+0<=3><3" 可以为大多数复杂的混合整数规 划问题提供一种快捷#强大的解决方案"使其更快得找到鲁棒性 更好的解! 短期水火电调度属于大规模#离散#非线性且非凸的数学规 划问题!系统决策变量包括了离散和连续变量$每台机组都有各 自的运行约束和物理约束"水电系统中还有库容约束! 因此"这 一问题在数学上是一个复杂的混合整数规划问题"也是一个 ?8 难题! 由于问题的困难性"直接寻找最优解几乎不可能! 目前较 多采用的为次优化算法"即寻找一个满意的解而不是最优解!近 年众多研究表明 &.<6.0<3 松弛法是一种求解此类问题的有效算 法@$A"它的主要优点包括&能够灵活处理多种约束$计算量随着 问题规模的增大仅呈线性增长$ 得到的对偶间隙可以定量 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 可行调度方案的优劣$&.<6.0<3 乘子有着重要的经济意义等! 但 是"即使在这种算法框架下"水电调度子问题仍然没有有效的求 解方法! 然而"正如上文所述"78&9: 综合了多种算法的优点" 它可以在较短的时间内解决多变量的#复杂的#混合整数规划问 题" 尤其是其中的混合整数优化程序对很多实际的混合整数规 划问题的求解都是行之有效的"所以本文采用 78&9: 优化软件 包进行二次开发来解决水火电调度问题中的水电调度子问题! 二#问题描述 能够应用 78&9: 求解的混合整数规划模型一定是线性的 混合整数规划模型"因此在有关利用 78&9: 求解水电调度问题 的文献 @!BCA 中"描述的模型通常没有考虑机组的最小开关机约 束这一非线性因素"这样的问题相对比较容易! 然而"考虑完整 的约束不仅符合实际运行情况"而且将大大减小运行费用"甚至 对水电机组的控制系统以及机组本身机械设备的维护和使用寿 命具有很大意义!因此"本文将考虑具有最小开关机时间约束情 况下的完整问题"将水电转换函数曲线分段线性化"通过引入多 组与分段线性函数相关的变量转换原问题的非线性性" 将非线 性的梯级水电问题转化成线性的混合整数规划问题! 下面考虑一个有 ! 个火电机组和 " 个水系的电力调度系统 在调度周期 # 内的调度问题"通过引入松弛因子"使原本具有耦 合关系的的水#火电调度问题具有可拆分性 @DA"得到如下的单水 系子问题& ,+0 # $ % E !’&’((’($)))*’($)+!($)(’($)+"($),’($)* 式中 (’($)和 ,’($)分别表示水系 ’ 在第 $ 小时的输出功率 和提供的备用$ &’($)和 *’($)表示第 ’ 个水系的燃料费用和启 动费用$!($)# "($)为松弛因子! 本文求解梯级水电子问题要满足两个假设& EF 一个水库至多有一个直接下游水库! !F 对于抽蓄机组而言"机组在抽蓄状态下用了多少电就可 以提供多少备用! 在满足这两个假设的情况下" 每一个独立水系的优化调度 子问题必须满足下面的约束&水电机组约束#河道约束#水库约 束@DA! 引入开#关机操作变量 -’./0($)"1’.20($)"他们都是 "!E 变量"分 别表示第 ’ 条水系中#第 . 个水库上的第 0 个机组在第 * 时段的 关机操作和开机操作"当变量取 E 时"表示该机组在第时段进行 了一次关机或开机操作!此时"对于水电机组而言"开#关机状态 约束可以描述为& 3’.20($)+3’.20($+E)G1’.20($)+-’.20($)" 1’.20($)H-’.20($)"$ 式中 3’.20($)也是 I!E 变量"表示机组在第时段的开关机状 态"当该变量取 E 时"表示该机组在第时段处于开机状态! 因此 最小开#关机时间约束可以描述为& #’.20和 #’.20分别表示第 ’ 条水系中#第 . 个水库上的第 0 个机 组的最小开机时间和最小关机时间! 另外"一般的水电转换曲线也是模型中的非线性因素"本文 采用分段线性化进行处理"用+机组独立状态,来描述机组是处 于关机#抽蓄还是开机状态"独立状态数有以下两种取值& 45,6,’.20 7EB 一般水电机组 45,6,’.20 J!B 抽蓄机# 组 其中 45,6,’.20表示第 ’ 条水系中# 第 . 个水库上的第 0 个机 组分段线性的 %K’ 曲线的分段数! 抽蓄机组在抽水时被认为是关机的" 且这时的发电量为负 值!无论是一般机组还是抽蓄机组"关机时所对应的状态即为原 点! 基于此"应该满足下面的约束& 3’.202$($)J4894’.($)"$ 3’.20($)=4894’.($)"I 3’.202$($)J3’.20($)"$ 式中 4894’.($)为 I!$ 变量"当它取值为 I 时表示第 $ 时段 ,min{ , 1} , , 1 ( ) ( ) 1 k j lT t k k j l j l t y t x t t t + - = + + £å ,min{ , 1} , , 1 ( ) ( ) 1 k j lT t k k j l j l t x t y t t t + - = + + £å !/ 福 建 电 脑福 建 电 脑!""#年第 $$期 询不同的是!上述查询的结果是与位置相关的!同样一个问题在 不同的地理位置得到的回答可能是不同的! 如最近的宾馆在哪 里!去最近的医院该怎么走等等" ! 总结 随着网络技术的迅速发展和不断渗透! 在任何地点和任何 时候都能接入网络获取各种信息!必将成为 !$ 世纪人类的普遍 要求! 移动数据库技术的许多特性都与信息时代的不断进步的 需求相吻合% 有着广阔的发展空间" 移动数据库技术配合 &’( 技术!可以用于智能交通管理#大宗货物运输管理和消防现场作 业等"移动数据库技术还在零售业#制造业#金融业#医疗卫生等 领域展现了广阔的应用前景"总之!随着人们对信息需求的不断 增加!无线网络和通信技术的不断进步!移动数据库领域的研究 大有希望!必将为人类带来巨大的商业和社会价值" 参考文献 !"#冯玉才$李东等 一种移动数据库管理系统的体系结构!%#& 计算机研究与发展$ ’(("!)& *+’(,+’-& !’#林怀忠$陈纯等& 移动环境下事务一致性的动态实现!%#& 计算机研究与发展$ ’((’$" *"((,"(-& !.#杨进才"刘云生等!嵌入式实时数据库系统的存储管理!%#!小型微型计算机系统!’((’!+ !-# 叶建位$苏宏业&实时数据库系统关键技术及实现!%#&计算机应用研究$’(()$/.0 !)# 赵旸$董逸生&移动数据库的同步管理技术的研究!%#&计算机应用$’((-$/"’1& 第 ! 个水库上没有任何机组处于发电状态$取值为 $ 表示第 " 时 段第 ! 个水库上没有任何机组处于抽水状态"#$%&’&(’%"&也是 )!$ 变 量!该变量取值为 $ 时表示机组处于第 " 时段它的 *+, 特性分段 线性曲线上的段" 利用分段线性函数在每一段的斜率# 最大发电量和最小发 电量可以简单地表示其他的发电量约束-./" 在进行了如上的处理后 ! 水电调度子问题的模型符合 0’123 对模型线性化的要求" 三!数值仿真 调度仿真中的火电机组数据均选自美国 45 公司的实际调 度数据" 该调度仿真中包括 !6 个火电机组和 7 个水电机组!完 成 !. 小时的短期优化调度"采用本文的混合整数规划线性模型 对水电子问题进行建模! 然后利用 *1,& 0’123 优化软件包在 8099的集成环境下开发#编译!选择 0’123 混合整数优化器! 将其中一些可变的选择策略进行用户化!寻求问题的最优解"为 了使该子问题的求解独立于编程语言! 并将其开发为动态链接 库! 从而可以被在 099 :;<=>?@ 环境中开发的调度主程序调用! 不受调度主程序的编译环境的限制" 下面分别提供了该调度问题的系统负载需求曲线 %图 A&# 水库拓扑结构以及各个水电机组的信息%图 !&" 从水电机组信 息表中可以看出该问题中共有三个水库" 图 A 系统负载需求曲线 图 !水库拓扑结构及水电机组信息 图 B 表示水火电联合调度时火电机组的出力情况" 在水火 电联合调度时!水电机组在调度中起到了削峰填谷的作用!所以 火电机组发电量曲线较为平缓" 图 B 水火电联合调度时 !6 个火电机组出力 另外!在 !6 个火电机组中!A!AA 号机组的最大发电量仅有 几十 CD!而 A!!!6 号机组最大发电量有几百 CD" 在加入水 电后!就每一个小时机组提供的负载来看!容量小的机组的出力 首先产生变化! 几个容量小的机组甚至在整个调度周期内一直 未开! 这是因为装机容量小的火电机组单位发电费用相对于大 装机容量的机组要大!为了使费用最优!这些小装机容量的机组 应该尽可能的少开或者不开" 图 . 中的三条曲线分别表示’水火电联合调度时!三个水库 上的水电机组在调度周期内各个小时提供的总的负载情况" 图 . 水火电联合调度时水电机组的出力 由图 . 可以得到如下的结论’ 在调度周期的开始几个小时 内!由于水量充足!因此水电机组出力较大!在以后的时段内!由 于受到库容约束和河道流量约束限制!出力减小!但是从总体来 看!用水首先保证了在负载出现高峰期的时段!水电机组保持开 机状态!从而达到(削峰)作用" 四!结论 本文着重研究了短期水火电调度问题中水电子问题的有效 求解方法"文中采用分段线性#引入整数变量等方法解决了水电 子问题约束的非线性情况! 建立水电子问题的混合整数规划模 型!并借助 0’123 优化软件包进行二次开发"通过数值仿真!初 步验证了该方法的有效性和合理性" 参考文献" !"# 2&345$ *&6& 789 :& ;845 45< *&=& >?@45& AB9C<8DE5@ ?F 2GCCYCL$ A&X V9HELI?F?HE