MTH601 Highlighted Handouts

Table of Contents

1. 1
2. 2
3. 3
4. 4
5. 4.1
6. 5
7. 6
8. 7 Uses of OR ................................................................................................................................................ 4
9. 7.1 Macro-Economic Planning................................................................................................................. 4
10. 7.2 Sectorial Planning .............................................................................................................................. 4
11. 7.3 Micro Economic Planning ................................................................................................................. 4
12. 8 Potential Areas of Applications .................................................................................................................. 4
13. 8.1 Operations Research in the Public Sector ........................................................................................... 4
14. 8.2 Operations Research in Industry & Commerce ................................................................................... 5
15. 8.3 Trucking policy for dairy products ..................................................................................................... 6
16. 8.4 OR in Transport ................................................................................................................................. 6
17. 9 Example .................................................................................................................................................... 6
18. 9.1 Operations ......................................................................................................................................... 6
19. 10 Requirements for Applying Successful OR ............................................................................................. 7
20. 11 Conclusion ............................................................................................................................................ 7
21. 12 Reference Texts ..................................................................................................................................... 7

Network Analysis (PERT/CPM) ...................................................................................................................... 9

2. 1
3. 2 Concept of Network ................................................................................................................................... 9
4. 2.1 Rules for Construction of Network ................................................................................................... 11
5. 2.2 Dummy Activities ........................................................................................................................... 11
6. 2.3 Exercises ......................................................................................................................................... 16
7. 3 Finding the Critical Path........................................................................................................................... 16
8. 3.1 Algorithm for Critical Path .............................................................................................................. 18
9. 3.2 Early start and early finish program.................................................................................................. 18
10. 3.3 Late start and Late finish program .................................................................................................... 19
11. 3.4 Slack or Float .................................................................................................................................. 20
12. 3.5 Free Slack ....................................................................................................................................... 21
13. 3.6 Independent slack ............................................................................................................................ 21
14. 4 Pert Model ............................................................................................................................................... 23
15. 4.1 Expected length of a critical path ..................................................................................................... 24
16. 4.2 Probability of completing a project with a given date ........................................................................ 25
17. 4.3 Exercise .......................................................................................................................................... 28
18. 5 Resource Scheduling in Network .............................................................................................................. 28
19. 5.1 Resource leveling program .............................................................................................................. 29
20. 5.2 Resource Allocation ........................................................................................................................ 29
21. 5.3 Exercises ......................................................................................................................................... 29

Inventory Control .......................................................................................................................................... 31

3. 1
4. 2 Inventory Costs ........................................................................................................................................ 31
5. 2.1 Item Cost (C1) ................................................................................................................................. 31
6. 2.2 Purchasing or Setup or Acquisition or Ordering Cost (C2) ................................................................ 31
7. 2.3 Inventory holding cost (C3) .............................................................................................................. 31
8. 2.4 Shortage Cost (C4) ........................................................................................................................... 32
9. 3 Inventory Models(E.O.Q. Models) ........................................................................................................... 32
10. 3.1 Model-1 Purchasing model with no shortages(Wilson’s model) ........................................................ 32
11. 3.2 Model-2 (Purchasing model with shortages) ..................................................................................... 35
12. 3.3 Model-3(Manufacturing model with no shortages) ........................................................................... 40
13. 3.4 Model-4 (Manufacturing model with shortages) ............................................................................... 43
14. 4 Order Quantity with Price Break .............................................................................................................. 45
15. 5 Exercises ................................................................................................................................................. 45
16. 6 Dynamic Order Quantity .......................................................................................................................... 46
17. 7 ABC Analysis .......................................................................................................................................... 47
18. 8 Some Definitions ..................................................................................................................................... 49
19. 8.1 Computation of Safety Stock ........................................................................................................... 49

Linear Programming ...................................................................................................................................... 56

