考虑边流量有限的网络路径博弈问题研究

考虑每条边有流量约束的网络路径博弈问题, 根据收益函数单调递增的特点分析其内在零和性质, 并建模为存在公共边的路径博弈模型。在寻找均衡解的过程中, 首先考虑非合作的情形, 在局中人风险中性的假设下, 给出了求Nash均衡流量分配的标号法并证明该均衡分配的唯一性。接着进一步考虑局中人合作的可能性, 给出模型求得所有局中人的整体最大收益, 并基于纳什谈判模型给出目标函数为凸函数的数学模型确定唯一收益分配方案。事实上, 该方案是对剩余价值的平均分配。最后给出一个算例, 验证本文理论和方法的可行性。关键词:流量约束; 均衡流量; 网络路径博弈; 收益分配     

运输问题的合作对策求解方法

产地间或销地间往往存在竞争,在这种情况下,使用运输问题最优化方法是不合理的。因此,从个体理性的视角提出运输问题的合作对策求解方法,方法将运输问题看作是一个博弈问题,各个产地或销地是博弈的局中人,求解其纳什均衡与纳什讨价还价解。在此基础上,说明了运输问题的非合作形式是一个指派问题,并证明指派问题的最优解是一个纳什均衡点。接着,通过实验验证运输问题的最优解是一个纳什讨价还价解,满足产地或销地的自身利益。在此基础上,针对纳什讨价还价解不唯一的问题,从决策者的视角给出最大可能激励成本的计算方法。最后,为弥补纳什讨价还价解不唯一及纳什讨价还价解不允许出现子联盟的缺陷,给出运输收益分配或成本分摊的Shapely值计算方法。     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献   

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

工件可自由下线最小化总完工时间的有界平行分批排序

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题.在该问题中,一台平行批机器可以同时处理b个工件作为一个平行批,这里b是批容量,一个批的加工时间等于分配给这个批的工件的最大加工时间.关于可自由下线工件,每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和.也就是,如果一个批■有一个开工时间S,那么包含在批■中的每一个工件乃的开工时间定义为S,而它的完工时间定义为S+p_j,这里p_j是工件J_j的加工时间.对此问题,首先研究最优排序的一些性质.然后,基于这些性质,给出一个运行时间为O(n~(b(b-1))的动态规划算法.     

基于退化效应的两台机器流水作业可拒绝排序

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.     

原始工件的完工时间限制下的最小化最大延误时间的重新排序

考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.     

一种资源投入不确定情形下的合作博弈形式及收益分配策略

首先,将经典合作博弈进行扩展,提出了一类模糊联盟合作博弈的通用形式,涵盖常见三种模糊联盟合作博弈,即多线性扩展博弈、比例模糊博弈与Choquet积分模糊博弈.比例模糊博弈、Choquet积分模糊博弈的Shapley值均可以作为一种特定形式下模糊联盟合作博弈的收益分配策略,但是对于多线性扩展博弈的Shapley值一直关注较少,因此利用经典Shapley值构造出多线性扩展博弈的Shapley值,以此作为一种收益分配策略.最后,通过实例分析了常见三类模糊联盟合作博弈的形式及其对应的分配策略,分析收益最大的模糊联盟合作对策形式及最优分配策略,为不确定情形下的合作问题提供了一定的收益分配依据.