摘要
针对n人n事的最短时限指派问题,文章通过确定当前最短时限值后,构造最短时限指派问题的最小费用流模型,结合对偶原理,提出求解最短时限指派问题的快速决策方法。该方法通过保持互补松弛条件不变,通过改变节点的势扩大允许网络进而在允许网络中寻求从源点到汇点的增广链而增广流量,直至得到流量为n的最小费用流,此时非0流边对应最短时限指派问题的最优解,算例表明该方法简单、有效可行。
Aiming at the shortest-time assignment problem for n people and n events,this paper constructs the minimum cost flow model of the shortest-time assignment problem by determining the current shortest-time limit,and then combines the duality principle to propose a fast decision-making method for solving the shortest-time assignment problem.By keeping the complementary relaxation condition invariant,and by changing the potential of the node to expand the allowable network and then seeking an augmented chain from the source point to the meeting point in the permitted network,the method expands the flow until is obtained the minimum cost flow with the flow quantity to be n.At this time,the non-zero flow edge corresponds to the optimal solution of the shortest-time limit assignment problem.Finally an example is given to show that the proposed method is simple,effective and feasible.
作者
胡勇文
陈国华
刘静
Hu Yongwen;Chen Guohua;Liu Jing(School of Mechanical Engineering,Hubei University of Arts and Science;Hubei Key Laboratory ofPower System Design and Test for Electrical Vehicle,Xiangyang Hubei 441053,China)
出处
《统计与决策》
CSSCI
北大核心
2019年第5期46-50,共5页
Statistics & Decision
基金
国家自然科学基金资助项目(51605150)
教育部人文社会科学研究青年基金项目(17YJC630084)
机电汽车湖北省优势特色学科群开放基金项目(XKQ2018063)
关键词
指派问题
最短时限
最小费用流
允许边算法
assignment problem
shortest time limited
minimal cost flow
allowable edge algorithm
