Solution of systems of linear equations simplex by online method. Simplex method for solving zlp. Simplex method, solution of a problem with an artificial basis

Here is a manual (not applet) solution of two problems using the simplex method (similar to 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 " ≤ " (a problem with an initial basis), the second one can contain signs " ≥ ", " ≤ " or " = " (a problem with an artificial basis), they are solved in different ways.

Simplex method, solution of a problem with an initial basis

1)Simplex method for a problem with an initial basis (all signs of constraint inequalities are " ≤ ").

Let's write the problem in canonical form, i.e. we rewrite the inequality constraints as 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 for which the simplex method is used 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. Compile the first simplex table (Iteration 0) for solving 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" - the column of the right parts of the equations of the system. The solution is not optimal, because there are negative coefficients in the z-line.

simplex method iteration 0

							Attitude

To improve the solution, let's move on to the next iteration simplex method, we obtain the following simplex tableau. For this you need to choose enable column, i.e. a variable that will enter the basis at the next iteration of the simplex method. It is chosen by the largest negative coefficient in the z-row (in the maximum problem) - in the initial iteration of the simplex method, this is the column x 2 (coefficient -6).

Then choose permission 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 resolving column ("Ratio" column) - in the initial iteration, this is row s 3 (coefficient 20).

Permissive element is located at the intersection of the enabling column and the enabling 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 relation is not searched in the z-string, a dash "-" is put there. If there are identical minimum ratios, then any of them is chosen. 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 in the following table "Iteration 1". We will get it from the "Iteration 0" table. The purpose of further transformations is to turn the x2 enable column into a single column (with one instead of the enable element and zeros instead of the rest of the elements).

1) Calculating row x 2 of the "Iteration 1" table. First, we divide all 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 the row x 2 in the "Iteration 1" table. Because the resolving element in this case is equal to 1, then the row s 3 of the "Iteration 0" table will match the 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 column x2 of the "Iteration 0" table, there should be a 0 in the first row of the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 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 "Iteration 0" table -4 -6 0 0 0 0, we get -4 0 0 0 6 120. Zero 0 appeared in the x 2 column, the goal was achieved. The elements of the permission 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 should be 0 in the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by -1, we get 0 -1 0 0 -1 -20 and add this row with s 1 - the row of the "Iteration 0" table 2 1 1 0 0 64, we get the row 2 0 1 0 -1 44. The required 0 is obtained in the x 2 column.

4) Calculation of row s 2 of the "Iteration 1" table. In place of 3 in s 2 row of the "Iteration 0" table should be 0 in the "Iteration 1" table. To do this, we multiply all the elements of row x 2 of the "Iteration 1" table 0 1 0 0 1 20 by -3, we get 0 -3 0 0 -3 -60 and add this row with s 1 - the row of the "Iteration 0" table 1 3 0 1 0 72, we get the row 1 0 0 1 -3 12. The required 0 is obtained in the x 2 column. The x 2 column in the "Iteration 1" table has become single, it contains one 1 and the rest 0.

The rows of the "Iteration 1" table are obtained according to the following rule:

New Row = Old Row - (Old Row Permission Factor)*(New Row).

For example, for the z-line we have:

Old z-string (-4 -6 0 0 0 0) -(-6)*New enable string -(0 -6 0 0 -6 -120) = New z-string (-4 0 0 0 6 120).

For the following tables, recalculation of table elements is done in a similar way, so we omit it.

simplex method iteration 1

							Attitude

Permissive column x 1 , permissive 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 a table with all positive coefficients in the z-row is obtained. 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, it is obtained optimal solution x 1 \u003d 24, x 2 \u003d 16, z max \u003d 192.

This method is a method of purposeful enumeration of reference solutions of a linear programming problem. It allows for a finite number of steps either to find the optimal solution or to establish that there is no optimal solution.

The main content of the simplex method is as follows:

1. Specify a method for finding the optimal reference solution
2. Specify the method of transition from one reference solution to another, on which the value of the objective function will be closer to the optimal, i.e. indicate a way to improve the reference solution
3. Set the criteria that allow you to timely stop the enumeration of support solutions on the optimal solution or follow the conclusion that there is no optimal solution.

Algorithm of the simplex method for solving linear programming problems

In order to solve the problem by the simplex method, you must do the following:

