The table below shows the number of hours required in each of two departments to make one unit of various products A, B and C. For example, product B requires 1 hour of time in department I and 3 hours in department II.
HOURS REQUIRED PER UNIT OF PRODUCT
DEPARTMENT 1
A=1
B=1
C=9
DEPARTMENT 2
A=1
B=3
C=7
Find the number of units of A, B, and C which could be made if department I has 75 hours available and Department II has 65 hours available. It is necessary that all of the available hours be used.
Check your 7-11-11,12:31am post for solution.
To find the number of units of A, B, and C that can be made given the available hours in each department, we need to use a linear programming technique called the simplex method.
First, let's set up the linear programming problem:
Let X1 = number of units of product A
Let X2 = number of units of product B
Let X3 = number of units of product C
Objective function:
We want to maximize the total number of units produced, so the objective function is:
Z = X1 + X2 + X3
Constraints:
1) Department I hours constraint: Each unit of product requires a specific number of hours in Department I, so the constraint is:
1X1 + 1X2 + 9X3 <= 75
2) Department II hours constraint: Each unit of product requires a specific number of hours in Department II, so the constraint is:
1X1 + 3X2 + 7X3 <= 65
Non-negativity constraint:
X1, X2, and X3 must be greater than or equal to zero.
Now, we need to solve this linear programming problem using the simplex method. This involves constructing an initial feasible solution and then iteratively improving it.
Step 1: Convert the constraints into equations
1X1 + 1X2 + 9X3 + X4 = 75 (Department I hours constraint)
1X1 + 3X2 + 7X3 + X5 = 65 (Department II hours constraint)
Step 2: Set up the initial tableau
X1 X2 X3 X4 X5 RHS
-----------------------------------------------------
Z | 1 1 1 0 0 0
X4 | 1 1 9 1 0 75
X5 | 1 3 7 0 1 65
Step 3: Identify the pivot column
Choose the column with the most negative coefficient in the Z row, which is column X3.
Step 4: Identify the pivot row
Choose the row with the smallest non-negative ratio of the RHS to the pivot column coefficient. In this case, X4 has the smallest ratio (75/9 = 8.33) compared to X5 (65/7 = 9.29).
Step 5: Perform row operations to make the pivot element equal to 1 and other elements in the pivot column equal to 0.
Divide row X4 by 9: X4 -> (1/9)X4
Row operations:
X1 X2 X3 X4 X5 RHS
-----------------------------------------------------
Z | 1 1 1 0 0 0
X4 | 1 1 1/9 1/9 0 75/9
X5 | 1 3 7 0 1 65
Step 6: Perform column operations to make other elements in the pivot column equal to 0.
Multiply row Z by -1: Z -> -Z
Multiply row X4 by -1/9: X4 -> (-1/9)X4
Row operations:
X1 X2 X3 X4 X5 RHS
-----------------------------------------------------
Z | -1 -1 -1 0 0 0
X4 | 1 1 1/9 1/9 0 75/9
X5 | 1 3 7 0 1 65
Step 7: Repeat steps 3 to 6 until there are no negative coefficients in the Z row.
In this case, the tableau is already optimized, as there are no negative coefficients in the Z row.
Step 8: Read the solution
The solution is obtained by looking at the right-hand side (RHS) values corresponding to the variables X1, X2, and X3.
X1 = 0
X2 = 15
X3 = 5
Therefore, we can make 0 units of A, 15 units of B, and 5 units of C given the available hours in each department.