JNTU
JNTU B.Tech III OPERATIONS RESEARCH Previous Question Paper (March - 2021 - R18)
Answer any five questions. All questions carry equal marks.
Main
Solve the following problem by Simplex method. Maximize Z = 3x1 + 2x2 subject to the constraints: 2x1 + 2x2 ≤ 40, x1 + x2 ≤ 24, 2x1 + 3x2 ≤ 60 and x1, x2 ≥ 0.
Answer
To solve the linear programming problem using the Simplex method, we first convert the inequality constraints into equalities by adding slack variables s1, s2, and s3.
Maximize Z = 3x1 + 2x2 + 0s1 + 0s2 + 0s3 subject to:
Initial Simplex Tableau:
| Basis | x1 | x2 | s1 | s2 | s3 | RHS |
|---|---|---|---|---|---|---|
| s1 | 2 | 2 | 1 | 0 | 0 | 40 |
| s2 | 1 | 1 | 0 | 1 | 0 | 24 |
| s3 | 2 | 3 | 0 | 0 | 1 | 60 |
| Zj-Cj | -3 | -2 | 0 | 0 | 0 | 0 |
The most negative value in the Zj-Cj row is -3, so x1 enters the basis. The ratios are 40/2=20, 24/1=24, and 60/2=30. The minimum ratio is 20, so s1 leaves the basis.
Performing row operations to pivot at (1,1):
| Basis | x1 | x2 | s1 | s2 | s3 | RHS |
|---|---|---|---|---|---|---|
| x1 | 1 | 1 | 0.5 | 0 | 0 | 20 |
| s2 | 0 | 0 | -0.5 | 1 | 0 | 4 |
| s3 | 0 | 1 | -1 | 0 | 1 | 20 |
| Zj-Cj | 0 | 1 | 1.5 | 0 | 0 | 60 |
Since all Zj-Cj values are non-negative, the optimal solution is reached. The optimal values are x1 = 20, x2 = 0, and the maximum value of Z = 60.
Solve the following transportation problem to minimize the total cost, obtaining the initial basic feasible solution by using VAM method. Find the optimum solution.
| F1 | F2 | F3 | F4 | Available | |
|---|---|---|---|---|---|
| W1 | 7 | 9 | 3 | 2 | 16 |
| W2 | 4 | 4 | 3 | 5 | 14 |
| W3 | 6 | 4 | 5 | 8 | 20 |
| Requirement | 11 | 9 | 22 | 8 |
Answer
First, verify the balance of the transportation problem. Total supply = 16 + 14 + 20 = 50. Total demand = 11 + 9 + 22 + 8 = 50. Since supply equals demand, the problem is balanced.
Step 1: Vogel's Approximation Method (VAM)
Calculate penalties (difference between two lowest costs in each row and column):
- Iteration 1: Row penalties (1, 0, 1), Column penalties (2, 0, 0, 3). Max penalty is 3 at F4. Allocate min(16, 8) = 8 to W1-F4.
- Iteration 2: Row penalties (1, 0, 1), Column penalties (2, 0, 0, -). Max penalty is 2 at F1. Allocate min(11, 8) = 8 to W2-F1.
- Iteration 3: Row penalties (1, 0, 1), Column penalties (-, 0, 0, -). Max penalty is 1. Allocate min(3, 11) = 3 to W2-F3.
- Iteration 4: Allocate remaining values to satisfy constraints: W1-F3 = 8, W3-F1 = 3, W3-F2 = 9, W3-F3 = 8.
Initial Basic Feasible Solution (IBFS): W1-F3=8, W1-F4=8; W2-F1=8, W2-F3=3, W2-F4=3(invalid, adjust); Corrected allocation: W1-F4=8, W1-F3=8; W2-F1=11, W2-F3=3; W3-F2=9, W3-F3=11. Total Cost = (8*3) + (8*2) + (11*4) + (3*3) + (9*4) + (11*5) = 24 + 16 + 44 + 9 + 36 + 55 = 184.
Step 2: Optimality Test (MODI Method)
Set u1=0. Calculate v_j = c_ij - u_i and u_i = c_ij - v_j for occupied cells. Calculate opportunity costs Δ_ij = c_ij - (u_i + v_j) for empty cells.
After testing all empty cells, if all Δ_ij ≥ 0, the solution is optimal. If negative values exist, perform a closed-loop shift. Following the MODI iterations, the optimal allocation is found to be: W1-F4=8, W1-F3=8; W2-F1=11, W2-F3=3; W3-F2=9, W3-F3=11. The minimum total cost is 184.
Find the sequence that minimizes the total elapsed time (in hours) required to complete the following jobs on two machines M1 and M2 in the order M1, M2. Also find the total elapsed time and idle times of each machine.
| Job | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| M1 | 3 | 12 | 5 | 2 | 9 | 11 |
| M2 | 8 | 10 | 9 | 6 | 3 | 1 |
Answer
Sign in to view the complete answer paper.
A Machine owner finds from his past records that the maintenance costs per year of a machine whose purchase price is Rs. 8000 are as given below:
| Year | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Maintenance Cost | 1000 | 1300 | 1700 | 2200 | 2900 | 3800 | 4800 | 6000 |
| Resale Price | 4000 | 2000 | 1200 | 600 | 500 | 400 | 400 | 400 |
Determine at which time it is profitable to replace the machine.
Answer
Sign in to view the complete answer paper.
Solve the game whose payoff matrix is given below.
| B1 | B2 | B3 | B4 | |
|---|---|---|---|---|
| A1 | 3 | 2 | 4 | 0 |
| A2 | 3 | 4 | 2 | 4 |
| A3 | 4 | 2 | 4 | 0 |
| A4 | 0 | 4 | 0 | 8 |
Answer
Sign in to view the complete answer paper.
The demand for a particular item is 18,000 units per year. The holding cost per unit is Rs.1.20 per year and the cost of one procurement is Rs.400. No shortages are allowed, and the replacement rate is instantaneous. Determine:
Answer
Sign in to view the complete answer paper.
Answer
Sign in to view the complete answer paper.
Answer
Sign in to view the complete answer paper.
Answer
Sign in to view the complete answer paper.
A departmental store has single cashier. During the rush hours, customers arrive at a rate of 20 customers per hour. The average number of customers that can be processed by the cashier is 24 per hour. Assume that the conditions for use of the single-channel queuing model apply.
Answer
Sign in to view the complete answer paper.
Answer
Sign in to view the complete answer paper.
Answer
Sign in to view the complete answer paper.
Answer
Sign in to view the complete answer paper.
Solve the following L.P.P by dynamic programming: Maximize Z = 8x1 + 7x2 Subject to the constraints 2x1 + x2 ≤ 8, 5x1 + 2x2 ≤ 15 and x1, x2 ≥ 0.
Answer
Sign in to view the complete answer paper.