DHANALAKSHMI SRINIVASAN COLLEGE OF ENGINEERING AND TECHNOLOGY
ECR, MAMALLAPURAM, CHENNAI-603 104
                          
                 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
QUESTION BANK(REG 2013)

SUBJECT: Resource Management Techniques
SUBCODE: CS6704                                                                                     
 SEM/YEAR: IV/VII                                                           

			
			UNIT-I
LINEAR PROGRAMMING
PARTA	
1.	Define operation research.

2.	Discuss the origin and development of operations research with a suitable classification.

3.	Define model.

4.	List the steps of modelling.

5.	Discuss the scope or applications of operations research.

6.	What is the necessity of operations research in industry?

7.	How operation research is used in decision making? List the advantages.

8.	List the phases of operation research.

9.	Define following terms. i) Solution ii) Feasible solution iii) Optimum solution iv) Degenerate solution v) Basic solution vi) Unbounded solution

10.	Explain the term. i) Non negative restrictions ii) Objective function iii) Feasible region

11.	What are basic & non basic variables?

12.	State the formulation of simplex method.

13.	What is degeneracy in case of LPP?

14.	What are the two forms of a LPP?

15.	What do you mean by standard form of LPP?

16.	What do you mean by canonical form of LPP?

17.	What are the limitations of LPP?

18.	What are the slack and surplus variables?

19.	What is meant by decision variable?

20.	Define artificial variable.

21.	What are the methods used to solve an LPP involving artificial variables?

22.	How sensitivity analysis can be carried out?

PART-B

1.	Under what condition is it possible for an LPP to have more than one optimal solution? What do these optimal solution represent?

2.	What is unbound solution, and how does it occur in graphical method?

3.	(a) Explain the scope of OR.

(b) List the phases of OR and explain them.

4.	(a) A company manufactures two products A and B. Each unit of B takes twice as long to produce as one unit of A and if the company were to produce only A it would have time to produce 2000 units per day. The availability of the raw material is sufficient to produce 1500 units per day of both A and B combined. Product B requiring a special Ingredient only 600units can be made per day. If A fetches a profit of Rs.2 per unit and B a profit of Rs.4 per unit, Formulate the optimum product min.

(b)A paper mill produces 2 grades of paper namely X and Y. Because of raw material restrictions, it cannot produce more than 400 tonnes of grade X and 300 tonnes of grade Y in a week. There are 160 production hours in a week. It requires 0.2 and 0.4 hours to produce a ton of products X and Y respectively with corresponding profits of Rs.200 and Rs.500 per ton. Formulate the above as a LPP to maximize profit and find the optimum product mix.

5.	(a) A company produces 2 types of hats. Every hat A require twice as much labor time as the second hat be. If the company produces only hat B then it can produce a total of 500 hats a day. The market limits daily sales of the hat A and hat B to 150 and 250 hats. The profits on hat A and B are Rs.8 and Rs.5 respectively. Solve graphically to get the optimal solution.

(b)	Use Graphical method to solve the following LP problem

Maximize Z= 15x1+10x2

Subject to the constraints:4x1+6x2≤360

3x1+0x2≤180

0x1+5x2≤200 ;	x1, x2≥0

6.	Use simplex method to solve the following LPP Maximize Z = 4x1+10x2

Subject to the constraints

2x1+x2≤ 50,

2x 1+5x2≤ 100,

2x 1+3x2≤ 90,

x 1, x2 ≥0

7.	Solve the following problem by simplex method Minimize Z = x1-3x2+2x3

Subject to the constraints 3x1-x2+2x3 ≤ 7, -2x1+4x2≤ 12, -4x1+3x2+8x3 ≤ 10,

x1, x2, x3 ≥0

8.	Apply Simplex method to solve the LPP. Maximize Z = 3X1 + 5X2 Subject to the constraints

3X 1 + 2X2  ≤ 18

0	≤ X1 ≤ 4, 0 ≤ X2 ≤ 6

9.	Use simplex method to solve the LPP.

Maximize Z = 4X1 + 10X2

