Simplex method online calculator with steps

The number of constraints:

The number of variables:

F =

matrixF,0,0,matrix

x₁

matrixF,0,1,matrix

x₂

matrixF,0,2,matrix

x₃

matrixF,0,3,matrix

x₄

→

matrixA,0,0,matrix

x₁

matrixA,0,1,matrix

x₂

matrixA,0,2,matrix

x₃

matrixA,0,3,matrix

x₄

matrixA,0,4,matrix

matrixA,1,0,matrix

x₁

matrixA,1,1,matrix

x₂

matrixA,1,2,matrix

x₃

matrixA,1,3,matrix

x₄

matrixA,1,4,matrix

matrixA,2,0,matrix

x₁

matrixA,2,1,matrix

x₂

matrixA,2,2,matrix

x₃

matrixA,2,3,matrix

x₄

matrixA,2,4,matrix

matrixA,3,0,matrix

x₁

matrixA,3,1,matrix

x₂

matrixA,3,2,matrix

x₃

matrixA,3,3,matrix

x₄

matrixA,3,4,matrix

=Solve

About Simplex method calculator

Solve linear programming problems with the simplex method online. Maximize or minimize an objective function under linear constraints with step-by-step iterations and the big-M method. with complete, detailed, step-by-step description of solutions, that solves linear-programming problems up to 20×20 in size with coefficients of this type: decimal numbers and fractions.

To start the calculation, you need to first enter the problem dimensions in the input fields at the very top of the screen, and also choose the desired operation from the side menu.

A little below you will find an input window where you need to enter the coefficients, constraints, and right-hand-side values using the keyboard. The input control panel is also located here, which simplifies work with LP problems and contains the following control elements:

The first element allows you to expand the input window. This can be especially useful when the tableau does not fit completely on the screen. If the table is still not fully visible after expanding the window, you can change the scale using the + / - buttons;
The second element copies the current problem input to the memory buffer. This can be useful when you frequently solve the same LP problem or need to transfer data between operations;
And the last element pastes the previously copied input, which allows you to restore problem data in just a few clicks instead of re-entering it manually;

And further down you will find a toolbar that allows you to customize the calculator and make it easier to work with. It is visually divided into three parts, each of which is responsible for the following functionality:

The first part lets you select the number format used when displaying the solution result. You can also turn off step-by-step comments if you already understand the method and only need to check your own calculations, or hide the step-by-step solution entirely if you only need the final answer;
The second part contains buttons that let you modify the input table dimensions, clear individual coefficients or the entire input, and the main button with an equal sign that takes you to the solution screen. All these buttons are duplicated by keyboard shortcuts. Hover over a button to see the corresponding key in a tooltip. You can also use the arrow keys to move the cursor between input fields;
And the last part allows you to choose the number of digits after the decimal point for rounding non-integer results. A live preview shows how the rounded values will appear;

What is the Simplex method?

The simplex method is an algorithm for solving linear programming problems that seek to maximize or minimize a linear objective function subject to linear inequality and equality constraints, with all decision variables required to be non-negative. It works by moving along the edges of the feasible polytope from one basic feasible solution (vertex) to an adjacent one with a better objective value. Greater-than or equality constraints are handled by introducing artificial variables penalized with the Big-M sentinel.

How to solve a linear programming problem with the simplex method?

First, convert the LP to standard (tableau) form by adding slack, surplus, and artificial variables to transform all constraints into equalities and establish an initial basis. At each iteration, apply the pivot rule: select the most negative reduced cost coefficient in the objective row as the entering variable, then use the minimum-ratio test to choose the leaving variable. Perform the pivot operation to update the tableau, bringing the entering variable into the basis. Repeat until all reduced costs in the objective row are non-negative, at which point the current basic feasible solution is optimal.

Example of solving a linear programming problem with the simplex method

F(x) = 3x₁+4x₂ → max

F(x) = 3x₁+4x₂+0x₃+0x₄+0x₅+0x₆+0x₇-Mx₈-Mx₉ → max

2x₁+x₂ ≤ 600

2x₁+x₂+x₃ = 600

≤ 225

+x₄ = 225

5x₁+4x₂ ≤ 1000

5x₁+4x₂+x₅ = 1000

2x₂ ≥ 150

2x₂-x₆+x₈ = 150

≥ 0

-x₇+x₉ = 0

The preliminary stage begins with the need to get rid of negative values 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.

Description

Iteration 1

