Admin مدير المنتدى
عدد المساهمات : 19001 التقييم : 35505 تاريخ التسجيل : 01/07/2009 الدولة : مصر العمل : مدير منتدى هندسة الإنتاج والتصميم الميكانيكى
| موضوع: كتاب Operations Research - An Introduction الأحد 6 نوفمبر 2016 - 20:40 | |
|
أخوانى فى الله أحضرت لكم كتاب Operations Research - An Introduction Tenth Edition Global Edition Hamdy A. Taha University of Arkansas, Fayetteville
و المحتوى كما يلي :
Contents What’s New in the Tenth Edition 23 Acknowledgments 25 About the Author 27 Trademarks 29 Chapter 1 What Is Operations Research? 31 1.1 Introduction 31 1.2 Operations Research Models 31 1.3 Solving the OR Model 34 1.4 Queuing and Simulation Models 35 1.5 Art of Modeling 36 1.6 More than Just Mathematics 37 1.7 Phases of an OR Study 39 1.8 About this Book 41 Bibliography 41 Problems 42 Chapter 2 Modeling with Linear Programming 45 2.1 Two-Variable LP Model 45 2.2 Graphical LP Solution 47 2.2.1 Solution of a Maximization Model 48 2.2.2 Solution of a Minimization Model 50 2.3 Computer Solution with Solver and AMPL 52 2.3.1 LP Solution with Excel Solver 52 2.3.2 LP Solution with AMPL 56 2.4 Linear Programming Applications 59 2.4.1 Investment 60 2.4.2 Production Planning and Inventory Control 62 2.4.3 Workforce Planning 67 2.4.4 Urban Development Planning 70 2.4.5 Blending and Refining 73 2.4.6 Additional LP Applications 76 Bibliography 76 Problems 76 78 Contents Chapter 3 The Simplex Method and Sensitivity Analysis 99 3.1 LP Model in Equation Form 99 3.2 Transition from Graphical to Algebraic Solution 100 3.3 The Simplex Method 103 3.3.1 Iterative Nature of the Simplex Method 103 3.3.2 Computational Details of the Simplex Algorithm 105 3.3.3 Summary of the Simplex Method 111 3.4 Artificial Starting Solution 112 3.4.1 M-Method 112 3.4.2 Two-Phase Method 115 3.5 Special Cases in the Simplex Method 117 3.5.1 Degeneracy 118 3.5.2 Alternative Optima 119 3.5.3 Unbounded Solution 121 3.5.4 Infeasible Solution 122 3.6 Sensitivity Analysis 123 3.6.1 Graphical Sensitivity Analysis 124 3.6.2 Algebraic Sensitivity Analysis—Changes in the Right-Hand Side 128 3.6.3 Algebraic Sensitivity Analysis—Objective Function 132 3.6.4 Sensitivity Analysis with TORA, Solver, and AMPL 136 3.7 Computational Issues in Linear Programming 138 Bibliography 142 Case Study: Optimization of Heart Valves Production 142 Problems 145 Chapter 4 Duality and Post-Optimal Analysis 169 4.1 Definition of the Dual Problem 169 4.2 Primal–Dual Relationships 172 4.2.1 Review of Simple Matrix Operations 172 4.2.2 Simplex Tableau Layout 173 4.2.3 Optimal Dual Solution 174 4.2.4 Simplex Tableau Computations 177 4.3 Economic Interpretation of Duality 178 4.3.1 Economic Interpretation of Dual Variables 179 4.3.2 Economic Interpretation of Dual Constraints 180 4.4 Additional Simplex Algorithms 182 4.4.1 Dual Simplex Algorithm 182 4.4.2 Generalized Simplex Algorithm 1844.5 Post-Optimal Analysis 185 4.5.1 Changes Affecting Feasibility 186 4.5.2 Changes Affecting Optimality 189 Bibliography 192 Problems 192 Chapter 5 Transportation Model and Its Variants 207 5.1 Definition of the Transportation Model 207 5.2 Nontraditional Transportation Models 211 5.3 The Transportation Algorithm 214 5.3.1 Determination of the Starting Solution 216 5.3.2 Iterative Computations of the Transportation Algorithm 220 5.3.3 Simplex Method Explanation of the Method of Multipliers 226 5.4 The Assignment Model 227 5.4.1 The Hungarian Method 227 5.4.2 Simplex Explanation of the Hungarian Method 230 Bibliography 231 Case Study: Scheduling Appointments at Australian Tourist Commission Trade Events 232 Problems 236 Chapter 6 Network Model 247 6.1 Scope and Definition of Network Models 247 6.2 Minimal Spanning Tree Algorithm 250 6.3 Shortest-Route Problem 251 6.3.1 Examples of the Shortest-Route Applications 252 6.3.2 Shortest-Route Algorithms 255 6.3.3 Linear Programming Formulation of the Shortest-Route Problem 261 6.4 Maximal Flow Model 265 6.4.1 Enumeration of Cuts 266 6.4.2 Maximal Flow Algorithm 267 6.4.3 Linear Programming Formulation of Maximal Flow Mode 272 6.5 CPM and PERT 273 6.5.1 Network Representation 274 6.5.2 Critical Path Method (CPM) Computations 276 6.5.3 Construction of the Time Schedule 279 Contents 96.5.4 Linear Programming Formulation of CPM 282 6.5.5 PERT Networks 283 Bibliography 285 Case Study: Saving Federal Travel Dollars 286 Problems 289 Chapter 7 Advanced Linear Programming 305 7.1 Simplex Method Fundamentals 305 7.1.1 From Extreme Points to Basic Solutions 306 7.1.2 Generalized Simplex Tableau in Matrix Form 309 7.2 Revised Simplex Method 311 7.2.1 Development of the Optimality and Feasibility Conditions 311 7.2.2 Revised Simplex Algorithm 312 7.2.3 Computational Issues in the Revised Simplex Method 315 7.3 Bounded-Variables Algorithm 317 7.4 Duality 322 7.4.1 Matrix Definition of the Dual Problem 322 7.4.2 Optimal Dual Solution 322 7.5 Parametric Linear Programming 325 7.5.1 Parametric Changes in C 325 7.5.2 Parametric Changes in b 327 7.6 More Linear Programming Topics 329 Bibliography 330 Problems 330 Chapter 8 Goal Programming 341 8.1 A Goal Programming Formulation 341 8.2 Goal Programming Algorithms 343 8.2.1 The Weights Method 343 8.2.2 The Preemptive Method 345 Bibliography 350 Case Study: Allocation of Operating Room Time in Mount Sinai Hospital 350 Problems 354 Chapter 9 Integer Linear Programming 359 9.1 Illustrative Applications 359 9.1.1 Capital Budgeting 360 9.1.2 Set-Covering Problem 361 10 Contents9.1.3 Fixed-Charge Problem 362 9.1.4 Either-Or and If-Then Constraints 364 9.2 Integer Programming Algorithms 366 9.2.1 Branch-and-Bound (B&B) Algorithm 367 9.2.2 Cutting-Plane Algorithm 373 Bibliography 378 Problems 379 Chapter 10 Heuristic Programming 397 10.1 Introduction 397 10.2 Greedy (Local Search) Heuristics 398 10.2.1 Discrete Variable Heuristic 399 10.2.2 Continuous Variable Heuristic 401 10.3 Metaheuristic 404 10.3.1 Tabu Search Algorithm 404 Summary of Tabu Search Algorithm 408 10.3.2 Simulated Annealing Algorithm 408 Summary of Simulated Annealing Algorithm 410 10.3.3 Genetic Algorithm 411 Summary of Genetic Algorithm 414 10.4 Application of Metaheuristics to Integer Linear Programs 415 10.4.1 ILP Tabu Algorithm 416 10.4.2 ILP Simulated Annealing Algorithm 418 10.4.3 ILP Genetic Algorithm 420 10.5 Introduction to Constraint Programming (CP) 423 Bibliography 425 Problems 425 Chapter 11 Traveling Salesperson Problem (TSP) 435 11.1 Scope of the TSP 435 11.2 TSP Mathematical Model 437 11.3 Exact TSP Algorithms 441 11.3.1 B&B Algorithm 441 11.3.2 Cutting-Plane Algorithm 444 11.4 Local Search Heuristics 445 11.4.1 Nearest-Neighbor Heuristic 445 11.4.2 Reversal Heuristic 446 11.5 Metaheuristics 449 11.5.1 TSP Tabu Algorithm 449 11.5.2 TSP Simulated Annealing Algorithm 452 Contents 1111.5.3 TSP Genetic Algorithm 454 Bibliography 458 Problems 458 Chapter 12 Deterministic Dynamic Programming 469 12.1 Recursive Nature of Dynamic Programming (DP) Computations 469 12.2 Forward and Backward Recursion 473 12.3 Selected DP Applications 474 12.3.1 Knapsack/Fly-Away Kit/Cargo-Loading Model 475 12.3.2 Workforce Size Model 480 12.3.3 Equipment Replacement Model 482 12.3.4 Investment Model 485 12.3.5 Inventory Models 488 12.4 Problem of Dimensionality 488 Bibliography 490 Case Study: Optimization of Crosscutting and Log Allocation at Weyerhaeuser 491 Problems 494 Chapter 13 Inventory Modeling (with Introduction to Supply Chains) 501 13.1 Inventory Problem: A Supply Chain Perspective 501 13.1.1 An Inventory Metric in Supply Chains 502 13.1.2 Elements of the Inventory Optimization Model 504 13.2 Role of Demand in the Development of Inventory Models 505 13.3 Static Economic-Order-Quantity Models 507 13.3.1 Classical EOQ Model 507 13.3.2 EOQ with Price Breaks 511 13.3.3 Multi-Item EOQ with Storage Limitation 514 13.4 Dynamic EOQ Models 517 13.4.1 No-Setup EOQ Model 518 13.4.2 Setup EOQ Model 521 13.5 Sticky Issues in Inventory Modeling 530 Bibliography 531 Case Study: Kroger Improves Pharmacy Inventory Management 531 Problems 535 12 ContentsChapter 14 Review of Basic Probability 543 14.1 Laws of Probability 543 14.1.1 Addition Law of Probability 544 14.1.2 Conditional Law of Probability 544 14.2 Random Variables and Probability Distributions 545 14.3 Expectation of a Random Variable 547 14.3.1 Mean and Variance (Standard Deviation) of a Random Variable 547 14.3.2 Joint Random Variables 548 14.4 Four Common Probability Distributions 551 14.4.1 Binomial Distribution 551 14.4.2 Poisson Distribution 551 14.4.3 Negative Exponential Distribution 552 14.4.4 Normal Distribution 553 14.5 Empirical Distributions 555 Bibliography 560 Problems 560 Chapter 15 Decision Analysis and Games 567 15.1 Decision Making Under Certainty—Analytic Hierarchy Process (AHP) 567 15.2 Decision Making Under Risk 574 15.2.1 Decision Tree–Based Expected Value Criterion 574 15.2.2 Variants of the Expected Value Criterion 576 15.3 Decision Under Uncertainty 581 15.4 Game Theory 585 15.4.1 Optimal Solution of Two-Person Zero-Sum Games 585 15.4.2 Solution of Mixed Strategy Games 587 Bibliography 592 Case Study: Booking Limits in Hotel Reservations 593 Problems 595 Chapter 16 Probabilistic Inventory Models 611 16.1 Continuous Review Models 611 16.1.1 “Probabilitized” EOQ Model 611 16.1.2 Probabilistic EOQ Model 613 16.2 Single-Period Models 617 16.2.1 No-Setup Model (Newsvendor Model) 618 16.2.2 Setup Model (s-S Policy) 620 Contents 1316.3 Multiperiod Model 623 Bibliography 625 Problems 625 Chapter 17 Markov Chains 629 17.1 Definition of a Markov Chain 629 17.2 Absolute and n-Step Transition Probabilities 632 17.3 Classification of the States in a Markov Chain 633 17.4 Steady-State Probabilities and Mean Return Times of Ergodic Chains 634 17.5 First Passage Time 636 17.6 Analysis of Absorbing States 639 Bibliography 642 Problems 642 Chapter 18 Queuing Systems 653 18.1 Why Study Queues? 653 18.2 Elements of a Queuing Model 654 18.3 Role of Exponential Distribution 656 18.4 Pure Birth and Death Models (Relationship Between the Exponential and Poisson Distributions) 657 18.4.1 Pure Birth Model 658 18.4.2 Pure Death Model 661 18.5 General Poisson Queuing Model 662 18.6 Specialized Poisson Queues 665 18.6.1 Steady-State Measures of Performance 667 18.6.2 Single-Server Models 670 18.6.3 Multiple-Server Models 674 18.6.4 Machine Servicing Model—(M/M/R): (GD/K/K), R 6 K 680 18.7 (M/G/1):(GD/H/H)—Pollaczek-Khintchine (P-K) Formula 682 18.8 Other Queuing Models 683 18.9 Queuing Decision Models 684 18.9.1 Cost Models 684 18.9.2 Aspiration Level Model 686 Bibliography 688 14 ContentsContents 15 Case Study: Analysis of an Internal Transport System in a Manufacturing Plant 688 Problems 690 Chapter 19 Simulation Modeling 711 19.1 Monte Carlo Simulation 711 19.2 Types of Simulation 715 19.3 Elements of Discrete Event Simulation 715 19.3.1 Generic Definition of Events 715 19.3.2 Sampling from Probability Distributions 716 19.4 Generation of Random Numbers 720 19.5 Mechanics of Discrete Simulation 722 19.5.1 Manual Simulation of a Single-Server Model 722 19.5.2 Spreadsheet-Based Simulation of the Single-Server Model 726 19.6 Methods for Gathering Statistical Observations 728 19.6.1 Subinterval Method 729 19.6.2 Replication Method 730 19.7 Simulation Languages 731 Bibliography 733 Problems 733 Chapter 20 Classical Optimization Theory 741 20.1 Unconstrained Problems 741 20.1.1 Necessary and Sufficient Conditions 742 20.1.2 The Newton-Raphson Method 744 20.2 Constrained Problems 746 20.2.1 Equality Constraints 747 20.2.2 Inequality Constraints—Karush–Kuhn–Tucker (KKT) Conditions 754 Bibliography 758 Problems 758 Chapter 21 Nonlinear Programming Algorithms 763 21.1 Unconstrained Algorithms 763 21.1.1 Direct Search Method 763 21.1.2 Gradient Method 766 21.2 Constrained Algorithms 769 21.2.1 Separable Programming 770 21.2.2 Quadratic Programming 77721.2.3 Chance-Constrained Programming 781 21.2.4 Linear Combinations Method 785 21.2.5 SUMT Algorithm 787 Bibliography 788 Problems 788 Appendix A Statistical Tables 793 Appendix B Partial Answers to Selected Problems 797 Index 833 Index 100% feasibility rule in LP, 165 100% optimality rule in LP, 167 6-sigma limits, 554 A Absorbing state. See Markov chains Additive 0–1 algorithm, 367 Algorithm, definition of, 34 Al-Khwarizmi, Muhammad Ibn-Musa. See also Algorithm Alternative optima in LP, 119 AMPL, 57, 61–65, 159, C.1–39 algebraic model, C.3–9 components of, C.2 example models Chapter 2, C.24 Chapter 5, C.24–25 Chapter 6, C.25–30 Chapter 8, C.30–33 Chapter 9, C.33–34 Chapter 13, C.34–35 Chapter 21, C.35–36 execution of AMPL model, C.22 input files read, C.13–14 spreadsheet, C.19 table, C.15 833 interactive commands, C.20–21 long-hand model, C.1 mathematical expression, C.9–12 output files print, C.14–15 sensitivity analysis in LP, 138 sets, C.3 indexed, C.12–13 subsets, C.12 Analytical Engine, Babbage’s, 35 Analytic Hierarchy Process (AHP), 567–574 comparison matrix, 569 consistency, 571–572 normalizing a comparison matrix, 571 Applications of OR, selected. See Case analyses Art of modeling, 41 Artificial constraints in dual simplex method, 202 Artificial variable in simplex method, 112. See also M-method Aspiration criterion in tabu search, 407 Aspiration level criterion in queues, 686 Assignment model, 227–231 relationship to simplex method, 230 traveling salesperson problem, use in, 438 Attribute in simulation, 716834 Index B Babbage, Charles, 35 Backward pass in CPM, 276 Backward recursive equation in DP, 473 Balance equation in queues, 663 Balancing transportation model, 209–210 Balking in queues, 655 Barrier algorithm, 141. See also Interior point algorithm Basic solution, 101–102, 306–308 relationship to corner (extreme) point, 101, 306 Basic variable, 103, 307 Basis, 307. See also Inverse restricted, 772–774, 779 vector representation of, 307–308 Bayes’ probabilities, 562, 576–579 Bernoulli, Daniel, 579 Bernoulli, Nicolas, 579 Binomial distribution, 551 Poisson approximation of, 551–552 probability calculations with excelStatTables.xls, 551 Birthday problem, 543–544 Blending and refining model, 73–76 Bounded variables definition, 318 dual simplex algorithm for, 324 primal simplex algorithm for, 317–322 Box-Muller sampling method for normal distribution, 719–720 Branch-and-bound algorithm integer programming, 367–373 traveling salesperson (TSP), 441–444 Bridges of Königsberg, 249 Bus scheduling model, 68–70 C Capacitated network model, 22.1–11 conversion to uncapacitated, 22.33 LP equivalence, 22.2–4 simplex-based algorithm, 22.6–11 Capital budgeting, 360–361 Cargo-loading model. See Knapsack model Case analysis AHP CIM facility layout, 26.45–54 assignment model scheduling trade events, 26.13–17 Bayes’ probabilities Casey’s medical test evaluation, 26.56–59 decision trees hotel booking limits, 26.53–55 dynamic programming Weyerhauser log cutting, 26.41–45 game theory Ryder Cup matches, 26.59–61 goal programming CIM facility layout, 26.45–54 Mount Sinai hospital, 26.29–33 heuristics bid lines generation at FedEx, 397 fuel tankering, 26.2–9 scheduling trade events, 26.13–17 integer programming Mount Sinai hospital, 26.29–33 PFG building glass, 26.33–40 Qantas telephone sales staffing, 26.74–80 ship routing, 26.21–28 inventory Dell’s supply chain, 26.65–69 Kroger pharmacy inventory management using spreadsheet simulation, linear programming, 501, 531–535, 26.61–65 fuel tankering, 26.2–9 heart valve production, 26.9–13 Markov chains Forest cover change prediction sub-Himalayan India, 629, 26.69–71 queuing internal transport system, 26.72–74 Qantas telephone sales staffing, 26.74–80 shortest route saving federal travel dollars, 26.17–21 transportation ship routing, 26.21–28 traveling salesperson high resolution imaging in Australia, 435 Case studies, E.1–34 decision theory, E.25–28Index 835 Correlation coefficient, 23.6 Covariance, 549 CPM. See Critical Path Method Critical activity in CPM: definition, 276 determination of, 277–278 Critical path method (CPM) calculations, 276–278 Cumulative distribution function (CDF), 545 Curse of dimensionality in DP, 489 Cuts in integer programming, 373–378 maximum flow network, 266–267 traveling salesperson problem, 444–445 Cutting plane algorithm ILP, 373–378 TSP, 444–445 Cycle. See Loop Cycling in LP, 118–119, 141 D Dantzig, George B., 105, 250, 317, 378, 448, 590 Decision-making, types of, 567–609 certainty, 567–574 risk, 574–581 uncertainty, 581–584 Decision trees, 574–575 Decomposition algorithm, 22.13–21 Degeneracy, 118, 141. See also Cycling in LP Determinant of a square matrix, D.5–6 Deviational variables in goal programming, 342 Dichotomous search, 788 Die rolling experiment, 545, 548 Diet problem, 50–52 Difference Engine, Babbage’s, 35 Dijkstra’s algorithm, 255–258. See also Floyd’s algorithm Direct search method, 763–766 Discrete distribution, 547 Dual price algebraic determination of, 129, 323 graphical determination of, 125 relationship to dual variables, 180 dynamic programming, E.23, E.34 forecasting, E.34 goal programming, E.15–16 integer programming, E.23–25 inventory, E.23–25, E.28–30 linear programming, E.1–7, E.13–15 networks, E.11–13, E.33 queuing, E.30–33 transportation, E.7–11 CDF. See Cumulative density function Central limit theorem, 554 Chance-constrained programming, 781–784 Chapman-Kolomogrov equations, 632 Chebyshev model for regression analysis, 356 Chi-square statistical table, 795 Chi-square test. See Goodness-of-fit test Circling in LP. See Cycling in LP Classical optimization constrained, 746–758 Jacobian method, 747–753 Karush-Khun-Tucker conditions, 754–758 Lagrangean method, 753–754 unconstrained, 741–746 Newton-Raphson method, 744–746 Column-dropping rule in goal programming, 345–350 Computational issues in LP, 138–142 Concave function, D.15 Conditional probability, 544–545 Connected network, 248 Constrained gradient, 749 Constraint programming, 423–425 constraint propagation, 424 Continuous probability distribution, 545 Continuous review in inventory, 505 Convex combination, 306 Convex function, D.15 Convex set, 305 Corner point in LP, 50. See also Extreme point in LP relationship to basic solution, 101 relationship to extreme point in LP, 305836 Index Employment scheduling model, 22.4–6 EOQ constrained, 515 dynamic no setup model, 518–520 setup model, 521–530 probabilistic, 611–617 static classical, 507–511 price-breaks, 511–514 storage limitation, 514–518 Equation form of LP, 99–100 Equipment replacement model, 252–253, 482–485 Ergodic Markov chain, 634. See also Markov Chains Euler, Leonard, 249, 250 Event in probability, 543 simulation, 715 Excel Solver. See Solver (Excel-based) Expected value, definition of, 547 joint random variables, 548–550 Experiment, statistical, 543 Exponential (negative) distribution, 552–553, 656–657 forgetfulness property, 656 probability calculations with excelStatTables.xls, 553 Exponential smoothing, 23.3–4 Extreme point in LP definition of, 305 relationship to basic solution, 306–308 viewed graphically as corner point, 50 F Fathoming solutions in B&B algorithm, 369, 373 Feasible solution, 34 FIFO. See Queue discipline First passage time. See Markov chains Fixed-charge problem, 362–364 Floats in CPM, 280 Floyd’s algorithm, 258–261. See also Dijkstra’s algorithm Fly-away kit model. See Knapsack model Forecasting models, 23.1–10 Dual problem in LP definition of, 169–172, 322 economic interpretation dual constraint, 180–182 dual variable, 179–180. See also Dual price optimal solution, 174–177, 320–324 use in transportation algorithm, 226–227 weak duality theory, 322 Dual simplex method, 140, 182–184, 324. See also Generalized simplex algorithm artificial constraints in, 184, 185 bounded variables, 337 motivation for, 324 revised matrix form, 317–322 Dual variable optimal value of, 174–177 relationship to dual price, 179 Dynamic programming, 469–500 applications equipment replacement, 482–485 inventory deterministic, 521–527 probabilistic, 587–589 investment, 485–488 knapsack problem, 475–480 mill operation, 26.71–75 shortest route model, 469–473 workforce size, 480–482 backward recursion, 473 deterministic models, 469–500 dimensionality problem, 488 forward recursion, 473 Markovian decision process, 25.2–5 optimality principle, 473 probabilistic models, 24.1–11 recursive equation, 472 stage in DP, 470, 475 state in DP, 472, 475 E Economic order quantity. See EOQ Edge in LP solution space, 104 Either-or constraint, 364–366 Elevator problem, 39 Empirical distribution, 555–560Index 837 Heuristic definition, 34 Silver-Meal, 527–530 TSP, 445–448 types of greedy, 398–403 meta, 404–415 Histograms, 556 Hitchcock, Frank, 211 Hungarian method. See Assignment model Hurwicz criterion, 583, 584 I If-then constraint, 364 Imputed cost, 180. See also Dual price Index of optimism, 583 Inequalities, conversion to equations, 99 Infeasible solution in LP, 122 Insufficient reason, principle of, 582 Integer programming algorithms branch-and-bound, 367–373 bounding, 369, 373 branching, 369, 373 fathoming, 369, 373 cutting plane, 373–378 implicit enumeration. See Additive algorithm traveling salesperson branch and bound, 441–443 cutting plane, 444–445 Intensification and diversification in tabu search, 407 Interval programming, E.13–14 Inventory, case study deterministic models EOQ, 507–516 constrained, 515–516 price breaks, 511–514 spreadsheet solution of, 514 dynamic, spreadsheet solution of, 523–524 heuristic (Silver-Meal), spreadsheet solution of, 529–530 static, 507–508 probabilistic models EOQ, 611–617 multiple-period, 623–624 Forgetfulness of the exponential, 656 Forward pass in CPM, 276–277 Forward recursion in DP, 473 Fractional cut, 375 Franklin, Benjamin, 398 Franklin rule, 398 Full-rank matrix. See Nonsingular matrix G Game theory, zero-sum, 571–577 non-cooperative, (aha!), 589 optimal solution graphical, 587–590 linear programming, 590–592 saddle point, 586 value, 586 Gauss-Jordan method, 108, 111, D.8 Generalized simplex algorithm, 184–185 Genetic algorithm, 411–415 crossover, 411, 412 gene coding, 411 ILP application, 420–423 mutation, 411 TSP application, 454–457 Goal programming, 341–350 column-dropping rule, 345–346, 347–350 deviatinal variables, 342 preemptive method, 343, 345–350 weights method, 343–345 Golden-section search method, 763 Goodness-of-fit test, 557–560 Gradient method, 733–736 Graphical solution games, 587–590 LP maximization, 47 LP minimization, 50 Greedy search heuristic, 398–403 H Hamming, Richard, 437 Hamming distance, 437 Harris EOQ formula. See also Inventory models Harris, Ford, 511838 Index Lead time in inventory models, 508 Least-cost transportation starting solution, 216–217 Leonardo da Vinci, 448 Leontief, Wassily, 105 LIFO. See Queue discipline Linear combinations method, 770 Linear independence of vectors, 307 Linear programming applications, 67–76. See also Case analysis corner-point solution, 141. See also Extremepoint solution feasible solution, 47 graphical solution of a two-variable model maximization, 48 minimization, 50 infeasible solution, 49 optimum feasible solution, 184 post-optimal analysis, 169–192. See also Linear programming; sensitivity analysis additional constraint, 188–189 additional variable, 182 feasibility (right-hand side) changes, 186–187 optimality (objective function) changes, 182–184 sensitivity analysis. See also Post-optimal analysis algebraic, 132–136 using AMPL, 143–144 dual price, 132, 136, 200, 377 graphical, 124–132 reduced cost, 177, 180–184, 189, 311 using Solver, 141–142 using TORA, 137–138 Little’s queuing formula, 667 Loop in a network, 248 Lottery in a utility function, 579 Lovelace, Ada, 35 M M -method, 112–115. See also Two-phase method M/D/1 queue. See Pollaczek-Khintchine formula M/M/1 queue, 670–672 M/M/c queue, 675–680 M/M/R queue, 680–681 Inventory, case study (Continued) newsvendor problem, 618–620 s-S policy, 620–623 spreadsheet simulation of, 617, 620 Inventory policy, 504 Inventory ratio, 502–503 Interval of uncertainty, 763 Inverse of a matrix, D.7 computing methods adjoint, D.8 partitioned matrix, D.11–D12 product form, D.9 row (Gauss-Jordan) operations, D.8 determinant of, D.5 location in the simplex tableau, 177 Investment model, 60–62, 485–488 Iteration, definition of, 34 J Jacobian method, 747–753 relationship to Lagrangean method, 753 Job sequencing model, 364–366 Jockeying, 655 Joint probability distribution, 548–551 K Kamarkar algorithm. See Interior point algorithm Kantorovich, Leonid, 105, 211 Karush-Khun-Tucker (KKT) conditions, 754–758 Kendall notation, 666 Kepler, Johannes, 472–473 Knapsack problem, 292, 475–480 Kolmogrov-Smirnov test, 558 Koopmans, Tjalling, 211 L Lack of memory property. See Forgetfulness property Lagrangean method, 753 Lagrangean multipliers, 753 Laplace criterion, 582Index 839 applications cartographic label placement, 428–429 job sequencing, 405–407, 409–410 map coloring, 430–432 minimal spanning tree, constrained, 428 timetable scheduling, 430 warehouse allocation, 427 Military planning, 96 Minimal spanning tree algorithm, 250–251 constrained, 428 Mixed cut, 377 Mixed integer problem, 360 Model, elements of an OR, 34 abstraction levels, 36 Modeling art of, 36–37 levels of abstraction in, 36 Monge, Gaspard, 211 Monte Carlo simulation, 711–732 MRP, See Material requirement planning Multiplicative congruential method for random numbers, 720 Multipliers, method of, 220. See also Transportation algorithm N N queens problem as ILP, 390 Nash Equilibrium, See Game theory, non-cooperative Nash, John, 589 Needle spinning experiment, 548 Neighborhood in heuristics, definition of, 416 Network definitions, 247–250 Networks LP representation capacitated network, 266 critical path method, 273–274 maximum flow, 272 shortest route, 282–283 News vendor problem, 618–620 Newton-Raphson method, 744–746 Non-Poisson queues, 682 Nonbasic variable, 103, 309 Nonlinear programming algorithms, 763–788 Nonnegativity restriction, 54 Nonsingular matrix, 307, D.6 Machine repair queuing model, 680–681 Manpower planning model, 68–70. See also Workforce size Marginal probability distribution, 549 Mark Twain, 559 Markov chain, 629–642 absolute probabilities, 632–633 absorption, probability of, 640 closed set, 633 cost-based decision model, 636 first passage time, 636–638 initial probabilities, 632 mean return time, 634–636 n-step transition matrix, 632–633 Spam filter, use in,steady state probabilities, 631 state classification in Markov chains, 633–634 Markov process, definition of, 630 Markovian decision process, 25.1–25.16 Exhaustive enumeration solution, 25.8, 25.11 linear programming solution, 25.13–25.15 policy iteration method, 25.11 Marriage problem, 472–473 Materials requirement planning, 517–518 Mathematical model, definition of, 34, 40–41 Matrices, D.1–D.5 addition of, D.1 product of, D.3–D.4 simple arithmetic operations, review of, 172–173 Maximal flow model, 265–273 algorithm, 267–272 AMPL solution of, 273 cuts in, 267 LP formulation, 272–273 Solver solution of, 272–273 Maximin criterion, 582 Maximization, conversion to minimization, 111 Mean return time. See Markov chains Mean value, 547. See also Expected value, definition of Metaheuristics, 404–415 algorithms genetic, 411–415 simulated annealing, 408–410 tabu, 404–408840 Index Principle of optimality in DP, 472 Prior probabilities, 576. See also Bayes’ probabilities Prisoner’s Dilemma, 589–590 Pro-con list, See Franklin rule Probability density function definition of, 545 joint, 548–549 marginal, 548–550 Probability laws addition, 544 conditional, 544–545 Probability theory, review of, 473 Product form of inverse, 317, D.9–D.11 in the revised simplex method, 316 Production-inventory control multiple period, 64 with production smoothing, 65 shortest route model, viewed as a single period, 62–63 Program evaluation and review technique (PERT), 273–285 Pseudorandom numbers, 720 Pure birth model, 657–660 Pure death model, 661–662 Pure integer problem, 360 Q Quadratic forms, 778, D.14–15 Quadratic programming, 777–778, 781, 786, 790 Queue discipline, 655 FIFO, 655, 666 GD, 666 LIFO, 655, 666 SIRO, 655, 666 Queuing models, 655–684 decision models, 684–686 aspiration level, 686–688 cost, 654, 684–686 generalized model, 662–665 machine service model, 680–681 multiple-server models, 674–676 non-Poisson models, 682–683 single-server models, 670–674 simulation using spreadsheet, 726–728 Normal distribution, 553–555 calculations with excelStatTables.xls, 554–555 statistical tables, 781–782 Northwest-corner starting solution, 216–217, 219 O Observation-based variable in simulation, 726 Optimal solution, 59, 181 OR study, phases of, 37, 39, 40 OR techniques, 34 P Parametric programming, 325–329. See also Linear programming; sensitivity analysis Partitioned matrices inverse, 173, D.11–D.12 product of, 176, D.9–D11 Path in networks, 248 pdf. See Probability density function Penalty method in LP. See M-method Periodic review in inventory, 505 PERT. See Program evaluation and review technique Petersburg paradox, 579 Petrie, Flinders, 436–437 Poisson distribution, 551–552, 658–659 approximation of binomial, 551 calculations with excelStatTables.xls, 548 truncated, 661 Poisson queuing model, generalized, 665 Policy iteration, 55.41 Pollaczek-Khintchine formula, 682 Post-optimal analysis, 185–192. See also Parametric programming Posterior probabilities. See Bayes’ probabilities Pre-solver, 142 Preemptive method in goal programming, 345–347 Price breaks in inventory, 510–514 Pricing in LP, hybrid, 139 Primal simplex algorithm. See Simplex algorithm Primal-dual relationships in LP, 172–178, 309Index 841 Secondary constraints, 205 Secretary problem, See Marriage problem Seed of a random number generator, 713 Self-service queuing model, 679 Sensitivity analysis in dynamic programming, 477 Jacobian method, 752–753 linear programming. See Linear programming Separable programming, 770–777 convex, 774–777 Set covering problem, 362 Shadow price. See Dual price Shortest-route problem algorithms Dijkstra’s, 255–256 DP, 478 Floyds’s, 258 LP, 261–263 transshipment, 224 applications, 252–255 computer solution using AMPL, 265 Solver, 263–265 TORA, 258, 261 Silver-Meal heuristic, 527–529 Simon, Herbert, 344 Simplex algorithm. See also Generalized simplex algorithm entering variable, 107–109, 111, 312 feasibility condition, 111, 114, 312 Gauss-Jordan row operations, 108–111 leaving variable, 110, 319 optimality condition, 111, 119, 181, 312 ratios, 107 steps of, 117, 312–313 Simplex method algorithms dual, 182–184, 309 generalized, 182 primal, 140, 149, 178, 312–313 Simplex multiplier, 220. See also Dual price Simplex tableau, 106, 172 layout of, 173–174 matrix computation of, 175–176 matrix form of, 172, 309–311 R Random number generator, 713, 722 Random variables definition of, 546 expected value, 547 standard deviation, 547–548 variance, 547–548 Reddy Mikks model, 45–53, 55–58 Reduced cost, 132–140, 144–145, 190–191, 311 Regression analysis, 23.4, 23.8 using mathematical programming, 94–95, 356 Regret (Savage) criterion, 582 Reneging in queues, 655 Reorder point in inventory, 505, 508–509 Residuals in network, 267 Resource, types of, 110 Restricted basis, 772–774, 779 Revised simplex method dual, 322–325 primal, 322–325 Risk, types of, 574 Roundoff error in simplex method, 112, 113, 115 S sS policy, 620–623 Saddle point, 586 Sample space in probability, 543–544 Sampling from distributions discrete, 722–728 Erlang (gamma), 718 exponential, 717–718 normal, 719 Poisson, 718–719 triangular, 727–728 uniform, 727 Sampling in simulation, methods of acceptance-rejection, 716–717 convolution, 716, 718–719 inverse, 717–718 normal distribution transformation, Box-Muller, 719–720 Savage criterion. See Regret criterion842 Index Supply chains, 501 Surplus variable, 100 T Tabu search algorithm, 404–408 aspiration criterion, 407 ILP application, 415–418 intensification and diversification, 407 tabu list, 404 tabu tenure period, 404 TSP application, 449–451 Tankering (fuel), 45, 26.2–9 Time-based variable in simulation, 725 Tool sharpening model, 211–214 TOYCO model, 128 Traffic light control, 95 Transient period in simulation, 729 Transition probability. See Markov chains Transition-rate diagram in queues 662 Transportation model algorithm, 214–227 applications, 207, 211–214 balancing of, 209–210 definition, 207 LP equivalence, 208 solution using, AMPL, 226 Solver, 225 Starting solution, 214–219 tableau, 209 Transpose of a matrix, D.3 Transshipment model, 22.12–13 Traveling salesperson problem, 435–468 algorithms, exact branch and bound, 441–444 cutting-plane, 444–445 algorithms, heuristics nearest neighbor, 445–446 reversal, 446–448 algorithms, metaheuristics genetic, 454–457 simulated annealing, 452–454 tabu, 449–451 applications automatic guided vehicles, 459, 463 celestial objects imaging, 459, 463 Simulated annealing algorithm, 408–410 acceptance condition, 408 ILP application, 359–366 temperature schedule, 408 TSP application, 435–436 Simulation discrete-event animation, 732 languages, 731 mechanics of, 722–728 sampling, 716–720 spreadsheet, 726–728 inventory, 727, 738 queues, 684, 715–716, 727 steady state, 728 statistical observations, gathering of, 728–731 regenerative method, 729 replication method, 730 subinterval method, 729 transient state, 728–730 Simultaneous linear equations, types of solutions, 306–307 Slack variable, 99 Solver, commercial, 141–142 Solver (Excel-based), 52–56 Spanning tree, definition of, 248 basic solution in capacitated network, 52.37 Stage in DP, definition of, 470 State in DP, definition of, 472 State classification. See Markov chains Statistical tables, 793–795 chi-square, 795 Excel-based (16 pdfs), 548, 551, 552, 553, 555 normal, 793–794 student t, 794–795 Steady-state in Markov chains. See Markov Chains queuing. See Queuing models simulation. See Discrete event simulation Steepest ascent method. See Gradient method Strategies in games, mixed and pure, 586–587 Student t statistical tables, 794–795 Suboptimal solution, 34 Sudoku puzzle as ILP, 382 SUMT algorithm, 787–788Index 843 Variables, types of artificial, 112 basic, 103 binary, 359, 360 bounded, 317–319 deviational, 342 integer, 359 nonbasic, 103 slack, 99–100 surplus, 100 unrestricted, 57, 66 Variance of a random variable, 547–548 Vectors, D.1–2 linear independence, 307, D.2 Vogel approximation method (VAM), 218 W Waiting line models. See Queuing models Waiting time distribution, first-come first-serve, 655 Warm-up period, See Transient period Water quality management, 96 Weak duality theory, 322 Weights method in goal programming, 343–345 Wilson EOQ formula. See Harris’s EOQ formula Workforce size model using DP, 480–482 Z Zero-one integer problem, conversion to, 360 Zero-sum game, 585 DNA sequencing, 459, 462–463 high resolution imaging, 435 integrated circuit board, 459, 462 Mona Lisa art, 459 paint product sequencing, 438 protein clustering, 459, 460–461 wallpaper cutting, 463–464 warehouse order picking, 464–465 assignment model, relationship to, 438, 440 asymmetric distance matrix, 437 lower bound, 440–441 open tour solution, 440 solution of, 439 subtours, 437 symmetric distance matrix, 437 Tree, definition of, 248 Triple operation (Floyd’s algorithm), 258 TSP. See Traveling salesperson problem Two-person zero-sum game, 585 Two-phase method, 115–117. See also M-method U Unbounded solution in LP, 121–122, 313, 323 Uniform distribution, 546, 711, 735 Unit worth of a resource. See Dual price Unrestricted variable, 57, 66 in goal programming. See Deviational variables Upper-bounded variables, 318 Urban renewal model, 70–72 Utility functions, 580–581 V Value of a game, 586 VAM. See Vogel approximation method Variables, types of artificial, 112 basic, 103 binary, 359, 360 bounded, 317–319 deviational, 342 integer, 359 nonbasic, 103 slack, 99–100 surplus, 100 unrestricted, 57, 66 Variance of a random variable, 547–548 Vectors, D.1–2 linear independence, 307, D.2 Vogel approximation method (VAM), 218 W Waiting line models. See Queuing models Waiting time distribution, first-come first-serve, 655 Warm-up period, See Transient period Water quality management, 96 Weak duality theory, 322 Weights method in goal programming, 343–345 Wilson EOQ formula. See Harris’s EOQ formula Workforce size model using DP, 480–482 Z Zero-one integer problem, conversion to, 360 Zero-sum game, 585
كلمة سر فك الضغط : books-world.net The Unzip Password : books-world.net أتمنى أن تستفيدوا من محتوى الموضوع وأن ينال إعجابكم رابط من موقع عالم الكتب لتنزيل كتاب Operations Research - An Introduction رابط مباشر لتنزيل كتاب Operations Research - An Introduction
|
|