Linear Programming Using Simplex Method

Linear Programming using Simplex Method
Jenny furniture shop produces two types of tables: an elegant table and an ordinary
table. The table, whether elegant or ordinary, passes through two departments, namely, the
assembly department and finishing department. Each elegant table requires 8 hours of
assembly work and 4 hours of finishing department. Each ordinary table requires 6 hours in the
assembly department and 2 hours in the finishing department. Every production period, the
shop has 480 hours of assembly time and 200 hours of finishing time. The elegant table
contributes P700 to the company’s profit, while the ordinary table has a profit of P500.
Required. Determine the number of units needed to be produced to maximize profits.
Step 1 – construct the objective function and constraints of the problem
Let x – is number of units to be produced of elegant table
Y – is the number of units to be produced of ordinary table
Simple matrix
Hours required per unit
Department X Y Available Hours
Assembly department 8 6 480
Finishing department 4 2 200
Profit P700 P500
Objective function: Maximize profit P700x + P500y

Constraints: 8x + 6y ≤ 480
4x + 2y ≤ 200
Step 2 – converted the explicit constraints from inequalities to equalities
Objective function: Maximize profit P700x + P500y +0S1 + 0 S2
Constraints: 8x + 6y+ S1= 480
4x + 2y+ S2 = 200
Step 3 – prepare the simplex tableau and compute for the value of Cj, Zj and Cj-Zj
Table 1 Incoming column
Cj 700 500 0 0
Product/Variable Quantity/RHS x y S1 S2
0 S1 480 8 6 1 0
0 S2 200 4 2 0 1
Zj 0 0 0 0 0
Cj-Zj 700 500 0 0
Outgoing row
To compute Zj, multiply the profit contribution of S1 and S2 to the right-side value
S1 0 (480 8 6 1 0) = 0 0 0 0 0
+ S2 0 (200 4 2 0 1) = 0 0 0 0 0
Zj =00000
Step 4 – Check if the simplex tableau is need to improve (NOTE: tableau is need to improve if
the Cj-Zj has a positive value and greater than 0 and no need to improve if Cj-Zj has a negative
value and less than 0)
The table 1 show that there is a positive value and greater than 0, it means that the
table needs to improve.
Step 5 – Determine the incoming column and outgoing row

Incoming column is the column X that has highest value in Cj-Zj, with a value of 700.
Outgoing row is computed below, and find the lowest value of replacement ratio.
The outgoing row is row of S2 with the value of 50.
RHS Pivot Value Replacement Ration
S1 480 ÷ 8 60
S2 200 ÷ 4 50 lowest values
*** the pivot intersection is 4
Step 6 – improve the tableau and repeat step 3 Incoming column
Cj 700 500 0 0
0 S1 80 0 2 1 -2
700 x 50 1 0.50 0 0.25
Zj 35,000 700 350 0 175
Cj-Zj 0 150 0 -175
Outgoing row
To compute the new value of x, first get the old value of outgoing row (S2) and divide by the
pivot intersection.
S2 200 4 2 0 1
4
X = 50 1 0.05 0 0.25
To compute the new value of S1, get the old value of S1 and subtract by the new value of S1
S1 480 8 6 1 0 **note the above and below value of
pivot intersection should be equal to
- X 8(50 1 0.50 0 0.25)
zero
S1 480 8 6 1 0
- X 400 8 4 0 2
80 0 2 1 -2 new value of S1
S1 0 (80 0 2 1 -2) = 0 0 0 0 0
- + X 700 (50 1 0.50 0 0.25) = 35,000 700 350 0 175
Zj = 35,000 700 350 0 175
Step 7 – Check if the simplex tableau is need to improve (NOTE: tableau is need to improve if
the Cj-Zj has a positive value and greater than 0 and no need to improve if Cj-Zj has a negative
value and less than 0)
The table 2 show that there is a positive value and greater than 0, it means that the
table needs to improve.
Step 8 – Determine the incoming column and outgoing row

Incoming column is the column Y that has highest value in Cj-Zj, with a value of 150.
Outgoing row is computed below, and find the lowest value of replacement ratio.
The outgoing row is row of S1 with the value of 40.
RHS Pivot Value Replacement Ration
S1 80 ÷ 2 40 lowest values
X 50 ÷ 0.05 100
*** the pivot intersection is 2
Step 9 – Improve the tableau and repeat step 3.
Cj 700 500 0 0
500 y 40 0 1 0.50 -1
700 x 30 1 0 -0.25 0.75
Zj 41,000 700 500 -75 25
Cj-Zj 0 0 -75 -25
To compute the new value of y, first get the old value of outgoing row (S1) and divide by the
pivot intersection.
S1 80 0 2 1 -2
2
y = 40 0 1 0.5 -1
To compute the new value of X, get the old value of S1 and subtract by the new value of X
X 50 1 0.50 0 0.25 **note the above and below value of
pivot intersection should be equal to
- Y 0.5 (40 0 1 0.5 -1)
zero
X 50 1 0.50 0 0.25
- Y 20 0 0.50 0.25 -0.50
30 1 0 -0.25 0.75 new value of X
X 700 (30 1 0 -0.25 0.75) = 21,000 700 0 -175 525
- + Y 500 (40 0 1 0.50 -1) = 20,000 0 500 250 -500
Zj = 41,000 700 500 -75 25
To summary, the table 3 has negative value and less than to zero. It does not need to
improve. The optimal solution is to produce 30 elegant table and 40 ordinary table to realized a
profit of P41,000.

Linear Programming Using Simplex Method

Uploaded by

Copyright:

Available Formats

Linear Programming Using Simplex Method

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Linear Programming Using Simplex Method

Uploaded by

Copyright:

Available Formats

Linear Programming using Simplex Method

Objective function: Maximize profit P700x + P500y

Step 5 – Determine the incoming column and outgoing row

Step 6 – improve the tableau and repeat step 3 Incoming column

Step 8 – Determine the incoming column and outgoing row

You might also like