Simplex Method Examples 🥇 Maximization and Minimization Problems

The Simplex Method is a simple but powerful technique used in the field of optimization to solve maximization and minimization problems in linear programming. Here you will find simplex method examples to deepen your learning. To solve the problems, we will use our linear programming calculators.

The Simplex Method is an iterative algorithm, meaning that it uses a series of steps to find the optimal value of a function. It is based on two important assertions:

  • A convex polyhedron can represent the feasible set of any linear programming problem.
  • If a linear programming problem has a finite optimal solution, it will be at a vertex of the convex polyhedron representing the problem.

In the examples to be developed we will show step by step the iterations of the simplex algorithm, addressing problems with unlimited solutions, with an unfeasible solution, and cases of minimization and maximization. We will not address problems with artificial variables.

2 of 2Next

Example 2: Unbounded Solutions

In this example, we will solve a maximization problem with the simplex method, where the result will have unbounded solutions.

Unlimited solutions in the simplex method are presented when no variable can enter the base (the feasibility condition is not met).

Maximization 2x1+3x2

Subject to
-x1 + x2 ≤ 2
x2 ≤ 5
x1, x2 ≥ 0

To solve the example, we will use our Big M method calculator.

Solution

Objective Function:

Maximize: Z = 2X1 + 3X2

Subject to:

-1X1 + 1X2 ≤ 2

0X1 + 1X2 ≤ 5

X1, X2 ≥ 0

The problem will be adapted to the standard linear programming model, adding the slack, excess and / or artificial variables in each of the constraints:

  • Constraint 1: It has a sign “≤” (less than or equal) so the slack variable will be added S1.
  • Constraint 2: It has a sign “≤” (less than or equal) so the slack variable will be added S2.

The problem is shown below in standard form. The coefficient 0 (zero) will be placed where it corresponds to create our table:

Objective Function:

Maximize: Z = 2X1 + 3X2 + 0S1 + 0S2

Subject to:

-1X1 + 1X2 + 1S1 + 0S2 = 2

0X1 + 1X2 + 0S1 + 1S2 = 5

X1, X2, S1, S2 ≥ 0

Initial Table

Table 1 Cj 2 3 0 0
Cb Base X1 X2 S1 S2 R
0 S1 -1 1 1 0 2
0 S2 0 1 0 1 5
Z -2 -3 0 0 0

Enter the variable X2 and the variable S1 leaves the base. The pivot element is 1

Iteration 1

Table 2 Cj 2 3 0 0
Cb Base X1 X2 S1 S2 R
3 X2 -1 1 1 0 2
0 S2 1 0 -1 1 3
Z -5 0 3 0 6

Enter the variable X1 and the variable S2 leaves the base. The pivot element is 1

Iteration 2

Table 3 Cj 2 3 0 0
Cb Base X1 X2 S1 S2 R
3 X2 0 1 0 1 5
2 X1 1 0 -1 1 3
Z 0 0 -2 5 21

The problem has an unlimited solution (not limited). The variable S1 must enter the base, but no variable can leave.

2 of 2Next

Example 2: Unbounded Solutions