The number of constraints:
The Number of variables:
Enter the values of the objective function:
F(x)
=
 x1 +
 x2 +
 x3 +
 x4
Enter the values of the system of constraints:
bracket
 x1 +
 x2 +
 x3 +
 x4
 x1 +
 x2 +
 x3 +
 x4
 x1 +
 x2 +
 x3 +
 x4
 x1 +
 x2 +
 x3 +
 x4

Solution example

F(x) = 3x1 + 4x2 → max

0002x1 + x2 ≤ 600
0x1 + 0x2 ≤ 225
5x1 +4x2 ≤ 1000
2x2 ≥ 150
0x1 + 0x2 ≥ 0
arrow transition
F(x) = 3x1 + 4x2 + 0x3 + 0x4 + 0x5 + 0x6 + 0x7 - Mx8 - Mx9 → max

0002x1 + x2 + x3 = 600
+ x4 = 225
5x1 + 4x2 + x5 = 1000
2x2 - x6 + x8 = 150
- x7 + x9 = 0

Preliminary stage:arrow down description
The preliminary stage begins with the need to get rid of negative values ​​(if any) in the right part of the restrictions. For what the corresponding restrictions are multiplied by -1. After this manipulation, the sign of inequality is reversed.

Next, you need to get rid of inequalities, for which we introduce compensating variables in the left-hand side of the inequalities. If an inequality of the form ≤, then the compensating variable has the sign +, if the inequality of the form ≥, then the compensating variable has the sign -. Compensating variables are included in the objective function of the problem with a zero coefficient.

Now in the constraint system it is necessary to find a sufficient number of basis variables. Each constraint must have one basis variable. The basic is a variable that has a coefficient of 1 with it and is found only in one constraint. If there are no basis variables in some restriction, then we add them artificially, and artificial variables enter the objective function with the coefficient -M if the objective function tends to max and M, if the objective function tends to min.

Iteration: 1

BCbPx1x2x3x4x5x6x7x8x9Q
3400000-M-M
x30600211000000600
x40225000100000
x501000540010000250
x8
-M15002000-101075
x9-M0000000-101
max-150M-3-2M-4000MM00

Calculation of table elements:arrow down description
Elements of the column basis (B)

Transfer to the table the basic elements that we identified in the preliminary stage:

B1 = x3;

B2 = x4;

B3 = x5;

B4 = x8;

B5 = x9;

Cb column items

Each cell of this column is equal to the coefficient, which corresponds to the base variable in the corresponding row.

Cb1 = 0;

Cb2 = 0;

Cb3 = 0;

Cb4 = -M;

Cb5 = -M;

Values ​​of variable variables and column P

At this stage, no calculations are needed, just transfer the values ​​from the preliminary stage to the corresponding table cells:

P1 = 600;

P2 = 225;

P3 = 1000;

P4 = 150;

P5 = 0;

x1,1 = 2;

x1,2 = 1;

x1,3 = 1;

x1,4 = 0;

x1,5 = 0;

x1,6 = 0;

x1,7 = 0;

x1,8 = 0;

x1,9 = 0;

x2,1 = 0;

x2,2 = 0;

x2,3 = 0;

x2,4 = 1;

x2,5 = 0;

x2,6 = 0;

x2,7 = 0;

x2,8 = 0;

x2,9 = 0;

x3,1 = 5;

x3,2 = 4;

x3,3 = 0;

x3,4 = 0;

x3,5 = 1;

x3,6 = 0;

x3,7 = 0;

x3,8 = 0;

x3,9 = 0;

x4,1 = 0;

x4,2 = 2;

x4,3 = 0;

x4,4 = 0;

x4,5 = 0;

x4,6 = -1;

x4,7 = 0;

x4,8 = 1;

x4,9 = 0;

x5,1 = 0;

x5,2 = 0;

x5,3 = 0;

x5,4 = 0;

x5,5 = 0;

x5,6 = 0;

x5,7 = -1;

x5,8 = 0;

x5,9 = 1;

Objective function value

We calculate the value of the objective function by elementwise multiplying the column Cb by the column P, adding the results of the products.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5 = (0 * 600) + (0 * 225) + (0 * 1000) + (-M * 150) + (-M * 0) = -150M;

Evaluated Control Variables

