Operations Research: A Model-Based Approach, 3rd Edition PDF by H A Eiselt and Carl-Louis Sandblom

By

Operations Research: A Model-Based Approach, Third Edition

By H A Eiselt and Carl-Louis Sandblom

Operations Research A Model-Based Approach, Third Edition

Contents:

1 Introduction to Operations Research . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 The Nature and History of Operations Research . . . . . . . . . . . 1

1.2 The Main Elements of Operations Research . . . . . . . . . . . . . . 4

1.3 The Modeling Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1 Introduction to Linear Programming . . . . . . . . . . . . . . . . . . . . 15

2.2 Applications of Linear Programming . . . . . . . . . . . . . . . . . . . 20

2.2.1 Production Planning . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.2 Diet Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.3 Allocation Problems . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2.4 Blending Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.2.5 Transportation and Assignment Problems . . . . . . . . . . 38

2.2.6 Dynamic Production-Inventory Models . . . . . . . . . . . 45

2.2.7 Employee Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 49

2.2.8 Cutting Stock Problems . . . . . . . . . . . . . . . . . . . . . . 52

2.3 Graphical Representation and Solution . . . . . . . . . . . . . . . . . . 70

2.3.1 The Graphical Solution Method . . . . . . . . . . . . . . . . . 71

2.3.2 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

2.4 Postoptimality Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2.4.1 Graphical Sensitivity Analyses . . . . . . . . . . . . . . . . . 90

2.4.2 Optimal Solution and Sensitivity Analyses on a Printout . . . . . . . . . . . . . . . . . . . . . . 101

2.5 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

3 Multiobjective Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

3.1 Vector Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

3.2 Solution Approaches to Vector Optimization Problems . . . . . . 131

3.3 Goal Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

4 Nonlinear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

4.2 Applications of Nonlinear Programming . . . . . . . . . . . . . . . . . 146

4.2.1 Forestry Logging . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

4.2.2 Maximizing Tax Revenues . . . . . . . . . . . . . . . . . . . . 147

4.2.3 Optimizing Inventory and Queuing Models . . . . . . . . 148

4.3 Properties of Nonlinear Programming Problems . . . . . . . . . . . 149

4.4 Solution Methods for Nonlinear Optimization . . . . . . . . . . . . . 152

4.4.1 Newton’s Method for Unconstrained Optimization . . . 153

4.4.2 Constrained Optimization . . . . . . . . . . . . . . . . . . . . . 154

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

5 Integer Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

5.1 Definitions and Basic Concepts . . . . . . . . . . . . . . . . . . . . . . . 162

5.2 Applications of Integer Programming . . . . . . . . . . . . . . . . . . . 170

5.2.1 Diet Problems Revisited . . . . . . . . . . . . . . . . . . . . . . 172

5.2.2 Land Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

5.2.3 Modeling Fixed Charges . . . . . . . . . . . . . . . . . . . . . . 175

5.2.4 Workload Balancing . . . . . . . . . . . . . . . . . . . . . . . . . 179

5.2.5 Political Districting . . . . . . . . . . . . . . . . . . . . . . . . . . 181

5.3 Solution Methods for Integer Programming Problems . . . . . . . 183

5.3.1 Cutting Plane Methods . . . . . . . . . . . . . . . . . . . . . . . 183

5.3.2 Branch-and-Bound Methods . . . . . . . . . . . . . . . . . . . 188

5.3.3 Heuristic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 194

6 Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

6.1 Definitions and Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 215

6.2 Social Network Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

6.3 Network Flow Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

6.4 Shortest Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

6.5 Spanning Tree Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

6.6 Routing Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

6.6.1 Arc Routing Problems . . . . . . . . . . . . . . . . . . . . . . . 241

6.6.2 Node Routing Problems . . . . . . . . . . . . . . . . . . . . . . 249

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

7 Location Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

7.1 The Major Elements of Location Problems . . . . . . . . . . . . . . . 267

7.2 Covering Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

7.2.1 The Location Set Covering Problem . . . . . . . . . . . . . 271

7.2.2 The Maximal Covering Location Problem . . . . . . . . . 274

7.3 Center Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