B	Cb	P	x₁	x₂↓	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
B	Cb	P	3	4	0	0	0	0	0	-M	-M	Q
x₃	0	600	2	1	1	0	0	0	0	0	0	600
x₄	0	225	0	0	0	1	0	0	0	0	0	∞
x₅	0	1000	5	4	0	0	1	0	0	0	0	250
x₈←	-M	150	0	2	0	0	0	-1	0	1	0	75
x₉	-M	0	0	0	0	0	0	0	-1	0	1	∞
max		-150M	-3	-2M-4	0	0	0	M	M	0	0

Elements of the column basis (B)

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

B₁ = x₃;

B₂ = x₄;

B₃ = x₅;

B₄ = x₈;

B₅ = x₉;

Cb column items

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

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 0;

Cb₄ = -M;

Cb₅ = -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:

P₁ = 600;

P₂ = 225;

P₃ = 1000;

P₄ = 150;

P₅ = 0;

x_1,1 = 2;

x_1,2 = 1;

x_1,3 = 1;

x_1,4 = 0;

x_1,5 = 0;

x_1,6 = 0;

x_1,7 = 0;

x_1,8 = 0;

x_1,9 = 0;

x_2,1 = 0;

x_2,2 = 0;

x_2,3 = 0;

x_2,4 = 1;

x_2,5 = 0;

x_2,6 = 0;

x_2,7 = 0;

x_2,8 = 0;

x_2,9 = 0;

x_3,1 = 5;

x_3,2 = 4;

x_3,3 = 0;

x_3,4 = 0;

x_3,5 = 1;

x_3,6 = 0;

x_3,7 = 0;

x_3,8 = 0;

x_3,9 = 0;

x_4,1 = 0;

x_4,2 = 2;

x_4,3 = 0;

x_4,4 = 0;

x_4,5 = 0;

x_4,6 = -1;

x_4,7 = 0;

x_4,8 = 1;

x_4,9 = 0;

x_5,1 = 0;

x_5,2 = 0;

x_5,3 = 0;

x_5,4 = 0;

x_5,5 = 0;

x_5,6 = 0;

x_5,7 = -1;

x_5,8 = 0;

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