Subject to the constraints

2X 1	+ X2  ≤ 50	
2X 1	+ 5X2 ≤ 100	
2X 1	+ 3X2  ≤ 90 and   X 1, X2 ≥ 0.	

		

10.	Apply graphical method to solve the following LPP. Maximize Z = 3X1 + 4X2

Subject to the constraints X 1 + X2 ≤ 450
2X 1 + X2 ≤ 600 X 1, X2 ≥ 0.

11.	Consider example and solve it by simplex method and generate the optimal table. Maximize Z=6X1+8X2 Subject to constraints

5 X1+10X2 ≤ 60

4X1+4X2 ≤ 40

X1 and X2 ≥ 0

Carry out sensitivity analysis under following conditions:

(a). if the right-hand side constants of constraint 1 and constraint 2 are changed from 60 and 40 to 40 and 20, respectively.

(b). if the right-hand side constants of the constraints are changed from 60 and 40 to 20 and 40 respectively.

12.	(a). A firm manufactures two types of products A and B and sells them at profit of Rs 2 on type A and Rs 3 on type B. Each product is processed on two machines M1 and M2.Type A requires 1 minute of processing time on M1 and 2 minutes on M2 Type B requires 1 minute of processing time on M1 and 1 minute on M2. Machine M1 is available for not more than 6 hours 40 minutes while machine M2 is available for 10 hours during any working day. Formulate the problem as a LPP so as to maximize the profit.

  (b). Write the Procedure for solving Linear Programming Problem using Simplex Method.

UNIT-II
                                                        DUALITY AND NETWORKS

                                                                 PART-A

1.	What is Dual Simplex method?

2.	State the feasibility and optimality condition in dual simplex method.

3.	What is two phase method?

4.	State the algorithm of two-phase method.

5.	State the formulation of duality problem.

6.	Define Big M Method.

7.	Define transportation problem.

8.	Define feasible and basic feasible solution.

9.	Provide a definition for optimal solution in transportation problem.

10.	Write the methods used in transportation problem to obtain the initial basic feasible solution.

11.	Can you provide the basic steps involved in solving a transportation problem?

12.	What do you understand by degeneracy in a transportation problem?

13.	What is balanced transportation problem & unbalanced transportation problem?

14.	How do you convert an unbalanced transportation problem into a balanced one?

15.	Explain how the profit maximization transportation problem can be converted to an equivalent cost minimization transportation problem.

16.	Define transshipment problems.

17.	What differences exist between Transportation problem & Transshipment Problem?

18.	What is assignment problem?

19.	Define unbounded assignment problem and describe the steps involved in solving it.

20.	Describe how a maximization problem is solved using assignment model.

21.	What do you understand by restricted assignment? How do you overcome it?

22.	How do you identify alternative solution in assignment problem?

23.	Illustrate the traveling salesman problem.

24.	Can you say how a minimization problem is solved using assignment model?

25.	Can you propose which method is best for finding initial basic feasible solution in transportation problem?

26.	Show the mathematical formulation of assignment model.

27.	What is the shortest path problem?

28.	Give some practical applications of the shortest path problem.

29.	What is minimum spanning problem? What are its practical applications?

30.	State maximal flow problem and give its practical applications.

PART-B

1.	Solve the following LP problem using dual simplex method: Minimize Z=X1+2X2+3X3

Subject to

2X1-X2+X3 ≥ 4 X1+X2+2X3 ≤ 8 X2-X3 ≥ 2 X1,X2 and X3 ≥ 0

2.	Write the dual of the following LP problem: Minimize Z=3X1-2X2+4X3

Subject to

3x1+5x2+4x3≥7

6x1+x2+3x3≥4

7x1-2x2-x3≤10 X1-2x2+5x3≥3

4x1+7x2-2x3≥2

X1,X2 and X3≥0

3.	Use Big M method to

Maximize Z = 3x1+2x2

Subject to the constraints

2x1+x2≤ 2,

3x 1+4x2≥ 12,

x 1, x2 ≥0

