Find the minimum and maximum values of the objective function calculator

Hotmath

• Home

A linear programming problem may be defined as the problem of maximizing or minimizing a linear function subject to system of linear constraints. The constraints may be equalities or inequalities. The linear function is called the objective function , of the form f ( x , y ) = a x + b y + c . The solution set of the system of inequalities is the set of possible or feasible solution , which are of the form ( x , y ) .

If a linear programming problem can be optimized, an optimal value will occur at one of the vertices of the region representing the set of feasible solutions.

For example, the maximum or minimum value of f ( x , y ) = a x + b y + c over the set of feasible solutions graphed occurs at point A , B , C , D , E or F .

When the graph of a system of inequalities forms a region that is closed, the region is said to be bounded. Sometimes a system of inequalities forms a region that is open. In this case, the region is called unbounded.

To solve a linear programming problem, follow these steps.

• Graph the region corresponding to the solution of the system of constraints.

• Find the coordinates of the vertices of the region formed.

• Evaluate the objective function at each vertex to determine which x - and y -values, if any, maximize or minimize the function.

Example:

Find the minimum value and maximum value of the objective function f ( x , y ) = 4 x + 5 y , subject to the following constraints.

{ x ≥ 0 y ≥ 0 x + y ≤ 6

Solution

First graph the region corresponding to the solution of the system of constraints.

Now find the coordinates of the vertices of the region formed.

The vertices are ( 0 , 0 ) , ( 0 , 6 ) , and ( 6 , 0 ) .

Evaluate the objective function at each vertex.

At ( 0 , 0 ) : f ( 0 , 0 ) = 4 ( 0 ) + 5 ( 0 ) = 0 , Minimum value of f ( x , y )

At ( 0 , 6 ) : f ( 0 , 6 ) = 4 ( 0 ) + 5 ( 6 ) = 30 , Maximum value of f ( x , y )

At ( 6 , 0 ) : f ( 6 , 0 ) = 4 ( 6 ) + 5 ( 0 ) = 24

So, the maximum value of f is 30 when x = 0 and y = 6 . The minimum value of f is 0 when x = 0 and y = 0 .

Solution example

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

F(x) = 3x1 + 4x2 + 0x3 + 0x4 + 0x5 + 0x6 + 0x7 - Mx8 - Mx9 → max

Preliminary stage:

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

Calculation of table elements:

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

Calculation of table elements:

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

Calculation of table elements:

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

Calculation of table elements:

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:

What is the maximum or the minimum value of an objective function?

What is the minimum value of the objective function?

What is the value of the objective function at maximum?