We calculate the estimates for each controlled variable, by element-wise multiplying the value from the variable column, by the value from the Cb column, summing up the results of the products, and subtracting the coefficient of the objective function from their sum, with this variable.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 2) + (0 * 0) + (0 * 5) + (-M * 0) + (-M * 0) ) - 3 = -3;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 1) + (0 * 0) + (0 * 4) + (-M * 2) + (-M * 0) ) - 4 = -2M-4;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (0 * 0) + (-M * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * 0) + (0 * 0) + (0 * 1) + (-M * 0) + (-M * 0) ) - 0 = 0;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * -1) + (-M * 0) ) - 0 = M;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 1) + (-M * 0) ) - -M = 0;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 1) ) - -M = 0;

Q column items

Since there are negative values ​​among the estimates of the controlled variables, the current table does not yet have an optimal solution. Therefore, in the basis we introduce the variable with the smallest negative estimate.

The number of variables in the basis is always constant, so it is necessary to choose which variable to derive from the basis, for which we calculate Q.

The elements of the Q column are calculated by dividing the values ​​from column P by the value from the column corresponding to the variable that is entered in the basis:

Q1 = P1 / x1,2 = 600 / 1 = 600;

Q2 = P2 / x2,2 = 225 / 0 = ∞;

Q3 = P3 / x3,2 = 1000 / 4 = 250;

Q4 = P4 / x4,2 = 150 / 2 = 75;

Q5 = P5 / x5,2 = 0 / 0 = ∞;

We deduce from the basis the variable with the least positive value of Q.

At the intersection of the line that corresponds to the variable that is derived from the basis, and the column that corresponds to the variable that is entered into the basis, is the resolving element.

This element will allow us to calculate the elements of the table of the next iteration.

Iteration: 2

BCbPx1x2x3x4x5x6x7x8x9Q
3400000-M-M
x30525201000.50-0.50262.5
x40225000100000
x5
07005000120-20140
x247501000-0.500.50
x9-M0000000-101
max300-30000-2MM+20

Calculation of table elements:arrow down description
Elements of the column basis (B)

For the results of the calculations of the previous iteration, we remove the variable from the basis x8 and put in her place x2. All other cells remain unchanged.

Cb column items

Each cell of this column is equal to the coefficient, which corresponds to the base variable in the corresponding row.

Cb1 = 0;

Cb2 = 0;

Cb3 = 0;

Cb4 = 4;

Cb5 = -M;

Values ​​of variable variables and column P(The data from the previous iteration is taken as the initial data)

Fill all cells with zeros corresponding to the variable that has just been entered into the basis:(The resolution element remains unchanged)

x1,2 = 0;

x2,2 = 0;

x3,2 = 0;

x5,2 = 0;

We transfer the row with the resolving element from the previous table into the current table, elementwise dividing its values ​​into the resolving element:

P4 = P4 / x4,2 = 150 / 2 = 75;

x4,1 = x4,1 / x4,2 = 0 / 2 = 0;

x4,2 = x4,2 / x4,2 = 2 / 2 = 1;

x4,3 = x4,3 / x4,2 = 0 / 2 = 0;

x4,4 = x4,4 / x4,2 = 0 / 2 = 0;

x4,5 = x4,5 / x4,2 = 0 / 2 = 0;

x4,6 = x4,6 / x4,2 = -1 / 2 = -0.5;

x4,7 = x4,7 / x4,2 = 0 / 2 = 0;

x4,8 = x4,8 / x4,2 = 1 / 2 = 0.5;

x4,9 = x4,9 / x4,2 = 0 / 2 = 0;

The remaining empty cells, except for the row of estimates and the column Q, are calculated using the rectangle method, relative to the resolving element:

P1 = (P1 * x4,2) - (x1,2 * P4) / x4,2 = ((600 * 2) - (1 * 150)) / 2 = 525;

P2 = (P2 * x4,2) - (x2,2 * P4) / x4,2 = ((225 * 2) - (0 * 150)) / 2 = 225;

P3 = (P3 * x4,2) - (x3,2 * P4) / x4,2 = ((1000 * 2) - (4 * 150)) / 2 = 700;

P5 = (P5 * x4,2) - (x5,2 * P4) / x4,2 = ((0 * 2) - (0 * 150)) / 2 = 0;

x1,1 = ((x1,1 * x4,2) - (x1,2 * x4,1)) / x4,2 = ((2 * 2) - (1 * 0)) / 2 = 2;