4.	Convert the following problem in dual problem & solve by Simplex Method Maximize (Z) = 300x1+400x2

Subject to Constraints 5x1+4x2≤200

3x1+5x2≤150

5x1+4x2≥100

8x1+4x2≥80

x1 , x2≥0

5.	Explain Transportation problem? Explain degeneracy in transportation problem.	

		
6.	Explain in detail ‘Stepping stone method’ for transportation problem with illustration.		
7.	Explain the steps used to solve transportation problem using MODI method.			
8.	What is unbalanced transportation problem? Does any extra cost required to considered in		
	case of such type of problem?										
9.	Write down the steps of North West Corner Method for solving transportation problem.		
10.	Explain with example how Initial Basic Feasible Solution for transportation problem using		
	Least Cost Method.

												
11.	Explain the steps of Vogel’s Approximation Method with example.			
12.	Solve by North West Corner Method										
																
							Warehouses				Supply		
		Plants	W1		W2		W3		W4				

		P1	6			2		6			12			120		
		P2	4			4		2			4			200		
		P3	13		8		7			2			80		
		Demand	50		80		90			180			400		
13.	What  are  Assignment  problems?  Describe  mathematical  formulation  of  an  assignment		
	problem?														
14.	Enumerate the steps in the “Hungarian Method” used for solving assignment problem.		
15.	A departmental head has four subordinates and four task for completion. The subordinates		
	differ in their capabilities and tasks differ in their capabilities and tasks differ in their work		
	contents and intrinsic difficulties. His estimate of time for each subordinate and each task is		
	given the matrix below												
															
		Tasks						Subordinates						
					I	II		III		IV		
							Processing Times (Hrs.)			
		A			17		25			26			20		
		B			28		27			23			25		
		C			20		18			17			14		
		D			28		25			23			19		
How should the tasks be assigned to minimize requirements of man-hours?

16.	Consider the assignment problem as shown in the following table. In this problem, 5 different jobs are to be assigned to 5 different operators such that the total processing time is minimized. The matrix entries represent processing times in hours. Solve the example using Hungerian method.

												

			Operator						
		1	2	3		4		5			
	1	10	12	15		12		8			
											
Job	2	7	16	14		14		11			

	3	13	14	7		9		9			
											
	4	12	10	11		13		10			
											
	5	8	13	15		11		15			
											
17.	Explain the steps of the following algorithms:

(a). Dijkstra’s algorithm (b). Floyd’s algorithm (c). PRIM algorithm (d). Kruskal’s algorithm

18.	Explain the matrix method for the maximal flow problem with an example.

19.	Consider the details of a distance network as shown below:

Arc	Distance	Arc	Distance	
1-2	8	3-6	6	
1-3	5	4-5	8	
1-4	7	4-6	12	
1-5	16	5-8	7	
2-3	15	6-8	9	
2-6	3	6-9	15	
2-7	4	7-9	12	
3-4	5	8-9	6	
a.	Construct the distance network.

b.	Find the shortest path from node 1 to node 9 using the systematic method.

c.	Find the shortest path from node 1 to node 9 using Dijkstra’s algorithm.

20.	Consider the details of a distance network as shown below:

Arc	Distance	
1-2	3	
1-3	8	
1-4	10	
2-3	4	
2-4	7	
3-4	2	
3-5	8	
4-5	6	
a.	Construct the distance network.
b.	Apply Floyd’s algorithm and obtain the final matrices, D5and P5.

c.	Find the shortest path and the corresponding distance for each of the following :

(i)	from node 1 to node 5

(ii)	from node 2 to node 5.

21. Consider the details of a distance network as shown below:

Arc	Distance	Arc	Distance	
1-2	6	5-6	13	
1-3	7	5-8	9	
1-4	10	6-7	5	
2-3	8	6-8	4	
2-5	4	6-9	8	
3-4	6	6-10	3	
3-5	11	7-9	10	
3-6	3	8-10	10	
3-7	5	9-10	9	
4-7	7			
a.	Construct the distance network.

