Simplex method artificial basis. Solving linear programming problems using the artificial basis method
When the condition contains restrictions such as equality. Let's consider the problem:
max(F(x)=∑c i x i |∑a ji x i =b j , j=1,m ; x i ≥0).
The so-called “artificial variables” R j are introduced into the constraints and into the goal function as follows:
∑a ji x+R j =b j , j=1,m ;F(x)=∑c i x i -M∑R j
When introducing artificial variables in a method artificial basis they are assigned a sufficiently large coefficient M to the goal function, which has the meaning of a penalty for introducing artificial variables. In the case of minimization, artificial variables are added to the goal function with a coefficient M. The introduction of artificial variables is permissible if, in the process of solving the problem, they successively vanish.
A simplex table, which is compiled during the solution process using the artificial basis method, is called extended.
It differs from the usual one in that it contains two lines for the goal function: one for the component F = ∑c i x i , and the other for the component M ∑R j Let's consider the procedure for solving the problem using a specific example.
Example 1. Find the maximum of the function F(x) = -x 1 + 2x 2 - x 3 under the restrictions:
2x 1 +3x 2 +x 3 =3,
x 1 ≥0, x 2 ≥0, x 3 ≥0.
Let's use the artificial basis method. Let's introduce artificial variables into the problem constraints
2x 1 + 3x 2 + x 3 + R 1 = 3;
x 1 + 3x 3 + R 2 = 2 ;
Objective function F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).
Let us express the sum R 1 + R 2 from the system of restrictions: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3 , then F(x) = -x 1 + 2x 2 - x 3 - M(5 - 3x 1 - 3x 2 - 4x 3) . When compiling the first simplex table (Table 1), we will assume that the original variables x 1 , x 2 , x 3 are non-basic, and the introduced artificial variables are basic. In maximization problems, the sign of the coefficients for non-basic variables in the F- and M-rows is reversed. The sign of the constant value in the M-line does not change. Optimization is carried out first along the M-line. Select leading column and row, all simplex transformations
The maximum negative coefficient in absolute value (-4) determines the leading column and the variable x 3, which will go into the basis. The minimum simplex ratio (2/3) corresponds to the second row of the table, therefore, the variable R 2 must be excluded from the basis. The leading element is outlined.
In the artificial basis method, artificial variables excluded from the basis are no longer returned to it, so the columns of elements of such variables are omitted. Table 2. decreased by 1 column. Carrying out a recalculation of this table, we move on to table. 3., in which the line M has been reset, it can be removed. After eliminating all artificial variables from the basis, we obtain the admissible basic solution of the original problem, which in the example under consideration is optimal:
x 1 =0; x 2 =7/9; F max =8/9.
If, when eliminating the M-string, the solution is not optimal, then the optimization procedure continues and is performed using the usual simplex method. Let's consider an example in which there are restrictions of all types: ≤,=,≥
Example 2. Find minimum value functions F(x) = 2x 1 + 3x 2 - x 3 under the following restrictions
2x 1 +x 2 -3x 3 ≥6,
x 1 -x 2 +2x 3 =4,
x 1 +x 2 +x 3 ≤5,
2x 1 +3x 2 +x 3 =3,
Let's multiply the first of the restrictions by (-1) and introduce into the restrictions additional variables x 4, x 5 and an artificial variable R as follows:
2x 1 -x 2 +3x 3 +x 4 =-6,
x 1 -x 2 +2x 3 +R=4,
x 1 +x 2 +x 3 +x 5 =5,
Let x 4, R and x 5 be basic variables, and x 1, x 2, x 3 – non-basic. Objective function F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).
In the first (Table 4), the coefficients for non-basic variables in the F-row and M-rows do not change sign, since the function is being minimized. The free term in the artificial basis method in the M-row is taken with the opposite sign. The solution corresponding to table. 4 is not valid because there is a negative dummy term.
Let's select the leading column and row in accordance with step 2 of the solution algorithm. After recalculation we get table. 5. Optimization of the solution in the artificial basis method (step 5 of the algorithm) is carried out first along the M-line. As a result, we introduce x 3 into the basis, and exclude the variable R from consideration, reducing the number of columns. After recalculation we get table. 6, which corresponds to the optimal solution to the problem.
Table 4
| basic variables | Free members | Non-basic variables | ||
| x 1 | x 2 | x 3 | ||
| x 4 | -6 | -2 | -1 | 3 |
| R | 4 | 1 | -1 | 2 |
| x 5 | 5 | 1 | 1 | 1 |
| F | 0 | 2 | 3 | -1 |
| M | -4 | -1 | 1 | -2 |
Table 5
| basic variables | Free members | Non-basic variables | ||
| x 4 | x 2 | x 3 | ||
| x 1 | 3 | -1/2 | 1/2 | -3/2 |
| R | 1 | 1/2 | -3/2 | 7/2 |
| x 5 | 2 | 1/2 | 1/2 | 5/2 |
| F | -6 | 1 | 2 | 2 |
| M | -1 | -1/2 | 3/2 | -7/2 |
Table 6
The required minimum of the function F(x) is equal to the free term of the F-row of the table. 6, taken with the opposite sign, since min F(x) = -max(-F(x)); x 4 = x 2 = 0;
x 1 =24/7; x 3 =2/7; x 5 =9/7; F min =46/7;
The artificial basis method algorithm has the following features:
1. Due to the fact that the initial reference solution of the extended problem contains artificial variables included in target function with coefficient - M(in a maximum task) or + M(in the minimum problem), estimates of expansions of vectors of conditions consist of two terms and 
, one of which does not depend on M, and the other 
depends on M. Because M arbitrarily large compared to unity ( M>> 1), then at the first stage of calculation to find the vectors introduced into the basis, only the terms of the estimates are used 
.
2. Vectors corresponding to artificial variables that are derived from the basis of the reference solution are excluded from consideration.
3. After all vectors corresponding to artificial variables are excluded from the basis, the calculation continues as usual simplex method using estimates independent of M.
4. The transition from solving the extended problem to solving the original problem is made using theorems 4.1-4.3 proven above.
Example 4.4. Solve a problem linear programming artificial basis method
.
Solution. Let's create an extended task. We introduce non-negative artificial variables with a coefficient (always) +1 into the left-hand sides of the equations of the system of constraints. It is convenient to write the introduced artificial variables to the right of the equations. In the first equation we enter , in the second - . This problem is a problem of finding the maximum, therefore they are introduced into the objective function with a coefficient - M. We get
The problem has an initial reference solution 
with unit basis 
.
We calculate estimates of the condition vectors based on the reference solution and the value of the objective function on the reference solution.
. 
.
We record the source data in a simplex table (Table 4.6).
Table 4.6
At the same time, estimates and 
for convenience of calculations, we write in two lines: in the first - terms that do not depend on M, in the second - the terms 
, depending on M. Values 
convenient to indicate without M, keeping in mind, however, that it is present there.
The initial support solution is not optimal, since the maximum problem has negative estimates. We select the number of the vector entered into the basis of the reference solution, and the number of the vector derived from the basis. To do this, we calculate the increments of the objective function when introducing each of the vectors with a negative estimate into the basis and find the maximum of this increment. In this case, the terms of the estimates (without M) is neglected as long as at least one term 
(With M) will not be different from zero. In this regard, the line with the terms of the estimates may not be in the table as long as the line is present 
. We find at k= 3.
In the third column " ", we select coefficient 1 in the second row as the resolving element and perform the Jordan transformation.
The vector derived from the basis is excluded from consideration (crossed out). We obtain the reference solution 
with basis 
(Table 4.7). The solution is not optimal because there is a negative estimate 
= —
1.
Table 4.7
In the " " column we take the only positive element as resolving and move on to a new reference solution 
with basis 
(Table 4.8).
Table 4.8
This reference solution is the only optimal solution to the extended problem, since in the maximum problem the estimates for all vectors not included in the basis are positive. By Theorem 4.1 original problem also has optimal solution, which is obtained from the optimal solution of the extended problem by discarding zero artificial variables, i.e. X* = (0,0,6,2).
Answer:max Z(X) = -10 at 
.
Example 4.5. Solve a linear programming problem with mixed constraints using the artificial basis method
Solution. We reduce the linear programming problem to canonical form. To do this, we introduce additional variables into the first and third constraints, respectively. We get
.
We create an extended problem, for which we introduce artificial variables into the second and third equations, respectively. We get
This extended problem has an initial support solution
With unit basis 
, 
. We calculate estimates of the condition vectors based on the reference solution and write them in the simplex table in the same way as in the previous example. The solution is not optimal, since in the minimum problem the vectors and have positive estimates. Improving support solutions. Each reference solution has its own table. All tables can be written one below the other, combining them into a single table (Table 4.9).
Table 4.9
We determine which of the vectors or into the basis of the initial support solution will lead to greater reduction target function. We find at k= 2, i.e. it is better to introduce the vector into the basis. We obtain the second support solution with the basis 
. Objective function 
. This solution is also not optimal, since the vector has a positive value 
. We introduce the vector into the basis, we obtain the third reference solution with the basis 
. Objective function 
. This solution is optimal, but not the only one, since the vector not included in the basis has a zero estimate. Therefore, it is necessary to move to a new reference solution, which will also be optimal. To do this, you need to introduce the vector into the basis.
Let's move on to the fourth reference (optimal) solution
With basis 
, wherein 
. Optimal solutions to the extended problem have zero artificial variables. Therefore (by Theorem 4.1) the original problem also has two optimal solutions 
And 
. We do not write additional variables in the optimal solution of the original problem.
Answer: 
at 
, 
, 
, 
.
The word simplex
The word simplex in English letters (translit) - simpleks
The word simplex consists of 8 letters: e and k l m p s s
Meanings of the word simplex. What is simplex?
Simplex
Simplex (from Latin simplex - simple) (mathematical), the simplest convex polyhedron given number dimensions n. When n = 3, the three-dimensional structure is an arbitrary, including irregular, tetrahedron.
TSB. - 1969-1978
A simplex is a convex polygon in n-dimensional space with n+1 vertices that do not lie in the same hyperplane. S. highlighted in separate class because in n-dimensional space n points always lie in the same hyperplane.
slovar-lopatnikov.ru
SIMPLEX is a convex polygon in n-dimensional space with n+1 vertices that do not lie in the same hyperplane. S. are singled out as a separate class because in n-dimensional space n points always lie in the same hyperplane.
Lopatnikov. - 2003
Sub simplex
Sub simplex Directions for use and dosage: Orally, during or after meals and, if necessary, before bedtime. Shake the bottle vigorously before use.
Solving the ZLP by the simplex method with an artificial basis
For the suspension to start flowing from the pipette...
Sub simplex Active ingredient ›› Simethicone* (Simethicone*) Latin name Sab simplex ATX:›› A02DA Carminative drugs Pharmacological group…
Dictionary of medicines. — 2005
SAB® SIMPLEX (SAB® SIMPLEX) Oral suspension from white to gray-white, slightly viscous, with a characteristic fruity (vanilla-raspberry) odor. 100 ml simethicone 6.919 g…
SHOCKE SIMPLEX
CHOQUET SIMPLEX is a non-empty compact convex set X in a locally convex space E, which has the following property: when E is embedded as a hyperplane in the space, there is a projecting cone.
Sheffield Simplex
"Sheffield-Simplex" - light machine-gun armored vehicle Armed Forces Russian Empire. Developed by the British company Sheffield-Simplex based on the chassis of its own passenger car...
en.wikipedia.org
Norditropin Simplex
Norditropin Simplex Indications: Growth retardation in children due to growth hormone deficiency or chronic renal failure (in prepubertal age), Shereshevsky-Turner syndrome...
NORDITROPIN® SIMPLEX® (NORDITROPIN SimpleXx) Solution for subcutaneous administration 1.5 ml (1 cartridge) somatropin 10 mg 1.5 ml - cartridges (1) - contour cell packaging (1) - cardboard packs.
Directory of medicines "Vidal"
STANDARD SIMPLEX
STANDARD SIMPLEX - 1) S. s. - a simplex of dimension n in space with vertices at points e i=(0,..., 1,..., 0), i=0,..., n (the unit is on i-th place), i.e.
Mathematical encyclopedia. — 1977-1985
Dual simplex method
The dual simplex method can be used to solve a linear programming problem, the free terms of the system of equations of which can be any numbers. In normal simplex algorithm the plan must always be valid.
en.wikipedia.org
Russian language
Simplex/.
Morphemic-spelling dictionary. - 2002
Search Lectures
An example of solving a problem using the artificial basis method.
Find the minimum of a function F=-2×1+3×2 – 6×3 – x4 under conditions
Solution. Let's write it down this task in the form of the main problem: find the maximum of the function F1=2×1 – 3×2 + 6×3 + x4 under conditions
In the system of equations of the last problem, consider the vectors of the coefficients for the unknowns:
A1= A2= A 3= A 4= A 5= A 6=
Among the vectors A1,…, A 6 only two single ones ( A 4 and A 5). Therefore, we add an additional non-negative variable to the left side of the third equation of the system of restrictions x 7 and consider the extended problem of maximizing the function
F=2×1 – 3×2 + 6×3 + x4 – Mx7
under conditions
The extended problem has a reference plan X=(0; 0; 0; 24; 22; 0; 10), defined by a system of three unit vectors: A 4 , A5 , A7 .
Table 1
| i | Basis | Сσ | A0 | -3 | —M | |
| A1 | A2 | A3 | A4 | A5 | A6 | P7 |
| A4 | -2 | |||||
| A5 | ||||||
| A7 | —M | -1 | -1 | |||
| m+1 | -8 | |||||
| m+2 | -10 | -1 | -2 |
We compile table (1) of iteration I, containing five rows. To fill in the 4th and 5th lines we find F 0 and difference values zj – cj(j=):
F 0 = 24–10M;
z1–c1= 0–M;
z2–c2 = 4+M;
z3–c3= –8–2M;
z4–c4=0+M;
z5–c5=0+M;
z6–c6= 0+M;
z7–c7=0+M;
Values F 0 and zj–cj consist of two terms, one of which contains M, and the other is not.
For the convenience of the iterative process, the number consisting of M, write in the 5th line, and the term that does not contain M, – in the 4th line.
In the 5th line of table 1 in the columns of vectors Аj (j= ) there are two negative numbers (-1 And -2). The presence of these numbers indicates that this reference plan for the extended problem is not optimal. Let's move on to the new reference plan of the extended problem.
Artificial basis method.
We introduce the vector into the basis A3. To determine the vector excluded from the basis, we find θ=min(22/4; 10/2)=10/2. Therefore, the vector A7 excluded from the basis. It makes no sense to enter this vector into any of the subsequent bases, so in the future the column of this vector is not filled in (Tables 2 and 3).
We compose table II of iteration (Table 2). It contains only four rows, since the artificial vector is excluded from the basis.
Table 2
| i | Basis | Сσ | A0 | -3 | |
| A1 | A2 | A3 | A4 | A5 | A6 |
| A4 | -1 | ||||
| A5 | -1 | ||||
| A3 | 1/2 | -1/2 | -1/2 | ||
| m+1 | -4 |
As can be seen from table. 2, for the original problem the reference is the plan X=(0;0;5;34;2).
Let's check it for optimality. To do this, consider the elements of the 4th line. In this row in the vector column A6 available a negative number(-4). Consequently, this reference plan is not optimal and can be improved by introducing the vector A6. The vector is excluded from the basis A5. We compile table III of iteration.
Table 3
In the 4th line of table 3 among the numbers ∆j no negative ones. This means that the found new reference plan of the original problem X*=(0; 0; 11/2; 35; 0; 1) is optimal. In this case, the value linear shapeFmax = 68.
The solution to this problem can be carried out using one table in which all iterations are sequentially recorded.
©2015-2018 poisk-ru.ru
All rights belong to their authors. This site does not claim authorship, but provides free use.
Copyright Infringement and Personal Data Violation
Until now, we have comprehensively considered the problem, the solution of which was carried out on the basis of the simplest algorithm of the simplex method, since all the constraints were of the form less than or equal to. In this case, the additional variables of the problem form a unit basis. But it may turn out that the system of restrictions is presented in canonical form, but it is not reduced to a unit basis.
When solving such problems, it was introduced artificial basis method. It is especially convenient when the number of variables significantly exceeds the number of equations.
Let's consider the algorithm for solving the problem using the simplex method with an artificial basis using an example.
Example 1
Find the maximum Z=4X1+2X2+X3
3Х1+2Х2+Х3=15
Хj³0, j=1,...,3
Let's move on to the canonical form:
X1+X2+X3-X4=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3=15
Хj³0, j=1,...,5
Zmax=4X1+2X2+X3+0×X4+0×X5
This system restrictions does not have a unit basis, since the additional variable X4 has a coefficient of minus one, and the third constraint was represented by an equation and does not have a basis variable. In order to have a unit basis, we introduce into the corresponding restrictions artificial variables y1 and y2 with positive coefficients (+1).
It should be noted that artificial variables are introduced only for the mathematical formalization of the problem. Therefore, the calculation scheme must be such that artificial variables cannot be included in the final solution among the basic variables. For this purpose, for artificial variables in the objective function, a coefficient M is introduced, denoting a very big number. In practice (especially when solving a problem on a computer), instead of M, they take a specific large number, for example, 10000. Moreover, when solving a problem to the maximum, this coefficient is entered into the objective function with a minus sign, and when solving to a minimum, with a plus sign. Now we will solve the T (M)-problem, the objective function of which contains the objective function of the Z-task and artificial variables with a coefficient ±M, i.e.
T=Z-M S yi, when solving for the maximum of the objective function and
T=Z+M S y, when solving for the minimum of the objective function
In our case:
X1+X2+X3-X4+y1=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3+y2=15
Хj³0, j=1,...,5
Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)
This problem is solved in simplex tables, but for convenience the objective function is divided into 2 lines:
In the first line we write down estimates that do not contain the coefficient M;
The second line contains estimates for each free variable, containing the coefficient M.
The calculation of the elements (scores) of these two lines is carried out according to formula (2). Only difference:
When calculating Z-row estimates, the coefficients Cj included in the Z function must be taken into account;
When calculating M-line estimates, this coefficient is not taken into account, and M is taken out as a common factor.
In order for the T-task and the Z-task to be equal, it is necessary that yi be equal to zero. Therefore, as long as y i is not zero, the resolving column is selected based on the estimates in the second row using the simplex method algorithm.
Only after all y i become equal to zero, further calculation will be carried out using the first index line, i.e. -regular Z-task.
Moreover, when the artificial variable is derived from the basis, we will throw it out of the simplex table, and the next simplex table will not have the former resolving column.
There is a connection between the optimal solutions of the M-problem and the Z-problem, established by the following theorem:
1. If in the optimal solution to the M-problem all artificial variables (y i) are equal to zero, then this solution will be the optimal solution to the Z-problem.
2. If in the optimal solution of the M-problem at least one of the artificial variables is different from zero, then the Z-problem has no solution due to the incompatibility of the system of constraints.
3. If the M-problem turns out to be unsolvable (T®+¥ or -¥), then the original problem is also unsolvable either because of the incompatibility of the system of constraints or because the function Z is unbounded.
Let's create the first simplex table. When solving using the M-method, the resolving column in the M-row can be selected not according to the largest negative estimate in absolute value (when solving for the maximum) and not according to the largest positive estimate (when solving for the minimum), but according to the one that displays Y faster from the basis. IN in this example the resolving column will be the column of the free variable X2 with a score of (-3).
Table 3.1.
First simplex table
Filling the Z-line is carried out according to formula (2):
a00 = 0 × 8– 0 = 0
a01 =0 × 2– 4 = -4
a02 =0 × 1– 2 = -2
a03 =0 × 1– 1 = -1
а02 =0 × 0– 0 = 0
Filling out the M-line:
а¢00 = -М × 8 + (–М) × 15 = -23М
a¢01 = -M × 1 + (–M) × 3 = -4M
а¢02 = -М × 1 + (–М) × 2= -3М
а¢03 = -М × 1+ (–М) × 1 = -2М
а¢04 = -М ×(-1)+ (–М) × 0 = 1М
We take out M as a common factor.
The last column in the resolution line contains 0, so the column of the free variable X4 is transferred without changes.
Table 3.2.
Second simplex table
In the second table we obtain a degenerate solution, since we obtain two identical minimal simplex relations. Therefore, we find the relationship of the elements of the column next to the resolving one to the elements of the resolving column, taking into account the sign.
Table 3.3.
Third simplex table
Now we solve using the usual simplex method.
Table 3.4.
Fourth simplex table
| St.P | Cj | |||
| B.P. | Ci | ai0 | X5 | X4 |
| X3 | -1 | |||
| X1 | ||||
| X2 | -2 | -1 | ||
| Z |
In the evaluation line, all elements are non-negative values, therefore the optimal solution is obtained:
Zmax=15 Xopt(0,7,1,0,0)
Example2
The problem was solved to the minimum (Z®min) of the objective function. At the last iteration we got the following table:
Table 3.5.
Latest simplex table
| St.P | Cj | ||||
| B.P. | Ci | ai0 | X1 | X3 | X4 |
| U1 | M | -1/2 | -1/2 | -1/2 | -1 |
| X5 | 1/2 | 1/2 | 1/2 | ||
| X2 | 15/2 | 3/2 | 1/2 | ||
| Z | -1 | ||||
| M | -1/2 | -1/2 | -1/2 | -1 |
In the T-problem, an optimal solution was obtained, since there are no more positive estimates in the M-row, i.e. the choice of a resolving column is impossible, and U1 is in the basis. In this case, the original problem has no solution due to incompatibility of the system of restrictions.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Warning
Clear all cells?
Close Clear
Data entry instructions. Numbers are entered as integers (examples: 487, 5, -7623, etc.), decimals (ex. 67., 102.54, etc.) or fractions. The fraction must be entered in the form a/b, where a and b (b>0) are integers or decimal numbers. Examples 45/5, 6.6/76.4, -7/6.7, etc.
Simplex method
Examples of solving ZLP using the simplex method
Example 1. Solve the following linear programming problem:
 |
