Answer to Question #185201 in Operations Research for Vaishu

Question

Use the simplex method to solve the following LPP .

Max z = 4x1 + 3x2

Subject to

2x1 + X2 ≤ 1000

x1 + x2 ≤ 800

x1 ≤ 400

x2 ≤ 700

x1 , x2 ≥ 0

Answer 1

Solution.

Let us determine the maximum value of the objective function F (X) = 4x1 + 3x2 under the following constraint conditions.

2x1 + x2≤1000

x1 + 2x2≤800

x1≤400

x2≤700

To construct the first reference plan, the system of inequalities is reduced to a system of equations by introducing additional variables.

2x1 + x2 + x3 = 1000

x1 + 2x2 + x4 = 800

x1 + x5 = 400

x2 + x6 = 700

The coefficient matrix A = a (ij) of this system of equations has the form:

A =

2 1 1 0 0 0

1 2 0 1 0 0

1 0 0 0 1 0

0 1 0 0 0 1

Let's solve the system of equations for the basic variables: x3, x4, x5, x6

Assuming the free variables are 0, we get the first baseline:

X0 = (0,0,1000,800,400,700)

A basic solution is called admissible if it is non-negative.

one.

The current baseline plan is not optimal because there are negative odds in the index row.

As the leading, we will choose the column corresponding to the variable x1, since this is the largest coefficient in absolute value.

Let's calculate the values ​​of Di line by line as a quotient of division: bi / ai1

and choose the smallest of them:

min (1000: 2, 800: 1, 400: 1, -) = 400

Therefore, the 3rd line is the leading one.

The resolver is (1) and is at the intersection of the leading column and the leading row.

Basis B x1 x2 x3 x4 x5 x6 min

x3 1000 2 1 1 0 0 0 500

x4 800 1 2 0 1 0 0 800

x5 400 1 0 0 0 1 0 400

x6 700 0 1 0 0 0 1 -

F (X1) 0 -4 -3 0 0 0 0

Instead of variable x5, plan 1 will include variable x1.

The line corresponding to the variable x1 in plan 1 is obtained by dividing all elements of line x5 in plan 0 by the resolving element RE = 1. In place of the resolving element, we get 1. Write zeros in the remaining cells of the column x1.

Thus, in the new plan 1, row x1 and column x1 are filled. All other elements of the new plan 1, including the elements of the index line, are determined by the rectangle rule.

To do this, we select four numbers from the old plan, which are located at the vertices of the rectangle and always include the resolving element of the RE.

NE = SE - (A * B) / RE

STE - an element of the old plan, RE - a resolving element (1), A and B - elements of the old plan, forming a rectangle with elements of STE and PE.

We get a new simplex table:

Basis B x1 x2 x3 x4 x5 x6

x3 200 0 1 1 0 -2 0

x4 400 0 2 0 1 -1 0

x1 400 1 0 0 0 1 0

x6 700 0 1 0 0 0 1

F (X1) 1600 0 -3 0 0 4 0

2.

The current baseline plan is not optimal because there are negative coefficients in the index row.

As a leading, we will choose the column corresponding to the variable x2, since this is the largest coefficient in absolute value.

We calculate the values ​​of Di line by line as a quotient of division: bi / ai2

and choose the smallest of them:

min (200: 1, 400: 2, -, 700: 1) = 200

Therefore, the 1st line is the leading one.

The resolver is (1) and is at the intersection of the leading column and the leading row.

Basis B x1 x2 x3 x4 x5 x6 min

x3 200 0 1 1 0 -2 0 200

x4 400 0 2 0 1 -1 0 200

x1 400 1 0 0 0 1 0 -

x6 700 0 1 0 0 0 1 700

F (X2) 1600 0 -3 0 0 4 0

Since there are several minimum elements of 200 in the last column, we choose the row number according to Cracko's rule. Line items that have the same smallest value min = 200 are divided by the supposed resolution items, and the results are written to additional lines. For the leading row, the one in which the smallest quotient is encountered earlier when reading the table from left to right in columns is selected.

We form the next part of the simplex table. Instead of variable x3, plan 2 will include variable x2.