Max_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) + (Cb₄ * P₄) + (Cb₅ * P₅) = (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.

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1)) - k_x₁ = ((0 * 2) + (0 * 0) + (0 * 5) + (-M * 0) + (-M * 0)) - 3 = -3;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2)) - k_x₂ = ((0 * 1) + (0 * 0) + (0 * 4) + (-M * 2) + (-M * 0)) - 4 = -2M-4;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3)) - k_x₃ = ((0 * 1) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * 0)) - 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4)) - k_x₄ = ((0 * 0) + (0 * 1) + (0 * 0) + (-M * 0) + (-M * 0)) - 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5)) - k_x₅ = ((0 * 0) + (0 * 0) + (0 * 1) + (-M * 0) + (-M * 0)) - 0 = 0;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6)) - k_x₆ = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * -1) + (-M * 0)) - 0 = M;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7)) - k_x₇ = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 0) + (-M * -1)) - 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8)) - k_x₈ = ((0 * 0) + (0 * 0) + (0 * 0) + (-M * 1) + (-M * 0)) - -M = 0;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9)) - k_x₉ = ((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:

Q₁ = P₁x_1,2 = 6001 = 600;

Q₂ = P₂x_2,2 = 2250 = ∞;

Q₃ = P₃x_3,2 = 10004 = 250;

Q₄ = P₄x_4,2 = 1502 = 75;

Q₅ = P₅x_5,2 = 00 = ∞;

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.

Description

Iteration 2

B	Cb	P	x₁↓	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
B	Cb	P	3	4	0	0	0	0	0	-M	-M	Q
x₃	0	525	2	0	1	0	0	12	0	-12	0	26212
x₄	0	225	0	0	0	1	0	0	0	0	0	∞
x₅←	0	700	5	0	0	0	1	2	0	-2	0	140
x₂	4	75	0	1	0	0	0	-12	0	12	0	∞
x₉	-M	0	0	0	0	0	0	0	-1	0	1	∞
max		300	-3	0	0	0	0	-2	M	M+2	0

Elements of the column basis (B)

For the results of the calculations of the previous iteration, we remove the variable from the basis x₈ and put in her place x₂. 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.

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 0;

Cb₄ = 4;

Cb₅ = -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)

x_1,2 = 0;

x_2,2 = 0;

x_3,2 = 0;

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

x_4,1 = x_4,1x_4,2 = 02 = 0;

x_4,2 = x_4,2x_4,2 = 22 = 1;

x_4,3 = x_4,3x_4,2 = 02 = 0;

x_4,4 = x_4,4x_4,2 = 02 = 0;

x_4,5 = x_4,5x_4,2 = 02 = 0;

x_4,6 = x_4,6x_4,2 = -12 = -12;

x_4,7 = x_4,7x_4,2 = 02 = 0;

x_4,8 = x_4,8x_4,2 = 12 = 12;

x_4,9 = x_4,9x_4,2 = 02 = 0;

P₄ = P₄x_4,2 = 1502 = 75;

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:

x_1,1 = (x_1,1 * x_4,2) - (x_1,2 * x_4,1)x_4,2 = (2 * 2) - (1 * 0)2 = 2;

x_1,3 = (x_1,3 * x_4,2) - (x_1,2 * x_4,3)x_4,2 = (1 * 2) - (1 * 0)2 = 1;

x_1,4 = (x_1,4 * x_4,2) - (x_1,2 * x_4,4)x_4,2 = (0 * 2) - (1 * 0)2 = 0;

x_1,5 = (x_1,5 * x_4,2) - (x_1,2 * x_4,5)x_4,2 = (0 * 2) - (1 * 0)2 = 0;

x_1,6 = (x_1,6 * x_4,2) - (x_1,2 * x_4,6)x_4,2 = (0 * 2) - (1 * -1)2 = 12;

x_1,7 = (x_1,7 * x_4,2) - (x_1,2 * x_4,7)x_4,2 = (0 * 2) - (1 * 0)2 = 0;

x_1,8 = (x_1,8 * x_4,2) - (x_1,2 * x_4,8)x_4,2 = (0 * 2) - (1 * 1)2 = -12;

x_1,9 = (x_1,9 * x_4,2) - (x_1,2 * x_4,9)x_4,2 = (0 * 2) - (1 * 0)2 = 0;

P₁ = (P₁ * x_4,2) - (x_1,2 * P₄)x_4,2 = (600 * 2) - (1 * 150)2 = 525;

x_2,1 = (x_2,1 * x_4,2) - (x_2,2 * x_4,1)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_2,3 = (x_2,3 * x_4,2) - (x_2,2 * x_4,3)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_2,4 = (x_2,4 * x_4,2) - (x_2,2 * x_4,4)x_4,2 = (1 * 2) - (0 * 0)2 = 1;

x_2,5 = (x_2,5 * x_4,2) - (x_2,2 * x_4,5)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_2,6 = (x_2,6 * x_4,2) - (x_2,2 * x_4,6)x_4,2 = (0 * 2) - (0 * -1)2 = 0;

x_2,7 = (x_2,7 * x_4,2) - (x_2,2 * x_4,7)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_2,8 = (x_2,8 * x_4,2) - (x_2,2 * x_4,8)x_4,2 = (0 * 2) - (0 * 1)2 = 0;

x_2,9 = (x_2,9 * x_4,2) - (x_2,2 * x_4,9)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

P₂ = (P₂ * x_4,2) - (x_2,2 * P₄)x_4,2 = (225 * 2) - (0 * 150)2 = 225;

x_3,1 = (x_3,1 * x_4,2) - (x_3,2 * x_4,1)x_4,2 = (5 * 2) - (4 * 0)2 = 5;

x_3,3 = (x_3,3 * x_4,2) - (x_3,2 * x_4,3)x_4,2 = (0 * 2) - (4 * 0)2 = 0;

x_3,4 = (x_3,4 * x_4,2) - (x_3,2 * x_4,4)x_4,2 = (0 * 2) - (4 * 0)2 = 0;

x_3,5 = (x_3,5 * x_4,2) - (x_3,2 * x_4,5)x_4,2 = (1 * 2) - (4 * 0)2 = 1;

x_3,6 = (x_3,6 * x_4,2) - (x_3,2 * x_4,6)x_4,2 = (0 * 2) - (4 * -1)2 = 2;

x_3,7 = (x_3,7 * x_4,2) - (x_3,2 * x_4,7)x_4,2 = (0 * 2) - (4 * 0)2 = 0;

x_3,8 = (x_3,8 * x_4,2) - (x_3,2 * x_4,8)x_4,2 = (0 * 2) - (4 * 1)2 = -2;

x_3,9 = (x_3,9 * x_4,2) - (x_3,2 * x_4,9)x_4,2 = (0 * 2) - (4 * 0)2 = 0;

P₃ = (P₃ * x_4,2) - (x_3,2 * P₄)x_4,2 = (1000 * 2) - (4 * 150)2 = 700;

x_5,1 = (x_5,1 * x_4,2) - (x_5,2 * x_4,1)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_5,3 = (x_5,3 * x_4,2) - (x_5,2 * x_4,3)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_5,4 = (x_5,4 * x_4,2) - (x_5,2 * x_4,4)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_5,5 = (x_5,5 * x_4,2) - (x_5,2 * x_4,5)x_4,2 = (0 * 2) - (0 * 0)2 = 0;

x_5,6 = (x_5,6 * x_4,2) - (x_5,2 * x_4,6)x_4,2 = (0 * 2) - (0 * -1)2 = 0;

x_5,7 = (x_5,7 * x_4,2) - (x_5,2 * x_4,7)x_4,2 = (-1 * 2) - (0 * 0)2 = -1;

x_5,8 = (x_5,8 * x_4,2) - (x_5,2 * x_4,8)x_4,2 = (0 * 2) - (0 * 1)2 = 0;

x_5,9 = (x_5,9 * x_4,2) - (x_5,2 * x_4,9)x_4,2 = (1 * 2) - (0 * 0)2 = 1;

P₅ = (P₅ * x_4,2) - (x_5,2 * P₄)x_4,2 = (0 * 2) - (0 * 150)2 = 0;

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.

Max_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) + (Cb₄ * P₄) + (Cb₅ * P₅) = (0 * 525) + (0 * 225) + (0 * 700) + (4 * 75) + (-M * 0) = 300;

