A Research On Solution Of Asset-Task Assignment Problem Basing On Genetic Algorithm Under The Framework Of Linear Programming

The asset-task assignment problem is a decision-making task for assigning limited resources.It requires the greatest profit at the minimum cost and has a wide range of applications in real life.In the past,the research on asset-task assignment problem was limited to non-linear programming models.With the improvement of algorithm design level,the linear programming model of the problem has been written but its solution method is extremely complicated.Therefore,this thesis is based on the linear model of the asset-task assignment problem,and aims to design a simpler and clearer solution algorithm for the model.By simplifying the solving method of the model,the model is better understood.First of all,this thesis proposes the method of combining precise algorithm and meta-heuristic algorithm for solving the asset-task assignment problem,and realizes the column enumeration method combined with genetic algorithm to solve the linear programming model.This method provides a new solution for large-scale linear programming models,and the method has good feasibility.Through this method,the model variables of the example in this thesis can be reduced on a large scale.Secondly,this thesis designs two initial algorithms for the column enumeration,and combines the dual test with the upper bound to reduce the entry into the base column.In addition,this thesis designs the genetic algorithm based on the upper bound to further reduce the columns of the main model to find a solution to the asset-task assignment problem.Among them,the sparse storage column is designed according to the characteristics of the population to reduce the storage and calculation of the algorithm.The elite selection strategy is used to enhance the stability of genetic algorithm,the design of large mutation method to solve the problem of "premature" and speed up the convergence speed,through convergence analysis proved that the genetic algorithm designed in this thesis has the characteristics of fast speed and good convergence.Finally,summarizing 13 literature examples and generating 48 full-scale examples based on international standard parameters,selecting a computer test environment,and setting up an algorithm test system for each example 10 times,the statistical results show that the over all average error of the examples does not exceed 1%,and more than half of the examples can be solved in real time.By comparing with the solutionmethods in the international literature,it is found that the accuracy of the algorithm in this paper is better than the method published in the International Journal of Advanced Computer Science and Application in 2017,and also has the advantage of speed.In this thesis,the method of using genetic algorithm to find the base line is a new solution method.The algorithm has good stability and is simple and intuitive.It uses the international standard example generation method and covers all scales for testing.It is found that this algorithm can solve the small,medium,and large-scale problems of asset-task assignment problem and can all obtain heuristic solutions with higher precision.The results of this thesis not only develop an efficient solution algorithm for asset-task assignment problem,but also provide a new solution for large-scale linear programming models.