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.
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).
-x1 + x2 ≤ 2
x2 ≤ 5
x1, x2 ≥ 0
To solve the example, we will use our Big M method calculator.
Maximize: Z = 2X1 + 3X2
-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:
Maximize: Z = 2X1 + 3X2 + 0S1 + 0S2
-1X1 + 1X2 + 1S1 + 0S2 = 2
0X1 + 1X2 + 0S1 + 1S2 = 5
X1, X2, S1, S2 ≥ 0
Enter the variable X2 and the variable S1 leaves the base. The pivot element is 1
Enter the variable X1 and the variable S2 leaves the base. The pivot element is 1
The problem has an unlimited solution (not limited). The variable S1 must enter the base, but no variable can leave.