This paper intends to give the readers an introduction to two algorithms as the typical representations for linear programming (LP), which are the Dantzig's Simplex Method and the Karmarkar's Method and nowaday widely implemented in the area of industrial production, management of finances, and flow of resources in the economy etc.
In Chapter 1, a short introduction for the linear programming as well as its complexity, some mathematical foundations and the idea how to construct a mathematic model according to optimizing problems from the real world will be introduced. Then the Dantzig's Simplex Method and the Karmarkar's Method are depicted in Chapter 2 and Chapter 3 respectively. The Simplex Method is the classical algorithm of linear programming which was discovered by George B. Dantzig in 1947, this paper describes a linear program solved by the Simplex Method as an example, then an implementation of the Simplex Method is introduced afterwards. At last analysis of complexity of the algorithm is given. In Chapter 3, the first polynomial-time linear programming algorithm Karmarkar's Method is introduced, which includes construction for a Karmarkar's standard form, an example solved by the Karmarkar's Method and analysis of the algorithm and its complexity. In order to simplify the understanding to the theory, this paper uses examples instead of many complicated mathematic transformation. The implementation and complexity of each algorithms is introduced as well. In the last Chapter 4, a summarization is given, and mainly compare the performance of both algorithms.
All the used and referenced literatures as well as all glossaries in this paper are listed in the 'Bibliography' and 'Glossary' at the end of the paper.
|
Football
