You get a bonus - 1 coin for daily activity. Now you have 1 coin

4 Transition from graphic solution to algebraic. Algorithm simplex - method. Computational algorithm of the simplex method.

Lecture



Limitations. Denote x 1 and x 2 respectively the number of servings of the pie and hamburgers. You can limit yourself to either 200 pounds of meat, or buy more. In the first case, the limit is 0.25x1 + 0.2x2,200, in the second, 0.25x1 + 0.2x2,200.

Naturally, the choice of inequality will influence the solution. Since we do not know what restriction is necessary, it is logical to replace them with one equality 0.25x 1 + 0.2x 2 -x 3 = 200, where x 3 is a free variable. Here it plays the role of both excess and residual.

Objective function If you need to maximize income, you need to sell as much products as possible, then you need additional purchases of meat, in this case x 3 should be negative, i.e. play the role of redundant variable. In order to uncover the “dual” nature of the variable x 3 , let’s represent it as follows:

4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. where 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. 0

If a 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. > 0 and 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. , then the variable x 3 plays the role of residual. If a 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. > 0 and 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. = 0, then x 3 appears as redundant. So the restrictions now have the form

4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. .

And the objective function

Z = 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method.

The transition from graphical solutions to algebraic.

The ideas underlying the graphic solution underlie the algebraic method, which is called the simplex method. In the graphical method, the solution space is defined as the intersection of half-spaces generated by constraints. In an algebraic or simplex method, the solution space is given by m linear equations and n non-negative variables.

In the algebraic representation, the number of equations m is always less than or equal to the number of variables n. (If the number of equations m is greater than the number of variables n, then mn equations are redundant.) If m = n and the system of equations is compatible, then it has one solution (if it is non-degenerate), if m

In the algebraic representation, candidates for the optimal solution (corner points in the graphical representation) are determined from a system of linear equations as follows. Let m

Example. Z = 2x 1 + 3x 2 max

2x 1 + x 2 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. four

x 1 + 2x 2 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. five

x 1 x 2 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. 0

4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method.

After conversion to the standard form, we have the following LP problem.

Z = 2x 1 + 3x 2 max

2x 1 + x 2 + S 1 = 4,

x 1 + 2x 2 + S 2 = 5,

x 1 , x 2 , S 1 , S 2 0.

We have a system of m = 2 equations for n = 4 variables. As we agreed, the corner points can be defined algebraically, assigning zero values ​​to n = m = 4-2 = 2 variables, and then solving the system for m = 2 variables. If we set x 1 = 0 and x 2 = 2 (point C).

Which variables are set equal to zero to get the corner points? You just need to consider all combinations of nm variables, equate them to zero and find all the corner points.

In our example, we have 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. corner points. In the picture we see only 4. Where are the other two? In fact, points E and F are also corner points. But they are not yet candidates for an optimal solution, because they do not satisfy all restrictions.

To complete the transition to the algebraic method of solving the LP problem, it is necessary to somehow name the corner points of different types. The nm variables that are considered equal to zero are called non-basic variables. If the remaining m variables have a unique solution, they are called basic variables, and the set of solutions that they give constitute the basic solution. If all variables take non-negative values, this basic solution is called valid.

Nonbasic (zero) variables

Base variables

Basic solutions

Corner points

Is the solution acceptable?

The value of the objective function Z

(x 1 , x 2 )

(S 1 , S 2 )

(5, 4)

A

Yes

0

(x 1 , s 1 )

(x 2 , S 2 )

(4, -3)

F

Not

-

(x 1 , s 2 )

(x 2 , s 1 )

(2.5, 1.5)

D

Yes

7.5

(x 2 , s 1 )

(x 1 , s 2 )

(2, 3)

B

Yes

four

(x 2 , S 2 )

(x 1 , s 1 )

(5, -6)

E

Not

-

(S 1 , S 2 )

(x 1 , x 2 )

(12)

C

Yes

8 (opt.)

From this example, it is seen that as the dimension of the problem (n and m) increases, the process of enumerating all the corner points becomes a very difficult task. For example, when n = 20 and m = 10, you need to solve 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. 184,756 systems of equations of the order of 1010. This is already an awesome computational problem. In reality, m and n can reach hundreds of thousands. Simplex method removes this problem.

Algorithm simplex - method.