The right side of the constraints of the system of equations has the form:
Let's write down the current reference plan:
 |
This reference plan is not optimal, since last line there are negative elements. The largest negative element in modulus is (-3), therefore the vector is included in the basis x 
at 
. min(40:6, 28:2)=20/3 corresponds to line 1. The vector emerges from the basis x 3. Let's do Gaussian elimination for the column x 2, given that the leading element corresponds to row 1. Let's reset all elements of this column except the leading element. To do this, add the lines of line 2, 3, 4 with line 1, multiplied by -1/3, 1/6, 1/2, respectively. Next, we divide the line with the leading element by the leading element.
This reference plan is not optimal, since the last row has a negative element (-3), therefore the basis includes the vector x 1 . We determine which vector comes out of the basis. To do this, we calculate 
at 
. min(44/3:11/3, 62/3:5/3)=4 corresponds to line 2. The vector emerges from the basis x 4 . Let's do Gaussian elimination for the column x 1, given that the leading element corresponds to row 2. Let's reset all elements of this column except the leading element. To do this, add lines 1, 3, 4 with line 2 multiplied by 1/11, -5/11, 9/11, respectively. Next, we divide the line with the leading element by the leading element.
The simplex table will take the following form:
The current reference plan is optimal, since in lines 4 under the variables 
there are no negative elements.
The solution can be written like this: 
.
The value of the objective function at this point: F(X)=
.
Example 2. Find the maximum of a function
Solution.
Basis vectors x 4 , x 3 therefore all elements in columns x 4 , x 3, below horizontal line must be zero.
Reset all column elements to zero x 4, except for the leading element. To do this, add row 3 with row 1 multiplied by 4. Reset all elements of the column to zero x 3, except for the leading element. To do this, add line 3 with line 2 multiplied by 1.
The simplex table will take the form:
This reference plan is not optimal, since the last row has a negative element (-11), therefore the basis includes the vector x 2. We determine which vector comes out of the basis. To do this, we calculate 
at 
. Therefore, the objective function is unbounded from above. Those. the linear programming problem is unsolvable.
Examples of solving ZLP using the artificial basis method
Example 1. Find the maximum of a function
Solution. Since the number of basis vectors must be 3, we add an artificial variable, and to the objective function we add this variable multiplied by −M, where M is a very large number:
 |
