多周期多设备公用工程系统的混合整数优化算法及应用
冯铁军、霍兆义、尹洪超
（1.大连市经济技术开发区热力公司辽宁 大连116600；2.大连理工大学能源与动力学院辽宁 大连116024）
摘要：本文提出了多周期公用工程系统的混合整数双线性优化模型，它含有两种优化变量和系统运行过程的离散动态约束，期望系统总设备投资（含设备折旧）与全周期运行操作费用之和最小。针对混合整数双线性优化求解上的困难，把混合整数双线性优化问题模型分解成有限多个关于连续变量的线性规划。并论述了混合整数双线性优化问题与分解模型的等价性，以及两种模型的主要数学性质。在此基础上构造了分解优化算法。最后将混合整数双线性优化模型应用于某石化企业的蒸汽动力系统最优设计与运行优化集成实例。
关键词：多周期多设备公用工程系统；混合整数双线性优化；离散动态约束
引言
公用工程系统是能源生产环节，向生产环节提供必需的电力、动力和工艺用蒸汽，是包括炼油石化行业在内的过程工业的重要组成部分。作为能源生产环节，公用工程系统同时也消耗大量的能源。公用工程系统的最优设计与优化运行是过程工业节能降耗，降低生产成本提高企业竞争力的重要途径。公用工程系统是由不同型号的锅炉、汽轮机、工业透平等多种设备组成，并在多种操作工况下运行。因此，系统设计包括结构设置、设备选型和运行策略制定，是提高公用工程系统热功联产效率和降低能耗的根本途径。多种设备多周期公用工程系统最优设计与优化运行的研究引起了众多国内外专家的关注。
多年来，针对最优设计和优化运行形成了三种比较成熟的方法：启发式方法、热力学目标法和数学规划法。1980年，Nishio等提出了减少蒸汽循环中可能的损失的启发式规则，并在热力学基础上进行了蒸汽动力学系统的优化设计。1982年，Nishio等对蒸汽、电力等多种需求进行了初步优化设计。Yoo与Yi对产汽过程与蒸汽分配网络运行建立了专家系统，并用牛顿迭代法与线性规划求解，大大提高了蒸汽系统的运行效率。1998年，Lee M.H. et al.，Papalexandri K. P. et al.，Mavromatis S.P. et al.，Strouvalis A.M. et al.把分层分解方法应用于公用工程系统用以消除工艺数据误差；其次对汽轮机效率的不确定性，分析了各周期间设备启停，转换费用对总运行费用的影响，建立了多周期MINLP模型，提出了关于透平网络运行的优化方法。2000年，Yi等依据公用工程系统内部与外部能量需求变化提出了多周期运行的优化方法，建立了相应的MINLP模型。2003年，Ueo等建立了公用工程系统优化运行的MINLP模型，并开发了相应的软件。2004年，Shang Z，Cheung K. Y.为解决公用工程系统与化学过程间的交互作用，建立了全局公用工程系统蒸汽能级优化调度的多周期MILP模型，针对工艺生产过程与公用工程系统的设备维护与调度问题，给出了公用工程系统多周期最优设备维护与调度的且以经济效益最大的MI模型。夏燕萍等，张国喜等给出了公用工程系统的优化调度，但没考虑设备的启停费用，Iycr R. R.等人虽考虑了设备的启停费用，但计算策略过于复杂。郭雨珍等对多周期公用工程系统运行优化问题建立了混合整数非线性约束优化模型，构造了优化算法，研制了软件，并应用于具体实例，但该模型没有考虑设备利用效率，设备投资，且把设备折旧作为常数处理。
本文将构造多周期多设备公用工程系统运行混合整数双线性优化模型及优化算法，论述了依有限离散变量分解为有限多个线性规划与原问题的等价性，并应用于某石化企业的蒸汽动力系统最优设计与运行优化。
1.混合整数双线性优化模型
本文提出的多周期多种设备公用工程系统的最优设计与优化运行问题是混合整数双线性优化，包括两种优化变量（离散变量与连续变量）和系统运行过程的离散动态约束，期望系统总设备投资与全周期运行操作费用之和最小。
设多周期多种设备公用工程系统有m1台锅炉，其中前u1台为高压锅炉，后u2台为低压锅炉，且u1+u2=m1。有m2台汽轮机，其中前v1台汽轮机将高压蒸汽转换为中压蒸汽，后v2台汽轮机将中压蒸汽转换为低压蒸汽，且v1+v2=m2。有m3个减温减压阀，其中前w1个减温减压阀把高压转换为中压，后w2个减温减压阀把中压转换为低压，且w1+w2=m3。令m1+m2=m，m+m3=n。设Mi，i∈In，为第i台设备容量，M={M1，M2，…，Mn}。一般取全周期为一年，单周期为一个月，T=12。
2.混合整数双线性优化问题的性质与分解算法
在问题MIBLP中，由于离散变量与M的取值范围是有限的，所以可把问题MIBLP分解成有限多个仅含有连续优化变量的子优化问题。
3.实例研究
该例为某石化企业拟设计公用工程系统，该企业需要高、中、低、超低压四个等级蒸汽，低等级蒸汽允许通过由高压蒸汽减温减压得到。一年被划分为12个周期，各周期动力和蒸汽需求如表1所示，允许从外部购买动力和超高压蒸汽，但数量有一定的限制。超高压蒸汽价格140元/t，动力价格为0.55元/kWh，锅炉效率取90%，汽轮机效率取80%，燃料煤价格为400元/吨标煤。（锅炉与汽轮机选型如表2和3所示。）锅炉价格4100万元/台，25MW汽轮机机组1000万元/套，60MW汽轮机机组1200万元/套。锅炉一次启停费用25000元，背压汽轮机一次启停费用15 000元，抽凝汽轮机一次启停费用50 000元。锅炉维护费率取0.08，汽轮机维护费率取0.06，年利率取0.05。
经过优化设计，公用工程系统流程图如图1所示。公用工程系统的年总费用为44 962.14万元，其中设备投资和折旧费用2214.9万元，运行费用中启停费用仅为18万元，设备和容量选择合理，避免了设备的频繁启停，对于延长设备的使用寿命也是非常有利。
4.结论
本文对已有公用工程系统运行优化模型作了改进，提出多周期多种设备公用工程系统最优设计与运行优化模型，并针对提出的模型性质制定求解算法：
（Ⅰ）在目标函数中考虑了设备投资，以及设备的折旧。这样使优化模型更接近工程实际及通货膨胀。
（Ⅱ）由于优化模型MIBLP 是关于离散变量及连续变量的双线性混合整数规划，属于NP难问题。因此，依离散变量仅有有限多个，将模型MIBLP分解为有限多个（个）关于连续变量的线性规划。通过求解个线性规划问题，便可求得MIBLP的解。
（Ⅲ）由于是个非常大的值，且有许多线性规划子问题的可行域。为减小计算量，研究了MIBLP问题的性质，给出了使的充分条件（见性质3），为构造求解的优化算法打下理论基础。
（Ⅳ）依据双线性混合整数规划模型和线性规划子问题模型的性质构造了优化算法OPTM，并将模型与算法应用于实际公用工程系统的最优设计与优化运行问题，证实了该方法的实用性和有效性。
Optimization algorithm and application of mixed integer bilinear programming for multi-period and multi-equipment utility system
Feng tie-jun1，Huo zhao-yi2，Yin hong-chao2
(1. Dalian economic and technological development zone heating power company，Dalian 116600，China；2. School of Energy and Power Engineering，Dalian University of Technology，Dalian 116024，China)
Abstract：A mixed integer bilinear programming model of multi-period and multi-equipment utilitysystem is proposed in this paper，which includes two types of optimization variables and distract dynamic constraints for systems operation and aims to obtain minimum cost consisting of capital investment and total period running cost. To simplify solution procedure of the optimization model，the presented model is decomposed into many continuous variable linear programmodels. The equivalence analysis and major mathematical properties between the optimization model and decomposed models are described in detail，which are theoretical basis for constructing effective optimization algorithm. Finally，the proposed method is usedto design a utility system for a chemical industrial plant.
Keywords：multi-period and multi-equipment utility system；mixed integer bilinear programming；distract dynamic constraints.
有尺寸的单机分批排序问题的近似算法
吴翠连
（曲阜师范大学管理学院山东 日照276826）
摘要：本文主要讨论了特定情形下单机分批排序问题的近似算法。对于大工件（工件的尺寸严格大于机器容量的）的加工时间不小于小工件（工件的尺寸小于或等于机器容量的）的加工时间的特定情形，利用动态规划的方法和拆分的技巧，我们提出了最差性能比为的多项式时间近似算法，此处，是任意小的正数。
关键词：分批排序；最大完工时间；最差性能比；近似算法
引言
分批排序问题是在半导体生产过程的最后阶段提炼出来的一类重要的排序问题。这方面的研究工作于20世纪90年代很快地发展并活跃起来，最富有代表性的应是文献等。一般情况下，我们要求尺寸大的工件的加工时间不小于尺寸小的工件的加工时间是合理的。本文考虑这种情形下的分批排序问题是有意义的。我们定义：当工件尺寸大于机器容量的时为大工件，否则为小工件。若每一个大工件的加工时间不小于任何一个小工件的加工时间，我们称此类工件为工时与尺寸成比例。我们考虑的是工件的工时与尺寸成比例的条件下目标函数为极小化最大完工时间的单机分批排序问题。用三参数表示法记作。
问题可描述为：设有个工件要在一台机器上加工，其到达时间、加工时间和尺寸分别为。其中，是整数且，是机器的容量，规定是个与问题规模无关的常数。这些工件可以分成若干个批。批加工机器可以把多个工件作为一批同时加工，只要这些工件的尺寸之和不超过机器的容量。对于批：到达时间记作，等于批中工件到达时间的最大值；加工时间记作，等于这批中所含工件的最大加工时间；同一批中的工件有相同的完工时间。工件一旦放在机器上开始加工，就不可中断，也不允许移走正在加工的工件。如果一批中所含工件的尺寸之和为，则称此批为满批；否则称为非满批。由上文规定若一个工件的尺寸大于，则称此工件为大工件；否则称为小工件。对于工时与尺寸成比例的工件集，如何对工件进行分批，如何安排各批的次序，使得所有工件的完工时间最小，就是我们要解决的问题。
对于，如果所有工件的加工时间都相等，则此问题等价于装箱问题，因此这个问题是强－难的，它没有最差性能比小于的近似算法；当工件的加工时间未必相同时，张国川、蔡小强等在工件的工时和尺寸成比例的情况下提出了最差性能比为的近似算法。从最差性能比来说，这是这种情况下最好的算法。对于，邓小铁、张玉忠等给出了算法。受这两篇文章的启发，我们设计出了本文的算法。李曙光、李国军等人首次考虑了工件同时具有工时、尺寸和到达时间的情形，并给出了最差性能比为的近似算法，是任意小的正数。
