An Introduction to Linear Programming and Game Theory

ISBN-13: 9780470232866 / Angielski / Twarda / 2008 / 480 str.

Paul R. Thie; Gerard E. Keough

Opis

Praise 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 the Solver add-in for Microsoft Office Excel, for solving linear programming problems. LP Assistant, developed by coauthor Gerard Keough, allows readers to perform the basic steps of the algorithms provided in the book and is freely available via the book's related Web site. The use of the sensitivity analysis report and integer programming algorithm from the Solver add-in for Microsoft Office Excel is introduced so readers can solve the book's linear and integer programming problems. A detailed appendix contains instructions for the use of both applications. Additional features of the Third Edition include:

• A discussion of sensitivity analysis for the two-variable problem, along with new examples demonstrating integer programming, non-linear programming, and make vs. buy models
• Revised proofs and a discussion on the relevance and solution of the dual problem
• A section on developing an example in Data Envelopment Analysis
• An outline of the proof of John Nash's theorem on the existence of equilibrium strategy pairs for non-cooperative, non-zero-sum games

Providing a complete mathematical development of all presented concepts and examples, Introduction to Linear Programming and Game Theory, Third Edition is an ideal text for linear programming and mathematical modeling courses at the upper-undergraduate and graduate levels. It also serves as a valuable reference for professionals who use game theory in business, economics, and management science.

Spis treści

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

O autorze

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.