特殊圈上的逆1-maxian问题

逆1-maxian问题主要研究如何在一定的预算下修改网络中边的长度,使得其他所有顶点到预先给定顶点的距离之和尽可能的大.研究了特殊4-圈上的逆1-maxian问题,得到了该问题在任意预算下的最优解.然后,将问题推广到特殊n-圈的情形.最后,得到Hamming距离下特殊n-圈情形的一个最优解.     

k-supplier问题的贪婪近似算法

给定无向完全图G=(V,E)和正整数k,图G的顶点集V被划分为子集F和子集D=V-F.k-supplier问题主要研究如何寻找F中顶点数不多于k的子集S,使得S中的顶点到D中顶点的最大距离最小.研究了k-supplier问题,得到了一个近似比为3的多项式时间贪婪近似算法,并通过实例验证了该算法的有效性.     

哈明距离下极大不一致支撑树的部分逆问题

给定一个简单无向赋权图和其中的一个森林,极大不一致支撑树的部分逆问题研究如何尽可能少地改变图中各边的权,使得在新的权值下存在一个极大不一致支撑树包含该森林.在赋权哈明距离下,得到了该问题的一些性质,并且给出了求解该问题的多项式时间算法.     

带弧费用约束的最短路径问题

对一类带弧费用约束的最短路径问题进行了研究,即对于网络中两个给定的顶点s,t,找出s和t之间的一条路,使得在满足总费用不超过一个给定正整数的s和t之间所有的路中,该条路的长度最短.通过将背包问题多项式时间变换为该问题的判定问题,证明了该问题是NP-完全的.并给出了求解此问题的一个动态规划算法.最后,我们得到了最优值的一个下界估计.     

星图上最短路改进问题的组合算法

给定星图中一个非中心点到其余所有非中心点之间的n对点对,当要求网络中边的权重只允许减少且减少量有上界,并且这n对点对的最短路长度都不超过给定的n个上界的条件下,研究了l1模下星图的最短路改进问题,得到了解该问题的强多项式时间的组合算法,算法的时间复杂度为O(|E|log|E|).     

基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法

对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算。笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用“假设-检验”方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为)(nO,判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次。该算法原理直观简单,实现容易。实际运行结果表明,该算法速度快捷、运行稳定。     

有限资源下最大可靠性网络流中断模型

提出了最大可靠性网络流中断模型。此模型是在给定的网络图中,通过在边上设置监测点来阻止给定两个顶点之间的网络流量,同时考虑所设置监测点失效的可能,在给定的资源限制下,最大化中断网络流的可能性,即给定起点和终点的网络图,在资源有限的情况下,选择一些边设置监测点使得从起点到终点的所有路都包含尽可能多的已被设置中断点的边。在给定图中,两点之间的路的条数是图的规模的指数次幂,为此将此模型转化为双层整数规划模型,鉴于双层整数规划模型在一般情况下是不可解的,通过探讨下层整数规划问题与其线性规划松弛之间的关系以及线性规划对偶理论来解此双层整数规划模型。本文不仅将该模型约束的个数从图的规模的指数次幂降到一次幂,同时也提供了一种解双层整数规划问题的方法。     

路、圈的Mycielskian图的反魔术标号

令G=(V,E)是一个含有m条边的无向图.G的一个反魔术标号是指从边集E到集合{1,2,…,m}的一个双射,使得图上所有顶点的边权和都不相同.如果图G具有一个反魔术标号,则称G为反魔术图.Hartsfield和Ringel猜测:除K_2外所有连通图都是反魔术图.通过给出具体的反魔术边标号方案,证实了路、圈的Mycielskian图均为反魔术图.     

电力市场的输电阻塞优化管理

我们研究了电力市场的输电阻塞管理,针对目前电力市场中出现的输电阻塞,提出了阻塞费用的计算办法,机组出力分配预案的算法,以及重新调整预案的模型,得到如下结果:问题1:根据32组试验数据,利用多元线性回归建立了6条主要线路的潮流值关于8台机组出力的线性表达式,利用SAS8软件得到回归方程都通过了显著性检验,复相关系数都不低于0.9995,最大均方误差不超过0.03995,相对误差不超过0.0267%,方案0的最大预测误差不超过0.0447%,说明该表达式很好地反映了线路潮流值与发电机组出力的关系。问题2:我们给出了一种合理的计算阻塞费用的规则:序外容量和序内容量都按照预案清算价和新方案出力对应报价之差计算,这在一定程度上体现了对多发电方和少发电方的公平补偿,还给出了相应补偿公式和阻塞费用计算公式,并证明了阻塞费用等于方案调整后与方案调整前支付费用之差。问题3:采用两种不同方案得到各机组出力分配预案,方案一给出了计算所有段价下各机组能完成的最大负荷的算法,该算法具有一般性,计算量小,并得到负荷需求为982.4MW时清算价是303元/MWh,购电费用74417元,各机组出力为:x1=150,x2=79,x3=180,x4=99.5,x5=125,x6=140,x7=95,x8=113.9方案二采用目标规划方法建立非线性0-1规划模型,采用lingo方便地得到任意     

电力市场的输电阻塞优化管理

我们研究了电力市场的输电阻塞管理,针对目前电力市场中出现的输电阻塞,提出了阻塞费用的计算办法,机组出力分配预案的算法,以及重新调整预案的模型,得到如下结果问题1根据32组试验数据,利用多元线性回归建立了6条主要线路的潮流值关于8台机组出力的线性表达式,利用SAS8软件得到回归方程都通过了显著性检验,复相关系数都不低于0.9995,最大均方误差不超过0.03995,相对误差不超过0.0267%,方案0的最大预测误差不超过0.0447%,说明该表达式很好地反映了线路潮流值与发电机组出力的关系.问题2我们给出了一种合理的计算阻塞费用的规则序外容量和序内容量都按照预案清算价和新方案出力对应报价之差计算,这在一定程度上体现了对多发电方和少发电方的公平补偿,还给出了相应补偿公式和阻塞费用计算公式,并证明了阻塞费用等于方案调整后与方案调整前支付费用之差.问题3采用两种不同方案得到各机组出力分配预案,方案一给出了计算所有段价下各机组能完成的最大负荷的算法,该算法具有一般性,计算量小,并得到负荷需求为982.4MW时清算价是303元/MWh,购电费用74417元,各机组出力为x1=150,x2=79,x3=180,x4=99.5,x5=125,x6=140,x7=95,x8=113.9方案二采用目标规划方法建立非线性0-1规划模型,采用lingo方便地得到任意负荷下清算价及各机组出力,计算结果与模型一相同.问题4检验到问题3的分配预案会引起输电阻塞,考虑约束线路潮流值不超过限值,我们建立了以阻塞费用最小为目标的单目标规划,得到的最小阻塞费用Z=4614.386元,各机组出力方案为x1=150.688,x2=88,x3=228,x4=80.059,x5=152,x6=96.673,x7=70,x8=117问题5对负荷需求1052.8MW,我们采用与问题3同样的方法得到清算价为356元/MWh,购电费用93699元,各机组出力为x1=150,x2=81,x3=218.2,x4=99.5,x5=135,x6=150,x7=102.1,x8=117检查到该预案会引起输电阻塞,用问题4的单目标模型发现潮流限值内无法调整方案,因此建立阻塞费用最小和各线路上潮流绝对值超过限值的百分比α最小的双目标规划模型,为降低安全隐患,α取最小值5.16%,得到的最小阻塞费用Z=1828.4元,该方案下各台机组出力为x1=153,x2=88,x3=228,x4=92.107,x5=152,x6=137.354,x7=85.339,x8=117