b.	Find the minimum spanning tree using PRIM algorithm.

c.	Find the minimum spanning tree using Kruskal’s algorithm.

UNIT-III
                                                        INTEGER PROGRAMMING

                                                                 PART-A

1.	What do you mean by integer programming problem?

2.	What are the applications of zero-one integer programming?

3.	Define a mixed integer programming problem.

4.	Differentiate between pure and mixed IPP.

5.	What are the methods used in solving IPP?

6.	Explain Gomorian constraint (or) Fractional Cut constraint.

7.	Where is branch and bound method used?

8.	What is dynamic programming?

9.	Define the terms in dynamic programming: stage, state ,state variables

10.	Give a few applications of DPP.

11.	State Bellman’s principle of optimality.

12.	What are the advantages of Dynamic programming?

13.	Explain the importance of the L.P.P.

14.	Explain the importance of Integer programming problem.

15.	Illustrate some of the applications of IPP.

16.	Can you provide various types of integer programming?

17.	What is Zero-one problem?

18.	Why not round off the optimum values instead of resorting to IP?

19.	What is cutting Plane method?

20.	What do you think about search method?

21.	Write about Branch and Bound Technique.

22.	Construct the general format of IPP.

23.	Write an algorithm for Gomory’s Fractional Cut algorithm.

24.	What is the purpose of Fractional cut constraints?

25.	A manufacturer of baby dolls makes two types of dolls, doll X and doll Y. Processing of these dolls is done on two machines A and B. Doll X requires 2 hours on machine A and 6 hours on Machine B. Doll Y requires 5 hours on machine A and 5 hours on Machine B. There are 16 hours of time per day available on machine A and 30 hours on machine B. The profit is gained on both the dolls is same. Format this as IPP?

26.	Explain Gomory’s Mixed Integer Method.

PART-B

1.	Solve the following mixed integer programming problem by using Gomory’s cutting plane method.

Maximize Z = x1+x2 Subject to the constraints 3x1+2x2≤ 5,

x2≤ 2

x1, x2 ≥0 , x1 is an integer

2.	Find an optimum integer solution to the following LPP.

Maximize Z = x1+2x2

Subject to the constraints

2x2≤ 7,

x1+x2≤ 7

2x 2≤ 11

x1, x2 ≥0 , x1, x2  are integers

3.	Solve the following integer programming problem. Maximize Z = 2x1+20 x2-10x3

Subject to the constraints 2x1+20x2+4x3 ≤15,
6x 1+20x2+4x3 =20,

x	1, x2, x3 ≥0 and are integers

4.	Solve the following all integer programming problem using the Branch and bound method. Minimize Z = 3x1+2.5x2

Subject to the constraints x1+2x2≥20,

3x 1+2x2≥ 50 and x1, x2 are nonnegative integers

5.	Use Branch and Bound technique to solve the following.

Maximize Z = x1+4x2

Subject to the constraints

2x1+4x2≤ 7,

5x1+3x2≤15

x1, x2 ≥0 and are integers

6.	A student has to take examination in three courses X,Y,Z. He has three days available for study. He feels it would be best to devote a whole day to study the same course, so that he may study a course for one day, two days or three days or not at all. His estimates of grades he may get by studying are as follows.

							

						
	Study	X	Y	Z		
	0	1	2	1		
	1	2	2	2		
	2	2	4	4		
	3	4	5	4		
How should he plan to study so that he maximizes the sum of his grades?

7.	The owner of a chain of four grocery stores has purchased six crates of fresh strawberries. The estimated probability distribution of potential sales of the strawberries before spoilage differ among four stores. The following table gives the estimated total expected profit at each store when various number of crates are allocated to it. For administrative reasons, the owner does not wish to split crates between stores. However, he is willing to distribute zero crates to any of his stores. Find the allocation of six crates to four stores so as to maximize the expected profit.

Number of		Stores		
crates					
0	0	0	0	0	
1	4	2	6	2	
2	6	4	8	3	
3	7	6	8	4	
4	7	8	8	4	
5	7	9	8	4	
6	7	10	8	4	

