Dual simplex method online calculator with steps

F =

x1

 +

x2

 +

x3

 +

x4

→

x1

 +

x2

 +

x3

 +

x4

x1

 +

x2

 +

x3

 +

x4

x1

 +

x2

 +

x3

 +

x4

x1

 +

x2

 +

x3

 +

x4

Solution comments
Without description (answer only)

a

b

c

d

x

y

z

AC

i

ab
x2
xn

Randomize

Number format
3131313131351515151515≈52188552198585858586
Round to
Digits after decimal point
10
=Solve

  About Dual simplex method calculator

Solve linear programming problems using the dual simplex method online with the simplex tableau and detailed step-by-step solution. 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 Dual simplex method?

The dual simplex method solves linear programs by exploiting the dual relationship to the standard simplex. It is particularly useful when the primal problem starts infeasible but dual-feasible — a situation that arises naturally after adding new constraints to an already-solved LP or when minimizing a problem with all-non-negative right-hand sides are negative. Unlike the primal simplex, which maintains primal feasibility throughout, the dual simplex maintains dual feasibility and drives the tableau toward primal feasibility.

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

Begin with a tableau that is dual-feasible (all reduced costs non-negative for a minimization problem) but not necessarily primal-feasible (some basic variables may be negative). At each iteration, apply the leaving-variable rule first: select the most negative basic variable as the leaving variable. Then apply the entering-variable rule: among all columns with a negative coefficient in the leaving row, choose the one with the smallest absolute ratio of reduced cost to that coefficient. Perform the pivot and repeat until all basic variables are non-negative, yielding the optimal primal-feasible solution.

  Example of solving a linear programming problem with the dual simplex method

Transition to a dual simplex
F(x) = 3x1+4x2 → max
2x1+x2 ≤ 600
≤ 225
5x1+4x2 ≤ 1000
-2x2 ≤ -150
≤ 0
Z(t) = 600t1+225t2+1000t3-150t4+0t5 → min
2t1+5t3 ≥ 3
t1+4t3-2t4 ≥ 4

Transition rules

1) The coefficients of the right side of the constraints of the direct problem become the coefficients of the objective function of the dual simplex;

2) The coefficients of the left side of the constraints of the dual simplex are formed by transposing the matrix of coefficients of the left side of the constraints of the direct problem;

3) The coefficients of the right-hand side of the constraints of the dual simplex are formed by the values ​​from the objective function of the direct problem with the corresponding controlled variables;

4) If F → max , than Z → min
If ≤ , than ≥
If = , than ≥

5) If F → min , than Z → max
If ≥ , than ≤
If = , than ≤

Description
F(x) = 600x1+225x2+1000x3-150x4+0x5 → min
F(x) = 600x1+225x2+1000x3-150x4+0x5+0x6+0x7+Mx8+Mx9 → min
2x1+5x3 ≥ 3
2x1+5x3-x6+x8 = 3
x1+4x3-2x4 ≥ 4
x1+4x3-2x4-x7+x9 = 4

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
2
Iteration 1
BCbPx1x2x3↓x4x5x6x7x8x9Q
6002251000-150000MM
x8←M320500-101035
x9M4104-200-1011
min7M3M-600-2259M-1000-2M+1500-M-M00

Elements of the column basis (B)

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

B1 = x8;

B2 = 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 = M;

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

x1,1 = 2;

x1,2 = 0;

x1,3 = 5;

x1,4 = 0;

x1,5 = 0;

x1,6 = -1;

x1,7 = 0;

x1,8 = 1;

x1,9 = 0;

x2,1 = 1;

x2,2 = 0;

x2,3 = 4;

x2,4 = -2;

x2,5 = 0;

x2,6 = 0;

x2,7 = -1;

x2,8 = 0;

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

MinP = (Cb1 * P1) + (Cb2 * P2) = (M * 3) + (M * 4) = 7M;

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 = ((M * 2) + (M * 1)) - 600 = 3M-600;

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

Minx3 = ((Cb1 * x1,3) + (Cb2 * x2,3)) - kx3 = ((M * 5) + (M * 4)) - 1000 = 9M-1000;

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

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

