Skip to content

DA6. Simplex Algorithm

Statement

In your own words describe the operation of the simplex algorithm to implement a linear programming solution to the real-world problem described below.

Include one or two examples to explain your thought process to show what is occurring and how the methodology works. Demonstrate your understanding of the intricacies of the algorithm. Use APA citations and references for any sources used.

Problem Statement:

A store has requested a manufacturer to produce pants and sports jackets. The manufacturer has one week to fill the order. For materials, the manufacturer has 1,000m2 of cotton textile and 950m2 of polyester. Every pair of pants (1 unit) needs .5m2 of cotton and 2m2 of polyester. Every jacket needs 3m2 of cotton and 2m2 of polyester.

Each item produced must go through a final inspection process and the factory can only inspect a maximum of 500 units per week.

The price of the pants is fixed at $40 and the jacket at $75.

What is the number of pants and jackets that the manufacturer must give to the store so that these items obtain a maximum sale?

Answer

Introduction

Linear Programming involves choosing a course of action that will maximize or minimize a linear objective function, subject to a set of linear constraints. Simplex Method is a popular algorithm for solving linear programming problems; it is an algorithm that implements LP solutions (UoPeople, n.d.).

The text will explain in detail the operation of the simplex algorithm to implement a linear programming solution to the problem of maximizing the sale of pants and jackets for a manufacturer, and then conclude with the final solution.

Problem Formulation

Let’s denote p as the number of pants and j as the number of jackets. The objective function is to maximize the profit, which can be represented as:

P = 40p + 75j

And the constraints are:

0.5p + 3j <= 1000 (cotton constraint) 2p + 2j <= 950 (polyester constraint) p + j <= 500 (inspection constraint)

And the non-negativity constraints are:

p >= 0 j >= 0

Hence, the equations can be represented as:

-40p - 75j + P = 0 0.5p + 3j + s1 = 1000 2p + 2j + s2 = 950 p + j + s3 = 500

Initial Simplex Table

And the simplex table can be represented as:

j p s1 s2 s3 P R
s1 3 0.5 1 0 0 0 1000
s2 2 2 0 1 0 0 950
s3 1 1 0 0 1 0 500
P -75 -40 0 0 0 1 0

Iteration 1

Now, the pivot column is j (the column with the most negative value for P) and hence we divide R by the corresponding j to get the ratios:

j p s1 s2 s3 P R
s1 3 0.5 1 0 0 0 1000 (1000/3 = 333.33)
s2 2 2 0 1 0 0 950 (950/2 = 475)
s3 1 1 0 0 1 0 500 (500/1 = 500)
P -75 -40 0 0 0 1 0

Now, the pivot row is s1(the row with minimum R) and hence we need to make the pivot element 1, so we do the following operations 1/3R1 -> R1:

j p s1 s2 s3 P R
s1 1 ⅙ ⅓ 0 0 0 333
s2 2 2 0 1 0 0 950
s3 1 1 0 0 1 0 500
P -75 -40 0 0 0 1 0

Now, we need to make the other elements in the pivot column 0, so we do the following operations -2R1 + R2 -> R2, -R1 + R3 -> R3, and 75R1 + R4 -> R4:

j p s1 s2 s3 P RHS
s1 1 ⅙ ⅓ 0 0 0 333
s2 0 5/3 -⅔ 1 0 0 284
s3 0 ⅚ -⅓ 0 1 0 167
P 0 -27.5 25 0 0 1 24975

We still have a negative value in the P row, so we need to iterate again.

Iteration 2

Now, the pivot column is p (the column with the most negative value for P) and hence we divide R by the corresponding p to get the ratios:

j p s1 s2 s3 P R
s1 1 ⅙ ⅓ 0 0 0 333 (333/⅙ = 2000)
s2 0 5/3 -⅔ 1 0 0 284 (284/5/3 = 170.4)
s3 0 ⅚ -⅓ 0 1 0 167 (167/⅚ = 200)
P 0 -27.5 25 0 0 1 24975

Now, the pivot row is s2(the row with minimum R) and hence we need to make the pivot element 1, so we do the following operations 3/5R2 -> R2:

j p s1 s2 s3 P R
s1 1 ⅙ ⅓ 0 0 0 333
s2 0 1 -⅖ ⅗ 0 0 170.4
s3 0 ⅚ -⅓ 0 1 0 167
P 0 -27.5 25 0 0 1 24975

Now, we need to make the other elements in the pivot column 0, so we do the following operations -1/6R2 + R1 -> R1, -5/6R2 + R3 -> R3, and 27.5R2 + R4 -> R4:

j p s1 s2 s3 P R
s1 1 0 ⅖ -0/10 0 0 304.6
s2 0 1 -⅖ ⅗ 0 0 170.4
s3 0 0 0 -½ 1 0 25
P 0 0 14 33/2 0 1 29661

There are no negative values in the P row, so the solution is optimal, and no further iterations are needed. The maximum profit is $29661, and the number of pants and jackets are 304.6 and 170.4, respectively.

Conclusion

The simplex algorithm is an iterative method for solving linear programming problems. It starts with an initial feasible solution and iteratively moves to adjacent feasible solutions that improve the objective function value until an optimal solution is reached. The algorithm uses pivot operations to move between adjacent solutions and maintains a tableau to keep track of the current solution and the objective function value. The simplex algorithm is widely used in practice due to its efficiency and effectiveness in solving linear programming problems.

The number of pants and jackets that the manufacturer must give to the store to obtain a maximum sale is 305 and 170, respectively (after rounding). The maximum profit that can be obtained using P = 40p + 75j = 40(305) + 75(170) = $24950.

The final solution is:
Number of Pants 305
Number of Jackets 170
Maximum Profit $24950

References

‌