The line corresponding to the variable x2 in plan 2 is obtained by dividing all elements of line x3 in plan 1 by the resolving element RE = 1. In place of the resolving element, we get 1. Write zeros in the remaining cells of the column x2.

Thus, in the new plan 2, row x2 and column x2 are filled. All other elements of the new plan 2, including the elements of the index line, are determined by the rectangle rule.

• -3): 1 0- (0 • -3): 1 4 - (- 2 • -3): 1 0- (0 • -3): 1

We get a new simplex table:

Basis B x1 x2 x3 x4 x5 x6

x2 200 0 1 1 0 -2 0

x4 0 0 0 -2 1 3 0

x1 400 1 0 0 0 1 0

x6 500 0 0 -1 0 2 1

F (X2) 2200 0 0 3 0 -2 0

Iteration number 2.

1. Checking the criterion of optimality.

The current baseline plan is not optimal because there are negative odds in the index row.

2. Determination of a new basis variable.

As the leading, we will choose the column corresponding to the variable x5, since this is the largest coefficient in absolute value.

3. Definition of a new free variable.

Let's calculate the values ​​of Di line by line as a quotient of division: bi / ai5

and choose the smallest of them:

min (-, 0: 3, 400: 1, 500: 2) = 0

Therefore, the 2nd line is the leading one.

The resolving element is (3) and is at the intersection of the leading column and the leading row.

Basis B x1 x2 x3 x4 x5 x6 min

x2 200 0 1 1 0 -2 0 -

x4 0 0 0 -2 1 3 0 0

x1 400 1 0 0 0 1 0 400

x6 500 0 0 -1 0 2 1 250

F (X3) 2200 0 0 3 0 -2 0

4. Recalculation of the simplex table. Instead of variable x4, plan 3 will include variable x5.

The line corresponding to the variable x5 in plan 3 is obtained by dividing all elements of line x4 in plan 2 by the resolving element RE = 3. In place of the resolving element, we get 1. Write zeros in the remaining cells of the column x5.

So in new plan 3, row x5 and column x5 are filled. All other elements of the new plan 3, including the elements of the index line, are determined by the rectangle rule.

B x1 x2 x3 x4 x5 x6

200- (0 • -2): 3 0- (0 • -2): 3 1- (0 • -2): 3 1 - (- 2 • -2): 3 0- (1 • -2): 3 -2- (3 • -2): 3 0- (0 • -2): 3

0: 3 0: 3 0: 3 -2: 3 1: 3 3: 3 0: 3

400- (0 • 1): 3 1- (0 • 1): 3 0- (0 • 1): 3 0 - (- 2 • 1): 3 0- (1 • 1): 3 1- (3 • 1): 3 0- (0 • 1): 3

500- (0 • 2): 3 0- (0 • 2): 3 0- (0 • 2): 3 -1 - (- 2 • 2): 3 0- (1 • 2): 3 2- ( 3 • 2): 3 1- (0 • 2): 3

2200- (0 • -2): 3 0- (0 • -2): 3 0- (0 • -2): 3 3 - (- 2 • -2): 3 0- (1 • -2): 3 -2- (3 • -2): 3 0- (0 • -2): 3

We get a new simplex table:

Basis B x1 x2 x3 x4 x5 x6

x2 200 0 1 -1/3 2/3 0 0

x5 0 0 0 -2/3 1/3 1 0

x1 400 1 0 2/3 -1/3 0 0

x6 500 0 0 1/3 -2/3 0 1

F (X3) 2200 0 0 5/3 2/3 0 0

1. Checking the criterion of optimality.

There are no negative values ​​in the index row. Therefore, this table determines the optimal task plan.

The final version of the simplex table:

Basis B x1 x2 x3 x4 x5 x6

x2 200 0 1 -1/3 2/3 0 0

x5 0 0 0 -2/3 1/3 1 0

x1 400 1 0 2/3 -1/3 0 0

x6 500 0 0 1/3 -2/3 0 1

F (X4) 2200 0 0 5/3 2/3 0 0

The optimal plan can be written like this:

x1 = 400, x2 = 200

F (X) = 4 * 400 + 3 * 200 = 2200.

Answer. 2200.