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.

Prev1 of 2

Example 1: Production Problem

The Gutchi Company manufactures purses, shaving bags, and backpacks. The construction of the three products requires leather and synthetic material, with leather being the limiting raw material.

The production process uses two types of skilled labor, sewing and finishing. The following table gives the availability of the resources, their usage by the three products, and the profits per unit

Resource requirements per unit
Resource Purse Bag Backpack Daily availability
Leather (ft2) 2 1 3 42
Sewing (hr) 2 1 2 40
Finishing (hr) 1 0.5 1 45
Profit ($) 24 22 45
  1. Formulate the problem as a linear program, and find the optimal solution.
  2. From the optimal solution, determine the state of each resource.

We got this problem from the book “Operations Research” by HAMDY A. TAHA. Chapter 3: Simplex Method and Sensitivity Analysis, Exercise 3.3B – 11. The Gutchi Company.

Solution

a. We define the variables:

  • x1 = number of purses per day.
  • x2=number of bags per day.
  • x3=number of backpacks per day.

The statement of the linear programming problem is:

Maximize Z=24x1+22x2+45x3

Subject to:
2x1+x2+3x3≤42
2x1+x2+2x3≤40
x1+0.5x2+x3≤45
x1, x2, x3≥0

To solve the problem, we use our online calculator of the simplex method:

Initial Table

Table 1 Cj 24 22 45 0 0 0
Cb Base X1 X2 X3 S1 S2 S3 R
0 S1 2 1 3 1 0 0 42
0 S2 2 1 2 0 1 0 40
0 S3 1 1/2 1 0 0 1 45
Z -24 -22 -45 0 0 0 0

Enter the variable X3 and the variable S1 leaves the base. The pivot element is 3

Iteration 1

Table 2 Cj 24 22 45 0 0 0
Cb Base X1 X2 X3 S1 S2 S3 R
45 X3 2/3 1/3 1 1/3 0 0 14
0 S2 2/3 1/3 0 -2/3 1 0 12
0 S3 1/3 1/6 0 -1/3 0 1 31
Z 6 -7 0 15 0 0 630

Enter the variable X2 and the variable S2 leaves the base. The pivot element is 1/3

Iteration 2

Table 3 Cj 24 22 45 0 0 0
Cb Base X1 X2 X3 S1 S2 S3 R
45 X3 0 0 1 1 -1 0 2
22 X2 2 1 0 -2 3 0 36
0 S3 0 0 0 0 -1/2 1 25
Z 20 0 0 1 21 0 882

The optimal solution is Z = 882

X1= 0, X2= 36, X3= 2, S1= 0, S2= 0, S3= 25

b. Status of Resources:

Resource Slack Status
Leather 0 Scarce
Sewing 0 Scarce
Finishing 25 Abundant
Prev1 of 2

Example 1: Production Problem