Introduction to Mathematical Programming

Chapter Preface page vii

Chapter 1 Introduction to the Problems page 1

Section 1.1 Introduction page 1

Section 1.2 Types of problems to be considered page 3

Section 1.3 Sample problems page 6

Section 1.4 Graphical solution of linear programs page 17

Section 1.5 Summary and objectives page 25

Chapter 2 Vectors and Matrices page 27

Section 2.1 Introduction page 27

Section 2.2 Vectors page 28

Section 2.3 The span of a set of vectors page 34

Section 2.4 Matrices page 38

Section 2.5 Linear independence page 47

Section 2.6 Systems of equations page 54

Section 2.7 The inverse of a matrix page 68

Section 2.8 Summary and objectives page 76

Chapter 3 Linear Programming page 81

Section 3.1 Introduction page 81

Section 3.2 Slack variables page 83

Section 3.3 The simplex algorithm page 89

Section 3.4 Basic feasible solutions and extreme points page 101

Section 3.5 Formulation examples page 111

Section 3.6 General constraints and variables page 127

Section 3.7 The dual and minimizing problems page 140

Section 3.8 Sensitivity analysis page 159

Section 3.9 Summary and objectives page 177

Chapter 4 Network Models page 181

Section 4.1 Introduction page 181

Section 4.2 The transportation problem page 187

Section 4.3 The critical path method page 209

Section 4.4 Shortest path models page 232

Section 4.5 Minimal spanning trees page 239

Section 4.6 Summary and objectives page 254

Chapter 5 Unconstrained Extrema page 257 < Section 5.1 Introduction page 257

Section 5.2 Locating extrema page 258

Section 5.3 The economic lot size model and convexity page 265

Section 5.4 Location of extrema in two variables page 277

Section 5.5 Least squares approximation page 286

Section 5.6 The \$n\$-variable case page 292

Section 5.7 Summary and objectives page 398

Chapter 6 Constrained Extrema page 301

Section 6.1 Introduction page 301

Section 6.2 Two variable problems page 308

Section 6.3 More variables; more constraints page 314

Section 6.4 Problems having inequality constraints page 324

Section 6.5 The convex programming problem page 334

Section 6.6 Linear programming revisited page 351

Section 6.7 Summary and objectives page 354

Chapter 7 Integer Programming page 357

Section 7.1 Introduction page 357

Section 7.2 The knapsack problem page 360

Section 7.3 The dual simplex algorithm page 369

Section 7.4 Adding a constraint page 378

Section 7.5 Branch and bound for integer programs: page 385

Section 7.6 Basic integer programming models page 392

Section 7.7 The traveling salesman problem page 410

Section 7.8 Summary and objectives page 421

Chapter 8 Introduction to Dynamic Programming page 425

Section 8.1 Introduction to recursion page 425

Section 8.2 The longest path page 433

Section 8.3 A fixed cost transportation problem page 436

Section 8.4 More examples page 441

Section 8.5 Summary and objectives page 448

Chapter 9 Case Studies page 451

Section 9.1 Tweaking Widget's production page 452

Section 9.2 A furniture sales opportunity page 459

Section 9.3 Building storage lockers page 460

Section 9.4 The McIntire farm page 451

Section 9.5 Cylinders for beverages page 462

Section 9.6 Books by the holidays page 464

Section 9.7 Into a blind trust page 466

Section 9.8 Max's taxes page 467

Section 9.9 A supply network page 468

Appendix Brief Introductions to LINDO and LINGO page 471

Section A.1 LINDO page 471

Section A.2 LINGO page 476

Appendix B A Brief Introduction to Maple page 481

Section B.1 The basics page 481

Section B,2 Using packages page 486

Appendix C Introduction to Texas Instruments Calculators page 493

Section C.1 A Brief Introduction to the TI-82 page 493

Section C.2 A Brief Introduction to the TI-92 page 501

Appendix D Selected Answers and Hints page 509

References page 535

Index page 539