Introduction to Linear Programming and Game Theory

PAUL R. THIE, PhD, is Professor Emeritus in the Department of Mathematics at Boston College. Dr. Thie has authored numerous journal articles in the areas of mathematical programming and several complex variables.GERARD E. KEOUGH, PhD, is Associate Professor and former chair of the Department of Mathematics at Boston College. He has written extensively on operator theory, functional analysis, and the use of technology in mathematics. Dr. Keough is the coauthor of Getting Started with Maple, Second Edition and Getting Started with Mathematica, Second Edition, both published by Wiley.

• Preface xi1 Mathematical Models 11.1 Applying Mathematics 11.2 The Diet Problem 21.3 The Prisoner's Dilemma 51.4 The Roles of Linear Programming and Game Theory 82 The Linear Programming Model 92.1 History 92.2 The Blending Model 102.3 The Production Model 212.4 The Transportation Model 342.5 The Dynamic Planning Model 382.6 Summary 473 The Simplex Method 573.1 The General Problem 573.2 Linear Equations and Basic Feasible Solutions 633.3 Introduction to the Simplex Method 723.4 Theory of the Simplex Method 773.5 The Simplex Tableau and Examples 853.6 Artificial Variables 933.7 Redundant Systems 1013.8 A Convergence Proof 1063.9 Linear Programming and Convexity 1103.10 Spreadsheet Solution of a Linear Programming Problem 1154 Duality 1214.1 Introduction to Duality 1214.2 Definition of the Dual Problem 1234.3 Examples and Interpretations 1324.4 The Duality Theorem 1384.5 The Complementary Slackness Theorem 1545 Sensitivity Analysis 1615.1 Examples in Sensitivity Analysis 1615.2 Matrix Representation of the Simplex Algorithm 1755.3 Changes in the Objective Function 1835.4 Addition of a New Variable 1895.5 Changes in the Constant-Term Column Vector 1925.6 The Dual Simplex Algorithm 1965.7 Addition of a Constraint 2046 Integer Programming 2116.1 Introduction to Integer Programming 2116.2 Models with Integer Programming Formulations 2146.3 Gomory's Cutting Plane Algorithm 2286.4 A Branch and Bound Algorithm 2376.5 Spreadsheet Solution of an Integer Programming Problem 2447 The Transportation Problem 2517.1 A Distribution Problem 2517.2 The Transportation Problem 2647.3 Applications 2828 Other Topics in Linear Programming 2998.1 An Example Involving Uncertainty 2998.2 An Example with Multiple Goals 3068.3 An Example Using Decomposition 3148.4 An Example in Data Envelopment Analysis 3259 Two-Person, Zero-Sum Games 3379.1 Introduction to Game Theory 3379.2 Some Principles of Decision Making in Game Theory 3459.3 Saddle Points 3509.4 Mixed Strategies 3539.5 The Fundamental Theorem 3609.6 Computational Techniques 3709.7 Games People Play 38210 Other Topics in Game Theory 39110.1 Utility Theory 39110.2 Two-Person, Non-Zero-Sum Games 39310.3 Noncooperative Two-Person Games 39710.4 Cooperative Two-Person Games 40410.5 The Axioms of Nash 40810.6 An Example 414A Vectors and Matrices 417B An Example of Cycling 421C Efficiency of the Simplex Method 423D LP Assistant 427E Microsoft Excel and Solver 431Bibliography 439Solutions to Selected Problems 443Index 457