Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
ACTIVITY NO. 4
LINEAR PROGRAMMING SIMPLEX METHOD
PROBLEM:
Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
A metal fabricator manufacturers three types of windows. Each of the windows needs four processes.
The time taken on various machines differ due to the size of windows. The time taken and available hours are
given in the table below:
Window Type Cutting Heat Treating Forging Grinding
A 5 7 1 4
B 7 4 4 8
C 4 8 6 2
Available Time 20 24 28 22
The profit contribution for windows A, B, and C are $3, $4, and $5 respectively.
a. Formulate the problem and LP model
b. Solve the problem using simplex method (showing the steps) to maximize the profit
c. Determine the excess time available in each processes and by how much (use the excel solver and print
the result, then interpret.)
Answers:
WINDOW TYPE CUTTING HEAT TREATING FORGING GRINDING Profit
A 5 7 1 4 3
B 7 4 4 8 4
C 4 8 6 2 5
Available Time 20 24 28 22
DECISION VARIABLES:
Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
Let X1 = the number of window type A to be manufactured
Let X2 = the number of window type B to be manufactured
Let X3 = the number of window type C to be manufactured
OBJECTIVE FUNCTION:
Zmax = 3X1 + 4X2 + 5X3
NON-NEGATIVE:
X1; x2; X3 ≥ 0
CONSTRAINTS:
Cutting 5X1 + 7X2 + 4X3≤ 20
Heat Treating 7X1 + 4X2 + 8X3≤ 24
Forging X1 + 4X2 + 6X3≤ 28
Grinding 4X1 + 8X2 + 2X3≤ 22
LINEAR PROGRAMMING MODEL:
Maximize Z = 3X1 + 4X2 + 5X3
CONSTRAINTS WITH SLACK VARIABLES:
5X1 + 7X2 + 4X3 + S1= 20
7X1 + 4X2 + 8X3 + S2= 24
X1 + 4X2 + 6X3 + S3= 28
4X1 + 8X2 + 2X3 + S4= 22
Zmax = 3X1 + 4X2 + 5X3 + OS1 + OS2 + OS3 + OS4
Where X1; X2; X3 ≥ 0
Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
Table 1 - Coefficient of Variables
Iteration Basic Solution Minimum
X1 X2 X3 S1 S2 S3 S4
Number Variable Variable Ratio
0 S1 20 5 7 4 1 0 0 0
S2 24 7 4 8 0 1 0 0
S3 28 1 4 6 0 0 1 0
S4 22 4 8 2 0 0 0 1
Table 2
Iteration Basic Solution Minimum
X1 X2 X3 S1 S2 S3 S4
Number Variable Variable Kc Ratio
0 S1 20 5 7 4 1 0 0 0 5
Kr S2 24 7 4 8 0 1 0 0 3
0 S3 28 1 4 6 0 0 1 0 4.7
0 S4 22 4 8 2 0 0 0 1 11
-Zj 0 -3 -4 -5 0 0 0 0
Note:
Kc = column with the highest absolute value of variable which is a negative number = -5 (column X3)
Kr = one which contains the smallest positive ratio
S1 = 20 1= 5 S2 = 24 1= 3 S3 = 28 S1 = 22 1= 11
Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
1=
4 8 6 4.67 2
Kr = S2 = 3
Note:
Pivotal Element = 8 value found in the intersection of Kr and Kc
.125R1
X1 X2 X3 S1 S2 S3 S4 P
5 7 4 1 0 0 0 0 20
.88 .50 1 0 .13 0 0 0 3
1 4 6 0 0 1 0 0 28
4 8 2 0 0 0 1 0 22
-3 -4 -5 0 0 0 0 0 0
-4R2 + R1
X1 X2 X3 S1 S2 S3 S4 P
1.5 5 0 1 -0.50 0 0 0 8
.88 .50 1 0 .13 0 0 0 3
1 4 6 0 0 1 0 0 28
4 8 2 0 0 0 1 0 22
-3 -4 -5 0 0 0 0 1 0
Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
-6R2 + R2
X1 X2 X3 S1 S2 S3 S4 P
1.5 5 0 1 -0.50 0 0 0 8
.88 .50 1 0 .13 0 0 0 3
-4.28 1 0 0 .78 1 0 0 10
4 8 2 0 0 0 1 0 22
-3 -4 -5 0 0 0 0 1 0
-2R2 + R4
X1 X2 X3 S1 S2 S3 S4 P
1.5 5 0 1 0.50 0 0 0 8
.88 .50 1 0 .13 0 0 0 3
-4.28 1 0 0 .78 1 0 0 10
2.25 7 0 0 .25 0 1 0 16
-3 -4 -5 0 0 0 0 1 0
5R2 + R5
X1 X2 X3 S1 S2 S3 S4 P
1.5 5 0 1 -0.50 0 0 0 8
.88 .50 1 0 .13 0 0 0 3
-4.28 1 0 0 -0.78 1 0 0 10
2.25 7 0 0 -0.25 0 1 0 16
1.40 -1.6 0 0 0.63 0 0 1 15
Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
5R2 + R5
X1 X2 X3 S1 S2 S3 S4 P
.30 1 0 .30 .30 0 0 0 1.6
.88 .50 1 0 .53 0 0 0 3
-4.24 1 0 0 0.78 1 0 0 10
2.25 7 0 0 0.25 0 1 0 16
1.40 -1.5 0 0 0.63 0 0 1 15
-5R2
X1 X2 X3 S1 S2 S3 S4 P
0.30 1 0 0.28 0.30 0 0 0 1.6
0.73 0 1 -0.10 0.17 0 0 0 2.2
-4.28 1 0 0 -0.78 1 0 0 10
2.25 7 0 0 -0.28 0 1 0 16
1.40 -1.5 0 0 0.63 0 0 1 15
-1R3
X1 X2 X3 S1 S2 S3 S4 P
0.30 1 0 0.20 0.10 0 0 0 1.60
0.73 0 1 -0.10 0.17 0 0 0 2.20
-4.28 0 0 -0.20 0.65 1 0 0 8.40
2.25 7 0 0 0.23 0 1 0 16
1.40 -1.5 0 0 0.63 0 0 1 15
Republic of the Philippines
PRESIDENT RAMON MAGSAYSAY STATE UNIVERSITY
formerly Ramon Magsaysay Technological University
Graduate School
Iba, Zambales
-7R4
X1 X2 X3 S1 S2 S3 S4 P
0.30 1 0 0.20 -0.10 0 0 0 1.60
0.73 0 1 -0.10 0.17 0 0 0 2.20
-4.58 0 0 -0.20 -0.68 1 0 0 8.40
0.15 0 0 -1.40 0.45 0 1 0 4.80
1.40 -1.5 0 0 0.63 0 0 1 15
1.5R2 + R5 = R5
X1 X2 X3 S1 S2 S3 S4 P
0.30 1 0 0.20 -0.10 0 0 0 1.60
0.73 0 1 -0.10 0.17 0 0 0 2.20
-4.50 0 0 -0.20 -0.65 1 0 0 8.40
0.15 0 0 -1.40 0.45 0 1 0 4.80
1.82 0 0 0.30 0.47 0 0 1 17.40
Maximum Profit: P 17.40
The maximum amount we would be prepared to pay for the machine. This is because if we pay more than this
amount, then, we will reduce our maximum profit