1. Submit the task to canonical form
2. Find an initial reference solution with a "unit basis" (if there is no reference solution, then the problem does not have a solution due to the incompatibility of the system of constraints)
3. Calculate estimates of vector expansions in terms of the basis of the reference solution and fill in the table of the simplex method
4. If the criterion for the uniqueness of the optimal solution is satisfied, then the solution of the problem ends
5. If the condition for the existence of a set of optimal solutions is satisfied, then by simple enumeration, all optimal solutions are found

An example of solving the problem by the simplex method

Example 26.1

Solve the problem using the simplex method:

Solution:

We bring the problem to the canonical form.

To do this, we introduce an additional variable x 6 with the coefficient +1 into 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 reference solution. To do this, we equate the 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).

Calculate vector decomposition estimates conditions on the basis of the reference solution according to the formula:

Δ k \u003d C b X k - c k

• C b = (с 1 , с 2 , ... , с m) is the vector of objective function coefficients with basic variables
• X k = (x 1k , x 2k , ... , x mk) is the expansion vector of the corresponding vector A k in terms of the basis of the reference solution
• C k - coefficient of the objective function for the variable x k.

Estimates of the vectors included in the basis are always equal to zero. The reference solution, coefficients of expansions, and estimates of expansions of condition vectors in terms of the basis of the reference solution are written in simplex table:

Above 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 of writing these vectors corresponds to the numbers of allowed unknowns in the constraint equations. In the second column of the table "With b" the coefficients of the objective function are written with basic variables in the same order. At correct location coefficients of the objective function in the column "C b" estimates of the unit vectors included in the basis, always equal to zero.

In the last row of the table with estimates of Δ k in the column "A 0 "the values ​​of the objective function are written on the reference solution Z(X 1).

The initial reference solution is not optimal, since in the maximum problem the estimates Δ 1 = -2, Δ 3 = -9 for the vectors A 1 and A 3 are negative.

According to the reference solution improvement theorem, if at least one vector in the maximum problem has a negative estimate, then it is possible to find a new reference 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 of the objective function.

The objective function increment is found by the formula: .

We calculate the values ​​of the parameter θ 01 for the first and third columns using the formula:

We get θ 01 = 6 for l = 1, θ 03 = 3 for l = 1 (table 26.1).

We find the increment of the objective function when the first vector ΔZ 1 = - 6 * (- 2) = 12 is introduced into the basis, and the third vector ΔZ 3 = - 3 * (- 9) = 27.

Therefore, for a faster approach to the optimal solution, it is necessary to introduce the 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 reached in the first row (l = 1).

We perform the Jordan transform 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 the vector A2 has a negative estimate Δ2 = - 6. To improve the solution, it is necessary to introduce the 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. Therefore, 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 that are not included in the basis, the estimates are positive

Δ 1 \u003d 7/2, Δ 4 \u003d 2, Δ 6 \u003d 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 in the face of severe restrictions related to the resources used in production (fixed assets, materials, labor resources). The application of this method in economic analysis allows us to solve problems related mainly to the planning of the organization's activities. This method helps to determine the optimal values ​​of output, as well as the directions for the most efficient use of the production resources available to the organization.

Using this method, the solution of the so-called extremal problems is carried out, which consists in finding the extreme values, that is, the maximum and minimum of functions of variables.

This period is based on solving a system of 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.

The solution of the so-called transport problem using the linear programming method is quite common. The content of this task is to minimize the costs incurred in connection with the operation of vehicles under the existing restrictions regarding the number of vehicles, their carrying capacity, the duration of their work, if there is a need to serve the maximum number of customers.

In addition, this method is widely used in solving the problem of scheduling. This task consists in such a distribution of the time of functioning of the personnel of this organization, which would be the most acceptable both for the members of this personnel and for the clients of the organization.

The objective is to maximize the number of clients served while limiting the number of available staff members and working hours.

Thus, the linear programming method is very common in the analysis of the placement and use of various kinds resources, as well as in the process of planning and forecasting the activities of organizations.

Nevertheless, mathematical programming can also be applied to those economic phenomena, the relationship between which is not linear. For this purpose, methods of nonlinear, dynamic and convex programming can be used.

Nonlinear programming relies on the non-linear nature of the objective function or constraints, or both. The forms of the objective function and constraint inequalities under these conditions can be different.

Nonlinear programming is used in economic analysis, in particular, when establishing the relationship between indicators expressing the effectiveness of the organization's activities and the volume of this activity, the structure of production costs, market conditions, etc.

