The Improvement Of The Least Adjustment Method And Its Applications In Economic Optimization

Economic optimization methods as important methods of optimization enrich and develop the calculation method and practice of economic problems from a different side in quantity economics. Economic optimization theory can also be called economic operations research, as a cross-cutting discipline, it also provides theoretical approaches for the model establishment and the anylysis and solution of quantity economics. For each economic entity as large as countries and as small as individual in the modern life with rapid economic development, they find and use a variety of methods and techniques in the realization of economic optimization not all the time, so economic optimization connects each economic entity, and it is the focus of concern for every one. There is a class of economic optimization problems such as maximize efficiency and minimize cost, associated with transportation problem, assignment problem, traveling salesman problem and other related issues in areas such as modern industry, agriculture, commercial and national defense construction. How to achieve the best transport, the best assign, and the best travel route often involves many factors, such as cost, time, resources, transport routes, technical conditions, etc. These factors are often interrelated and mutual constraints. At the same time they constitute the expansion of a variety of issues with transportation, assignment, traveling salesman problem in different environments and requirements. Because the extended problems of transportation problem, assignment problem, traveling salesman problem have their own uniqueness, and in view of the importance of efficient algorithms we need to establish different algorithms for transportation problem, assignment problem, and traveling salesman problem and related economic issues in general. This would bring certain difficulties for the practical applications.In order to solve these problems flexibly and rapidly, this paper concerning the links of three types of problem of the economic optimization, systematically sums up a universal algorithm-the Least Adjustment Method for the solution of these problems and issues related to the expansion of the problems on the basis of previous studies. The Least Adjustment Method takes the classical shortest path algorithm-Dijkstra algorithm as the channel giving a polynomial algorithm. The initial form of the Least Adjustment Method is the Label Method of assignment poblem, and then by solving transportation problem, gradually evolving into a mature-the Least Adjustment Method. This paper has the basic idea, the implementation process, the proof of validity, the analysis of complexity and so on. The paper introduces the algorithm as the main line, and improves to apply neatly the algorithm to transportation problem, assignment problem, traveling salesman problem and related economic expansion issues. This reflects that the algorithm is general, feasible, practical and simple.This paper consists of three main parts. The first part constituted of Chapter I, Chapter II, sets out the background and the meaning of paper topics, and then gives the relevant critical literature overview. The second part constituted of Chapter III, discusses the basic idea and the implementation process, the way to realize and the initial form, the process of the evolution of the Least Adjustment Method in detail. The third part constituted of Chapter IV, Chapter V, and Chapter VI, is the discussion on the application of the Least Adjustment Method for transportation problem, assignment problem, traveling salesman problem and the expansion of the problems in the economic optimization problems.The paper has seven chapters, and they are as follows,Chapter I Introduction. First the background and the significance are described, and the problems and models are introduced. And then because this paper mainly introduces economic optimization algorithms and applications, it overviews and explains the algorithm system and its effectiveness in order to have the merits of a general evaluation criteria. Finally, the idea of this paper, methods, and the structure of the overall content and the overall framework of the paper are given.Chapter II Related Literature Review. It carries out literature category summary in accordance with transportation problem, assignment problem, traveling salesman problem and at the same time comments on the basis of a large number of relevant documents. First of all, for Literature Review of the transport part, foreign literature review focuses mainly on the algorithm, and national literatures classify to summary from different perspectives, from the algorithm point of view, from the perspective of the objective function and from the perspective of the constraint function. It makes the concluding comments for transportation problem at last. Then Literature Review-assignment problem, foreign literature review also focuses on the research of their algorithm, and the domestic literature based on different contents makes summary of critical into two categories. One is the general algorithm for assignment problem, the other is to expand on various models and algorithms of assignment problem, and it makes the overall summary of literature reviews. Finally, the part of Literature Review is about traveling salesman problem. First it gives the review of the algorithm for solving traveling salesman problem. And then its algorithm can be divided into two major categories of general, solving a class of exact values can be the basic algorithm and solving the approximation by the computer intelligent algorithm is the other, and it makes the overall summary of literature reviews about traveling salesman problem. And then comment on the domestic and foreign literature review of traveling salesman problem. The end of the Chapter summarizes the links of the three types of economic optimization problems.Chapter III Introduction of the Least Adjustment Method. First it describes the basic ideas and the implementation process, introduces the realization means of the Least Adjustment Method-Dijkstra algorithm solving the shortest path, and then gives the initial form-the Label Method of assignment problem, and makes the steps of the algorithm, the efficiency and the complexity of the algorithm, at last gives the evolution of the Least Adjustment Method. This chapter is the core of the paper, and the following chapters are built on the basis of this chapter.Chapter IV the Application of the Least Adjustment Method in Transportation Problem. It applies the Least Adjustment Method to solve the general transportation problem, and introduces the general transportation traditional method-the list of working method, illuminates the steps for solving transportation problem by the Least Adjustment Method and its effectiveness, verifies the Least Adjustment Method which is a polynomial algorithm for computation only O(n3) simple by examples, and compares the Least Adjustment Method to the list of working method. At the same time based on the Least Adjustment Method, it analyses the integer solutions of transport problem with production and sales for the integer. And then it introduces a series of related expansion models of transportation problem, gives the improved Least Adjustment Method to solve transport problem, and lists a large number of numerical examples. This reflects the universal applicability of the method about transport problem. Finally, based the theorem of the necessary and sufficient conditions of the transportation problem'paradox'from the perspective of the Least Adjustment Method, it gives the practical problem to make use of the transportation problem'paradox'to maximize the traffic, the maximum increase in the traffic with keeping the least total freight, and gives the specific steps to implement and carries out a rigorous proof, use examples to verify.Chapter V the Application of the Least Adjustment Method in Assignment Problem. It applies the Least Adjustment Method to the general assignment problem, and introduces the general assignment method-Hungary method, gives the steps for solving assignment problem by the Least Adjustment Method and proves its effectiveness, verifies the Least Adjustment Method simple by examples, and its calculation is only O(n2), and compares the Least Adjustment Method to the traditional method. Then it solves a class assignment problem with the shortest time by the improved Least Adjustment Method, and the other related expansion models of assignment problem, such as a class assignment problem with the two persons for one thing, a class of assignment problem for default, the assignment problem with priority by the improved Least Adjustment Method, and by theoretical analysis and examples to prove its validity. These problems reflect the actual assignment problems in a variety of special circumstances. Finally, it solves the special 0-1 programming based on the idea of the Least Adjustment Method, which reflects the general applicability of the Least Adjustment method.Chapter VI the Application of the Least Adjustment Method in Traveling Salesman Problem. First it introduces the traditional algorithms-dynamic programming. And then it analyses the relation between traveling salesman problem ,and assignment problem, uses the Least Adjustment Method to solve traveling salesman problem combining with restrictions on certain conditions, and analyses the effectiveness of the algorithm. Although the algorithm sometimes obtains the approximate solution of traveling salesman problem, but the difference of the approximation and the optimal value of the corresponding assignment problem is very small, it would be a good approximate solution, and the calculation is only O(n2). Finally, it makes some ways of the improvements.Chapter VII Conclusions and Outlook. First of all, it summarizes the main conclusions, gives the deficiencies of the research, and innovation points. Finally, make the prospect of further research.In this paper, the innovations and the defects are as follows, it systematically sums up the general algorithm-the Least Adjustment Method based on predecessors existing research achievements, makes it systematization, integrated, and maturation. And the description of its basic idea and the implementation process is penetrating and new. It is applied to more economic optimization problems and improved flexibly. The specific innovation and lackness are as follows.In Chapter IV it uses the transportation problem'paradox'to solve the maximum of traffic which is of great economic significance and value for the full use of transport resources. In Chapter VI it applies the improved Least Adjustment Method to solve the shortest time assignment problem, and the theoretical analysis and the proof are of practical significance. And it is innovative to solve the assignment problem of two persons for one thing, the default assignment problem and the priority assignment problem and analyses the effectiveness by the Least Adjustment Method. For solving traveling salesman problem, it gives the algorithm to the approximate solution with less computational complexity by the Least Adjustment Method and the algorithm is simple, and the calculation is only O(n2). However, how to give the exact solution by the Least Adjustment Method is yet to be studied. Uncertain problems and complex nonlinear problems for transport problem, assignment problem, and traveling salesman problem have yet to be added. A large number of examples in this paper from related literatures, and the scales of examples are small solved by hand in order to illustrate principles and processes, if the cited examples are of even larger scales, this will be realized by computer. How to give the computer program will be the next step.