Evaluated Control Variables

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1)) - k_x₁ = ((0 * 2) + (0 * 0) + (0 * 5) + (4 * 0) + (-M * 0)) - 3 = -3;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2)) - k_x₂ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0)) - 4 = 0;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3)) - k_x₃ = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4)) - k_x₄ = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5)) - k_x₅ = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6)) - k_x₆ = ((0 * 12) + (0 * 0) + (0 * 2) + (4 * -12) + (-M * 0)) - 0 = -2;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7)) - k_x₇ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1)) - 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8)) - k_x₈ = ((0 * -12) + (0 * 0) + (0 * -2) + (4 * 12) + (-M * 0)) - -M = M+2;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9)) - k_x₉ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1)) - -M = 0;

Q column items

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:

Q₁ = P₁x_1,1 = 5252 = 26212;

Q₂ = P₂x_2,1 = 2250 = ∞;

Q₃ = P₃x_3,1 = 7005 = 140;

Q₄ = P₄x_4,1 = 750 = ∞;

Q₅ = P₅x_5,1 = 00 = ∞;

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

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

Description

Iteration 3

B	Cb	P	x₁	x₂	x₃	x₄	x₅	x₆↓	x₇	x₈	x₉	Q
B	Cb	P	3	4	0	0	0	0	0	-M	-M	Q
x₃	0	245	0	0	1	0	-25	-310	0	310	0	∞
x₄	0	225	0	0	0	1	0	0	0	0	0	∞
x₁←	3	140	1	0	0	0	15	25	0	-25	0	350
x₂	4	75	0	1	0	0	0	-12	0	12	0	∞
x₉	-M	0	0	0	0	0	0	0	-1	0	1	∞
max		720	0	0	0	0	35	-45	M	M+45	0

Elements of the column basis (B)

For the results of the calculations of the previous iteration, we remove the variable from the basis x₅ and put in her place x₁. 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.

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 3;

Cb₄ = 4;

Cb₅ = -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)

x_1,1 = 0;

x_2,1 = 0;

x_4,1 = 0;

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

x_3,1 = x_3,1x_3,1 = 55 = 1;

x_3,2 = x_3,2x_3,1 = 05 = 0;

x_3,3 = x_3,3x_3,1 = 05 = 0;

x_3,4 = x_3,4x_3,1 = 05 = 0;

x_3,5 = x_3,5x_3,1 = 15 = 15;

x_3,6 = x_3,6x_3,1 = 25 = 25;

x_3,7 = x_3,7x_3,1 = 05 = 0;

x_3,8 = x_3,8x_3,1 = -25 = -25;

x_3,9 = x_3,9x_3,1 = 05 = 0;

P₃ = P₃x_3,1 = 7005 = 140;

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:

x_1,2 = (x_1,2 * x_3,1) - (x_1,1 * x_3,2)x_3,1 = (0 * 5) - (2 * 0)5 = 0;