x1,2 = ((x1,2 * x4,2) - (x1,2 * x4,2)) / x4,2 = ((1 * 2) - (1 * 2)) / 2 = 0;

x1,4 = ((x1,4 * x4,2) - (x1,2 * x4,4)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x1,5 = ((x1,5 * x4,2) - (x1,2 * x4,5)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x1,6 = ((x1,6 * x4,2) - (x1,2 * x4,6)) / x4,2 = ((0 * 2) - (1 * -1)) / 2 = 0.5;

x1,7 = ((x1,7 * x4,2) - (x1,2 * x4,7)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x1,8 = ((x1,8 * x4,2) - (x1,2 * x4,8)) / x4,2 = ((0 * 2) - (1 * 1)) / 2 = -0.5;

x1,9 = ((x1,9 * x4,2) - (x1,2 * x4,9)) / x4,2 = ((0 * 2) - (1 * 0)) / 2 = 0;

x2,1 = ((x2,1 * x4,2) - (x2,2 * x4,1)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x2,2 = ((x2,2 * x4,2) - (x2,2 * x4,2)) / x4,2 = ((0 * 2) - (0 * 2)) / 2 = 0;

x2,4 = ((x2,4 * x4,2) - (x2,2 * x4,4)) / x4,2 = ((1 * 2) - (0 * 0)) / 2 = 1;

x2,5 = ((x2,5 * x4,2) - (x2,2 * x4,5)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x2,6 = ((x2,6 * x4,2) - (x2,2 * x4,6)) / x4,2 = ((0 * 2) - (0 * -1)) / 2 = 0;

x2,7 = ((x2,7 * x4,2) - (x2,2 * x4,7)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x2,8 = ((x2,8 * x4,2) - (x2,2 * x4,8)) / x4,2 = ((0 * 2) - (0 * 1)) / 2 = 0;

x2,9 = ((x2,9 * x4,2) - (x2,2 * x4,9)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x3,1 = ((x3,1 * x4,2) - (x3,2 * x4,1)) / x4,2 = ((5 * 2) - (4 * 0)) / 2 = 5;

x3,2 = ((x3,2 * x4,2) - (x3,2 * x4,2)) / x4,2 = ((4 * 2) - (4 * 2)) / 2 = 0;

x3,4 = ((x3,4 * x4,2) - (x3,2 * x4,4)) / x4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x3,5 = ((x3,5 * x4,2) - (x3,2 * x4,5)) / x4,2 = ((1 * 2) - (4 * 0)) / 2 = 1;

x3,6 = ((x3,6 * x4,2) - (x3,2 * x4,6)) / x4,2 = ((0 * 2) - (4 * -1)) / 2 = 2;

x3,7 = ((x3,7 * x4,2) - (x3,2 * x4,7)) / x4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x3,8 = ((x3,8 * x4,2) - (x3,2 * x4,8)) / x4,2 = ((0 * 2) - (4 * 1)) / 2 = -2;

x3,9 = ((x3,9 * x4,2) - (x3,2 * x4,9)) / x4,2 = ((0 * 2) - (4 * 0)) / 2 = 0;

x5,1 = ((x5,1 * x4,2) - (x5,2 * x4,1)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x5,2 = ((x5,2 * x4,2) - (x5,2 * x4,2)) / x4,2 = ((0 * 2) - (0 * 2)) / 2 = 0;

x5,4 = ((x5,4 * x4,2) - (x5,2 * x4,4)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x5,5 = ((x5,5 * x4,2) - (x5,2 * x4,5)) / x4,2 = ((0 * 2) - (0 * 0)) / 2 = 0;

x5,6 = ((x5,6 * x4,2) - (x5,2 * x4,6)) / x4,2 = ((0 * 2) - (0 * -1)) / 2 = 0;

x5,7 = ((x5,7 * x4,2) - (x5,2 * x4,7)) / x4,2 = ((-1 * 2) - (0 * 0)) / 2 = -1;

x5,8 = ((x5,8 * x4,2) - (x5,2 * x4,8)) / x4,2 = ((0 * 2) - (0 * 1)) / 2 = 0;

x5,9 = ((x5,9 * x4,2) - (x5,2 * x4,9)) / x4,2 = ((1 * 2) - (0 * 0)) / 2 = 1;

Objective function value

We calculate the value of the objective function by elementwise multiplying the column Cb by the column P, adding the results of the products.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5 = (0 * 525) + (0 * 225) + (0 * 700) + (4 * 75) + (-M * 0) = 300;

Evaluated Control Variables

We calculate the estimates for each controlled variable, by element-wise multiplying the value from the variable column, by the value from the Cb column, summing up the results of the products, and subtracting the coefficient of the objective function from their sum, with this variable.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 2) + (0 * 0) + (0 * 5) + (4 * 0) + (-M * 0) ) - 3 = -3;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * 0.5) + (0 * 0) + (0 * 2) + (4 * -0.5) + (-M * 0) ) - 0 = -2;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * -0.5) + (0 * 0) + (0 * -2) + (4 * 0.5) + (-M * 0) ) - -M = M+2;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Q column items

Since there are negative values ​​among the estimates of the controlled variables, the current table does not yet have an optimal solution. Therefore, in the basis we introduce the variable with the smallest negative estimate.

The number of variables in the basis is always constant, so it is necessary to choose which variable to derive from the basis, for which we calculate Q.

The elements of the Q column are calculated by dividing the values ​​from column P by the value from the column corresponding to the variable that is entered in the basis:

Q1 = P1 / x1,1 = 525 / 2 = 262.5;

Q2 = P2 / x2,1 = 225 / 0 = ∞;

Q3 = P3 / x3,1 = 700 / 5 = 140;

Q4 = P4 / x4,1 = 75 / 0 = ∞;

Q5 = P5 / x5,1 = 0 / 0 = ∞;

We deduce from the basis the variable with the least positive value of Q.

At the intersection of the line that corresponds to the variable that is derived from the basis, and the column that corresponds to the variable that is entered into the basis, is the resolving element.

This element will allow us to calculate the elements of the table of the next iteration.

Iteration: 3

BCbPx1x2x3x4x5x6x7x8x9Q
3400000-M-M
x302450010-0.4-0.300.30-816.67
x40225000100000
x1
314010000.20.40-0.40350
x247501000-0.500.50-150
x9-M0000000-101
max72000000.6-0.8MM+0.80

Calculation of table elements:arrow down description
Elements of the column basis (B)

For the results of the calculations of the previous iteration, we remove the variable from the basis x5 and put in her place x1. All other cells remain unchanged.

Cb column items

Each cell of this column is equal to the coefficient, which corresponds to the base variable in the corresponding row.

Cb1 = 0;

Cb2 = 0;

Cb3 = 3;

Cb4 = 4;

Cb5 = -M;

Values ​​of variable variables and column P(The data from the previous iteration is taken as the initial data)

Fill all cells with zeros corresponding to the variable that has just been entered into the basis:(The resolution element remains unchanged)

x1,1 = 0;

x2,1 = 0;

x4,1 = 0;

x5,1 = 0;

We transfer the row with the resolving element from the previous table into the current table, elementwise dividing its values ​​into the resolving element:

P3 = P3 / x3,1 = 700 / 5 = 140;

x3,1 = x3,1 / x3,1 = 5 / 5 = 1;

x3,2 = x3,2 / x3,1 = 0 / 5 = 0;

x3,3 = x3,3 / x3,1 = 0 / 5 = 0;

x3,4 = x3,4 / x3,1 = 0 / 5 = 0;

x3,5 = x3,5 / x3,1 = 1 / 5 = 0.2;

x3,6 = x3,6 / x3,1 = 2 / 5 = 0.4;

x3,7 = x3,7 / x3,1 = 0 / 5 = 0;

x3,8 = x3,8 / x3,1 = -2 / 5 = -0.4;

x3,9 = x3,9 / x3,1 = 0 / 5 = 0;

The remaining empty cells, except for the row of estimates and the column Q, are calculated using the rectangle method, relative to the resolving element:

P1 = (P1 * x3,1) - (x1,1 * P3) / x3,1 = ((525 * 5) - (2 * 700)) / 5 = 245;

P2 = (P2 * x3,1) - (x2,1 * P3) / x3,1 = ((225 * 5) - (0 * 700)) / 5 = 225;

P4 = (P4 * x3,1) - (x4,1 * P3) / x3,1 = ((75 * 5) - (0 * 700)) / 5 = 75;

P5 = (P5 * x3,1) - (x5,1 * P3) / x3,1 = ((0 * 5) - (0 * 700)) / 5 = 0;

x1,1 = ((x1,1 * x3,1) - (x1,1 * x3,1)) / x3,1 = ((2 * 5) - (2 * 5)) / 5 = 0;

x1,3 = ((x1,3 * x3,1) - (x1,1 * x3,3)) / x3,1 = ((1 * 5) - (2 * 0)) / 5 = 1;

x1,4 = ((x1,4 * x3,1) - (x1,1 * x3,4)) / x3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x1,5 = ((x1,5 * x3,1) - (x1,1 * x3,5)) / x3,1 = ((0 * 5) - (2 * 1)) / 5 = -0.4;

x1,6 = ((x1,6 * x3,1) - (x1,1 * x3,6)) / x3,1 = ((0.5 * 5) - (2 * 2)) / 5 = -0.3;

x1,7 = ((x1,7 * x3,1) - (x1,1 * x3,7)) / x3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x1,8 = ((x1,8 * x3,1) - (x1,1 * x3,8)) / x3,1 = ((-0.5 * 5) - (2 * -2)) / 5 = 0.3;

x1,9 = ((x1,9 * x3,1) - (x1,1 * x3,9)) / x3,1 = ((0 * 5) - (2 * 0)) / 5 = 0;

x2,1 = ((x2,1 * x3,1) - (x2,1 * x3,1)) / x3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x2,3 = ((x2,3 * x3,1) - (x2,1 * x3,3)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x2,4 = ((x2,4 * x3,1) - (x2,1 * x3,4)) / x3,1 = ((1 * 5) - (0 * 0)) / 5 = 1;

x2,5 = ((x2,5 * x3,1) - (x2,1 * x3,5)) / x3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x2,6 = ((x2,6 * x3,1) - (x2,1 * x3,6)) / x3,1 = ((0 * 5) - (0 * 2)) / 5 = 0;

x2,7 = ((x2,7 * x3,1) - (x2,1 * x3,7)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x2,8 = ((x2,8 * x3,1) - (x2,1 * x3,8)) / x3,1 = ((0 * 5) - (0 * -2)) / 5 = 0;

x2,9 = ((x2,9 * x3,1) - (x2,1 * x3,9)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,1 = ((x4,1 * x3,1) - (x4,1 * x3,1)) / x3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x4,3 = ((x4,3 * x3,1) - (x4,1 * x3,3)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,4 = ((x4,4 * x3,1) - (x4,1 * x3,4)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,5 = ((x4,5 * x3,1) - (x4,1 * x3,5)) / x3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x4,6 = ((x4,6 * x3,1) - (x4,1 * x3,6)) / x3,1 = ((-0.5 * 5) - (0 * 2)) / 5 = -0.5;

x4,7 = ((x4,7 * x3,1) - (x4,1 * x3,7)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x4,8 = ((x4,8 * x3,1) - (x4,1 * x3,8)) / x3,1 = ((0.5 * 5) - (0 * -2)) / 5 = 0.5;

x4,9 = ((x4,9 * x3,1) - (x4,1 * x3,9)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x5,1 = ((x5,1 * x3,1) - (x5,1 * x3,1)) / x3,1 = ((0 * 5) - (0 * 5)) / 5 = 0;

x5,3 = ((x5,3 * x3,1) - (x5,1 * x3,3)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x5,4 = ((x5,4 * x3,1) - (x5,1 * x3,4)) / x3,1 = ((0 * 5) - (0 * 0)) / 5 = 0;

x5,5 = ((x5,5 * x3,1) - (x5,1 * x3,5)) / x3,1 = ((0 * 5) - (0 * 1)) / 5 = 0;

x5,6 = ((x5,6 * x3,1) - (x5,1 * x3,6)) / x3,1 = ((0 * 5) - (0 * 2)) / 5 = 0;

x5,7 = ((x5,7 * x3,1) - (x5,1 * x3,7)) / x3,1 = ((-1 * 5) - (0 * 0)) / 5 = -1;

x5,8 = ((x5,8 * x3,1) - (x5,1 * x3,8)) / x3,1 = ((0 * 5) - (0 * -2)) / 5 = 0;

x5,9 = ((x5,9 * x3,1) - (x5,1 * x3,9)) / x3,1 = ((1 * 5) - (0 * 0)) / 5 = 1;

Objective function value

We calculate the value of the objective function by elementwise multiplying the column Cb by the column P, adding the results of the products.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5) = (0 * 245) + (0 * 225) + (3 * 140) + (4 * 75) + (-M * 0) = 720;

Evaluated Control Variables

We calculate the estimates for each controlled variable, by element-wise multiplying the value from the variable column, by the value from the Cb column, summing up the results of the products, and subtracting the coefficient of the objective function from their sum, with this variable.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 0) + (0 * 0) + (3 * 1) + (4 * 0) + (-M * 0) ) - 3 = 0;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (3 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * -0.4) + (0 * 0) + (3 * 0.2) + (4 * 0) + (-M * 0) ) - 0 = 0.6;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * -0.3) + (0 * 0) + (3 * 0.4) + (4 * -0.5) + (-M * 0) ) - 0 = -0.8;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * 0.3) + (0 * 0) + (3 * -0.4) + (4 * 0.5) + (-M * 0) ) - -M = M+0.8;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Q column items

Since there are negative values ​​among the estimates of the controlled variables, the current table does not yet have an optimal solution. Therefore, in the basis we introduce the variable with the smallest negative estimate.

The number of variables in the basis is always constant, so it is necessary to choose which variable to derive from the basis, for which we calculate Q.

The elements of the Q column are calculated by dividing the values ​​from column P by the value from the column corresponding to the variable that is entered in the basis:

Q1 = P1 / x1,6 = 245 / -0.3 = -816.67;

Q2 = P2 / x2,6 = 225 / 0 = ∞;

Q3 = P3 / x3,6 = 140 / 0.4 = 350;

Q4 = P4 / x4,6 = 75 / -0.5 = -150;

Q5 = P5 / x5,6 = 0 / 0 = ∞;

We deduce from the basis the variable with the least positive value of Q.

At the intersection of the line that corresponds to the variable that is derived from the basis, and the column that corresponds to the variable that is entered into the basis, is the resolving element.

This element will allow us to calculate the elements of the table of the next iteration.

Iteration: 4

BCbPx1x2x3x4x5x6x7x8x9Q
3400000-M-M
x303500.75010-0.250000
x40225000100000
x603502.50000.510-10
x242501.251000.250000
x9-M0000000-101
max1000200010MM0

Calculation of table elements:arrow down description
Elements of the column basis (B)

For the results of the calculations of the previous iteration, we remove the variable from the basis x1 and put in her place x6. All other cells remain unchanged.

Cb column items

Each cell of this column is equal to the coefficient, which corresponds to the base variable in the corresponding row.

Cb1 = 0;

Cb2 = 0;

Cb3 = 0;

Cb4 = 4;

Cb5 = -M;

Values ​​of variable variables and column P(The data from the previous iteration is taken as the initial data)

Fill all cells with zeros corresponding to the variable that has just been entered into the basis:(The resolution element remains unchanged)

x1,6 = 0;

x2,6 = 0;

x4,6 = 0;

x5,6 = 0;

We transfer the row with the resolving element from the previous table into the current table, elementwise dividing its values ​​into the resolving element:

P3 = P3 / x3,6 = 140 / 0.4 = 350;

x3,1 = x3,1 / x3,6 = 1 / 0.4 = 2.5;

x3,2 = x3,2 / x3,6 = 0 / 0.4 = 0;

x3,3 = x3,3 / x3,6 = 0 / 0.4 = 0;

x3,4 = x3,4 / x3,6 = 0 / 0.4 = 0;

x3,5 = x3,5 / x3,6 = 0.2 / 0.4 = 0.5;

x3,6 = x3,6 / x3,6 = 0.4 / 0.4 = 1;

x3,7 = x3,7 / x3,6 = 0 / 0.4 = 0;

x3,8 = x3,8 / x3,6 = -0.4 / 0.4 = -1;

x3,9 = x3,9 / x3,6 = 0 / 0.4 = 0;

The remaining empty cells, except for the row of estimates and the column Q, are calculated using the rectangle method, relative to the resolving element:

P1 = (P1 * x3,6) - (x1,6 * P3) / x3,6 = ((245 * 0.4) - (-0.3 * 140)) / 0.4 = 350;

P2 = (P2 * x3,6) - (x2,6 * P3) / x3,6 = ((225 * 0.4) - (0 * 140)) / 0.4 = 225;

P4 = (P4 * x3,6) - (x4,6 * P3) / x3,6 = ((75 * 0.4) - (-0.5 * 140)) / 0.4 = 250;

P5 = (P5 * x3,6) - (x5,6 * P3) / x3,6 = ((0 * 0.4) - (0 * 140)) / 0.4 = 0;

x1,1 = ((x1,1 * x3,6) - (x1,6 * x3,1)) / x3,6 = ((0 * 0.4) - (-0.3 * 1)) / 0.4 = 0.75;

x1,2 = ((x1,2 * x3,6) - (x1,6 * x3,2)) / x3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x1,3 = ((x1,3 * x3,6) - (x1,6 * x3,3)) / x3,6 = ((1 * 0.4) - (-0.3 * 0)) / 0.4 = 1;

x1,4 = ((x1,4 * x3,6) - (x1,6 * x3,4)) / x3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x1,5 = ((x1,5 * x3,6) - (x1,6 * x3,5)) / x3,6 = ((-0.4 * 0.4) - (-0.3 * 0.2)) / 0.4 = -0.25;

x1,6 = ((x1,6 * x3,6) - (x1,6 * x3,6)) / x3,6 = ((-0.3 * 0.4) - (-0.3 * 0.4)) / 0.4 = 0;

x1,8 = ((x1,8 * x3,6) - (x1,6 * x3,8)) / x3,6 = ((0.3 * 0.4) - (-0.3 * -0.4)) / 0.4 = 0;

x1,9 = ((x1,9 * x3,6) - (x1,6 * x3,9)) / x3,6 = ((0 * 0.4) - (-0.3 * 0)) / 0.4 = 0;

x2,1 = ((x2,1 * x3,6) - (x2,6 * x3,1)) / x3,6 = ((0 * 0.4) - (0 * 1)) / 0.4 = 0;

x2,2 = ((x2,2 * x3,6) - (x2,6 * x3,2)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x2,3 = ((x2,3 * x3,6) - (x2,6 * x3,3)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x2,4 = ((x2,4 * x3,6) - (x2,6 * x3,4)) / x3,6 = ((1 * 0.4) - (0 * 0)) / 0.4 = 1;

x2,5 = ((x2,5 * x3,6) - (x2,6 * x3,5)) / x3,6 = ((0 * 0.4) - (0 * 0.2)) / 0.4 = 0;

x2,6 = ((x2,6 * x3,6) - (x2,6 * x3,6)) / x3,6 = ((0 * 0.4) - (0 * 0.4)) / 0.4 = 0;

x2,8 = ((x2,8 * x3,6) - (x2,6 * x3,8)) / x3,6 = ((0 * 0.4) - (0 * -0.4)) / 0.4 = 0;

x2,9 = ((x2,9 * x3,6) - (x2,6 * x3,9)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x4,1 = ((x4,1 * x3,6) - (x4,6 * x3,1)) / x3,6 = ((0 * 0.4) - (-0.5 * 1)) / 0.4 = 1.25;

x4,2 = ((x4,2 * x3,6) - (x4,6 * x3,2)) / x3,6 = ((1 * 0.4) - (-0.5 * 0)) / 0.4 = 1;

x4,3 = ((x4,3 * x3,6) - (x4,6 * x3,3)) / x3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x4,4 = ((x4,4 * x3,6) - (x4,6 * x3,4)) / x3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x4,5 = ((x4,5 * x3,6) - (x4,6 * x3,5)) / x3,6 = ((0 * 0.4) - (-0.5 * 0.2)) / 0.4 = 0.25;

x4,6 = ((x4,6 * x3,6) - (x4,6 * x3,6)) / x3,6 = ((-0.5 * 0.4) - (-0.5 * 0.4)) / 0.4 = 0;

x4,8 = ((x4,8 * x3,6) - (x4,6 * x3,8)) / x3,6 = ((0.5 * 0.4) - (-0.5 * -0.4)) / 0.4 = 0;

x4,9 = ((x4,9 * x3,6) - (x4,6 * x3,9)) / x3,6 = ((0 * 0.4) - (-0.5 * 0)) / 0.4 = 0;

x5,1 = ((x5,1 * x3,6) - (x5,6 * x3,1)) / x3,6 = ((0 * 0.4) - (0 * 1)) / 0.4 = 0;

x5,2 = ((x5,2 * x3,6) - (x5,6 * x3,2)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x5,3 = ((x5,3 * x3,6) - (x5,6 * x3,3)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x5,4 = ((x5,4 * x3,6) - (x5,6 * x3,4)) / x3,6 = ((0 * 0.4) - (0 * 0)) / 0.4 = 0;

x5,5 = ((x5,5 * x3,6) - (x5,6 * x3,5)) / x3,6 = ((0 * 0.4) - (0 * 0.2)) / 0.4 = 0;

x5,6 = ((x5,6 * x3,6) - (x5,6 * x3,6)) / x3,6 = ((0 * 0.4) - (0 * 0.4)) / 0.4 = 0;

x5,8 = ((x5,8 * x3,6) - (x5,6 * x3,8)) / x3,6 = ((0 * 0.4) - (0 * -0.4)) / 0.4 = 0;

x5,9 = ((x5,9 * x3,6) - (x5,6 * x3,9)) / x3,6 = ((1 * 0.4) - (0 * 0)) / 0.4 = 1;

Objective function value

We calculate the value of the objective function by elementwise multiplying the column Cb by the column P, adding the results of the products.

MaxP = (Cb1 * P1) + (Cb11 * P2 + (Cb21 * P3 + (Cb31 * P4 + (Cb41 * P5 = (0 * 350) + (0 * 225) + (0 * 350) + (4 * 250) + (-M * 0) = 1000;

Evaluated Control Variables

We calculate the estimates for each controlled variable, by element-wise multiplying the value from the variable column, by the value from the Cb column, summing up the results of the products, and subtracting the coefficient of the objective function from their sum, with this variable.

Maxx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) + (Cb3 * x3,1) + (Cb4 * x4,1) + (Cb5 * x5,1) ) - kx1 = ((0 * 0.75) + (0 * 0) + (0 * 2.5) + (4 * 1.25) + (-M * 0) ) - 3 = 2;

Maxx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) + (Cb3 * x3,2) + (Cb4 * x4,2) + (Cb5 * x5,2) ) - kx2 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0) ) - 4 = 0;

Maxx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) + (Cb3 * x3,3) + (Cb4 * x4,3) + (Cb5 * x5,3) ) - kx3 = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) + (Cb3 * x3,4) + (Cb4 * x4,4) + (Cb5 * x5,4) ) - kx4 = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) + (Cb3 * x3,5) + (Cb4 * x4,5) + (Cb5 * x5,5) ) - kx5 = ((0 * -0.25) + (0 * 0) + (0 * 0.5) + (4 * 0.25) + (-M * 0) ) - 0 = 1;