The coefficient matrix of the system of equations has the form:
Basis vectors therefore all elements in the columns below the horizontal line must be zero.
Let's reset all elements of the column except the leading element. To do this, add line 5 with line 3 multiplied by -1.
The simplex table will take the form:
This reference plan is not optimal because there are negative elements in the last row. The largest absolute negative element is (-5), therefore the vector is included in the basis. We determine which vector comes out of the basis. To do this, we calculate 
at 
corresponds to row 3. A vector emerges from the basis. Let's make a Gaussian exception for the column, given that the leading element corresponds to row 3. Let's reset all elements of this column, except the leading element. To do this, add the lines line 5 with line 3 multiplied by 1. Next, divide the line with the leading element by the leading element.
The simplex table will take the following form:
This reference plan is not optimal because there are negative elements in the last row. The largest absolute negative element is (-3), therefore the vector is included in the basis. We determine which vector comes out of the basis. To do this, we calculate 
at 
corresponds to row 1. The vector emerges from the basis x 2. Let's do Gaussian elimination for the column x 1 , given that the leading element corresponds to row 1. Let's reset all elements of this column except the leading element. To do this, add lines 2, 3, 4 with line 1, multiplied by 3/2, -1/10, 3/2, respectively. Next, we divide the line with the leading element by the leading element.
The simplex table will take the following form:
This reference plan is not optimal because there are negative elements in the last row. The largest negative element in modulus (-13/2), therefore the basis includes the vector x 3. We determine which vector comes out of the basis. To do this, we calculate 
at 
corresponds to line 3. The vector emerges from the basis x 5 . Let's do Gaussian elimination for the column x 3, given that the leading element corresponds to row 3. Let's reset all elements of this column except the leading element. To do this, add the lines of line 1, 2, 4 with line 3, multiplied by 5/3, 25/9, 65/9, respectively. Next, we divide the line with the leading element by the leading element.
The simplex table will take the following form:
The current reference plan is optimal, since there are no negative elements under the variables in lines 4−5.
The solution to the original problem can be written as follows:
Example 2. Find optimal plan linear programming problems:
The coefficient matrix of the system of equations has the form:
Basis vectors x 4 , x 5 , x 6 therefore all elements in columns x 4 , x 5 , x 6, below the horizontal line should be zero.
Reset all column elements to zero x 4, except for the leading element. To do this, add line 4 with line 1 multiplied by -1. Reset all column elements to zero x 5, except for the leading element. To do this, add line 5 with line 2 multiplied by -1. Reset all column elements to zero x 6, except for the leading element. To do this, add line 5 with line 3 multiplied by -1.
The simplex table will take the form:
In line 5 the elements corresponding to the variables x 1 , x 2 , x 3 , x 4 , x 5 , x 6 are non-negative, and the number located at the intersection of a given row and column x 0 is negative. Then the original problem does not have reference plan. Therefore it is undecidable.