x_1,3 = (x_1,3 * x_3,1) - (x_1,1 * x_3,3)x_3,1 = (1 * 5) - (2 * 0)5 = 1;

x_1,4 = (x_1,4 * x_3,1) - (x_1,1 * x_3,4)x_3,1 = (0 * 5) - (2 * 0)5 = 0;

x_1,5 = (x_1,5 * x_3,1) - (x_1,1 * x_3,5)x_3,1 = (0 * 5) - (2 * 1)5 = -25;

x_1,6 = (x_1,6 * x_3,1) - (x_1,1 * x_3,6)x_3,1 = (12 * 5) - (2 * 2)5 = -310;

x_1,7 = (x_1,7 * x_3,1) - (x_1,1 * x_3,7)x_3,1 = (0 * 5) - (2 * 0)5 = 0;

x_1,8 = (x_1,8 * x_3,1) - (x_1,1 * x_3,8)x_3,1 = (-12 * 5) - (2 * -2)5 = 310;

x_1,9 = (x_1,9 * x_3,1) - (x_1,1 * x_3,9)x_3,1 = (0 * 5) - (2 * 0)5 = 0;

P₁ = (P₁ * x_3,1) - (x_1,1 * P₃)x_3,1 = (525 * 5) - (2 * 700)5 = 245;

x_2,2 = (x_2,2 * x_3,1) - (x_2,1 * x_3,2)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_2,3 = (x_2,3 * x_3,1) - (x_2,1 * x_3,3)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_2,4 = (x_2,4 * x_3,1) - (x_2,1 * x_3,4)x_3,1 = (1 * 5) - (0 * 0)5 = 1;

x_2,5 = (x_2,5 * x_3,1) - (x_2,1 * x_3,5)x_3,1 = (0 * 5) - (0 * 1)5 = 0;

x_2,6 = (x_2,6 * x_3,1) - (x_2,1 * x_3,6)x_3,1 = (0 * 5) - (0 * 2)5 = 0;

x_2,7 = (x_2,7 * x_3,1) - (x_2,1 * x_3,7)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_2,8 = (x_2,8 * x_3,1) - (x_2,1 * x_3,8)x_3,1 = (0 * 5) - (0 * -2)5 = 0;

x_2,9 = (x_2,9 * x_3,1) - (x_2,1 * x_3,9)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

P₂ = (P₂ * x_3,1) - (x_2,1 * P₃)x_3,1 = (225 * 5) - (0 * 700)5 = 225;

x_4,2 = (x_4,2 * x_3,1) - (x_4,1 * x_3,2)x_3,1 = (1 * 5) - (0 * 0)5 = 1;

x_4,3 = (x_4,3 * x_3,1) - (x_4,1 * x_3,3)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_4,4 = (x_4,4 * x_3,1) - (x_4,1 * x_3,4)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_4,5 = (x_4,5 * x_3,1) - (x_4,1 * x_3,5)x_3,1 = (0 * 5) - (0 * 1)5 = 0;

x_4,6 = (x_4,6 * x_3,1) - (x_4,1 * x_3,6)x_3,1 = (-12 * 5) - (0 * 2)5 = -12;

x_4,7 = (x_4,7 * x_3,1) - (x_4,1 * x_3,7)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_4,8 = (x_4,8 * x_3,1) - (x_4,1 * x_3,8)x_3,1 = (12 * 5) - (0 * -2)5 = 12;

x_4,9 = (x_4,9 * x_3,1) - (x_4,1 * x_3,9)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

P₄ = (P₄ * x_3,1) - (x_4,1 * P₃)x_3,1 = (75 * 5) - (0 * 700)5 = 75;

x_5,2 = (x_5,2 * x_3,1) - (x_5,1 * x_3,2)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_5,3 = (x_5,3 * x_3,1) - (x_5,1 * x_3,3)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_5,4 = (x_5,4 * x_3,1) - (x_5,1 * x_3,4)x_3,1 = (0 * 5) - (0 * 0)5 = 0;

x_5,5 = (x_5,5 * x_3,1) - (x_5,1 * x_3,5)x_3,1 = (0 * 5) - (0 * 1)5 = 0;

x_5,6 = (x_5,6 * x_3,1) - (x_5,1 * x_3,6)x_3,1 = (0 * 5) - (0 * 2)5 = 0;

x_5,7 = (x_5,7 * x_3,1) - (x_5,1 * x_3,7)x_3,1 = (-1 * 5) - (0 * 0)5 = -1;