Dynamic programming is based on building a decision tree. Each tier of this tree serves as a stage for determining the consequences previous decision and to eliminate inefficient options for this solution. Thus, dynamic programming has a multi-step, multi-stage character. This type of programming is used in economic analysis to find best options organization, both now and in the future.

Convex programming is a type of non-linear programming. This type of programming expresses the non-linear nature of the relationship between the results of the organization's activities and the costs incurred by it. Convex (otherwise concave) programming analyzes convex objective functions and convex constraint systems (feature points). Convex programming is used in the analysis of economic activity in order to minimize costs, and concave programming is used in order to maximize income in the conditions of existing restrictions on the action of factors that affect the analyzed indicators in the opposite way. Consequently, under the types of programming under consideration, convex objective functions are minimized, and concave ones are maximized.

Consider simplex method for solving problems of linear programming (LP). 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:

1. We translate the original problem into a canonical form by introducing additional variables. For an inequality 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 the corresponding signs with a coefficient equal to 0 , because the objective function should not change its economic meaning.
2. Vectors are issued Pi 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 constraint system.
3. After that, the initial data are entered into the simplex table. Unit vectors are introduced into the basis, and excluding them from the basis, the optimal solution is found. The objective function coefficients are written with the opposite sign.
4. The optimality criterion for the LP problem is that the solution is optimal if in f– row all coefficients are positive. Permission Column Finding Rule – Viewed f is a string and among its negative elements the smallest is chosen. Vector Pi its containing becomes permissive. The rule for choosing 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, relative to which the simplex table will be recalculated. The string containing this element is called the enable string. If there are no positive elements in the resolution column, then the problem has no solution. After determining the resolving element, they proceed to the recalculation of a new simplex table.
5. Rules for filling in a new simplex table. In place of the resolving element, one is put down, and the 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 unchanged. The elements of the permissive line are divided by the permissive element, and the remaining elements are recalculated according to the rule of rectangles.
6. This is done until the f– all elements of the string will not become positive.

Consider the solution of the problem using the above algorithm.
Given:

We bring the problem to the canonical form:

We compose vectors:

Fill in the simplex table:

:
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 string contains one negative element – ​​(-5/3), vectors P1. It contains in its column the only positive element, which will be the resolving element. Let's recalculate the table with respect to this element:

The absence of negative elements in f- string means found optimal plan:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Linear programming, M: Nauka, 1998,
• Wentzel 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− it is a method of ordered enumeration of reference plans (ordering is ensured by a monotonous change in the value of the objective function during the transition to the next plan). In this case, it is necessary to observe the principle: each next step should improve or, in extreme cases, not worsen the value of the objective function.

To solve the LLP simplex method it is reduced to canonical form, i.e. from restrictions - inequalities it is necessary to make restrictions - equalities. To do this, each constraint is supplemented with an additional non-negative balance sheet variable with the “+” sign if the inequality sign is “£”, and with the “–” sign if the inequality sign is “³”.

In the objective function, these additional variables enter with zero coefficients, i.e. the target function entry will not change. Each variable that is not subject to the non-negativity condition can be represented as the difference of two non-negative variables: .

If the task constraints reflect the presence and consumption of resources, then the numerical value of the additional variable in the task plan, written in canonical form, is equal to the amount of unused resource.

To solve the problem by the simplex method, we will use shortened simplex tables of a system of linear equations and the modified Jordan elimination method.

1. We draw up the first basic plan

The task remains the same. Let us bring the standard form of the system of inequalities (1) into the canonical form of the system of equations by introducing additional balance variables x 3 , x 4 , x 5 ,x 6 .

In the economic sense, the values ​​of additional variables x 3 , x 4 , x 5 determine the balance of raw materials after the sale of products.

The matrix of the resulting system of equations has the form:

It can be seen that in the matrix A the basis minor of the 4th order is the determinant, composed of unit coefficients for additional variables x 3 , x 4 , x 5 ,x 6 , since it is non-zero and equal to 1. This means that the column vectors for these variables are linearly independent, i.e. form basis, and the corresponding variables x 3 , x 4 , x 5 ,x 6 are basic(basic). Variables x 1 , x 2 will be called free(minor).

If free variables x 1 and x 2 to set different values, then, solving the system with respect to the basic variables, we obtain an infinite set of particular solutions. If only zero values ​​are set for free variables, then from an infinite set of particular solutions, basic solutions- basic plans.

