Faculty Shruti Kohli
SP\1 2
Question Bank
Optimization Theory
1. What is operations research? Explain the scope of OR.
2. List the phases of OR and explain them.
3. Define the following:
a. Feasible region.
b. Feasible solution.
c. Optimal solution.
d. Unbounded solution.
e. Artificial variable.
4. What is the difference between feasible solution and basic feasible solution?
5. Define What are the two forms of a LPP? Explain in detail.
6. What do you mean by standard form of LPP?
7. What do you mean by canonical form of LPP?
8. What are the limitations of LPP?
9. What are the slack and surplus variables?
10. What is meant by optimality?
11. What are the methods used to solve an LPP involving artificial variables?
12. Explain various steps of the simplex method involved in the computation of an optimum solution to a linear programming problem.
13. What is simplex? Describe simplex method of solving LPP?
14. Given a general LPP explain how you would test whether a basic feasible solution is an optimal solution or not? How would proceed to change the basic feasible solution in case it si not optimal?
15. What are artificial variables? Why do we need them? Describe two phase method to solve LPP?
16. What is significance of cj-zj numbers in the simplex table? Interpret their economic significance in terms of marginal worth.
17. What conditions must exist in a simplex table to establish the existence of an alternative solution? No feasible solution? Unbounded solution? Degeneracy?
18. What is meant by degeneracy and cycling in linear programming?
19. Define dual of a LPP? State functional properties of duality?
20. Explain principles of duality? What is its significance in a LP model?
21. State the optimality condition in dual simplex method.
22. What is the difference between regular simplex method and dual simplex
method?
23. What do you understand by transportation problem?
24. List any three approaches used with T.P for determining the starting solution.
25. What do you mean by degeneracy in a T.P?
26. What do you mean by an unbalanced T.P?
27. How do you convert the unbalanced T.P into a balanced one?
35. What is an assignment problem?
37. State the difference between the T.P and A.P.
38. What is the objective of the traveling salesman problem?
39. How do you convert the maximization assignment problem into a minimization one?
40. What is the name of the method used in getting the optimum assignment?
41. What do you mean by integer programming problem?
42. Define a pure integer programming problem.
43. Define a mixed integer programming problem.
44. Differentiate between pure and mixed IPP.
45. What are the methods used in solving IPP
46. Explain Gomorian constraint (or) Fractional Cut constraint.
47. Where is branch and bound method used?
48. What is dynamic programming?
49. Define the terms in dynamic programming : stage, state ,state variables
50. State Bellman’s principle of optimality.
Numericals
1. 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.
2. A company produces 2 types of hats. Every hat A require twice as much labour 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.
3. A company wishes to advertise its products on local radio and TV stations. Each minute of radio advertisement will cost Rs.50 and each minute of TV advertisement will cost Rs. 600. The budget of the company limits the advertisement expenditure to Rs.25000 per month. The company decides to use radio atleast twice as much as TV. Past records of the company show that each minute of TV advertisement will generate 30 times as many sales as each minute radio advertisement. Formulate the problem for optimal allocation of monthly budget to radio and TV advertisement.
4. Use graphical method to solve the following LPP
Maximize Z = 2x1+4x2
subject to the constraints
x1+2x2 = 5,
x1+x2 = 4,
x1, x2 ≥ 0
5. Use simplex method to solve the following LPP
Maximize Z = 4x1+10x2
subject to the constraints
2x1+x2 ≤ 50,
2x1+5x2 ≤100,
2x1+3x2 ≤ 90,
x1, x2 ≥0
6. 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
7. Use Big M method to
Maximize Z = 3x1+2x2
subject to the constraints
2x1+x2 ≤ 2,
3x1+4x2 ≥ 12,
x1, x2 ≥ 0
8 Use Two Phase Simplex method to
Maximize Z = 5x1-4x2+3x3
subject to the constraints
2x1+x2-6x3 = 20,
6x1+5x2+10x3 ≤ 76,
8x1-3x2+6x3 ≤ 50,
x1, x2, x3 ≥ 0
9. Use Two Phase Simplex Method to
Maximize Z = -4x1-3x2-9x3
.
Subject to the constraints
2x1+4x2+6x3 ≥ 15,
6x1+x2+6x3 ≥ 12,
x1, x2, x3 ≥ 0
10. Write the dual of the following primal LP problem.
Max Z = x1+2x2+x3
Subject to
2x1+x2 –x3 ≤ 2
-2x1 + x2 -5x3 ≥ -6
4x1 + x2+x3 ≤ 6
x1, x2, x3 ≥ 0
11. Obtain an initial basic feasible solution to the following TP using Matrix
minima method
D1 D2 D3 D4 Supply
O1 1 2 3 4 6
O2 4 3 2 0 8
O3 0 2 2 1 10
Required 4 6 8 6 24
12. Obtain an initial basic feasible solution to the following TP using Matrix
minima method
D1 D2 D3 D4 Supply
O1 11 13 17 14 250
O2 16 18 14 10 300
O3 21 24 13 10 400
Required 200 225 275 250 950
Comments