Solution Methods of linear programming. After the design stage of the linear optimization model, it is necessary to solve it. For this, different solution methods are used.
Summary
[ hide ]
- 1 Main methods used
- 2 Graphic Method
- 3 Fundamental Disadvantage of the Graphic Method
- 4 Simplex method
- 5 Source
Main methods used
Different solution methods are used to solve a linear programming problem . The most widespread are: the graphic method and the Simplex Method . Solving a Linear Programming problem using a graphical procedure is possible if you have no more than two variables. The Simplex Method was the first method to solve linear programming problems , which is why it is considered the classic solution method par excellence. Taking into account the philosophy of this method, other methods have emerged whose fundamental advantages are concentrated in their possibilities to be programmed by computers.
Graphic Method
The graphical procedure begins by drawing a graph showing the possible solutions (values X1 and X2). The graph will have values X1 values on the horizontal axis and X2 values on the vertical axis. The procedure to find the graphical solution consists of the following:
- For each inequality of the constraint system (half closed space), the corresponding line is taken and the intercepts are determined with the graph. If the line passes through the origin of the coordinate axis, the independent term is zero, then the line is drawn taking the origin and another determined point giving an arbitrary value to one of the variables.
- To determine the points that satisfy each inequality, any point in space is substituted (the origin whose coordinates are (0,0) is recommended), and in this way it is determined if the points that satisfy the same are towards the side where the origin or to the opposite side, pointing with an arrow that side. When the line passes through the origin, then any other point is taken but its coordinate values are simple, for example, (0,1), (1,0), (1,1), etc.
- Then the solution region is determined, which is the region of the plane that satisfies all the constraints at the same time and must be in the first quadrant. The formed figure is a convex polyhedron that has a set of end points.
- The optimal point is sought among the set of extreme points. For this, each pair of points (X1, X2) of the extreme points in the objective function is substituted and the value of Z is calculated. If the value of Z is being maximized, the optimal point will be the one that provides the highest value for Z and if the optimization criterion is to minimize, then the optimal point will be the one that provides the minimum value of Z.
Fundamental Disadvantage of the Graphic Method
This graphical method has the disadvantage that it only allows the solution of problems that have two variables, so most linear programming problems are solved using the simplex method as a base.
Simplex method
It is an iterative algebraic procedure that solves any problem in a finite number of steps. It was elaborated by George Dantzing in 1947. The conception of this method has made it easier for other specialists on the subject to develop other solution methods with the same philosophy, but more suitable for computer programming. To explain the simplex method, it is necessary to define a set of basic concepts necessary for understanding it.
