Simplex method is an algorithm for solving linear programming optimization problem by sorting the vertices of a convex polyhedron in a multidimensional space. Linear programming problem is that it is necessary to maximize or minimize a linear functional on a multidimensional space for a given linear constraints.
The sequence of calculations simplex method can be divided into two main phases:
- finding the original vertices of the set of feasible solutions,
- gradual transition from one vertex to another, leading to the optimization of the objective function.
Thus in some cases, the initial solution is obviously its definition or does not require complex calculations, for example, when all the constraints are represented by inequalities of the form 'is less than or equal to "(then exactly zero vector is a feasible solution, although likely far less than optimal) . In such problems, the first phase of the simplex method can generally be dispensed with. Simplex method, respectively, divided into single-phase and two-phase.
Consider the following linear programming problem:
Now put this task in the equivalent strengthened form. It is necessary to maximize Z, where:
Here x - variables from the initial linear functional, xs - new variables that complement the old in such a way that the inequality becomes an equality, c - coefficients of the original linear functional, Z - variable that needs to be maximized.
Half-spaces x≥0, x≤0 in the intersection of the polyhedron are representing the set of feasible solutions. The difference between the number of variables and equations gives us the number of degrees of freedom. Simply put, if we consider the vertices of the polyhedron, it is the number of edges on which we can continue to move. Then we can assign to the number of variables to 0, and call them "uneasy." The other variables in this case will be calculated uniquely called "simple". The resulting point is the vertex at the intersection of hyperplanes corresponding difficult variables. To find t. N. initial feasible solution (top, from which we start movement), assign all the original variables x 0, and we consider them difficult, and all new, we assume simple. In this case, the initial feasible solution is calculated explicitly: .
Now we present the steps of the algorithm. At each step, we will change the set of simple and complicated vectors (move on the ribs), and the matrix has the following form:
where cB - coefficients vector c, corresponding to a simple variable (xs correspond to 0), B - columns , corresponding to simple variables. Matrix formed by the remaining columns denoted D. Why the matrix will have the kind of explain in the description of steps of the algorithm.
First step. Choosing the initial allowable value as mentioned above. In the first step B is the identity matrix, as simple variables are xs. cB is zero vector for the same reasons.
Second step. We show that in the expression is only difficult variables have non-zero coefficient. Note that the expression Ax + xs = b simple variables uniquely expressed in terms of challenging, since the number of simple variables equal to the number of equations. Let x '- simple and x' '- difficult variables on a given iteration. The equation Ax + xs = b can be written as Bx '+ Dx' '= b. Multiply it by from the left: . Thus, we expressed through simple variables difficult, and in the expression of , equivalent to the left side of the equation, all simple variables have unity coefficients. Therefore, if we add to the equation the equality , then the resulting equation are all simple variables will have a zero coefficient - all simple variables like x reduced and simple variables of the form xs not enter into the expression .
Third step. Now, you must understand what a simple variable of the first turn to zero with increasing entering variable. It is enough to consider the system:
For fixed values of variables difficult system is uniquely solvable relatively simple, so we can determine which of the simple variables first reaches zero with increasing entering. This variable is said to be leaving. This will mean that we have stumbled upon a new vertex. Now incoming and outgoing variable interchange - a member of "logging" in a simple and coming out of them "come out" in the difficult. Now rewrite the matrix B and the vector cB in accordance with the new set of simple and complicated variables, then return to the second step. x ''
Since the number of vertices is finite, then the algorithm will one day end. Found vertex will be the best solution.
Example
The company produces shelves for bathrooms in two sizes - A and B. Realtors believe that in a week on the market can be realized up to 550 shelves. For each shelf of type A it is required two square meters of material, and for shelf-type B – 3 square meters of material. The company may receive up to 1200 m2 of material per week. For manufacturing a shelf of type A it is required 12 minutes of computing time, and for producing a shelf-type B - 30 minutes; machine can be used during the 160 hr. If the profit from the sale shelves of type A is 3 monetary units and shelves of type B - 4 monetary units, how many of each type of shelves should be released in a week?
We construct a mathematical model of the problem. Let x1 - number of shelves form A, x2 - the number of shelves in the form B, which are produced in the week (within the meaning of the problem, these variables are non-negative). Profits from the sale of such a large number of shelves will be 3x1 + 4x2, required to maximize profits. We write out the constraints of the problem. x1 + x2 ≤ 550 - a week on the market can be realized up to 550 shelves. Material costs: 2x1 + 3x2 ≤ 1200 computer time: 12x1 + 30x2 ≤ 9600.
Thus, we come to the problem of linear programming.
Solve it by the simplex method. We introduce three additional variables x3, x4, x5, and come to the problem:
The reference plan choose X0 = (0, 0, 550, 1200, 9600). Construct the simplex tableau.
We can solve now this problem using MS Excel Solver and obtain the following results:
Hence, to have the maximum profit, the company should produce 450 shelves of type A and 100 shelves of type B. The profit amount is 1750 monetary units, also there are 20 hours (1200 minutes) of computing time left unused.
References
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp. 790–804.
Frederick S. Hillier and Gerald J. Lieberman: Introduction to Operations Research, 8th edition. McGraw-Hill. ISBN 0-07-123828-X