So, the procedure of enumeration of all basic solutions is inefficient. Consider the simplex method.

The iterative nature of the simplex method.

Consider the solution space for the same example.

4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method.

Usually, the simplex method algorithm starts from the starting point, where x 1 = x 2 = 0 (point A). At this starting point, the value of the objective function Z is zero. The question arises: if one or both of the nonbasic variables x 1 and x 2 take positive values, will this lead to an improvement in the objective function?

Z = 2x 1 + 3x 2 max.

Obviously, if the variable x 1 and x 2 (or both) take positive values, this will increase the value of the GF.

However, the algorithm of the simplex method at each step allows changing the value of only one nonbasic variable.

1. If you increase the value of the variable x 1 , then its value should increase so as to correspond to the corner point B (candidates are only corner points). At point B, the simplex method should increase the value of the variable x 2 , moving to the corner point C. Since point C corresponds to optimum, then the process ends. So simplex method algorithm creates path A 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. B 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. C.

2. If you first increase the value of the variable x 2 , then the next corner point will be point D, from which we go to point C and end the process A 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. D 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. C.

Note that both ways are A 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. B 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. C and A 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. D 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. C are located along the boundary Γ of the solution space. So simplex - the method cannot immediately jump from t.A to t.C.

Does every nonbasic variable be made positive at a given corner point? If we consider the maximization problem, then we should choose a nonbasic variable that has the largest positive coefficient in the expression of the objective function. If there are several such variables, then the choice is arbitrary. This rule is empirical.

How to translate non-basic variables into basic variables and vice versa when moving from one corner point to another?

4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method.

The figure shows that at point A, the variables S 1 and S 2 are basic, and the variables x 1 and x 2 are nonbasic If the variable x1 takes a positive value, we move to the corner point B, in which the state of the variable x 1 changes from nonbasic to basic. At the same time, a variable that was basic at point A becomes nonbasic and takes a zero value at point B. Here it is significant, there is a simultaneous “state exchange” between nonbasic variable x 1 and basic S 1 , which leads to new basic (x 1 , S 2 ) and nonbasic (S 1 , x 2 ) variables at point B. At point A, variable x 1 is introduced into the basic solution, and variable S 1 is excluded from the basic solution. In the terminology of the simplex method, the selected nonbasic (zero) variable is called input (to the basic solution), and the removed variable (from the basic solution) basic variable is excluded. In m. In the input and exclude variables will be respectively x 2 and S 2 .

Computational algorithm of the simplex method.

Consider the following example.

Let's return to the problem about the Reddy Mikks company. In standard form, this task is written as:

Z = 5x 1 + 4x 2 + 0S 1 + 0S 2 + 0S 3 + 0S 4 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. max

under restrictions:

6x 1 + 4x 2 + S 1 = 24

x 1 + 2x 2 + S 2 = 6

-x 1 + x 2 + S 3 = 1

x 2 + S 4 = 2

x 1 , x 2 , S 1 , S 2 , S 3 , S 4 0

Here S 1 , S 2 , S 3 , S 4 are additional (residual) variables.

The objective function will be represented as an equation:

Z - 5x 1 - 4x 2 = 0

The LP task in the standard form will be presented in the form of a table:

Basis

Z

x 1

x 2

S 1

S 2

S 3

S 4

Decision

Z

one

- five

- four

0

0

0

0

0

Z-string

S 1

0

6

four

one

0

0

0

24

S 1 line

S 2

0

one

2

0

one

0

0

6

S 2 line

S 3

0

-one

one

0

0

one

0

one

S 3 - line

S 4

0

0

one

0

0

0

one

2

S 4 - line

The table shows the sets of basic and nonbasic variables, as well as the solution corresponding to this (initial) iteration. The initial iteration starts from the point (x 1 , x 2 ) = (0,0). This corresponds to the following sets of basic and nonbasic variables:

Non-basic (zero): (x 1 , x 2 )

Basic: (S 1 , S 2 , S 3 , S 4 )

Since x 1 = 0, x 2 = 0 and the coefficients with the basic variables S 1 , S 2 , S 3 , S 4 in the equation of the objective function are zero, and in the formulas of the left parts of the equality of the restrictions - 1, without additional calculations we have: Z = 0, S 1 = 24, S 2 = 6, S 3 = 1, S 4 = 0.

