Question

Find the optimum solution to the following LP by using the Simplex Algorithm.

Min z = 3x1 – 2x2+ 3x3

s.t.
-x1 + 3x2 ≤ 3

x1 + 2x2 ≤ 6

x1, x2, x3≥ 0

a) Convert the LP into a maximization problem in standard form.

b) Construct the initial tableau and find a bfs.

c) Apply the Simplex Algorithm.

Answer 1

Elements of the column basis (B)

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

B1 = x4;

B2 = x5;

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 = 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 = 3;

P2 = 6;

x1,1 = -1;

x1,2 = 3;

x1,3 = 0;

x1,4 = 1;

x1,5 = 0;

x2,1 = 1;

x2,2 = 2;

x2,3 = 0;

x2,4 = 0;

x2,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.

MinP = (Cb1 * P01) + (Cb11 * P2 = (0 * 3) + (M * 6) = 6M;

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.

Minx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) ) - kx1 = ((0 * -1) + (M * 1) ) - 3 = M-3;

Minx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) ) - kx2 = ((0 * 3) + (M * 2) ) - -2 = 2M+2;

Minx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) ) - kx3 = ((0 * 0) + (M * 0) ) - 3 = -3;

Minx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) ) - kx4 = ((0 * 1) + (M * 0) ) - 0 = 0;

Minx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) ) - kx5 = ((0 * 0) + (M * 1) ) - M = 0;

Q column items

Since there are positive 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 highest positive 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 = 3 / 3 = 1;

Q2 = P2 / x2,2 = 6 / 2 = 3;

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.

Elements of the column basis (B)

For the results of the calculations of the previous iteration, we remove the variable from the basis x4 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 = -2;

Cb2 = 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)

x2,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:

P1 = P1 / x1,2 = 3 / 3 = 1;

x1,1 = x1,1 / x1,2 = -1 / 3 = -0.33;

x1,2 = x1,2 / x1,2 = 3 / 3 = 1;

x1,3 = x1,3 / x1,2 = 0 / 3 = 0;

x1,4 = x1,4 / x1,2 = 1 / 3 = 0.33;

x1,5 = x1,5 / x1,2 = 0 / 3 = 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:

P2 = (P2 * x1,2) - (x2,2 * P1) / x1,2 = ((6 * 3) - (2 * 3)) / 3 = 4;

x2,1 = ((x2,1 * x1,2) - (x2,2 * x1,1)) / x1,2 = ((1 * 3) - (2 * -1)) / 3 = 1.67;

x2,2 = ((x2,2 * x1,2) - (x2,2 * x1,2)) / x1,2 = ((2 * 3) - (2 * 3)) / 3 = 0;

x2,4 = ((x2,4 * x1,2) - (x2,2 * x1,4)) / x1,2 = ((0 * 3) - (2 * 1)) / 3 = -0.67;

x2,5 = ((x2,5 * x1,2) - (x2,2 * x1,5)) / x1,2 = ((1 * 3) - (2 * 0)) / 3 = 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.

MinP = (Cb1 * P01) + (Cb11 * P2 = (-2 * 1) + (M * 4) = 4M-2;

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.

Minx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) ) - kx1 = ((-2 * -0.33) + (M * 1.67) ) - 3 = 1.67M-2.33;

Minx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) ) - kx2 = ((-2 * 1) + (M * 0) ) - -2 = 0;

Minx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) ) - kx3 = ((-2 * 0) + (M * 0) ) - 3 = -3;

Minx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) ) - kx4 = ((-2 * 0.33) + (M * -0.67) ) - 0 = -0.67M-0.67;

Minx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) ) - kx5 = ((-2 * 0) + (M * 1) ) - M = 0;

Q column items

Since there are positive 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 highest positive 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 = 1 / -0.33 = -3;

Q2 = P2 / x2,1 = 4 / 1.67 = 2.4;

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.

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 = -2;

Cb2 = 3;

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;

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

P2 = P2 / x2,1 = 4 / 1.67 = 2.4;

x2,1 = x2,1 / x2,1 = 1.67 / 1.67 = 1;

x2,2 = x2,2 / x2,1 = 0 / 1.67 = 0;

x2,3 = x2,3 / x2,1 = 0 / 1.67 = 0;

x2,4 = x2,4 / x2,1 = -0.67 / 1.67 = -0.4;

x2,5 = x2,5 / x2,1 = 1 / 1.67 = 0.6;

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 * x2,1) - (x1,1 * P2) / x2,1 = ((1 * 1.67) - (-0.33 * 4)) / 1.67 = 1.8;

x1,1 = ((x1,1 * x2,1) - (x1,1 * x2,1)) / x2,1 = ((-0.33 * 1.67) - (-0.33 * 1.67)) / 1.67 = 0;

x1,3 = ((x1,3 * x2,1) - (x1,1 * x2,3)) / x2,1 = ((0 * 1.67) - (-0.33 * 0)) / 1.67 = 0;

x1,4 = ((x1,4 * x2,1) - (x1,1 * x2,4)) / x2,1 = ((0.33 * 1.67) - (-0.33 * -0.67)) / 1.67 = 0.2;

x1,5 = ((x1,5 * x2,1) - (x1,1 * x2,5)) / x2,1 = ((0 * 1.67) - (-0.33 * 1)) / 1.67 = 0.2;

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.

MinP = (Cb1 * P01) + (Cb11 * P2 = (-2 * 1.8) + (3 * 2.4) = 3.6;

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.

Minx1 = ((Cb1 * x1,1) + (Cb2 * x2,1) ) - kx1 = ((-2 * 0) + (3 * 1) ) - 3 = 0;

Minx2 = ((Cb1 * x1,2) + (Cb2 * x2,2) ) - kx2 = ((-2 * 1) + (3 * 0) ) - -2 = 0;

Minx3 = ((Cb1 * x1,3) + (Cb2 * x2,3) ) - kx3 = ((-2 * 0) + (3 * 0) ) - 3 = -3;

Minx4 = ((Cb1 * x1,4) + (Cb2 * x2,4) ) - kx4 = ((-2 * 0.2) + (3 * -0.4) ) - 0 = -1.6;

Minx5 = ((Cb1 * x1,5) + (Cb2 * x2,5) ) - kx5 = ((-2 * 0.2) + (3 * 0.6) ) - M = -M+1.4;

Answer:

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

The value of the objective function:

F* = 3.6;

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 = 2.4;

x2 = 1.8;

x3 = 0;

so the answers are

F* = 3.6

X* = (2.4; 1.8; 0)