Minx6 = ((Cb1 * x1,6) + (Cb2 * x2,6)) - kx6 = ((M * -1) + (M * 0)) - 0 = -M;

Minx7 = ((Cb1 * x1,7) + (Cb2 * x2,7)) - kx7 = ((M * 0) + (M * -1)) - 0 = -M;

Minx8 = ((Cb1 * x1,8) + (Cb2 * x2,8)) - kx8 = ((M * 1) + (M * 0)) - M = 0;

Minx9 = ((Cb1 * x1,9) + (Cb2 * x2,9)) - kx9 = ((M * 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 = P1x1,3 = 35 = 35;

Q2 = P2x2,3 = 44 = 1;

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
3
Iteration 2
BCbPx1x2x3x4x5x6↓x7x8x9Q
6002251000-150000MM
x3100035250100-150150∞
x9←M135-3500-2045-1-4512
min135M+600-35M-200-2250-2M+150045M-200-M-145M+2000

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 x3. 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 = 1000;

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,3 = 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:

x1,1 = x1,1x1,3 = 25 = 25;

x1,2 = x1,2x1,3 = 05 = 0;

x1,3 = x1,3x1,3 = 55 = 1;

x1,4 = x1,4x1,3 = 05 = 0;

x1,5 = x1,5x1,3 = 05 = 0;

x1,6 = x1,6x1,3 = -15 = -15;

x1,7 = x1,7x1,3 = 05 = 0;

x1,8 = x1,8x1,3 = 15 = 15;

x1,9 = x1,9x1,3 = 05 = 0;

P1 = P1x1,3 = 35 = 35;

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:

x2,1 = (x2,1 * x1,3) - (x2,3 * x1,1)x1,3 = (1 * 5) - (4 * 2)5 = -35;

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

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

x2,5 = (x2,5 * x1,3) - (x2,3 * x1,5)x1,3 = (0 * 5) - (4 * 0)5 = 0;

x2,6 = (x2,6 * x1,3) - (x2,3 * x1,6)x1,3 = (0 * 5) - (4 * -1)5 = 45;

x2,7 = (x2,7 * x1,3) - (x2,3 * x1,7)x1,3 = (-1 * 5) - (4 * 0)5 = -1;

x2,8 = (x2,8 * x1,3) - (x2,3 * x1,8)x1,3 = (0 * 5) - (4 * 1)5 = -45;

x2,9 = (x2,9 * x1,3) - (x2,3 * x1,9)x1,3 = (1 * 5) - (4 * 0)5 = 1;

P2 = (P2 * x1,3) - (x2,3 * P1)x1,3 = (4 * 5) - (4 * 3)5 = 135;

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 * P1) + (Cb2 * P2) = (1000 * 35) + (M * 135) = 135M+600;

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 = ((1000 * 25) + (M * -35)) - 600 = -35M-200;

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

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

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

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

Minx6 = ((Cb1 * x1,6) + (Cb2 * x2,6)) - kx6 = ((1000 * -15) + (M * 45)) - 0 = 45M-200;

Minx7 = ((Cb1 * x1,7) + (Cb2 * x2,7)) - kx7 = ((1000 * 0) + (M * -1)) - 0 = -M;

Minx8 = ((Cb1 * x1,8) + (Cb2 * x2,8)) - kx8 = ((1000 * 15) + (M * -45)) - M = -145M+200;

Minx9 = ((Cb1 * x1,9) + (Cb2 * x2,9)) - kx9 = ((1000 * 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 = P1x1,6 = 35-15 = ∞;

Q2 = P2x2,6 = 13545 = 2;

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
4
Iteration 3
BCbPx1x2x3x4x5x6x7x8x9Q
6002251000-150000MM
x3100011401-1200-14014
x602-3400-21201-114-1114
min1000-350-2250-35000-250-M-M+250

Elements of the column basis (B)

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

Cb2 = 0;

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;

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

x2,1 = x2,1x2,6 = -3545 = -34;

x2,2 = x2,2x2,6 = 045 = 0;

x2,3 = x2,3x2,6 = 045 = 0;

x2,4 = x2,4x2,6 = -245 = -212;

x2,5 = x2,5x2,6 = 045 = 0;

x2,6 = x2,6x2,6 = 4545 = 1;

x2,7 = x2,7x2,6 = -145 = -114;

x2,8 = x2,8x2,6 = -4545 = -1;

x2,9 = x2,9x2,6 = 145 = 114;

P2 = P2x2,6 = 13545 = 2;

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:

x1,1 = (x1,1 * x2,6) - (x1,6 * x2,1)x2,6 = (25 * 45) - (-15 * -35)45 = 14;

x1,2 = (x1,2 * x2,6) - (x1,6 * x2,2)x2,6 = (0 * 45) - (-15 * 0)45 = 0;

x1,3 = (x1,3 * x2,6) - (x1,6 * x2,3)x2,6 = (1 * 45) - (-15 * 0)45 = 1;

x1,4 = (x1,4 * x2,6) - (x1,6 * x2,4)x2,6 = (0 * 45) - (-15 * -2)45 = -12;

x1,5 = (x1,5 * x2,6) - (x1,6 * x2,5)x2,6 = (0 * 45) - (-15 * 0)45 = 0;

x1,7 = (x1,7 * x2,6) - (x1,6 * x2,7)x2,6 = (0 * 45) - (-15 * -1)45 = -14;

x1,8 = (x1,8 * x2,6) - (x1,6 * x2,8)x2,6 = (15 * 45) - (-15 * -45)45 = 0;

x1,9 = (x1,9 * x2,6) - (x1,6 * x2,9)x2,6 = (0 * 45) - (-15 * 1)45 = 14;

P1 = (P1 * x2,6) - (x1,6 * P2)x2,6 = (35 * 45) - (-15 * 135)45 = 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 * P1) + (Cb2 * P2) = (1000 * 1) + (0 * 2) = 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.

Minx1 = ((Cb1 * x1,1) + (Cb2 * x2,1)) - kx1 = ((1000 * 14) + (0 * -34)) - 600 = -350;

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

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

Minx4 = ((Cb1 * x1,4) + (Cb2 * x2,4)) - kx4 = ((1000 * -12) + (0 * -212)) - -150 = -350;

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

Minx6 = ((Cb1 * x1,6) + (Cb2 * x2,6)) - kx6 = ((1000 * 0) + (0 * 1)) - 0 = 0;

Minx7 = ((Cb1 * x1,7) + (Cb2 * x2,7)) - kx7 = ((1000 * -14) + (0 * -114)) - 0 = -250;

Minx8 = ((Cb1 * x1,8) + (Cb2 * x2,8)) - kx8 = ((1000 * 0) + (0 * -1)) - M = -M;

Minx9 = ((Cb1 * x1,9) + (Cb2 * x2,9)) - kx9 = ((1000 * 14) + (0 * 114)) - M = -M+250;

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* = 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 = 0;

x3 = 1;

x4 = 0;

x5 = 0;

Description
Answer
F → max
F* = 1000
X* = (0; 0; 1; 0; 0)
Variables2Constraints5ObjectivemaxF*1000
Conventions
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;

  Frequently asked questions

What is the dual simplex method?

The dual simplex method keeps the optimality condition satisfied while restoring feasibility — the reverse of the primal simplex, which keeps feasibility and works toward optimality. It is useful when a starting basis is optimal but infeasible.

When should I use dual simplex instead of the primal simplex?

It is most efficient when you already have a dual-feasible (optimal but infeasible) basis — for example after adding a constraint to a solved problem, or during sensitivity analysis — because it can re-optimize without restarting from scratch.

How is the dual simplex related to the primal problem?

Every linear program has a dual. The dual simplex operates on the primal tableau but pivots according to dual feasibility. At the optimum the primal and dual objective values coincide (strong duality).

Does the dual simplex give the same optimum as the primal simplex?

Yes. For a problem with a finite optimum, both methods reach the same optimal objective value and an optimal solution; they differ only in the path taken through the tableaus.

  Related calculators

  Sources

Google PlayApp Store