An 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 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