LINEAR PROGRAMMING
Vikas Vasam
ID: 100-11-5919
Faculty: Prof. Dr Goran Trajkovski
CMP 561: Algorithm Analysis
VIRGINIA INTERNATIONAL UNIVERSITY
Introduction:
One of the section of mathematical programming is linear programming.
Methods and linear programming models are widely used in the optimization of processes in all sectors of the economy: the development of the production program of the company, its distribution on the performers, when placing orders between the performers and the time intervals, to determine the best range of products, in problems of perspective, current and operational planning and management, traffic planning, defining a plan of trade and distribution, in the problems of development and distribution of productive forces, bases and depots of material handling systems, resources, etc. especially widely used methods and linear programming model for solving problems are savings (choice of resource-saving technologies, preparation of mixes, nesting materials), production, transportation and other tasks.
Beginning of linear programming was initiated in 1939 by the Soviet mathematician and economist Kantorovich in his paper "Mathematical methods of organizing and planning production." The appearance of this work has opened a new stage in the application of mathematics in economics. Ten years later American mathematician George Dantzig developed an efficient method for solving this class of problems - the simplex method. The general idea of the simplex method to solve the LPP is as follows: ability to find initial support plan; the presence of the optimality of the support program; the ability to move to an improved support program.
1.1 The concept of linear programming : Linear programming - the section of mathematical programming, applied in the development of methods for finding the extremum of linear
References: 1. Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-653678. 2. R. G. Bland, New finite pivoting rules for the simplex method, Math. Oper. Res. 2 (1977) 103–107. 3. George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag. 4. J. E. Beasley, editor. Advances in Linear and Integer Programming. Oxford Science, 1996. (Collection of surveys)