To find out whether the variables can be basic, it is necessary to calculate the determinant consisting of the coefficients of these variables. If this determinant is not equal to zero, then these variables can be basic.

The number of basic solutions and the corresponding number of groups of basic variables can be no more than , where n is the total number of variables, r is the number of basic variables, r≤ m≤ n.

For our task r = 4; n= 6. Then , i.e. 15 groups of 4 basic variables are possible (or 15 basic solutions).

Let us solve the system of equations with respect to the basic variables x 3 , x 4 , x 5 ,x 6:

Assuming that the free variables x 1 = 0, x 2 = 0, we get the values ​​of the basic variables: x 3 = 312; x 4 = 15; x 5 = 24;x 6 = -10, i.e. the basic solution will be = (0; 0; 312; 15; 24; -10).

This basic solution is unacceptable, because x 6 = –10 ≤ 0, and by the constraint condition x 6 ≥ 0. Therefore, instead of the variable x 6 as a basis, you need to take another variable from among the free x 1 or x 2 .

We will carry out the further solution using shortened simplex tables, filling in the rows of the first table with the coefficients of the system as follows (Table 1):

Table 1

F- the string is called index. It is filled with objective function coefficients taken with opposite signs, since the equation of the function can be represented as F = 0 – (– 4x 1 – 3x 2).

In the column of free members b i there is a negative element b 4 = -10, i.e. the solution of the system is invalid. To get a valid solution (base plan), the element b 4 must be made non-negative.

Choose x 6 - a line with a negative free member. This line contains negative elements. Choose any of them, for example, "-1" in x 1 -column, and x 1 - column accept as permission column(it will determine that the variable x 1 will go from free to basic).

We share free members b i on the relevant elements a is resolving column, we get evaluative relationsΘ i==(24, 15, 12, 10). Of these, we choose the smallest positive (minΘ i=10), which will correspond to permission line. Permission string defines a variable x j, which at the next step protrudes from the basis and becomes free. That's why x 6 -line is a permissive line, and the element "-1" is enabling element. We circle it. Variables x 1 and x 6 are swapped.

Estimated ratios Θ i in each line are determined by the rules:

1) Θ i= if b i And a is have different signs;

2) Θ i= ∞ if b i= 0 and a is < 0;

3) Θ i= ∞ if a is = 0;

4) Θ i= 0 if b i= 0 and a is > 0;

5) Θ i= if b i And a is have the same signs.

We take the step of the modified Jordan elimination (MJJI) with a permissive element and compile a new table (Table 2) according to the following rule:

1) in place of the resolving element (RE), a value is set, its inverse, i.e. ;

2) the elements of the permissive line are divided into RE;

3) the elements of the resolving column are divided into RE and the sign changes;

4) the remaining elements are found according to the rectangle rule:

From Table. 2 shows that the free members in b i-column are non-negative, therefore, the initial admissible solution is obtained - first base plan= (10; 0; 182; 5; 4; 0). In this case, the value of the function F() = 40. Geometrically, this corresponds to the top F(10; 0) solution polygon (Fig. 1).

table 2

2. We check the plan for optimality. The base plan is not optimal, because in F-line available negative coefficient"-4". We improve the plan.

3. Finding a new baseline

We select the allowing element according to the rule:

We choose the smallest negative coefficient in F-line "-4", which determines the enabling column - x 6; variable x 6 translate into basic;

We find the ratios Θ i, among them we choose the smallest positive one, which corresponds to the permissive string:

min Θ i = min(14, 5, 2, ∞) = 2, hence x 5 - line - permissive, variable x 5 we translate into free (variables x 5 and x 6 are swapped).

At the intersection of the permissive row and column is the permissive element "2";

We perform the step SHMZhI, we build the table. 3 according to the above rule and get a new reference plan = (12; 0; 156; 3; 0; 2).

Table 3

4. Checking the new basic plan for optimality

The base plan is also not optimal, since in F-line has a negative coefficient "-1". Function value F() = 48, which geometrically corresponds to the top E(12; 0) solution polygon (Fig. 1). We improve the plan.

5. Finding a new baseline

