MTH601 Official 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
22. 1
23. 2 Concept of Network ......................................................................................................................................... 9
24. 2.1 Rules for Construction of Network ........................................................................................................ 11
25. 2.2 Dummy Activities .................................................................................................................................. 11
26. 2.3 Exercises ................................................................................................................................................ 16
27. 3 Finding the Critical Path ................................................................................................................................. 16
28. 3.1 Algorithm for Critical Path .................................................................................................................... 18
29. 3.2 Early start and early finish program ....................................................................................................... 18
30. 3.3 Late start and Late finish program ......................................................................................................... 19
31. 3.4 Slack or Float ......................................................................................................................................... 20
32. 3.5 Free Slack .............................................................................................................................................. 21
33. 3.6 Independent slack .................................................................................................................................. 21
34. 4 Pert Model ...................................................................................................................................................... 23
35. 4.1 Expected length of a critical path: ......................................................................................................... 24
36. 4.2 Probability of completing a project with a given date ........................................................................... 25
37. 4.3 Exercise ................................................................................................................................................. 28
38. 5 Resource Scheduling in Network ................................................................................................................... 28
39. 5.1 Resource leveling program .................................................................................................................... 29
40. 5.2 Resource Allocation ............................................................................................................................... 29
41. 5.3 Exercises ................................................................................................................................................ 29 Inventory Control ................................................................................................................................................. 31
42. 1
43. 2 Inventory Costs ............................................................................................................................................... 31
44. 2.1 Item Cost (C1) ........................................................................................................................................ 31
45. 2.2 Purchasing or Setup or Acquisition or Ordering Cost (C2) .................................................................... 31
46. 2.3 Inventory holding cost (C3) .................................................................................................................... 31
47. 2.4 Shortage Cost (C4) ................................................................................................................................. 32
48. 3 Inventory Models(E.O.Q. Models) ................................................................................................................. 32
49. 3.1 Model-1 Purchasing model with no shortages(Wilson’s model) ........................................................... 32
50. 3.2 Model-2 (Purchasing model with shortages) ......................................................................................... 35
51. 3.3 Model-3(Manufacturing model with no shortages) ............................................................................... 40
52. 3.4 Model-4 (Manufacturing model with shortages) ................................................................................... 43
53. 4 Order Quantity with Price Break .................................................................................................................... 45
54. 5 Exercises ......................................................................................................................................................... 45
55. 6 Dynamic Order Quantity ................................................................................................................................ 46
56. 7 ABC Analysis ................................................................................................................................................. 47
57. 8 Some Definitions ............................................................................................................................................ 49
58. 8.1 Computation of Safety Stock ................................................................................................................. 49 Linear Programming ............................................................................................................................................. 56
59. 1
60. 2 Formulation of the Linear Programming Problem ......................................................................................... 56
61. 2.1 Product Mix Problem ............................................................................................................................. 57
62. 2.2 Ingredients Mixing Problem .................................................................................................................. 59
63. 2.3 Investment Planning Problem ................................................................................................................ 61
64. 2.4 Chemical Mixture Problem .................................................................................................................... 63
65. 2.5 Marketing Problem ................................................................................................................................ 64
66. 2.6 Transportation Problem ......................................................................................................................... 66
67. 3 General form of Linear Programming Problem .............................................................................................. 68
68. 3.1 Exercise ................................................................................................................................................. 69
69. 4 Limitations of Linear Programming ............................................................................................................... 71
70. 4.1 Proportionality ....................................................................................................................................... 71
71. 4.2 Additivity ............................................................................................................................................... 72
72. 4.3 Divisibility ............................................................................................................................................. 72
73. 4.4 Deterministic.......................................................................................................................................... 72
74. 5 Solution to Linear Programming Problems .................................................................................................... 73
75. 6 Graphical solution to LPP............................................................................................................................... 73
76. 6.1 Procedure for Graphical Solution to LPP .............................................................................................. 76
77. 7 Certain Definitions ......................................................................................................................................... 80
78. 7.1 Exercise ................................................................................................................................................. 81
79. 8 Simplex Method ............................................................................................................................................. 82
80. 8.1 Simplex Procedure ................................................................................................................................. 83
81. 9 Application of Simplex Algorithm ................................................................................................................. 86
82. 9.1 Step 1 (Selection of basic entering variable).......................................................................................... 87
83. 9.2 Step 2 (Selection of leaving basic variable) ........................................................................................... 87
84. 9.3 Step 3 (Elimination of coefficients in the key column) ......................................................................... 87
85. 9.4 Step 4 (Further improvement of solution).............................................................................................. 87
86. 9.5 Step 5 (Stopping rule) ............................................................................................................................ 88
87. 9.6 Exercise ................................................................................................................................................. 89
88. 10 Artificial Variable Technique..................................................................................................................... 94
89. 10.1 The ' Big M' Technique ........................................................................................................................... 94
90. 10.2 The Two Phase Method ....................................................................................................................... 100
91. 10.3 Excerice ............................................................................................................................................... 103
92. 11 Variants of Simplex Method .................................................................................................................... 105
93. 11.1 Minimization........................................................................................................................................ 105
94. 11.2 Inequality in the wrong direction. ........................................................................................................ 106
95. 11.3 Tie for the Leaving Basic Variable (Degeneracy). .............................................................................. 106
96. 11.4 Temporary Degenerate Solution .......................................................................................................... 107
97. 11.5 Unbounded solution ............................................................................................................................. 109
98. 11.6 Unbounded solution space but bounded optimal solution ................................................................... 110
99. 11.7 Multiple or Alternative optimal Solutions ........................................................................................... 112
100. 11.8 Non-existing feasible solution ............................................................................................................. 114
101. 11.9 Unrestricted Variables ......................................................................................................................... 116
102. 11.10 Exercise ........................................................................................................................................... 118
103. 12 Duality Theory ......................................................................................................................................... 119
104. 12.1 Dual Formulation ................................................................................................................................. 119
105. 12.2 Constraints having equality sign .......................................................................................................... 120
106. 12.3 Economic Interpretation of the Dual .................................................................................................... 124
107. 12.4 Applications of Duality ........................................................................................................................ 124
108. 12.5 Excercise .............................................................................................................................................. 125 Transportation Models ........................................................................................................................................ 127
109. 1
110. 2 Transportation Model as a Linear Programming Problem ........................................................................... 128
111. 3 Formulations of a transportation problem .................................................................................................... 129
112. 4 Initial Basic Feasible Solution ...................................................................................................................... 129
113. 4.1 North West Corner Rule ...................................................................................................................... 130
114. 4.2 Least Cost Method ............................................................................................................................... 131
115. 4.3 Vogel's Approximation Method (VAM) .............................................................................................. 132
116. 5 Exercise ........................................................................................................................................................ 135
117. 6 Moving Towards Optimality ........................................................................................................................ 136
118. 6.1 The rationale behind optimality ........................................................................................................... 136
119. 6.2 Optimality test ..................................................................................................................................... 138
120. 7 VAM for maximization problem .................................................................................................................. 145
121. 8 Exercise ........................................................................................................................................................ 150
122. 9 Degeneracy ................................................................................................................................................... 153
123. 10 Exercise .................................................................................................................................................... 156 Assignment Models ............................................................................................................................................ 158
124. 1
125. 2 Mathematical Formulation of the Assignment Problem ............................................................................... 158
126. 3 Solution of an Assignment Problem ............................................................................................................. 159
127. 3.1 Multiple Solutions ............................................................................................................................... 161
128. 4 Hungarian Algorithm .................................................................................................................................... 163
129. 5 Maximization in Assignment Model ............................................................................................................ 168
130. 6 Impossible Assignment ................................................................................................................................ 170
131. 7 Exercise ........................................................................................................................................................ 173 Queuing Theory .................................................................................................................................................. 176
132. 1
133. 2 Definitions of some important terms in Queuing Model .............................................................................. 176
134. 2.1 Customer .............................................................................................................................................. 176
135. 2.2 Server ................................................................................................................................................... 176
136. 2.3 Waiting Line or Queue ........................................................................................................................ 176
137. 2.4 Service Channel ................................................................................................................................... 177
138. 2.5 Arrival Rate ......................................................................................................................................... 177
139. 2.6 Service Rate ......................................................................................................................................... 177
140. 2.7 Infinite Queue ...................................................................................................................................... 177
141. 2.8 Finite Queue......................................................................................................................................... 177
142. 2.9 Priority ................................................................................................................................................. 177
143. 2.10 Expected Number in Queue ................................................................................................................. 177
144. 2.11 Expected Number in System ................................................................................................................ 177
145. 2.12 Expected Time in Queue ...................................................................................................................... 177
146. 2.13 Expected Number in Nonempty Queue ............................................................................................... 177
147. 2.14 Expected Waiting Time For Nonempty Queue .................................................................................... 178
148. 2.15 System Utilization or Traffic Intensity ................................................................................................ 178
149. 3 Single Channel Infinite-Population Model ................................................................................................... 178
150. 4 Results for Poisson Arrival and Exponential Service Time .......................................................................... 184
151. 5 Exercise ........................................................................................................................................................ 188
152. 6 Multi-Channel Service Infinite Queue .......................................................................................................... 189
153. 6.1 Exercise ............................................................................................................................................... 191
154. 7 Multi-Channel Queue with Finite Population ............................................................................................... 192 Replacement Models .......................................................................................................................................... 194
155. 1 Why Replacement? ....................................................................................................................................... 194
156. 2 Replacement of items with gradual deterioration ......................................................................................... 194