In the table, the basic variables are listed in the left column “Basis”, and their values ​​in the right column “Solution”. Thus, the current corner point is defined.

Since the coefficient of the variable x1 in the formula of the objective function is the largest, it should be included in the number of base variables (it will be introduced). The table shows that the input variable is defined among the set of nonbasic as having the largest negative coefficient in the 2nd line. If all coefficients in the 2nd line are non-negative, then the maximum is reached.

To determine the excluded variable, it is necessary to calculate the intersection points of all functions with the positive direction of the x 1 axis. These coordinates can be calculated as the ratio of the right-hand sides of the equality (the “Solution” column) and the coefficients of the variable x 1 .

Basis

Coefficients

at x 1

Decision

Relationship (intersection point)

S 1

6

24

x 1 = 24/6 = 4

S 2

one

6

x 1 = 6/1 = 6

S 3

-one

one

x 1 = 1 / (- 1) = - 1 - does not fit

S 4

0

2

x 1 = 2/0 = - not suitable

The maximum non-negative relation corresponds to the basic variable S 2 , it is determined as excluded (that is, at the next iteration its value will be zero). The value of the input variable x 1 is also equal to the minimum non-negative relation: x 1 = 6

4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method.

Maximize

Z = 5x 1 + 4x 2

1) 6x 1 + 4x 2 + S 1 = 24

2) x 1 + 2x 2 + S 2 = 6

3) -x 1 + x 2 + S 3 = 1

4) x 2 + S 4 = 2

x 1 x 2 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. 0

The value of the objective function will increase to 5. 4 Transition from graphic solution to algebraic.  Algorithm simplex - method.  Computational algorithm of the simplex method. 4 = 20.

Replacing the excluded variable S 1 with the input variable x 1 leads to new sets of basic and non-basic variables and to a new solution in TV

Nonbasic (zero) variables (S 1 , x 2 )

Basic variables (x 1 , S 2 , S 3 , S 4 )

Now you need to perform the conversion in the table so that in the columns “Basis” and “Solution” you get a new solution corresponding to point B.

In the following table, which so far coincides with the initial, we define the leading column associated with the input variable and the leading row associated with the excluded variable. The element located at the intersection of the leading column and leading line is called leading.

Basis

Z

x 1

x 2

S 1

S 2

S 3

S 4

Decision

Z

one

- five

- four

0

0

0

0

0

S 1

0

6

four

one

0

0

0

24

Leading line

S 2

0

one

2

0

one

0

0

6

S 3

0

-one

one

0

0

one

0

one

S 4

0

0

one

0

0

0

one

2

Lead column

The process of calculating a new basic solution consists of two steps:

1. Calculate the elements of the new leading line.

New Sun = Current Sun / Lead

2. Calculation of the elements of the remaining lines, including the Z-line.

New line = Current line - its coefficient in the leading column New Sun

In the example, the calculations are:

1. New lead S 1 line = Current lead S 1 line / 6

2. New Z-line = Current Z-line - (-5) New Sun

3. New S 2 line = Current S 2 line - (1) New Sun

4. New S 3 line = Current S 3 line - (-1) New Sun

5. New S 4 line = Current S 4 line - (0) New Sun

Basis

Z

x 1

x 2

S 1

S 2

S 3

S 4

Decision

Z

one

0

0

3/4

1/2

0

0

21

x 1

0

one

0

1/4

-1/2

0

0

3

x 2

0

0

one

-1/8

3/4

0

0

3/2

S 3

0

0

0

3/8

-5/4

one

0

5/2

S 4

0

0

0

1/8

-3/4

0

one

1/2

Since the Z-line does not have negative coefficients corresponding to nonbasic variables S 1 and S 2 , the solution obtained is optimal.

The values ​​of the additional variables S 1 = S 2 = 0, S 3 = 5/2 and S 4 = 1/2 are consistent with the values ​​of the variables x 1 and x 2 .

With the help of the simplex table you can get a lot of additional information about the state of resources. The status “deficient” or “non-deficient” for a resource is determined by whether it is used or not. If the additional variable is zero, the resource is fully used, it receives the status of deficit.

Resource

Residual variable

Status

Raw M 1

S 1 = 0

In short supply

Raw M 2

S 2 = 0

In short supply


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Mathematical methods of research operations. The theory of games and schedules.

Terms: Mathematical methods of research operations. The theory of games and schedules.