x 2-column is permissive, since in F-line the smallest negative coefficient "-1" is in x 2-column (Δ 2 = -1). Finding the smallest Θ i: min Θ i = min(≈ 9, 6, ∞, 24) = 6, hence x 4th line - permissive. Permissive element "1/2". Swapping variables x 2 and x 4 . We perform the step SHMZhI, we build the table. 4, we get a new reference plan = (9; 6; 51; 0; 0; 5).

6. Checking the basic plan for optimality

IN F-line, all coefficients are non-negative, therefore, the reference plan is optimal. Geometrically corresponds to a point D(9;6) (see Fig. 1). The optimal plan gives the maximum value of the objective function c.u.

Find the largest value of a function

x 1 ≥ 0 x 2 ≥ 0

1. The free members of the system must be non-negative.

This condition has been met.

2. Each constraint of the system must be an equation.

x 1 + x 1 x 1 x2

			2	x2	≤	4
			-		x2	≥	1
			+		≤	8

x 1 + S1 x 1 x 1 x2 S3

			2	x2	+								=	4
			-		x2				-		S2				=	1
			+								+		=	8

S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. The introduced variables S 1 , S 2 , S 3 are called balance variables.

3. Finding the initial basis and the value of the function F, which corresponds to the found initial basis.

What is a basis?
A variable is called basic for a given equation if it enters the given equation with factor one and is not included in the remaining equations of the system (provided that there is a non-negative number on the right side of the equation).
If every equation has a basis variable, then the system is said to have a basis.
Variables that are not basic are called free variables.

What is the idea behind the simplex method?
Each basis corresponds to a single value of the function. One of them is highest value F functions.
We will move from one basis to another.
The next basis will be chosen in such a way as to obtain the value of the function F not less than the existing one.
Obviously, the number of possible bases for any problem is not very large.
Therefore, sooner or later, the answer will be received.

How is the transition from one basis to another carried out?
It is more convenient to record the solution in the form of tables. Each row of the table is equivalent to the equation of the system. The highlighted line consists of the coefficients of the function (see the table below). This allows you not to rewrite variables every time, which saves a lot of time.
In the selected line, select the largest positive coefficient (you can choose any positive one).
This is necessary in order to obtain the value of the function F not less than the existing one.
Column selected.
For positive coefficients of the selected column, we calculate the ratio Θ and choose the smallest value.
This is necessary so that after the transformation the column of free terms remains non-negative.
Row selected.
The element that will be the base element is defined. Next, we count.

Does our system have a basis?

x 1 + x 1 x 1 x2

2

x2

+

S1

=

4

-

x2

-

S2

=

1

+

+

S3

=

8

There is no basis, i.e. we can't start a solution.
Will have to find him. To do this, we solve an auxiliary problem.
Let's add an artificial variable to the equation where there is no base variable.

x 1 + x 1 x 1 x2

2

x2

+

S1

=

4

-

x2

-

S2

+

R1

=

1

+

+

S3

=

8

R 1 ≥ 0. The introduced variable R 1 is called an artificial variable.

We introduce the function W into consideration and look for its smallest value.

The algorithm for finding the smallest value of the function W has only one difference from the algorithm discussed above.

x 1	x2	S1	S2	S3	R1	St. member	Θ
1	2	1	0	0	0	4	4: 1 = 4
1	-1	0	-1	0	1	1	1: 1 = 1
1	1	0	0	1	0	8	8: 1 = 8
-1	1	0	1	0	0	W - 1
0	3	1	1	0	-1	3
1	-1	0	-1	0	1	1
0	2	0	1	1	-1	7
0	0	0	0	0	1	W - 0

We equate the free variables to zero. Verbally find the values ​​of the basic variables. (see table)
The function W is expressed in terms of free variables. Therefore, the value of the function W, for a given basis, can be found instantly. (see highlighted line of the table)

x 2 = 0 S 2 = 0 R 1 = 0 x 1 = 1 S 1 = 3 S 3 = 7

=> W - 0 = 0 => W = 0

Among the coefficients of the selected line, there are no negative ones. Therefore, the smallest value of the function W is found.
A basis is obtained without using an artificial variable. Which is what was required.
The column corresponding to the artificial variable can be crossed out.
As a result, our system looks like this:

S2 S2

3

x2

+

S1

+

=

3

x 1

-

x2

-

S2

=

1

2

x2

+

+

S3

=

7

F

=

-

x 1

+

3

x2

F = - ( 1 + x2 + S2 ) + 3 x2

= -1 + 2 x2 - S2