7.3.1 1-Center Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 278

7.3.2 p-Center Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 280

7.4 Median Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

7.4.1 Minisum Problems in the Plane . . . . . . . . . . . . . . . . . 281

7.4.2 Minisum Problems in Networks . . . . . . . . . . . . . . . . 285

7.5 Other Location Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

8 Project Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

8.1 The Critical Path Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

8.2 Project Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

8.3 Project Planning with Resources . . . . . . . . . . . . . . . . . . . . . . 317

8.4 The PERT Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

9 Machine Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

9.1 Basic Concepts of Machine Scheduling . . . . . . . . . . . . . . . . . 334

9.2 Single-Machine Scheduling Models . . . . . . . . . . . . . . . . . . . . 336

9.3 Parallel Machine Scheduling Models . . . . . . . . . . . . . . . . . . . 340

9.4 Dedicated Machine Scheduling Models . . . . . . . . . . . . . . . . . 345

Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

10 Decision Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

10.1 Introduction to Decision Analysis . . . . . . . . . . . . . . . . . . . . . . 353

10.2 Visualizations of Decision Problems . . . . . . . . . . . . . . . . . . . . 355

10.3 Decision Rules Under Uncertainty and Risk . . . . . . . . . . . . . . 357

10.4 Sensitivity Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

10.5 Decision Trees and the Value of Information . . . . . . . . . . . . . 366

10.6 Utility Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

11 Multiattribute Decision Making . . . . . . . . . . . . . . . . . . . . . . . . . . 385

11.1 The General Model and a Generic Solution Method . . . . . . . . 385

11.2 TOPSIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

11.3 The Analytic Hierarchy Process . . . . . . . . . . . . . . . . . . . . . . . 391

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

12 Inventory Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

12.1 Basic Concepts in Inventory Planning . . . . . . . . . . . . . . . . . . 401

12.2 The Economic Order Quantity (EOQ) Model . . . . . . . . . . . . . 404

12.3 The Economic Order Quantity with Positive Lead Time . . . . . 407

12.4 The Economic Order Quantity with Backorders . . . . . . . . . . . 410

12.5 The Economic Order Quantity with Quantity Discounts . . . . . . 412

12.6 The Production Lot Size Model . . . . . . . . . . . . . . . . . . . . . . . 414

12.7 The Economic Order Quantity with Stochastic Lead Time

Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

12.7.1 A Model that Optimizes the Reorder Point . . . . . . . . . 418

12.7.2 A Stochastic Model with Simultaneous

Computation of Order Quantity and Reorder Point . . . 419

12.8 Extensions of the Basic Inventory Models . . . . . . . . . . . . . . . 420

Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424

13 Stochastic Processes and Markov Chains . . . . . . . . . . . . . . . . . . . 425

13.1 Basic Ideas and Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 425

13.2 Steady-State Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

13.3 Decision Making with Markov Chains . . . . . . . . . . . . . . . . . . 431

14 Reliability Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439

14.1 Fundamentals of Reliability Systems . . . . . . . . . . . . . . . . . . . 440

14.2 Time Aspects of Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . 445

14.3 Failure Rates and the Hazard Function . . . . . . . . . . . . . . . . . . 447

14.4 Redundancy and Standby Systems . . . . . . . . . . . . . . . . . . . . . 450

14.5 Estimating Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

15 Waiting Line Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457

15.1 Basic Queuing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458

15.2 Optimization in Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466

16 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473

16.1 Introduction to Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 474

16.2 Random Numbers and Their Generation . . . . . . . . . . . . . . . . . 475

16.3 Examples of Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

16.3.1 Simulation of a Waiting Line System . . . . . . . . . . . . . 480

16.3.2 Simulation of an Inventory System . . . . . . . . . . . . . . 483

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494

17 Heuristic Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495

Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504

Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505

Appendix A: Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . 505

Appendix B: Systems of Simultaneous Linear Equations . . . . . . . . . . 506

Appendix C: Probability and Statistics . . . . . . . . . . . . . . . . . . . . . . . 509

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517

This book is US$10
To get free sample pages OR Buy this book
Send email: [email protected]


Share this Book!

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.