x_5,8 = (x_5,8 * x_3,1) - (x_5,1 * x_3,8)x_3,1 = (0 * 5) - (0 * -2)5 = 0;

x_5,9 = (x_5,9 * x_3,1) - (x_5,1 * x_3,9)x_3,1 = (1 * 5) - (0 * 0)5 = 1;

P₅ = (P₅ * x_3,1) - (x_5,1 * P₃)x_3,1 = (0 * 5) - (0 * 700)5 = 0;

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.

Max_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) + (Cb₄ * P₄) + (Cb₅ * P₅) = (0 * 245) + (0 * 225) + (3 * 140) + (4 * 75) + (-M * 0) = 720;

Evaluated Control Variables

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1)) - k_x₁ = ((0 * 0) + (0 * 0) + (3 * 1) + (4 * 0) + (-M * 0)) - 3 = 0;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2)) - k_x₂ = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 1) + (-M * 0)) - 4 = 0;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3)) - k_x₃ = ((0 * 1) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4)) - k_x₄ = ((0 * 0) + (0 * 1) + (3 * 0) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5)) - k_x₅ = ((0 * -25) + (0 * 0) + (3 * 15) + (4 * 0) + (-M * 0)) - 0 = 35;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6)) - k_x₆ = ((0 * -310) + (0 * 0) + (3 * 25) + (4 * -12) + (-M * 0)) - 0 = -45;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7)) - k_x₇ = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * -1)) - 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8)) - k_x₈ = ((0 * 310) + (0 * 0) + (3 * -25) + (4 * 12) + (-M * 0)) - -M = M+45;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9)) - k_x₉ = ((0 * 0) + (0 * 0) + (3 * 0) + (4 * 0) + (-M * 1)) - -M = 0;

Q column items

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:

Q₁ = P₁x_1,6 = 245-310 = ∞;

Q₂ = P₂x_2,6 = 2250 = ∞;

Q₃ = P₃x_3,6 = 14025 = 350;

Q₄ = P₄x_4,6 = 75-12 = ∞;

Q₅ = P₅x_5,6 = 00 = ∞;

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

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

Description

Iteration 4

B	Cb	P	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	Q
B	Cb	P	3	4	0	0	0	0	0	-M	-M	Q
x₃	0	350	34	0	1	0	-14	0	0	0	0
x₄	0	225	0	0	0	1	0	0	0	0	0
x₆	0	350	212	0	0	0	12	1	0	-1	0
x₂	4	250	114	1	0	0	14	0	0	0	0
x₉	-M	0	0	0	0	0	0	0	-1	0	1
max		1000	2	0	0	0	1	0	M	M	0

Elements of the column basis (B)

For the results of the calculations of the previous iteration, we remove the variable from the basis x₁ and put in her place x₆. 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.

Cb₁ = 0;

Cb₂ = 0;

Cb₃ = 0;

Cb₄ = 4;

Cb₅ = -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)

x_1,6 = 0;

x_2,6 = 0;

x_4,6 = 0;

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

x_3,1 = x_3,1x_3,6 = 125 = 212;

x_3,2 = x_3,2x_3,6 = 025 = 0;

x_3,3 = x_3,3x_3,6 = 025 = 0;

x_3,4 = x_3,4x_3,6 = 025 = 0;

x_3,5 = x_3,5x_3,6 = 1525 = 12;

x_3,6 = x_3,6x_3,6 = 2525 = 1;

x_3,7 = x_3,7x_3,6 = 025 = 0;

x_3,8 = x_3,8x_3,6 = -2525 = -1;

x_3,9 = x_3,9x_3,6 = 025 = 0;

P₃ = P₃x_3,6 = 14025 = 350;

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:

x_1,1 = (x_1,1 * x_3,6) - (x_1,6 * x_3,1)x_3,6 = (0 * 25) - (-310 * 1)25 = 34;

x_1,2 = (x_1,2 * x_3,6) - (x_1,6 * x_3,2)x_3,6 = (0 * 25) - (-310 * 0)25 = 0;

x_1,3 = (x_1,3 * x_3,6) - (x_1,6 * x_3,3)x_3,6 = (1 * 25) - (-310 * 0)25 = 1;

x_1,4 = (x_1,4 * x_3,6) - (x_1,6 * x_3,4)x_3,6 = (0 * 25) - (-310 * 0)25 = 0;

