Simplex method solution algorithm c. Simplex method for solving problems
. Simplex method algorithm
Example 5.1. Solve the following problem linear programming simplex method:
Solution:
I iteration:
x3, x4, x5, x6 x1,x2. Let's express the basic variables in terms of free ones:
Let us reduce the objective function to the following form:
Based on the obtained problem, we will form the initial simplex table:
Table 5.3
Original simplex table
Evaluative Relationships |
||||
According to the definition of the basic solution, the free variables are equal to zero, and the values of the basic variables are equal to the corresponding values of the free numbers, i.e.:
Stage 3: checking the compatibility of the PAP restrictions system.
At this iteration (in Table 5.3), the sign of inconsistency of the constraint system (sign 1) is not identified (i.e. there is no line with a negative free number (except for the line of the objective function) in which there would not be at least one negative element (i.e. . negative coefficient for a free variable)).
At this iteration (in Table 5.3), the sign of unboundedness of the objective function (sign 2) was not identified (i.e., there is no column with a negative element in the row of the objective function (except for the column of free numbers) in which there would not be at least one positive element) .
Since the found basic solution does not contain negative components, it is admissible.
Stage 6: optimality check.
The found basic solution is not optimal, since according to the optimality criterion (sign 4) there should be no negative elements in the line of the objective function (the free number of this line is not taken into account when considering this criterion). Therefore, according to the simplex method algorithm, we move on to stage 8.
Since the found basic solution is admissible, we will search for the resolving column according to the following scheme: we determine the columns with negative elements in the row of the objective function (except for the column of free numbers). According to Table 5.3, there are two such columns: column “ x1" and column " x2" From such columns, the one that contains the smallest element in the row of the target function is selected. She will be the permissive one. Column " x2" contains the smallest element (–3) compared to the column " x1
To determine the resolving line, we find the positive estimated ratios of free numbers to the elements of the resolving column; the line that corresponds to the smallest positive evaluation ratio is accepted as resolved.
Table 5.4
Original simplex table
In Table 5.4, the smallest positive evaluative relationship corresponds to the line “ x5", therefore, it will be permissive.
The element located at the intersection of the enabling column and the enabling row is accepted as enabling. In our example, this is the element that is located at the intersection of the line “ x5" and columns " x2».
The resolving element shows one basic and one free variable that must be swapped in the simplex table to move to the new “improved” one. basic solution. IN in this case these are variables x5 And x2, in the new simplex table (Table 5.5) we swap them.
9.1. Transformation of the resolving element.
The resolution element of Table 5.4 is converted as follows:
We enter the resulting result into a similar cell in Table 5.5.
9.2. Resolution string conversion.
We divide the elements of the resolving row of table 5.4 by the resolving element of this simplex table, the results fit into similar cells of the new simplex table (table 5.5). Transformations of resolution string elements are given in Table 5.5.
9.3. Conversion of the resolution column.
We divide the elements of the resolution column of Table 5.4 by the resolution element of this simplex table, and the result is taken with the opposite sign. The results obtained fit into similar cells of the new simplex table (Table 5.5). Transformations of the elements of the resolution column are given in Table 5.5.
9.4. Transformation of the remaining elements of the simplex table.
The transformation of the remaining elements of the simplex table (i.e., elements not located in the resolving row and resolving column) is carried out according to the “rectangle” rule.
For example, consider transforming an element located at the intersection of the line " x3" and columns "", let's conditionally denote it " x3" In Table 5.4, we mentally draw a rectangle, one vertex of which is located in the cell whose value we are transforming (i.e. in the cell “ x3"), and the other (diagonal vertex) is in a cell with a resolving element. The other two vertices (of the second diagonal) are uniquely determined. Then the transformed value of the cell " x3" will be equal to the previous value of this cell minus the fraction, in the denominator of which is the resolving element (from Table 5.4), and in the numerator is the product of two other unused vertices, i.e.:
« x3»: .
The values of other cells are converted similarly:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
As a result of these transformations, we received a new simplex table(Table 5.5).
II iteration:
Stage 1: drawing up a simplex table.
Table 5.5
Simplex tableII iterations
Estimated relationship |
||||
| ||||
|
|
Stage 2: determination of the basic solution.
As a result of the simplex transformations, a new basic solution was obtained (Table 5.5):
As you can see, with this basic solution the value of the objective function = 15, which is greater than with the previous basic solution.
The inconsistency of the system of restrictions in accordance with feature 1 in Table 5.5 has not been identified.
Stage 4: checking the boundedness of the objective function.
The unboundedness of the objective function in accordance with criterion 2 in Table 5.5 is not revealed.
Stage 5: checking the admissibility of the found basic solution.
The found basic solution in accordance with criterion 4 is not optimal, since the line of the objective function of the simplex table (Table 5.5) contains a negative element: –2 (the free number of this line is not taken into account when considering this characteristic). Therefore, we move on to stage 8.
Stage 8: determination of the resolving element.
8.1. Definition of the resolution column.
The found basic solution is acceptable; we determine the columns with negative elements in the row of the objective function (except for the column of free numbers). According to Table 5.5, there is only one such column: “ x1" Therefore, we accept it as permitted.
8.2. Definition of an enable string.
According to the obtained values of positive evaluative relations in Table 5.6, the minimum is the relation corresponding to the line “ x3" Therefore, we accept it as permitted.
Table 5.6
Simplex tableII iterations
Estimated relationship |
||||
3/1=3 – min |
||||
Stage 9: transformation of the simplex table.
Transformations of the simplex table (Table 5.6) are performed in the same way as in the previous iteration. The results of transformations of elements of the simplex table are given in Table 5.7.
III iteration
Based on the results of simplex transformations of the previous iteration, we compose a new simplex table:
Table 5.7
Simplex tableIII iterations
Estimated relationship |
||||
| ||||
|
|
Stage 2: determination of the basic solution.
As a result of the simplex transformations, a new basic solution was obtained (Table 5.7):
Stage 3: checking the compatibility of the system of restrictions.
The inconsistency of the system of restrictions in accordance with feature 1 in Table 5.7 has not been identified.
Stage 4: checking the boundedness of the objective function.
The unboundedness of the objective function in accordance with criterion 2 in Table 5.7 is not revealed.
Stage 5: checking the admissibility of the found basic solution.
The found basic solution in accordance with criterion 3 is acceptable, since it does not contain negative components.
Stage 6: checking the optimality of the found basic solution.
The found basic solution in accordance with criterion 4 is not optimal, since the line of the objective function of the simplex table (Table 5.7) contains a negative element: –3 (the free number of this line is not taken into account when considering this characteristic). Therefore, we move on to stage 8.
Stage 8: determination of the resolving element.
8.1. Definition of the resolution column.
The found basic solution is acceptable; we determine the columns with negative elements in the row of the objective function (except for the column of free numbers). According to Table 5.7, there is only one such column: “ x5" Therefore, we accept it as permitted.
8.2. Definition of an enable string.
According to the obtained values of positive evaluative relations in Table 5.8, the minimum is the relation corresponding to the line “ x4" Therefore, we accept it as permitted.
Table 5.8
Simplex tableIII iterations
Estimated relationship |
||||
5/5=1 – min |
||||
Stage 9: transformation of the simplex table.
Transformations of the simplex table (Table 5.8) are performed in the same way as in the previous iteration. The results of transformations of elements of the simplex table are given in Table 5.9.
IV iteration
Stage 1: construction of a new simplex table.
Based on the results of simplex transformations of the previous iteration, we compose a new simplex table:
Table 5.9
Simplex tableIV iterations
Estimated relationship |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
Stage 2: determination of the basic solution.
As a result of the simplex transformations, a new basic solution was obtained; according to Table 5.9, the solution is as follows:
Stage 3: checking the compatibility of the system of restrictions.
The inconsistency of the system of restrictions in accordance with feature 1 in Table 5.9 has not been identified.
Stage 4: checking the boundedness of the objective function.
The unboundedness of the objective function in accordance with criterion 2 in Table 5.9 is not revealed.
Stage 5: checking the admissibility of the found basic solution.
The found basic solution in accordance with criterion 3 is acceptable, since it does not contain negative components.
Stage 6: checking the optimality of the found basic solution.
The found basic solution in accordance with feature 4 is optimal, since there are no negative elements in the line of the objective function of the simplex table (Table 5.9) (the free number of this line is not taken into account when considering this feature).
Stage 7: checking the alternativeness of the solution.
The solution found is unique, since there are no zero elements in the line of the objective function (Table 5.9) (the free number of this line is not taken into account when considering this feature).
Answer: optimal value objective function of the problem under consideration =24, which is achieved at.
Example 5.2. Solve the above linear programming problem provided that the objective function is minimized:
Solution:
I iteration:
Stage 1: formation of the initial simplex table.
The original linear programming problem is given in standard form. Let us bring it to canonical form by introducing an additional non-negative variable into each of the inequality constraints, i.e.
In the resulting system of equations we take as allowed (basic) variables x3, x4, x5, x6, then the free variables will be x1,x2. Let us express the basic variables in terms of free ones.
Let's consider simplex method for solving linear programming (LP) problems. It is based on the transition from one reference plan to another, in which the value of the objective function increases.
The simplex method algorithm is as follows:
- We translate the original problem into canonical view by introducing additional variables. For inequalities of the form ≤, additional variables are introduced with a sign (+), but if of the form ≥, then with a sign (-). Additional variables are introduced into the objective function with corresponding signs with a coefficient equal to 0 , because the target function should not change its economic meaning.
- Vectors are written out P i from the coefficients of the variables and the column of free terms. This action determines the number of unit vectors. The rule is that there should be as many unit vectors as there are inequalities in the system of constraints.
- After this, the source data is entered into a simplex table. Unit vectors are introduced into the basis, and by excluding them from the basis, the optimal solution is found. The coefficients of the objective function are written with the opposite sign.
- An optimality sign for an LP problem is that the solution is optimal if in f– in the row all coefficients are positive. Rule for finding the enabling column - viewed f– a string and among its negative elements the smallest one is selected. Vector P i its containing becomes permissive. The rule for selecting a resolving element - the ratios of the positive elements of the resolving column to the elements of the vector are compiled P 0 and the number that gives the smallest ratio becomes the resolving element with respect to which the simplex table will be recalculated. The line containing this element is called the enable line. If there are no positive elements in the resolution column, then the problem has no solution. After determining the resolving element, they proceed to recalculation of a new simplex table.
- Rules for filling out a new simplex table. Unit is put in place of the resolving element, and other elements are assumed to be equal 0 . The resolving vector is added to the basis, from which the corresponding zero vector is excluded, and the remaining basis vectors are written without changes. The elements of the resolution string are divided by the resolution element, and the remaining elements are recalculated according to the rectangle rule.
- This is done until f– all elements of the string will not become positive.
Let's consider solving the problem using the algorithm discussed above.
Given:
We bring the problem to canonical form:
We compose the vectors:
Fill out the simplex table:
:
Let's recalculate the first element of the vector P 0, for which we make a rectangle of numbers: and we get: 
.
We perform similar calculations for all other elements of the simplex table:
In the received plan f– the line contains one negative element – (-5/3), vector P 1. It contains in its column a single positive element, which will be the enabling element. Let's recalculate the table regarding this element:
No negative elements in f– line means found optimal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).
- Ashmanov S. A. Linear programming, M: Nauka, 1998,
- Ventzel E.S. Operations Research, M: Soviet Radio, 2001,
- Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Mathematical programming, M: Higher School, 1986.
Custom Linear Programming Solution
You can order any assignments in this discipline on our website. You can attach files and specify deadlines at
Simplex method is an iterative process of directed solution of a system of equations step by step, which begins with a reference solution and in search of best option moves along the corner points of the feasible solution area, improving the value of the objective function until the objective function reaches the optimal value.Purpose of the service. The service is intended for online solutions Linear programming problems (LPP) using the simplex method in the following notation forms:
- in the form of a simplex table (Jordan transformation method); basic recording form;
- modified simplex method; in column form; in line form.
Instructions. Select the number of variables and the number of rows (number of constraints). The resulting solution is stored in Word file and Excel.
In this case, do not take into account restrictions like x i ≥ 0. If there are no restrictions in the task for some x i, then the ZLP must be converted to the KZLP, or use this service. When solving, the usage is automatically determined M-method(simplex method with artificial basis) and two-stage simplex method.The following are also used with this calculator:
Graphical method for solving ZLP
Solution of the transport problem
Solving a matrix game
Using the service in online mode you can determine the price of a matrix game (lower and upper bounds), check for the presence of a saddle point, find a solution to a mixed strategy using the following methods: minimax, simplex method, graphical (geometric) method, Brown's method.
Extremum of a function of two variables
Dynamic programming problems
Distribute 5 homogeneous lots of goods between three markets so as to obtain maximum income from their sale. Income from sales in each market G(X) depends on the number of sold batches of product X and is presented in the table.
| Product volume X (in lots) | Income G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Simplex method algorithm includes the following steps:
- Drawing up the first basic plan. Transition to canonical form linear programming problems by introducing non-negative additional balance variables.
- Checking the plan for optimality. If there is at least one index line coefficient less than zero, then the plan is not optimal and needs to be improved.
- Determining the leading column and row. From the negative coefficients of the index line, the largest in absolute value is selected. Then the elements of the free member column of the simplex table are divided into elements of the same sign of the leading column.
- Building a new reference plan. The transition to a new plan is carried out as a result of recalculation of the simplex table using the Jordan-Gauss method.
If it is necessary to find the extremum of the objective function, then we are talking about searching minimum value(F(x) → min , see example of solving a function minimization) and maximum value((F(x) → max , see example of solving a function maximization)
An extreme solution is achieved at the boundary of the region admissible solutions at one of the vertices of the corner points of the polygon, or on a segment between two adjacent corner points.
Fundamental Theorem of Linear Programming. If the ZLP objective function reaches an extreme value at some point in the region of feasible solutions, then it takes this value at the corner point. If the ZLP objective function reaches an extreme value at more than one corner point, then it takes the same value at any of the convex linear combinations of these points.
The essence of the simplex method. Movement to the optimum point is carried out by moving from one corner point to the neighboring one, which brings closer and faster to X opt. Such a scheme for enumerating points, called the simplex method, suggested by R. Danzig.
Corner points are characterized by m basic variables, so the transition from one corner point to a neighboring one can be accomplished by changing only one basic variable in the basis to a variable from a non-basis.
The implementation of the simplex method, due to various features and formulations of LP problems, has various modifications.
The construction of simplex tables continues until it is obtained optimal solution. How can you use a simplex table to determine that the solution to a linear programming problem is optimal?
If the last line (values of the objective function) does not contain negative elements, therefore, it will find the optimal plan.
Remark 1. If one of the basic variables is equal to zero, then the extreme point corresponding to such a basic solution is degenerate. Degeneracy occurs when there is ambiguity in the choice of the guide line. You may not notice the degeneracy of the problem at all if you choose another line as a guide. In case of ambiguity, the row with the lowest index should be selected to avoid looping.
Remark 2. Let at some extreme point all simplex differences be non-negative D k ³ 0 (k = 1..n+m), i.e. an optimal solution is obtained and there exists such A k - a non-basic vector for which D k = 0. Then the maximum is achieved by at least at two points, i.e. there is an alternative optimum. If we introduce this variable x k into the basis, the value of the objective function will not change.
Remark 3. Solution dual problem is in the last simplex table. The last m components of the vector of simplex differences (in the columns of balance variables) are the optimal solution to the dual problem. The values of the objective functions of the direct and dual problems at optimal points coincide.
Remark 4. When solving the minimization problem, the vector with the largest positive simplex difference is introduced into the basis. Next, the same algorithm is applied as for the maximization problem.
If the condition “It is necessary that type III raw materials be completely consumed” is specified, then the corresponding condition is an equality.
This method is a method of purposeful enumeration of reference solutions to a linear programming problem. He allows for final number steps to either find an optimal solution or establish that there is no optimal solution.
The main content of the simplex method is as follows:- Indicate a method for finding the optimal reference solution
- Indicate the method of transition from one reference solution to another, at which the value of the objective function will be closer to the optimal one, i.e. indicate a way to improve the reference solution
- Set criteria that allow you to promptly stop searching for support solutions at the optimal solution or draw a conclusion about the absence of an optimal solution.
Algorithm of the simplex method for solving linear programming problems
In order to solve a problem using the simplex method, you must do the following:- Bring the problem to canonical form
- Find the initial support solution with a “unit basis” (if there is no support solution, then the problem does not have a solution due to the incompatibility of the system of constraints)
- Calculate estimates of vector decompositions based on the reference solution and fill in the table of the simplex method
- If the criterion for the uniqueness of the optimal solution is satisfied, then the solution of the problem ends
- If the condition for the existence of a set of optimal solutions is met, then all optimal solutions are found by simple enumeration
An example of solving a problem using the simplex method
Example 26.1Solve the problem using the simplex method:
Solution:
We bring the problem to canonical form.
To do this, we introduce an additional variable x 6 with coefficient +1 to the left side of the first inequality constraint. The variable x 6 is included in the objective function with a coefficient of zero (i.e., it is not included).
We get:
We find the initial support solution. To do this, we equate free (unresolved) variables to zero x1 = x2 = x3 = 0.
We get reference solution X1 = (0,0,0,24,30,6) with unit basis B1 = (A4, A5, A6).
We calculate estimates of vector decompositions conditions on the basis of the reference solution according to the formula:
Δ k = C b X k - c k
- C b = (c 1, c 2, ..., c m) - vector of coefficients of the objective function for the basic variables
- X k = (x 1k, x 2k, ..., x mk) - vector of expansion of the corresponding vector A k according to the basis of the reference solution
- C k is the coefficient of the objective function for the variable x k.
The estimates of the vectors included in the basis are always equal to zero. The reference solution, coefficients of expansions and estimates of expansions of vectors of conditions on the basis of the reference solution are written in simplex table:
At the top of the table, for the convenience of calculating estimates, the coefficients of the objective function are written. The first column "B" contains the vectors included in the basis of the reference solution. The order in which these vectors are written corresponds to the numbers of allowed unknowns in the constraint equations. In the second column of the table "C b" the coefficients of the objective function for the basic variables are written in the same order. At correct location The coefficients of the objective function in the column "C b" of the estimate of the unit vectors included in the basis are always equal to zero.
IN last line tables with estimates of Δ k in the column “A 0” the values of the objective function on the reference solution Z(X 1) are written.
The initial support solution is not optimal, since in the maximum problem the estimates Δ 1 = -2, Δ 3 = -9 for vectors A 1 and A 3 are negative.
According to the theorem on improving the support solution, if in a maximum problem at least one vector has a negative estimate, then you can find a new support solution on which the value of the objective function will be greater.
Let us determine which of the two vectors will lead to a larger increment in the objective function.
The increment of the objective function is found by the formula: .
We calculate the values of the parameter θ 01 for the first and third columns using the formula:
We obtain θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (Table 26.1).
We find the increment of the objective function when introducing into the basis the first vector ΔZ 1 = - 6*(- 2) = 12, and the third vector ΔZ 3 = - 3*(- 9) = 27.
Consequently, for a faster approach to the optimal solution, it is necessary to introduce vector A3 into the basis of the reference solution instead of the first vector of the basis A6, since the minimum of the parameter θ 03 is achieved in the first row (l = 1).
We perform the Jordan transformation with the element X13 = 2, we obtain the second reference solution X2 = (0,0,3,21,42,0) with the basis B2 = (A3, A4, A5). (Table 26.2)
This solution is not optimal, since vector A2 has a negative estimate Δ2 = - 6. To improve the solution, it is necessary to introduce vector A2 into the basis of the reference solution.
We determine the number of the vector derived from the basis. To do this, we calculate the parameter θ 02 for the second column, it is equal to 7 for l = 2. Consequently, we derive the second basis vector A4 from the basis. We perform the Jordan transformation with the element x 22 = 3, we obtain the third reference solution X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Table 26.3).
This solution is the only optimal one, since for all vectors not included in the basis the estimates are positive
Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.
Answer: max Z(X) = 201 at X = (0.7,10,0.63).
Linear programming method in economic analysis
Linear programming method makes it possible to justify the most optimal economic solution under conditions of severe restrictions related to the resources used in production (fixed assets, materials, labor resources). Application of this method in economic analysis allows you to solve problems related mainly to planning the organization’s activities. This method helps determine the optimal output levels, as well as the directions for the most effective use production resources available to the organization.
Using this method, the so-called extremal problems are solved, which consists in finding extreme values, that is, the maximum and minimum of functions of variable quantities.
This period is based on the solution of the system linear equations in cases where the analyzed economic phenomena are connected by a linear, strictly functional dependence. The linear programming method is used to analyze variables in the presence of certain limiting factors.
A very common solution is the so-called transport problem using the linear programming method. The content of this task is to minimize the costs incurred in connection with the operation Vehicle under existing restrictions regarding the number of vehicles, their carrying capacity, the duration of their operation, and if there is a need for maintenance maximum quantity customers.
Besides, this method is widely used in solving scheduling problems. This task consists of such a distribution of operating time for the personnel of a given organization that would be most acceptable both for the members of this personnel and for the clients of the organization.
This task is to maximize the number of clients served under conditions of limitations on the number of available staff members, as well as the working time fund.
Thus, the linear programming method is quite common in placement and usage analysis. various types resources, as well as in the process of planning and forecasting the activities of organizations.
Yet mathematical programming can also be applied to those economic phenomena the relationship between which is not linear. For this purpose, nonlinear, dynamic and convex programming methods can be used.
Nonlinear programming relies on the nonlinear nature of the objective function or constraints, or both. The forms of the objective function and inequalities of restrictions in these conditions can be different.
Nonlinear programming is used in economic analysis, in particular, when establishing the relationship between indicators expressing the efficiency of an organization’s activities and the volume of this activity, the structure of production costs, market conditions, etc.
Dynamic programming is based on constructing a decision tree. Each tier of this tree serves as a stage for determining the consequences of a previous decision and for eliminating ineffective options for that decision. Thus, dynamic programming has a multi-step, multi-stage nature. This type of programming is used in economic analysis to find optimal options development of the organization both now and in the future.
Convex programming is a type of nonlinear programming. This type of programming expresses the nonlinear nature of the relationship between the results of an organization’s activities and its costs. Convex (aka concave) programming analyzes convex objective functions and convex systems of restrictions (points acceptable values). Convex programming is used in the analysis of economic activities with the aim of minimizing costs, and concave programming with the aim of maximizing income under existing restrictions on the action of factors that influence the analyzed indicators in the opposite way. Consequently, with the types of programming under consideration, convex objective functions are minimized, and concave objective functions are maximized.
Here is a manual (not applet) solution of two problems using the simplex method (similar to the applet solution) with detailed explanations in order to understand the algorithm for solving problems using the simplex method. The first problem contains inequality signs only "≤" (problem with an initial basis), the second can contain signs "≥", "≤" or "=" (problem with artificial basis), they are solved differently.
Simplex method, solving a problem with an initial basis
1)Simplex method for a problem with an initial basis (all signs of inequality constraints " ≤ ").
Let's write the problem in canonical form, i.e. we rewrite the inequality restrictions in the form of equalities, adding balance sheet variables:
This system is a system with a basis (basis s 1, s 2, s 3, each of them is included in only one equation of the system with a coefficient of 1), x 1 and x 2 are free variables. Problems to be solved using the simplex method must have the following two properties: - the system of constraints must be a system of equations with a basis; -free terms of all equations in the system must be non-negative.
The resulting system is a system with a basis and its free terms are non-negative, so we can apply simplex method. Let's create the first simplex table (Iteration 0) to solve the problem on simplex method, i.e. a table of coefficients of the objective function and a system of equations for the corresponding variables. Here “BP” means the column of basic variables, “Solution” means the column of the right-hand sides of the system equations. The solution is not optimal, because there are negative coefficients in the z-row.
simplex method iteration 0
|
Attitude |
|||||||
To improve the solution, let's move on to the next iteration simplex method, we get the following simplex table. To do this you need to select permission column, i.e. a variable that will be included in the basis at the next iteration of the simplex method. It is selected by the largest absolute negative coefficient in the z-row (in the maximum problem) - in the initial iteration of the simplex method this is column x 2 (coefficient -6).
Then select enable string, i.e. a variable that will leave the basis at the next iteration of the simplex method. It is selected by the smallest ratio of the “Decision” column to the corresponding positive elements of the resolution column (column “Ratio”) - in the initial iteration this is row s 3 (coefficient 20).
Permissive element is at the intersection of the resolving column and the resolving row, its cell is highlighted in color, it is equal to 1. Therefore, at the next iteration of the simplex method, the variable x 2 will replace s 1 in the basis. Note that the relationship is not searched for in the z-string; a dash “-” is placed there. If there are identical minimal relations, then any of them is selected. If all coefficients in the resolution column are less than or equal to 0, then the solution to the problem is infinite.
Let's fill out the following table “Iteration 1”. We will get it from the “Iteration 0” table. The goal of further transformations is to turn the x2 resolution column into a unit column (with a one instead of the resolution element and zeros instead of the remaining elements).
1) Calculate row x 2 of the “Iteration 1” table. First, we divide all the members of the resolving row s 3 of the “Iteration 0” table by the resolving element (it is equal to 1 in this case) of this table, we get row x 2 in the “Iteration 1” table. Because the resolving element in this case is equal to 1, then row s 3 of the “Iteration 0” table will coincide with row x 2 of the “Iteration 1” table. Row x 2 of the Iteration 1 table we got 0 1 0 0 1 20, the remaining rows of the Iteration 1 table will be obtained from this row and the rows of the Iteration 0 table as follows:
2) Calculation of the z-row of the “Iteration 1” table. In place of -6 in the first row (z-row) in the x2 column of the Iteration 0 table, there should be a 0 in the first row of the Iteration 1 table. To do this, multiply all the elements of the row x 2 of the table "Iteration 1" 0 1 0 0 1 20 by 6, we get 0 6 0 0 6 120 and add this row with the first row (z - row) of the table "Iteration 0" -4 -6 0 0 0 0, we get -4 0 0 0 6 120. A zero 0 appears in the x 2 column, the goal is achieved. Elements of the resolution column x 2 are highlighted in red.
3) Calculation of row s 1 of the “Iteration 1” table. In place of 1 in s 1 row of the “Iteration 0” table there should be a 0 in the “Iteration 1” table. To do this, multiply all the elements of row x 2 of the table "Iteration 1" 0 1 0 0 1 20 by -1, get 0 -1 0 0 -1 -20 and add this row with s 1 - row of the table "Iteration 0" 2 1 1 0 0 64, we get the row 2 0 1 0 -1 44. In the x 2 column we get the required 0.
4) Calculate row s 2 of the “Iteration 1” table. In place 3 in s 2 row of the table "Iteration 0" there should be 0 in the table "Iteration 1". To do this, multiply all the elements of row x 2 of the table "Iteration 1" 0 1 0 0 1 20 by -3, we get 0 -3 0 0 -3 -60 and add this row with s 1 - row of the table "Iteration 0" 1 3 0 1 0 72, we get the row 1 0 0 1 -3 12. In the x 2 column, the required 0 is obtained. The x 2 column in the “Iteration 1” table has become a unit, it contains one 1 and the rest 0.
The rows of the table “Iteration 1” are obtained according to the following rule:
New row = Old row – (Old row resolution column coefficient)*(New resolution row).
For example, for a z-string we have:
Old z-string (-4 -6 0 0 0 0) -(-6)*New resolving string -(0 -6 0 0 -6 -120) =New z-string (-4 0 0 0 6 120).
For the following tables, the recalculation of table elements is done in a similar way, so we omit it.
simplex method iteration 1
|
Attitude |
|||||||
Resolving column x 1, resolving row s 2, s 2 leaves the basis, x 1 enters the basis. In exactly the same way, we obtain the remaining simplex tables until we obtain a table with all positive coefficients in the z-row. This is a sign of an optimal table.
simplex method iteration 2
|
Attitude |
|||||||
Resolving column s 3, resolving row s 1, s 1 leaves the basis, s 3 enters the basis.
simplex method iteration 3
|
Attitude |
|||||||
In the z-row, all coefficients are non-negative, therefore, the optimal solution x 1 = 24, x 2 = 16, z max = 192 is obtained.