Simplex method for solving optimization problems of linear programming

The simplex method is a computational procedure based on the principle of sequential improvement of solutions during the transition from one base point (basic solution) to another. This improves the value of the objective function.

The basic solution is one of the valid solutions that are at the vertices of the realm of valid values. Checking for optimality vertex after vertex of the simplex, they come to the desired optimum. The simplex method is based on this principle.

A simplex is a convex polygon in n-dimensional space with n+1 vertices not lying in the same hyperplane (hyperplane divides space into two semispaces).

For example, the line of budget constraints divides goods into available and inaccessible.

It is proved that if the optimal solution exists, then it will necessarily be found through a finite number of iterations (steps), except in cases of “looping”.

The simplex method algorithm consists of a number of steps.

First stage. The initial optimization model is built. Further, the original matrix of conditions is transformed into the given canonical form, which among all other canonical forms is distinguished by the fact that:

(a) The right-hand parts of the conditions (free bi members) are non-negative values;

b) the conditions themselves are equal;

c) the condition matrix contains a complete single submatrix.

If the free terms are negative, then both parts of the inequality are multiplied by -1, and the equal sign is reversed. To convert inequalities into equalities, additional variables are introduced, which usually indicate the amount of underutilized resources. That’s their economic sense.

Finally, if, after adding additional variables, the condition matrix does not contain a complete unit submatrix, then artificial variables are introduced that make no economic sense. They are introduced solely in order to obtain a single sub-spot and begin the process of solving the problem using the simplex method.

In the optimal solution of the problem, all artificial variables (IP) should be equal to zero. To do this, introduce artificial variables into the objective function of the problem with large negative coefficients (-M) when solving the problem at max, and with large positive coefficients (+M) when the problem is solved at min. In this case, even a small non-zero value of the artificial variable will dramatically reduce (increase) the value of the objective function. Usually M should be 1000 times greater than the values of the coefficients at the main variables.

Second stage. The original simplex table is built and some initial basic solution is found. The set of variables that make up a single sub-matrix are taken as the initial basis decision. The values of these variables are equal to the free terms. All other non-basin variables are zero.

Third stage. Verification of the basic solution for optimality is carried out with the help of special estimates of the coefficients of the objective function. If all estimates of the coefficients of the objective function are negative or zero, then the available basic solution is optimal. If at least one estimate of the coefficient of the objective function is greater than zero, then the available basic solution is not optimal and should be improved.

Fourth stage. Transition to a new baseline solution. Obviously, the optimal plan should include the variable that greatestly increases the objective function. When solving problems for maximum profit, the products whose production is most profitable are introduced into the optimal plan. This is determined by the maximum positive value of the evaluation of the coefficient of the objective function.

A column in a simplex table with this number on this iteration is called a master column.

Further, if at least one element of the master column aij0 is strictly positive, then the master row is found (otherwise the problem does not have an optimal solution).

To find the master row, all free members (resources) are divided into the corresponding elements of the master column (the rate of resource consumption per unit of product). From the results obtained, the least is selected. The corresponding line in this iteration is called the general line. It corresponds to a resource that limits production on a given iteration.

The simplex table element at the intersection of the master column and row is called the master element.

Then, all the elements of the master line (including the free term) are divided into the master element. As a result of this operation, the general element becomes equal to one. Next, it is necessary that all other elements of the master column become zero, i.e. the master column must become a unit column. All lines (except the general row) are converted as follows: The resulting elements of the new row are multiplied by the corresponding element of the master column and the resulting product is subtracted from the elements of the old row.

The values of the new base variables are obtained in the corresponding cells of the column of free members.

Fifth stage. The resulting basic solution is checked for optimality (see the third stage). If it is optimal, then the calculations stop. Otherwise, it is necessary to find a new basic solution (the fourth stage), etc.

An example of solving optimization problems of linear programming by the simplex method

Let it be necessary to find the optimal plan for the production of two types of products (x1 and x2).

Source data:

Let’s build an optimization model

– resource limit A;

– Resource limit B.

Let’s bring the problem to the above canonical form. To do this, it is enough to enter additional variables X3 and X4. As a result, inequalities are transformed into strict equality.

Let’s build the original simplex table and find the initial basic solution. They will have additional variables, because they correspond to a single submatrix.

x3=20 and x4=36

1st iteration. Find the general column and the general line:

max (7,3) = 7

The general element is 5.

2nd iteration. The found basic solution is not optimal, because the series of estimates (Fj-Cj) contains one positive element. Find the general column and the general line:

max (0,0.3,-1.4,0) = 0.2

The solution found is optimal, since all special estimates of the objective function Fj – Cj are zero or negative. F(x)=29 x1=2; x2=5.