x_1,5 = (x_1,5 * x_3,6) - (x_1,6 * x_3,5)x_3,6 = (-25 * 25) - (-310 * 15)25 = -14;

x_1,7 = (x_1,7 * x_3,6) - (x_1,6 * x_3,7)x_3,6 = (0 * 25) - (-310 * 0)25 = 0;

x_1,8 = (x_1,8 * x_3,6) - (x_1,6 * x_3,8)x_3,6 = (310 * 25) - (-310 * -25)25 = 0;

x_1,9 = (x_1,9 * x_3,6) - (x_1,6 * x_3,9)x_3,6 = (0 * 25) - (-310 * 0)25 = 0;

P₁ = (P₁ * x_3,6) - (x_1,6 * P₃)x_3,6 = (245 * 25) - (-310 * 140)25 = 350;

x_2,1 = (x_2,1 * x_3,6) - (x_2,6 * x_3,1)x_3,6 = (0 * 25) - (0 * 1)25 = 0;

x_2,2 = (x_2,2 * x_3,6) - (x_2,6 * x_3,2)x_3,6 = (0 * 25) - (0 * 0)25 = 0;

x_2,3 = (x_2,3 * x_3,6) - (x_2,6 * x_3,3)x_3,6 = (0 * 25) - (0 * 0)25 = 0;

x_2,4 = (x_2,4 * x_3,6) - (x_2,6 * x_3,4)x_3,6 = (1 * 25) - (0 * 0)25 = 1;

x_2,5 = (x_2,5 * x_3,6) - (x_2,6 * x_3,5)x_3,6 = (0 * 25) - (0 * 15)25 = 0;

x_2,7 = (x_2,7 * x_3,6) - (x_2,6 * x_3,7)x_3,6 = (0 * 25) - (0 * 0)25 = 0;

x_2,8 = (x_2,8 * x_3,6) - (x_2,6 * x_3,8)x_3,6 = (0 * 25) - (0 * -25)25 = 0;

x_2,9 = (x_2,9 * x_3,6) - (x_2,6 * x_3,9)x_3,6 = (0 * 25) - (0 * 0)25 = 0;

P₂ = (P₂ * x_3,6) - (x_2,6 * P₃)x_3,6 = (225 * 25) - (0 * 140)25 = 225;

x_4,1 = (x_4,1 * x_3,6) - (x_4,6 * x_3,1)x_3,6 = (0 * 25) - (-12 * 1)25 = 114;

x_4,2 = (x_4,2 * x_3,6) - (x_4,6 * x_3,2)x_3,6 = (1 * 25) - (-12 * 0)25 = 1;

x_4,3 = (x_4,3 * x_3,6) - (x_4,6 * x_3,3)x_3,6 = (0 * 25) - (-12 * 0)25 = 0;

x_4,4 = (x_4,4 * x_3,6) - (x_4,6 * x_3,4)x_3,6 = (0 * 25) - (-12 * 0)25 = 0;

x_4,5 = (x_4,5 * x_3,6) - (x_4,6 * x_3,5)x_3,6 = (0 * 25) - (-12 * 15)25 = 14;

x_4,7 = (x_4,7 * x_3,6) - (x_4,6 * x_3,7)x_3,6 = (0 * 25) - (-12 * 0)25 = 0;

x_4,8 = (x_4,8 * x_3,6) - (x_4,6 * x_3,8)x_3,6 = (12 * 25) - (-12 * -25)25 = 0;

x_4,9 = (x_4,9 * x_3,6) - (x_4,6 * x_3,9)x_3,6 = (0 * 25) - (-12 * 0)25 = 0;

P₄ = (P₄ * x_3,6) - (x_4,6 * P₃)x_3,6 = (75 * 25) - (-12 * 140)25 = 250;

x_5,1 = (x_5,1 * x_3,6) - (x_5,6 * x_3,1)x_3,6 = (0 * 25) - (0 * 1)25 = 0;

x_5,2 = (x_5,2 * x_3,6) - (x_5,6 * x_3,2)x_3,6 = (0 * 25) - (0 * 0)25 = 0;

x_5,3 = (x_5,3 * x_3,6) - (x_5,6 * x_3,3)x_3,6 = (0 * 25) - (0 * 0)25 = 0;

x_5,4 = (x_5,4 * x_3,6) - (x_5,6 * x_3,4)x_3,6 = (0 * 25) - (0 * 0)25 = 0;

x_5,5 = (x_5,5 * x_3,6) - (x_5,6 * x_3,5)x_3,6 = (0 * 25) - (0 * 15)25 = 0;

