The model is called canonical. Canonical form of a linear programming problem
Analytical method for solving the problem linear programming is simplex method. To apply it, the LP problems presented in various ways, must be reduced to canonical form. The linear programming problem, written in the form (2.1.1)-(2.1.3), is an expanded form of notation common task linear programming (LPP).
We will call the following problem a canonical linear programming problem (CLPT):
under restrictions having the form of equalities,
If for a problem in the form (2.3.1)-(2.3.4) the condition is satisfied t = n, then its solution reduces to solving the system of equations
- (2.3.2) . In this case, the problem will have no solutions if the condition
- (2.3.3) is not satisfied or the system of equations has no solution.
condition T
- 1. To go from the maximization problem objective function (2.3.1) to minimization problem enough take all coefficients Cj objective function with reverse signs and solve the resulting problem to the maximum. After finding the maximum, the value of the objective function must be taken with the opposite sign. The optimal solution will remain the same.
- 2. To go from less than or equal to equality constraint it is necessary with a plus sign:
3. To go from a “greater than or equal to” constraint to equality it is necessary introduce an additional non-negative variable with a minus sign:
In this case, each inequality introduces its own (n +/)-th additional variable.
- 4. Everything equalities having negative free terms are divided into-1, in order for condition (2.3.4) to be satisfied.
- 5. If on some variable Xj the non-negativity condition is not imposed, That make a change of variables Xj=x".- X" x"j > 0, x"> 0. In the transformed problem all variables are non-negative.
There is a statement that any ZLP can be reduced to a canonical form.
Example 2.3.1. Let's transform the problem given in Example 2.2.2 into canonical form. The objective function and system of constraints look like this:
Let us introduce an additional variable jc 3 > 0 with a plus sign into the first inequality, and into the second x 4> 0 with a minus sign and in the third x 5> 0 also with a plus sign. As a result, we obtain a system of problem constraints in canonical form:
Given these restrictions, you need to find the maximum value of the function:
Let us consider the economic meaning of additional variables in the canonical problem of optimal use of resources.
Example 2.3.2. Optimal resource utilization problem (carpet problem)[17 J.
The factory has at its disposal a certain amount of resources of three types: labor (80 man-days), raw materials (480 kg) and equipment (130 machine hours). The factory can produce four types of carpets. Information on the number of units of each resource required to produce one carpet of each type, and on the income received by the enterprise from a unit of each type of product is given in Table. 2.3.1.
It is required to find a production plan at which its total cost will be maximum.
Economic and mathematical model of the problem Variables: x x, x 2, x 3, x 4 - number of carpets of each type. Objective function - is the total cost of production that needs to be maximized:
Resource Limits:
Let us bring the problem to canonical form by introducing additional variables x 5, x 6 And x 7:
It will be shown below that the optimal production plan is the vector X* =(0; 30; 10; 0), the value of the objective function is 150, i.e. To maximize the total cost of production, it is necessary to produce 30 carpets of the second type and 10 carpets of the third type. Let's substitute optimal values vector X in the restrictions of the KZLP:
We obtain that the resources “labor” and “equipment” are fully used, the resource “raw materials” is available in abundance:
In this case x in shows that there are 200 kg of raw materials left.
So the main variables x v x 2, x 3, x l mean the number of carpets of each type, and additional variables x 5, x 6 their 7 - volume of underutilized resources.
Answer. Optimal production plan X* = (0; 30;
10; 0).
Plan, or acceptable solution, KZLP is called a vector X =(jc p X 2 ,..., x n), satisfying conditions (2.3.2)-(2.3.4).
If all components of the basic solution of the system of CLLP constraints are non-negative, then such a solution is called reference solution or reference plan. The number of positive components of the reference plan cannot exceed T.
The reference plan is called non-degenerate, if it contains T positive components, otherwise it is called degenerate.
Optimal plan or optimal solution The PLP is the plan that delivers the greatest (smallest) value linear function (2.3.1).
The set of all plans of the PAP (if they exist) is convex polyhedron. Each corner (extreme) point of the solution polyhedron corresponds to reference plan(non-negative basic solutions of the KZLP system of equations). Each reference plan is determined by the system T linearly independent vectors contained in a given system of P vectors D, D,..., A p. If there is an optimal plan, then there is a corner point of the decision polyhedron at which the linear function reaches its greatest (smallest) value.
To find the optimal plan, it is enough to examine only the reference plans. The upper limit on the number of reference plans contained in a problem is determined by the number of combinations S t p (see paragraph 1.4).
Example 2.3.3. Get a solution to the problem about optimal use limited resources (solve AP P):
Solution. Let's reduce the problem to canonical form by introducing additional variables x 3, x 4 and x 5:
Let's find all the supporting plans of the system of restrictions of this KZLP (l? - 5; /77 - 3); their number does not exceed 10:
Using the Jordan-Gauss method (see paragraph 1.4), we write out all the basic solutions of the system of equations (Table 2.3.2).
|
Number basis nogo solutions |
Basis |
Plan |
|||||
Among ten basic solutions five support:
The indicated reference plans in Fig. 2.3.1 correspond respectively to the following corner points and the values of the CF in them:
Rice. 2.3.1.
According to theory LP optimal solution contained among the reference plans.
Thus, the maximum value equal to 2300 is reached by the objective function at the point IN on the reference plan X 5 = (70; 80; 0; 60; 0).
Answer. Optimal task plan: x ( = 70, x 2 = 80, objective function value f(x v x 2) = 2300.
MP tasks
General ZLP is called <,=,>=)bi (i=1,n) (2) provided xj>
Symmetrical < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Canonical mixed.
min f(x) = -max(-f(x))
<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>
Geometric interpretation of the objective function and constraints of the ZLP. Geometric formulation of the ZLP.
Let the problem f=c1x1+c2x2-max (1) be given
a11x1+a12x2<=b1 }
am1x1+am2x2<=bm}
x1>=0, x2>=0 (3)
The plan of the problem (x1,x2) is a point on the plane. Each inequality with-we 2 representations. is a half-plane. A half-plane is a convex set. Convex is called a set in which the points of the segment connecting (x1 and x2) belonging to this set also belong to the set. C-ma 2 represents the intersection of half-planes. When crossing you can get:
1) convex polygonal closed area.
2) convex open polygonal area
3) single point
4) empty set
5) ray and segment
Geometric interpretation of the objective function: Function 1 is a family of parallel straight lines, which are called level lines (lines of constant value of the objective function). The partial derivatives of the function with respect to x1 and x2 show the rate of increase of the objective function along the coordinates of the axes. Gradient vector shows the direction of the fastest increase in the objective function. For problem 1-3, the gradient vector = (c1; c2) leaves the point (0,0) and is directed to the point with coordinates (c1; c2). The gradient vector is perpendicular to the level lines. The intersection of half-planes is usually called area of admissible solutions (ADD).
The main theorem of LP. Schematic diagram solution of the ZLP, which follows from this theorem.
If the ZLP has a solution, then the objective function reaches an extreme value at at least one of the extreme points of the plan polyhedron. If the objective function reaches an extreme value at more than one extreme point, then it reaches one and the same value, which is a convex linear combination of them, at any point. At decision of the PPP It is convenient to use a table entry manually.
| BP | SP -Xm+1 -Xm+2 -Xn | |
| x1 | b1o | b11 b12 b1n-m |
| x2 | b2o | b21 b22 b2n-m |
| xm | bm | bm1 bm2 bmn-m |
| f | boo | bo1 bo2 bon-m |
Algorithm of the simplex method.
1. bring the problem model to canonical form;
2. find the initial reference plan;
3. write the problem in simple. table;
5. move to a new reference plan, to a new symp. table. In order to move to a new reference plan, it is enough to replace one basic variable with a free one. The variable included in the basis and the corresponding resolution column are determined by the largest absolute negative element of the f-row. The variable that excludes from the basis and the corresponding resolving line are determined by the smallest simplex ratio, i.e. the relationship of the elements of the unit column to the corresponding element of the resolution column. The simplex ratio is a non-negative quantity. At the intersection of the resolving row and the resolving column there is a resolving element, with respect to which the simplex transformation is performed in the following way. rule: 1. the elements of the allowing string are divided into the allowing element; 2. the elements of the resolution column are divided into the resolution element and change their sign to the opposite; 3. the remaining elements of the table are re-arranged according to the rectangle rule:
bij bis bkj=(bkj*bis-bij*bks)/bi
The second duality theorem.
if one of the dual problems has an optimal plan, then the other is also solvable, i.e. has an optical plan. In this case, the extreme values of the objective functions coincide (j=from 1 to n) Σcjxj*= (i=from 1 to m)Σbiyi* if in the original. problem, the objective function is unlimited on the set of plans, then in dual problem the system of restrictions is inconsistent.
Theorem on the rank of the TK matrix.
The rank of matrix A of the transport problem is one less than the number of equations: r(A)=m+n-1.
39. Algorithm for constructing the initial reference plan of the ZLP.
To find the initial reference plan, we can suggest the following algorithm:
1. write the problem in the form of a Jordan table so that all elements of the column of free terms are non-negative, i.e. the inequality aio>=0 (i=1,m) was satisfied. Those equations in which the free terms are negative are first multiplied by -1.
| -x1….. -xn | ||
| 0= | a1o | a11…. a1n |
| ….. | ….. | ……………………….. |
| 0= | amo | am1…..amn |
| f= | -c1…. -cn |
Transform the table using Jordan elimination steps, replacing the zeros in the left column with the corresponding x. At the same time, at every step permissive can be selected any column containing at least one positive element. The resolving row is determined by the smallest of the ratios of the free terms to the corresponding positive elements of the resolving column. If, in the process of elimination, a 0-row is encountered, all of whose elements are zero, and the free term is nonzero, then the system of constraint equations has no solutions. If we encounter a 0-row in which, apart from the free term, there are no other positive elements, then the set of restrictive equations does not have non-negative solutions. If the set of restrictive equations joint, then after a certain number of steps all the zeros in the left column will be replaced by x and thereby obtain a certain basis, and, consequently, a corresponding support plan.
40. Algorithm for constructing the optimal reference plan of the ZLP.
Ho's initial support plan is examined for optimality.
If there are no negative elements in the f-row (not counting the free term), the -plan is optimal. If there are also no zero elements in the f-row, then there is only one optimal plan; if among the elements there is at least one zero, then there is an infinite number of optimal plans. If there is at least one negative element in the f-row, and there are no positive elements in the corresponding column, then the objective function is not limited in the feasible region. The problem is not solvable. If there is at least one negative element in the f-row, and in each column with such an element there is at least one positive element, then you can move to a new reference plan that is closer to the optimal one. To do this, the column with a negative element in the f-row is taken as permissive; They determine the resolving string from the minimum simplex relation and perform the Jordan elimination step. The resulting reference plan is again examined for optimality. This is repeated until the optimal reference plan is found or the unsolvability of the problem is established.
Algorithm of the Gomori method.
1. Using the simplex method, the optimal plan for the problem is found. If all components of an optimal plan are integers, then it is optimal. Otherwise, go to step 2
2. Among the non-integer components, you should choose the one with fraction is the largest and, using the corresponding row of the simplex table, formulate the correct cutoff using the formula
(n-m,s=1)∑ (αkm+1)Xm+1≥(βk)
3. Transform the formulated inequality into an equivalent zero equality and include it in simplex table with a non-integer optimal plan
4. The resulting extended problem is solved using the simplex method. If the resulting plan is not integer, proceed to step 2.
If during the solution process a line appears with a non-integer free term and other integer coefficients, then the corresponding equation does not have a solution in integers. In this case, and original problem undecidable in integers. Gomori's method has limited application. With its help, it is advisable to solve small problems, because... the number of interactions can be very large.
Various forms of notation of ZLP (general, canonical, symmetric)
MP tasks: determination of the optimal plan, determination of the optimal volume of output, determination of the optimal combination of crops, formation of the optimal package of assets, maximizing bank profits, etc.
General ZLP is called maximization (minimization) problem linear function f=Σcj*xj-max(min) (1) under linear restrictions ∑aij *xj(=<,=,>=)bi (i=1,n) (2) provided xj>=0(j=1,n1), xj-arbitrary (j=n1+1,n)(3) where cj,aij, bi-constants numbers.
Symmetrical The form of writing the ZLP is called the problem of maximizing function (1) under linear constraints in signed inequalities< либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком >or = and non-negative variables. Canonical the form for recording the PAP is called a task maximum function(1) under linear constraints of equalities and non-negative variables. Any other form is called mixed.
min f(x) = -max(-f(x))
The transformation of an inequality into an equation and vice versa is carried out on the basis of the Lemma: for every solution x1...xn of the inequality a1x1+...+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) and vice versa. Every solution x1…xn,xn+1 of equation 6 and inequality 7 corresponds to a solution x1…xn of inequality 5.
To move from the back sim form to the back canonical form, you must enter balance (equalizing) variables. This is based on the inequality theorem: any inequality can be represented as an equation or a simple inequality.
Linear programming problem of the form ax = b where a is the coefficient matrix, b is the constraint vector.
Example:
In each LP problem, values of variables are sought under the condition that:
- these values satisfied some system linear equations or inequalities;
- at these values, the objective function would turn to a minimum or maximum.
Instructions. Select the number of variables and the number of rows (number of constraints). The resulting solution is saved in a Word file.
One of universal methods LP is a simplex method, which, however, can be used if the LP problem has a canonical form.
Definition. The LP problem has a canonical form if all system constraints consist only of equations (except for inequalities expressing the non-negativity of variables) and the objective function must be minimized.
An example of such an LP problem in canonical form is Problem 1 – a balanced transport problem with a system of constraints (1) and target function (2).
However, in most economic tasks Most often, the system of constraints initially includes not only equations, but also inequalities.
Statement. Any general LP problem can be reduced to canonical form.
Reducing the general LP problem to canonical form is achieved by introducing new (they are called additional) variables.
The system of constraints (3) of this problem consists of four inequalities. By introducing additional variables y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0, y 4 ≥ 0, we can go to the system of restrictions: 
These additional variables y i have an absolutely clear economic meaning, namely, they mean the amount of unused work time (machine downtime i-th type).
For example, if machines of the first type worked for all 18 hours, then x + y = 18, therefore, y 1 = 0. But we allow for the possibility of incomplete use of the operating time of the first machine x + y<18. В этом случае y 1 takes on a positive value and can be considered as an unused time limit. For example, knowing the solution to this problem from paragraph 3.3.2, x = 12, y= 6, we can conclude from the system of restrictions (3.9) that y 1 = y 2 = y 3 = 0, and y 4 = 12 – 6 = 6. That is, machines of the first, second, third types use their working time completely. But the fourth machine is only half loaded, 6 hours, and, given the optimal plan, is idle. Perhaps, after such conclusions, the head of the enterprise will want to load it with other work, rent it out for this time, etc.
So, by introducing additional variables, we can reduce any inequality type constraint to an equation.
Let's consider the mixture problem. The system of restrictions has the form: 
The inequalities were turned towards “more”, therefore, introducing additional variables y 1, y 2, y 3 ≥ 0, they must be subtracted from the left side in order to equalize it with the right. We obtain a system of restrictions in canonical form:
The variables y i will also make economic sense. If you remember the practical content of the problem, then the variable y 1 will mean the amount of excess substance A in the mixture, y 2 will mean the amount of excess substance IN in the mixture y 3 – surplus WITH in the mixture.
The task of finding the maximum value of the objective function can be reduced to finding the minimum for the function - F due to the obviousness of the statement max F = –min (– F). Look at the picture: if at some point x= x 0 function y= F(x) reaches its maximum, then the function y= –F(x), symmetrical to it relative to the axis OX, at the same point x 0 will reach a minimum, and F max = – (– F min) at x = x 0 .
Conclusion. To represent the LP problem in canonical form it is necessary:
- transform the inequalities included in the system of constraints of the problem into equations by introducing additional variables;
- if the objective function F→max (maximizes), it is replaced by the function – F→ min (which is minimized).
canonical form, if you want to maximize the objective function, all the system constraints are equations and the non-negativity condition is imposed on all variables.
The linear programming problem is given in symmetrical shape, if it is required to maximize the objective function, all system restrictions are inequalities “” (or minimize the objective function, all system restrictions are inequalities “”) and the non-negativity condition is imposed on all variables.
A set of numbers is called acceptable solution (plan), if it satisfies the system of restrictions of the ZLP.
The set of all feasible solutions is called area of feasible solutions(ODR).
An admissible solution for which the maximum (minimum) value of the function is achieved is called optimal PAP plan.
The terms "plan" and "optimal plan" originate from economic applications.
All three forms of ZLP recording are equivalent in the sense that there are algorithms for transition from one form to another. Thus, if there is a way to solve a problem in one of the forms, then it is always possible to determine the optimal plan for a problem given in any other form. The problem in symmetric form is solved by the graphical method, and in canonical form by the simplex method.
Let's consider algorithms for transition from one form to another.
Symmetrical canonical. The transition is carried out by adding an additional non-negative variable to the left side of each inequality. If the inequality was “≤”, then the balance variable is added to the left side of the inequality with a “+” sign. If the inequality was “”, then the balance variable is added to the left side of the inequality with a “–” sign. The new variables introduced are called balance sheet. The problem of minimizing the function Z is replaced by the problem of maximizing the function (–Z) and it is used that min Z = –max (–Z).
Canonical symmetrical. To carry out such a transition, a general solution to the system of equations – constraints is found, the target function is expressed in terms of free variables. Next, taking advantage of the non-negativity of the basis variables, we can exclude them from the problem. The symmetric form of the problem will contain inequalities relating only the free variables and an objective function depending only on the free variables. The values of the basic variables are found from the general solution of the original system of equations.
General canonical. Each variable on which the non-negativity condition was not imposed is represented as the difference of two new non-negative variables. Inequalities are converted into equations by introducing a balance variable on the left side of each inequality in the same way as was described in the transition from symmetric to canonical form. The problem of minimizing the function Z is replaced by the problem of maximizing the function (–Z) in the same way as was described during the transition from the symmetric to the canonical form.
Graphical method for solving a linear programming problem
The set of points is called convex, if for any two points of the set it contains a segment connecting them.
Example 1
The following sets of points on the plane are convex:
The following sets of points on the plane are not convex: 
Theorem 1 The intersection of any number of convex sets is a convex set.
Theorem 2 Let there be two arbitrary points in space R n. Then for any point of the segment [ PQ] must be executed: .where .
Hyperplane in space R n is a set of points that satisfies the equation. Note that in the two-dimensional case the hyperplane is a straight line.
Half-space is a set of points that satisfies one of the inequalities or . A hyperplane divides points in space into two half-spaces. In the two-dimensional case, the hyperplane is a half-plane.
Theorem 3 A half-space is a convex set.
Consequence The intersection of any number of half-spaces is a convex set.
Polyhedron is called the intersection of one or more half-spaces. A polyhedron in the two-dimensional case is called a polygon.
Example 2
The following sets are polygons.
Limited set
Unlimited set
Single point
Empty set
A point of a convex set is called angular, if it does not lie inside any segment connecting two other points from the set.
Example 3
The corner points of a triangle are its vertices (there are three of them). The corner points of a circle are the points of the circle that bounds it (there are an infinite number of them).
The corner point of a polyhedron is called its top.
Let us consider the ZLP given in symmetric form.
Theorem 4 The optimal plan of the ZLP corresponds to the vertex of the decision polyhedron determined by its system of constraints.
Any linear programming problem can be reduced to a linear programming problem in canonical form. To do this, in the general case, you need to be able to reduce the maximization problem to the minimization problem; move from inequality constraints to equality constraints and replace variables that do not obey the non-negativity condition. Maximizing a certain function is equivalent to minimizing the same function taken with the opposite sign, and vice versa.
The rule for bringing a linear programming problem to canonical form is as follows:
- if in the original problem it is necessary to determine the maximum of a linear function, then you should change the sign and look for the minimum of this function;
- if the right side of the restrictions is negative, then this restriction should be multiplied by -1;
- if there are inequalities among the restrictions, then by introducing additional non-negative variables they are transformed into equalities;
- if some variable x j has no sign restrictions, then it is replaced (in the objective function and in all restrictions) by the difference between two new non-negative variables:
x 3 = x 3 + - x 3 - , Where x 3 + , x 3 - ≥ 0 .
Example 1. Reducing the linear programming problem to canonical form:
min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x2 ≥ 0; x 3 ≥ 0.
Let us introduce leveling variables into each equation of the system of constraints x 4 , x 5 , x 6. The system will be written in the form of equalities, and in the first and third equations of the system of constraints the variables x 4 , x 6 are entered into the left side with a “+” sign, and into the second equation the variable x 5 is entered with a "-" sign.
2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.
The free terms in the canonical form must be positive; to do this, multiply the last two equations by -1:
2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.
In the canonical form of writing linear programming problems, all variables included in the system of constraints must be negative. Let's assume that x 1 = x 1 " - x 7 , Where x 1 "≥ 0, x 7 ≥ 0 .
Substituting this expression into the system of constraints and the objective function and writing the variables in ascending index order, we obtain a linear programming problem presented in canonical form:
L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.
Optimality condition for the basic plan of the canonical LP problem. Simplex method and its convergence.
The simplex method is universal, since it allows you to solve almost any linear programming problem written in canonical form.
The idea of the simplex method consistent improvement of the plan, is that, starting from some initial reference solution, sequentially directed movement from the reference solutions of the problem to the optimal one.
The value of the objective function does not decrease during this movement for problems to the maximum.
Since the number of support solutions is finite, then after a finite number of steps we obtain the optimal support solution.
A reference solution is a basic non-negative solution.
Simplex method algorithm
1. The mathematical model of the problem must be canonical. If it is non-canonical, then it must be brought to canonical form.
2. Find the initial reference solution and check it for optimality.
To do this, fill out simplex table 1.
We fill out all rows of the table of the 1st step according to the data of the system of restrictions and the objective function.
The following cases are possible when solving problems on maximum:
1. If all the coefficients of the last row of the simplex table DJ³ 0, then found
solution optimal.
2 If at least one coefficient Dj £ 0, but for the corresponding variable there is not a single positive evaluative relationship, then the solution we stop tasks, since F(X) ® ¥ , i.e. the objective function is not limited in the area of feasible solutions.
If at least one coefficient of the last row is negative, and for the corresponding variable there is at least one positive evaluative attitude, then you need to move to another reference solution.
4. E if there are several negative coefficients in the last row, then to the underlying variable column(BP) introduce that variable, which corresponds to the largest negative coefficient in absolute value.
5. If at least one coefficient Dk< 0 ,That k - thy column accept for the presenter.
6. For leading line we accept the one that corresponds minimum ratio of free members bi to positive coefficients leading, k – that one column.
7. The element located at the intersection of the leading rows and column is called leading element.
Filling out simplex table 2 :
· fill the base column with zeros and ones
· rewrite the leading line by dividing it by the leading element
· if the leading row has zeros, then the corresponding columns can be moved to the next simplex table
· we find the remaining coefficients using the “rectangle” rule
We obtain a new reference solution, which we check for optimality:
If all coefficients of the last row DJ³ 0, then the solution found maximum.
If not, then fill out the simplex table of the 8th step and so on.
If the objective function F(X) requires finding minimum value, then the criterion optimality of the problem is non-positive coefficients D j for all j = 1,2,...n.
Convergence of the simplex method. Degeneracy in LP problems. The most important property of any computational algorithm is convergence, i.e. the possibility of obtaining the desired results during its application (with a given accuracy) in a finite number of steps (iterations).
It is easy to see that problems with the convergence of the simplex method can potentially arise at the stage of choosing the value of r (section 2") in the case where the same minimum values of the ratio
will be achieved for several rows of table T (q) simultaneously. Then at the next iteration, column b(β(q+1)) will contain zero elements.