Maxx6 = ((Cb1 * x1,6) + (Cb2 * x2,6) + (Cb3 * x3,6) + (Cb4 * x4,6) + (Cb5 * x5,6) ) - kx6 = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0) ) - 0 = 0;

Maxx7 = ((Cb1 * x1,7) + (Cb2 * x2,7) + (Cb3 * x3,7) + (Cb4 * x4,7) + (Cb5 * x5,7) ) - kx7 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1) ) - 0 = M;

Maxx8 = ((Cb1 * x1,8) + (Cb2 * x2,8) + (Cb3 * x3,8) + (Cb4 * x4,8) + (Cb5 * x5,8) ) - kx8 = ((0 * 0) + (0 * 0) + (0 * -1) + (4 * 0) + (-M * 0) ) - -M = M;

Maxx9 = ((Cb1 * x1,9) + (Cb2 * x2,9) + (Cb3 * x3,9) + (Cb4 * x4,9) + (Cb5 * x5,9) ) - kx9 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1) ) - -M = 0;

Result:

Since there are no negative values ​​among the estimates of the controlled variables, the current table has an optimal solution.

The value of the objective function:

F* = 1000

The variables that are present in the basis are equal to the corresponding cells of the column P, all other variables are equal to zero:

x1 = 0;

x2 = 250;

Result:

F* = 1000

X* = (0; 250)

Conventions:arrow down description
xi - we enter a variable into the basis;
xi
- print the variable from the base;
xi - permissive element;
xi - basic element;
B - basis;
Cb - coefficient at the base variable;
P - plan;