4. 1
5. 2 Formulation of the Linear Programming Problem ..................................................................................... 56
6. 2.1 Product Mix Problem ....................................................................................................................... 57
7. 2.2 Ingredients Mixing Problem ............................................................................................................. 59
8. 2.3 Investment Planning Problem .......................................................................................................... 61
9. 2.4 Chemical Mixture Problem .............................................................................................................. 63
10. 2.5 Marketing Problem .......................................................................................................................... 64
11. 2.6 Transportation Problem ................................................................................................................... 66
12. 3 General form of Linear Programming Problem ......................................................................................... 68
13. 3.1 Exercise .......................................................................................................................................... 69
14. 4 Limitations of Linear Programming .......................................................................................................... 71
15. 4.1 Proportionality................................................................................................................................. 71
16. 4.2 Additivity ........................................................................................................................................ 72
17. 4.3 Divisibility ...................................................................................................................................... 72
18. 4.4 Deterministic ................................................................................................................................... 72
19. 5 Solution to Linear Programming Problems ............................................................................................... 73
20. 6 Graphical solution to LPP ........................................................................................................................ 73
21. 6.1 Procedure for Graphical Solution to LPP .......................................................................................... 76
22. 7 Certain Definitions ................................................................................................................................... 80
23. 7.1 Exercise .......................................................................................................................................... 81
24. 8 Simplex Method....................................................................................................................................... 82
25. 8.1 Simplex Procedure........................................................................................................................... 83
26. 9 Application of Simplex Algorithm ............................................................................................................ 86
27. 9.1 Step 1 (Selection of basic entering variable) ..................................................................................... 87
28. 9.2 Step 2 (Selection of leaving basic variable) ...................................................................................... 87
29. 9.3 Step 3 (Elimination of coefficients in the key column) ...................................................................... 87
30. 9.4 Step 4 (Further improvement of solution) ......................................................................................... 87
31. 9.5 Step 5 (Stopping rule) ...................................................................................................................... 88
32. 9.6 Exercise .......................................................................................................................................... 89
33. 10 Artificial Variable Technique ............................................................................................................... 94
34. 10.1 The ' Big M' Technique ..................................................................................................................... 94
35. 10.2 The Two Phase Method ................................................................................................................. 100
36. 10.3 Excerice ........................................................................................................................................ 103
37. 11 Variants of Simplex Method .............................................................................................................. 105
38. 11.1 Minimization ................................................................................................................................. 105
39. 11.2 Inequality in the wrong direction. ................................................................................................... 106
40. 11.3 Tie for the Leaving Basic Variable (Degeneracy) ........................................................................... 106
41. 11.4 Temporary Degenerate Solution ..................................................................................................... 107
42. 11.5 Unbounded solution ....................................................................................................................... 109
43. 11.6 Unbounded solution space but bounded optimal solution ................................................................ 110
44. 11.7 Multiple or Alternative optimal Solutions....................................................................................... 112
45. 11.8 Non-existing feasible solution ........................................................................................................ 114
46. 11.9 Unrestricted Variables ................................................................................................................... 116
47. 11.10 Exercise .................................................................................................................................... 118
48. 12 Duality Theory .................................................................................................................................. 119
49. 12.1 Dual Formulation .......................................................................................................................... 119
50. 12.2 Constraints having equality sign ..................................................................................................... 120
51. 12.3 Economic Interpretation of the Dual ............................................................................................... 124
52. 12.4 Applications of Duality .................................................................................................................. 124
53. 12.5 Excercise ....................................................................................................................................... 125

Transportation Models ................................................................................................................................. 127

5. 1
6. 2 Transportation Model as a Linear Programming Problem ........................................................................ 128
7. 3 Formulations of a transportation problem ............................................................................................... 129
8. 4 Initial Basic Feasible Solution ................................................................................................................ 129
9. 4.1 North West Corner Rule ................................................................................................................ 130
10. 4.2 Least Cost Method ......................................................................................................................... 131
11. 4.3 Vogel's Approximation Method (VAM) ......................................................................................... 132
12. 5 Exercise ................................................................................................................................................. 135
13. 6 Moving Towards Optimality .................................................................................................................. 136
14. 6.1 The rationale behind optimality ...................................................................................................... 136
15. 6.2 Optimality test ............................................................................................................................... 138
16. 7 VAM for maximization problem ............................................................................................................ 145
17. 8 Exercise ................................................................................................................................................. 150
18. 9 Degeneracy ............................................................................................................................................ 153
19. 10 Exercise ............................................................................................................................................. 156

Assignment Models ..................................................................................................................................... 158

6. 1
7. 2 Mathematical Formulation of the Assignment Problem ........................................................................... 158
8. 3 Solution of an Assignment Problem ........................................................................................................ 159
9. 3.1 Multiple Solutions ......................................................................................................................... 161
10. 4 Hungarian Algorithm ............................................................................................................................. 163
11. 5 Maximization in Assignment Model ....................................................................................................... 168
12. 6 Impossible Assignment .......................................................................................................................... 170
13. 7 Exercise ................................................................................................................................................. 173

Queuing Theory ........................................................................................................................................... 176

7. 1
8. 2 Definitions of some important terms in Queuing Model .......................................................................... 176
9. 2.1 Customer ....................................................................................................................................... 176
10. 2.2 Server............................................................................................................................................ 176
11. 2.3 Waiting Line or Queue .................................................................................................................. 176
12. 2.4 Service Channel............................................................................................................................. 177
13. 2.5 Arrival Rate ................................................................................................................................... 177
14. 2.6 Service Rate .................................................................................................................................. 177
15. 2.7 Infinite Queue ............................................................................................................................... 177
16. 2.8 Finite Queue .................................................................................................................................. 177
17. 2.9 Priority .......................................................................................................................................... 177
18. 2.10 Expected Number in Queue ........................................................................................................... 177
19. 2.11 Expected Number in System .......................................................................................................... 177
20. 2.12 Expected Time in Queue ................................................................................................................ 177
21. 2.13 Expected Number in Nonempty Queue .......................................................................................... 177
22. 2.14 Expected Waiting Time For Nonempty Queue ............................................................................... 178
23. 2.15 System Utilization or Traffic Intensity ........................................................................................... 178
24. 3 Single Channel Infinite-Population Model .............................................................................................. 178
25. 4 Results for Poisson Arrival and Exponential Service Time ...................................................................... 184
26. 5 Exercise ................................................................................................................................................. 188
27. 6 Multi-Channel Service Infinite Queue .................................................................................................... 189
28. 6.1 Exercise ........................................................................................................................................ 191
29. 7 Multi-Channel Queue with Finite Population .......................................................................................... 192

Replacement Models ................................................................................................................................... 194

8. 1 Why Replacement? ................................................................................................................................ 194
9. 2 Replacement of items with gradual deterioration..................................................................................... 194