x_5,7 = (x_5,7 * x_3,6) - (x_5,6 * x_3,7)x_3,6 = (-1 * 25) - (0 * 0)25 = -1;

x_5,8 = (x_5,8 * x_3,6) - (x_5,6 * x_3,8)x_3,6 = (0 * 25) - (0 * -25)25 = 0;

x_5,9 = (x_5,9 * x_3,6) - (x_5,6 * x_3,9)x_3,6 = (1 * 25) - (0 * 0)25 = 1;

P₅ = (P₅ * x_3,6) - (x_5,6 * P₃)x_3,6 = (0 * 25) - (0 * 140)25 = 0;

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.

Max_P = (Cb₁ * P₁) + (Cb₂ * P₂) + (Cb₃ * P₃) + (Cb₄ * P₄) + (Cb₅ * P₅) = (0 * 350) + (0 * 225) + (0 * 350) + (4 * 250) + (-M * 0) = 1000;

Evaluated Control Variables

Max_x₁ = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) + (Cb₄ * x_4,1) + (Cb₅ * x_5,1)) - k_x₁ = ((0 * 34) + (0 * 0) + (0 * 212) + (4 * 114) + (-M * 0)) - 3 = 2;

Max_x₂ = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) + (Cb₄ * x_4,2) + (Cb₅ * x_5,2)) - k_x₂ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0)) - 4 = 0;

Max_x₃ = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) + (Cb₄ * x_4,3) + (Cb₅ * x_5,3)) - k_x₃ = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₄ = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) + (Cb₄ * x_4,4) + (Cb₅ * x_5,4)) - k_x₄ = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₅ = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) + (Cb₄ * x_4,5) + (Cb₅ * x_5,5)) - k_x₅ = ((0 * -14) + (0 * 0) + (0 * 12) + (4 * 14) + (-M * 0)) - 0 = 1;

Max_x₆ = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) + (Cb₄ * x_4,6) + (Cb₅ * x_5,6)) - k_x₆ = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0)) - 0 = 0;

Max_x₇ = ((Cb₁ * x_1,7) + (Cb₂ * x_2,7) + (Cb₃ * x_3,7) + (Cb₄ * x_4,7) + (Cb₅ * x_5,7)) - k_x₇ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1)) - 0 = M;

Max_x₈ = ((Cb₁ * x_1,8) + (Cb₂ * x_2,8) + (Cb₃ * x_3,8) + (Cb₄ * x_4,8) + (Cb₅ * x_5,8)) - k_x₈ = ((0 * 0) + (0 * 0) + (0 * -1) + (4 * 0) + (-M * 0)) - -M = M;

Max_x₉ = ((Cb₁ * x_1,9) + (Cb₂ * x_2,9) + (Cb₃ * x_3,9) + (Cb₄ * x_4,9) + (Cb₅ * x_5,9)) - k_x₉ = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1)) - -M = 0;

Answer

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:

x₁ = 0;

x₂ = 250;

Description

Answer

F → max

F* = 1000

X* = (0; 250)

Variables2Constraints5ObjectivemaxF*1000

Frequently asked questions

What is the simplex method used for?

The simplex method solves linear programming problems — maximizing or minimizing a linear objective function subject to linear inequality or equality constraints. It moves between vertices of the feasible region, improving the objective at each step until it reaches the optimum.

How does this calculator handle maximization versus minimization?

Choose "max" or "min" above the objective row. A minimization is solved internally by negating the objective and maximizing, so the reported optimum always matches the direction you selected.

What do "infeasible" and "unbounded" results mean?

"Infeasible" means no point satisfies every constraint at once, so there is no solution. "Unbounded" means the objective can grow without limit inside the feasible region, so no finite optimum exists. The calculator reports these instead of a numeric optimum.

Why are artificial variables and a large M used?

Constraints of type ≥ or = have no obvious starting basic feasible solution, so the method adds artificial variables and penalizes them with a large constant M in the objective. This Big-M penalty drives the artificial variables to zero, recovering a valid solution to the original problem.

Sources

Google Play App Store

x_i ↓	- we enter a variable into the basis;
x_i←	- print the variable from the base;
x_i	- permissive element;
x_i	- basic element;
B	- basis;
Cb	- coefficient at the base variable;
P	- plan;

About Simplex method calculator

What is the Simplex method?

How to solve a linear programming problem with the simplex method?

Example of solving a linear programming problem with the simplex method

Frequently asked questions

Related calculators

Sources