Description
Book SynopsisPraise for the Second Edition: This is quite a well-done book: very tightly organized, better-than-average exposition, and numerous examples, illustrations, and applications.
Mathematical Reviews of the American Mathematical Society
An Introduction to Linear Programming and Game Theory, Third Edition presents a rigorous, yet accessible, introduction to the theoretical concepts and computational techniques of linear programming and game theory. Now with more extensive modeling exercises and detailed integer programming examples, this book uniquely illustrates how mathematics can be used in real-world applications in the social, life, and managerial sciences, providing readers with the opportunity to develop and apply their analytical abilities when solving realistic problems.
This Third Edition addresses various new topics and improvements in the field of mathematical programming, and it also presents two software programs, LP Assistant and t
Table of Contents
Preface xi
1 Mathematical Models 1
1.1 Applying Mathematics 1
1.2 The Diet Problem 2
1.3 The Prisoner's Dilemma 5
1.4 The Roles of Linear Programming and Game Theory 8
2 The Linear Programming Model 9
2.1 History 9
2.2 The Blending Model 10
2.3 The Production Model 21
2.4 The Transportation Model 34
2.5 The Dynamic Planning Model 38
2.6 Summary 47
3 The Simplex Method 57
3.1 The General Problem 57
3.2 Linear Equations and Basic Feasible Solutions 63
3.3 Introduction to the Simplex Method 72
3.4 Theory of the Simplex Method 77
3.5 The Simplex Tableau and Examples 85
3.6 Artificial Variables 93
3.7 Redundant Systems 101
3.8 A Convergence Proof 106
3.9 Linear Programming and Convexity 110
3.10 Spreadsheet Solution of a Linear Programming Problem 115
4 Duality 121
4.1 Introduction to Duality 121
4.2 Definition of the Dual Problem 123
4.3 Examples and Interpretations 132
4.4 The Duality Theorem 138
4.5 The Complementary Slackness Theorem 154
5 Sensitivity Analysis 161
5.1 Examples in Sensitivity Analysis 161
5.2 Matrix Representation of the Simplex Algorithm 175
5.3 Changes in the Objective Function 183
5.4 Addition of a New Variable 189
5.5 Changes in the Constant-Term Column Vector 192
5.6 The Dual Simplex Algorithm 196
5.7 Addition of a Constraint 204
6 Integer Programming 211
6.1 Introduction to Integer Programming 211
6.2 Models with Integer Programming Formulations 214
6.3 Gomory's Cutting Plane Algorithm 228
6.4 A Branch and Bound Algorithm 237
6.5 Spreadsheet Solution of an Integer Programming Problem 244
7 The Transportation Problem 251
7.1 A Distribution Problem 251
7.2 The Transportation Problem 264
7.3 Applications 282
8 Other Topics in Linear Programming 299
8.1 An Example Involving Uncertainty 299
8.2 An Example with Multiple Goals 306
8.3 An Example Using Decomposition 314
8.4 An Example in Data Envelopment Analysis 325
9 Two-Person, Zero-Sum Games 337
9.1 Introduction to Game Theory 337
9.2 Some Principles of Decision Making in Game Theory 345
9.3 Saddle Points 350
9.4 Mixed Strategies 353
9.5 The Fundamental Theorem 360
9.6 Computational Techniques 370
9.7 Games People Play 382
10 Other Topics in Game Theory 391
10.1 Utility Theory 391
10.2 Two-Person, Non-Zero-Sum Games 393
10.3 Noncooperative Two-Person Games 397
10.4 Cooperative Two-Person Games 404
10.5 The Axioms of Nash 408
10.6 An Example 414
A Vectors and Matrices 417
B An Example of Cycling 421
C Efficiency of the Simplex Method 423
D LP Assistant 427
E Microsoft Excel and Solver 431
Bibliography 439
Solutions to Selected Problems 443
Index 457
