Advanced optimization and operations research

Preface......Page 7
Contents......Page 9
About the Authors......Page 15
 1.2 Introduction......Page 17
 1.3 Definitions of Operations Research......Page 18
 1.4 Applications of OR......Page 19
 1.5 Main Phases of OR......Page 21
 1.6 Scope of OR......Page 22
 1.7 Modelling in OR......Page 23
 1.8 Development of OR in India......Page 26
 1.9 Role of Computers in OR......Page 27
 2.3 Convex and Concave Functions......Page 28
 2.4 Geometrical Interpretation......Page 30
 2.5 Properties of Convex and Concave Functions......Page 33
 2.6 Differentiable Convex and Concave Functions......Page 35
 2.7 Differentiable Strictly Convex and Concave Functions......Page 39
 3.2 General Linear Programming Problem......Page 43
 3.3 Slack and Surplus Variables......Page 44
 3.4 Canonical and Standard Forms of LPP......Page 45
 3.5 Fundamental Theorem of LPP......Page 47
 3.6 Replacement of a Basis Vector......Page 51
 3.7 Improved Basic Feasible Solution......Page 53
 3.8 Optimality Condition......Page 54
 3.9 Unbounded Solution......Page 56
 3.10 Simplex Algorithm......Page 59
 3.11 Simplex Table......Page 60
 3.12 Use of Artificial Variables......Page 67
  3.12.1 Big M Method......Page 68
  3.12.2 Solution of Simultaneous Linear Equations by Simplex Method......Page 69
  3.12.3 Inversion of a Matrix by Simplex Method......Page 70
  3.12.4 Two-Phase Method......Page 80
 3.13 Exercises......Page 90
 4.2 Introduction......Page 93
 4.4 Standard Form I of Revised Simplex Method......Page 94
 4.5 Computational Procedure of Standard Form I of Revised Simplex Method......Page 97
 4.6 Standard Form II of Revised Simplex Method......Page 103
  4.6.1 Charne’s Big M Revised Simplex Method......Page 104
  4.6.2 Two-Phase Revised Simplex Method......Page 109
 4.7 Advantages of Revised Simplex Method......Page 120
 4.9 Exercises......Page 121
 5.2 Introduction......Page 123
 5.3 Dual Simplex Algorithm......Page 128
 5.5 Modified Dual Simplex Method......Page 134
 5.6 Exercises......Page 138
 6.2 Introduction......Page 140
 6.3 The Computational Procedure......Page 141
 6.4 Exercises......Page 148
 7.2 Introduction......Page 150
 7.3 Discrete Changes in the Profit Vector......Page 151
 7.4 Discrete Changes in the Requirement Vector......Page 158
 7.5 Discrete Changes in the Coefficient Matrix......Page 164
 7.6 Addition of a Variable......Page 169
 7.7 Deletion of a Variable......Page 171
 7.8 Addition of a New Constraint......Page 172
 7.9 Exercises......Page 179
 8.2 Introduction......Page 183
 8.3 Gomory’s All-Integer Cutting-Plane Method......Page 184
 8.4 Construction of Gomory’s Constraint......Page 185
 8.6 Construction of Additional Constraint for Mixed-Integer Programming Problems......Page 194
 8.7 Branch and Bound Method......Page 199
 8.8 Exercises......Page 205
 9.2 Optimization of Functions of a Single Variable......Page 208
 9.3 Optimization of Functions of Several Variables......Page 212
 9.4 Exercises......Page 220
 10.2 Introduction......Page 222
 10.3 Direct Substitution Method......Page 223
 10.4 Method of Constrained Variation......Page 226
  10.4.2 Necessary Conditions for Extremum of a General Problem for Constrained Variation Method......Page 228
  10.4.3 Sufficient Conditions for a General Problem in Constrained Variation Method......Page 231
 10.5 Lagrange Multiplier Method......Page 236
  10.5.1 Necessary Conditions for Optimality......Page 237
  10.5.2 Sufficient Conditions for Optimality......Page 239
  10.5.3 Alternative Approach for Testing Optimality......Page 241
 10.6 Interpretation of Lagrange Multipliers......Page 252
 10.7 Applications of Lagrange Multiplier Method......Page 256
 10.8 Exercises......Page 257
 11.2 Introduction......Page 259
 11.3 Feasible Direction......Page 261
  11.4.1 Kuhn-Tucker Necessary Conditions......Page 263
  11.4.2 Kuhn-Tucker Sufficient Conditions......Page 265
 11.5 Exercises......Page 277
 12.2 Introduction......Page 278
 12.3 Solution Procedure of QPP......Page 280
 12.4 Wolfe’s Modified Simplex Method......Page 284
 12.5 Advantage and Disadvantage of Wolfe’s Method......Page 285
 12.6 Beale’s Method......Page 301
 12.7 Beale’s Algorithm for QPPs......Page 302
 12.8 Exercises......Page 310
 13.2 Introduction......Page 312
 13.3 Cooperative and Non-cooperative Games......Page 313
 13.4 Antagonistic Game......Page 316
 13.5 Matrix Games or Rectangular Games......Page 317
 13.6 Dominance......Page 333
 13.7 Graphical Solution of 2 × n or m × 2 Games......Page 339
 13.8 Matrix Games and Linear Programming Problems (LPPs)......Page 345
 13.9 Infinite Antagonistic Game......Page 350
 13.10 Continuous Game......Page 356
 13.11 Separable Game......Page 357
 13.12 Exercises......Page 373
 14.2 Introduction......Page 376
 14.3 Phases of Project Management......Page 377
 14.5 Basic Components......Page 378
 14.6 Common Errors......Page 381
 14.7 Rules for Network Construction......Page 382
 14.8 Numbering of Events......Page 383
 14.9 Critical Path Analysis......Page 384
 14.10 PERT Analysis......Page 389
 14.11 Difference Between PERT and CPM......Page 395
 14.12 Project Time-Cost Trade-Off......Page 396
 14.13 Exercises......Page 408
  15.2.1 Introduction......Page 412
  15.2.2 Reason Behind the Queue......Page 413
  15.2.3 Characteristics of Queueing Systems......Page 414
  15.2.5 The State of the System......Page 418
  15.2.6 Probability Distribution in a Queueing System......Page 419
  15.2.7 Classification of Queueing Models......Page 424
  15.3.1 Introduction......Page 425
  15.3.2 Model (M/M/1):(∞/FCFS/∞)......Page 426
  15.3.3 Model (M/M/1):(N/FCFS/∞)......Page 437
  15.3.4 Model (M/M/C):(∞/FCFS/∞)......Page 443
  15.3.5 Model (M/M/C):(N/FCFS/∞)......Page 451
  15.3.6 Model (M/M/R):(K/GD) K  greaterthan  R......Page 457
  15.3.7 Power Supply Model......Page 465
  15.4.1 Introduction......Page 468
  15.4.2 Model (M/Ek/1):(∞/FCFS/∞)......Page 469
  15.4.3 Model (M/G/1):(\infty/GD)......Page 477
  15.5.2 Mixed Queueing Model......Page 482
 15.6 Cost Models in Queueing System......Page 486
 15.7 Exercises......Page 488
 16.2 Introduction......Page 496
 16.3 Graphs......Page 497
 16.4 Minimum Path Problem......Page 500
 16.5 Problem of Potential Difference......Page 503
 16.6 Network Flow Problem......Page 504
 16.7 Generalized Problem of Maximum Flow......Page 508
 16.8 Formulation of an LPP of a Flow Network......Page 509
 16.9 Exercises......Page 526
 17.2 Introduction......Page 529
  17.2.1 Types of Inventories......Page 531
 17.3 Basic Terminologies in Inventory......Page 532
 17.4 Classification of Inventory Models......Page 534
 17.5 Purchasing Inventory Model with No Shortage (Model 1)......Page 535
 17.6 Manufacturing Model with No Shortage (Model 2)......Page 538
 17.7 Purchasing Inventory Model with Shortage (Model 3)......Page 541
 17.8 Manufacturing Model with Shortage......Page 546
 17.9 Multi-item Inventory Model......Page 551
  17.9.1 Limitation on Inventories......Page 552
  17.9.2 Limitation of Floor Space (or Warehouse Capacity)......Page 554
  17.9.3 Limitation on Investment......Page 555
 17.10 Inventory Models with Price Breaks......Page 560
  17.10.1 Purchasing Inventory Model with Single Price Break......Page 561
  17.10.2 Purchase Inventory Model with Two Price Breaks......Page 563
  17.11.1 Single Period Inventory Model with Continuous Demand (No Replenishment Cost Model)......Page 565
  17.11.2 Single Period Inventory Model with Instantaneous Demand (no Replenishment Cost Model)......Page 572
 17.12 Fuzzy Inventory Model......Page 578
 17.13 Exercises......Page 584
 18.2 Matrices......Page 588
 18.3 Determinant......Page 594
 18.4 Rank of a Matrix......Page 596
 18.5 Solution of a System of Linear Equations......Page 597
 18.6 Vectors......Page 598
 18.7 Probability......Page 603
 18.8 Markov Process......Page 617
Bibliography......Page 621
Index......Page 624