Admin
مدير المنتدى
عدد المساهمات : 18724
التقييم : 34706
تاريخ التسجيل : 01/07/2009
الدولة : مصر
العمل : مدير منتدى هندسة الإنتاج والتصميم الميكانيكى
 |  موضوع: كتاب Operations Research - An Introduction الأحد 06 نوفمبر 2016, 8:40 pm | |
| 
أخوانى فى الله
أحضرت لكم كتاب
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 
|
|
