Linear programming – mathematical area of a research of linear dependences between variables and decisions on their basis of tasks on search of optimum values of any given indicator. In this regard methods of linear programming, including a simplex method, are widely applied in the economic theory.
Instruction
1. A simplex method – one of the main ways of the solution of problems of linear programming. It consists in consecutive creation of the mathematical model characterizing the considered process. The decision breaks into three main stages: choice of variables, creation of a system of restrictions and search of criterion function.
2. Proceeding from this division, the statement of the problem can be paraphrased as follows: to find an extremum of criterion function of Z(X) = f (x1, x2, …, xn) → max (min) and the corresponding variables if it is known that they satisfy to the system of restrictions: Φ _ i (x1, x2, …, xn) = 0 at i = 1, 2, …, k; Φ _ i (x1, x2, …, xn)) 0 at i = k+1, k+2, …, m.
3. The system of restrictions needs to be given to a canonical form, i.e. to the system of the linear equations where number of variables more number of the equations (m> k). In this system surely there will be variables which can be expressed through other variables, and if it not so, then they can be entered artificially. In this case the first are called basis or artificial basis, and the second – free.
4. It is more convenient to consider a simplex method on a concrete example. Let the linear f (x) function = 6x1 + 5x2 + 9x3 and the system of restrictions be given: 5x1 + 2x2 + 3x3 ≤ 25; x1 + 6x2 + 2x3 ≤ 20;4x1 + 3x3 ≤ 18. It is required to find the maximum value of function f (x).
5. ReshenieNa the first stage set the initial (basic) solution of a system of the equations absolutely arbitrarily which at the same time has to satisfy to this system of restrictions. In this case introduction of artificial basis, i.e. basic x4, x5 and x6 variables as follows is required: 5x1 + 2x2 + 3x3 + x4 = 25; x1 + 6x2 + 2x3 + x5 = 20;4x1 + 3x3 + x6 = 18.
6. As you can see, inequalities were transformed to equalities thanks to added variables x4, x5, x6 which are non-negative sizes. Thus, you led a system to a canonical form. X4 variable enters the first equation with coefficient 1, and two others – with coefficient 0, the same is fair for variables x5, x6 and the corresponding equations that corresponds to determination of basis.
7. You prepared a system and found an initial basic solution – X0 = (0, 0, 0, 25, 20, 18). Now present coefficients of variables and free members of the equations (figures to the right of the sign "=") in the form of the table for optimization of further calculations (see rice).
8. The essence a simplex method is in leading this table to such look in which all figures in line L will be non-negative sizes. If it becomes clear that it is impossible, then the system has no optimal solution at all. For a start choose the most minimum element of this line, it is-9. The figure costs in the third column. Transform the corresponding x3 variable to basic. For this purpose divide a line into 3 that in a cell [3.3] 1 turned out.
9. Now it is necessary that cells [1.3] and [2.3] addressed in 0. For this purpose take away the corresponding figures of the third line increased by 3 from elements of the first line. From elements of the second line - the elements of the third increased by 2. And, at last, from elements of line L - increased on (-9). You received the second basic decision: f(x) = L = 54 at x1 = (0, 0, 6, 7, 8, 0).
10. In line L there was only one negative number-5 in the second column. Therefore we will transform x2 variable to a basic look. For this purpose elements of a column have to take a form (0, 1, 0). Divide all elements of the second line into 6.
11. Now from elements of the first line take away the corresponding figures of the second line increased by 2. Then take away from elements of line L the same figures, but with coefficient (-5).
12. You received the third and final basic decision as all elements of line L became non-negative. So, X2 = (0, 4/3, 6, 13/3, 0, 0) and L = 182/3 =-83/18x1 - 5/6x5 - 22/9x6. Maximum value of the f (x) function = L (X2) = 182/3. As all x_i in decision X2 are not negative, as well as value L, the optimal solution is found.