8.	Use dynamic programming to solve the following LPP. Maximize Z = x1+9x2

Subject to the constraints 2x1+x2≤25

x 2≤11, x1, x2 ≥0

UNIT-IV
                                              CLASSICAL OPTIMISATION THEORY

                                                                       PART-A

1.	Discuss the different types of nonlinear programming problems.

2.	Explain the application areas of nonlinear programming problems.

3.	State the Lagrangean model.

4.	What is Newton Ralphson method?

5.	State the equality constraints.

6.	Define Jacobean method.

7.	State the Kuhn-Tucker conditions.

8.	What is bordered Hessian matrix? Give an example.

                                                                       PART-B

1.	Solve the following non linear programming problem using Langrangean multipliers method. Minimize Z=4X12+2X22+X32-4X1X2
Subject to

X1+X2+X3=15

2X1-X2+2X3=20

X1,X2 AND X3 ≥0

2.	Solve the following non linear programming problem using Kuhn-Tucker conditions. Maximize Z=8X1+10X2- X12-X22
Subject to

3X1+2X2≤6

X1 and X2≥0

3.	State and explain the Lagrangean method and steps involved in it with an example.

4.	Explain the Kuhn-Tucker method and steps involved in it with an example.

5.	Explain the Newton-Raphson method in detail and justify how it is used to solve the non linear equations.

6.	What is Jacobian method? Explain the steps how Jacobian matrix is generated.

UNIT-V
                                                        OBJECT SCHEDULING

                                                                 PART-A

1.	Write difference between PERT Network & CPM Network.

2.	Write a note on ‘activity and critical activity’.

3.	What do you mean by project?

4.	What are the three main phases of project?

5.	What are the two basic planning and controlling techniques in a network analysis?

6.	Write down the advantages of CPM and PERT techniques.

7.	Differentiate between PERT and CPM.

8.	Define network.

9.	What do you mean Event in a network diagram?

10.	Can you write about activity & Critical Activities?

11.	Define Dummy Activities and duration.

12.	Explain Total Project Time & Critical path.

13.	What is float or slack?

14.	Classify Total float, Free float and Independent float?

15.	Can you list the characteristics of Interfering Float?

16.	Define Optimistic time.

17.	Show and define Pessimistic time.

18.	How do you calculate most likely time estimation?

19.	What is a parallel critical path?

20.	Distinguish standard deviation and variance in PERT network?

21.	Give the difference between direct cost and indirect cost.

22.	What is meant by resource analysis?

		
                                                                     PART-B

1.	Critically comment on the assumptions on which PERT/CPM analysis is done for projects.
2.	A project schedule has the following characteristics
Activity	0-1	0-2	1-3	2-3	2-4	3-4	3-5	4-5	4-6	5-6	
Time	2	3	2	3	3	0	8	7	8	6	
(i). Construct Network diagram.
(ii). Compute earliest time and latest time for each event.

(iii). Find the critical path. Also obtain the Total float, Free float and slack time and Independent float.

3.	Draw a network for the following project and number the events according to Fulkerson’s
rule:

A is the start event and K is the end event.
A precedes event B.
J is the successor event to F.
C and D are the successor events of B.
D is the preceding event to G.
E and F occur after event C.
E precedes event F.

C restraints the occurrence of G and G precedes H.
H precedes J and K succeeds J.
F restraints the occurrence of H.
4.	A project has the following time schedule:
Activity	Predecessor	Optimistic Time	Most	Likely	Pessimistic	
A	-	4	4		10	
B	-	1	2		9	
C	-	2	5		14	
D	A	1	4		7	
E	A	1	2		3	
F	A	1	5		9	
G	B,C	1	2		9	
H	C	4	4		4	
I	D	2	2		8	
J	E,G	6	7		8	

Construct PERT network diagram and find the expected duration and variance of each activity. Find the critical path and expected project completion time.

5.	What is critical path analysis? What are the areas where these techniques can be applied?
6.	What is the significance of three times estimates used in PERT?