Linear Programming and Network Flows / Edition 3

Linear Programming and Network Flows / Edition 3

by Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali
     
 

ISBN-10: 0471485993

ISBN-13: 9780471485995

Pub. Date: 11/19/2004

Publisher: Wiley

The only book to treat both linear programming techniques and network flows under one cover, Linear Programming and Network Flows, Fourth Edition has been completely updated with the latest developments on the topic. This new edition continues to successfully emphasize modeling concepts, the design and analysis of algorithms, and implementation strategies for

Overview

The only book to treat both linear programming techniques and network flows under one cover, Linear Programming and Network Flows, Fourth Edition has been completely updated with the latest developments on the topic. This new edition continues to successfully emphasize modeling concepts, the design and analysis of algorithms, and implementation strategies for problems in a variety of fields, including industrial engineering, management science, operations research, computer science, and mathematics.

The book begins with basic results on linear algebra and convex analysis, and a geometrically motivated study of the structure of polyhedral sets is provided. Subsequent chapters include coverage of cycling in the simplex method, interior point methods, and sensitivity and parametric analysis. Newly added topics in the Fourth Edition include:

The cycling phenomenon in linear programming and the geometry of cycling

Duality relationships with cycling

Elaboration on stable factorizations and implementation strategies

Stabilized column generation and acceleration of Benders and Dantzig-Wolfe decomposition methods

Line search and dual ascent ideas for the out-of-kilter algorithm

Heap implementation comments, negative cost circuit insights, and additional convergence analyses for shortest path problems

The authors present concepts and techniques that are illustrated by numerical examples along with insights complete with detailed mathematical analysis and justification. An emphasis is placed on providing geometric viewpoints and economic interpretations as well as strengthening the understanding of the fundamental ideas. Each chapter is accompanied by Notes and Referencessections that provide historical developments in addition to current and future trends. Updated exercises allow readers to test their comprehension of the presented material, and extensive references provide resources for further study.

Linear Programming and network Flows, Fourth Edition is an excellent book for linear programming and network flow courses at the upper-undergraduate and graduate levels. It is also valuable resource for applied who would like to refresh their understanding of linear programming and network flow techniques.

Product Details

ISBN-13:
9780471485995
Publisher:
Wiley
Publication date:
11/19/2004
Edition description:
REV
Pages:
744
Product dimensions:
6.52(w) x 9.59(h) x 1.61(d)

Table of Contents

Preface xi

1 Introduction 1

1.1 The Linear Programming Problem 1

1.2 Linear Programming Modeling and Examples 7

1.3 Geometric Solution 18

1.4 The Requirement Space 2

1.5 Notation 27

Exercises 29

Notes and References 42

2 Linear Algebra, Convex Analysis, and Polyhedral Sets 45

2.1 Vectors 45

2.2 Matrices 51

2.3 Simultaneous Linear Equations 61

2.4 Convex Sets and Convex Functions 64

2.5 Polyhedral Sets and Polyhedral Cones 70

2.6 Extreme Points, Faces, Directions, and Extreme Directions of Polyhedral Sets: Geometric Insights 71

2.7 Representation of Polyhedral Sets 75

Exercises 82

Notes and References 90

3 The Simplex Method 91

3.1 Extreme Points and Optimality 91

3.2 Basic Feasible Solutions 94

3.3 Key to the Simplex Method 103

3.4 Geometric Motivation of the Simplex Method 104

3.5 Algebra of the Simplex Method 108

3.6 Termination: Optimality and Unboundedness 114

3.7 The Simplex Method 120

3.8 The Simplex Method in Tableau Format 125

3.9 Block Pivoting 134

Exercises 135

Notes and References 148

4 Starting Solution and Convergence 151

4.1 The Initial Basic Feasible Solution 151

4.2 The Two-Phase Method 154

4.3 The Big-M Method 165

4.4 How Big Should Big-M Be? 172

4.5 The Single Artificial Variable Technique 173

4.6 Degeneracy, Cycling, and Stalling 175

4.7 Validation of Cycling Prevention Rules 182

Exercises 187

Notes and References 198

5 Special Simplex Implementations and Optimality Conditions 201

5.1 The Revised Simplex Method 201

5.2 The Simplex Method for Bounded Variables 220

5.3 Farkas' Lemma via the Simplex Method 234

5.4 The Karush-Kuhn-Tucker Optimality Conditions 237

Exercises243

Notes and References 256

6 Duality and Sensitivity Analysis 259

6.1 Formulation of the Dual Problem 259

6.2 Primal-Dual Relationships 264

6.3 Economic Interpretation of the Dual 270

6.4 The Dual Simplex Method 277

6.5 The Primal-Dual Method 285

6.6 Finding an Initial Dual Feasible Solution: The Artificial Constraint Technique 293

6.7 Sensitivity Analysis 295

6.8 Parametric Analysis 312

Exercises 319

Notes and References 336

7 The Decomposition Principle 339

7.1 The Decomposition Algorithm 340

7.2 Numerical Example 345

7.3 Getting Started 353

7.4 The Case of an Unbounded Region X 354

7.5 Block Diagonal or Angular Structure 361

7.6 Duality and Relationships with other Decomposition Procedures 371

Exercises 376

Notes and References 391

8 Complexity of the Simplex Algorithm and Polynomial-Time Algorithms 393

8.1 Polynomial Complexity Issues 393

8.2 Computational Complexity of the Simplex Algorithm 397

8.3 Khachian's Ellipsoid Algorithm 401

8.4 Karmarkar's Projective Algorithm 402

8.5 Analysis of Karmarkar's Algorithm: Convergence, Complexity, Sliding Objective Method, and Basic Optimal Solutions 417

8.6 Affine Scaling, Primal-Dual Path Following, and Predictor-Corrector Variants of Interior Point Methods 428

Exercises 435

Notes and References 448

9 Minimal-Cost Network Flows 453

9.1 The Minimal Cost Network Flow Problem 453

9.2 Some Basic Definitions and Terminology from Graph Theory 455

9.3 Properties of the A Matrix 459

9.4 Representation of a Nonbasic Vector in Terms of the Basic Vectors 465

9.5 The Simplex Method for Network Flow Problems 466

9.6 An Example of the Network Simplex Method 475

9.7 Finding an Initial Basic Feasible Solution 475

9.8 Network Flows with Lower and Upper Bounds 478

9.9 The Simplex Tableau Associated with a Network Flow Problem 481

9.10 List Structures for Implementing the Network Simplex Algorithm 482

9.11 Degeneracy, Cycling, and Stalling 488

9.12 Generalized Network Problems 494

Exercises 497

Notes and References 511

10 The Transportation and Assignment Problems 513

10.1 Definition of the Transportation Problem 513

10.2 Properties of the A Matrix 516

10.3 Representation of a Nonbasic Vector in Terms of the Basic Vectors 520

10.4 The Simplex Method for Transportation Problems 522

10.5 Illustrative Examples and a Note on Degeneracy 528

10.6 The Simplex Tableau Associated with a Transportation Tableau 535

10.7 The Assignment Problem: (Kuhn's) Hungarian Algorithm 535

10.8 Alternating Path Basis Algorithm for Assignment Problems 544

10.9 A Polynomial-Time Successive Shortest Path Approach for Assignment Problems 546

10.10 The Transshipment Problem 551

Exercises 552

Notes and References 564

11 The Out-Of-Kilter Algorithm 567

11.1 The Out-of-Kilter Formulation of a Minimal Cost Network Flow Problem 567

11.2 Strategy of the Out-of-Kilter Algorithm 573

11.3 Summary of the Out-of-Kilter Algorithm 586

11.4 An Example of the Out-of-Kilter Algorithm 587

11.5 A Labeling Procedure for the Out-of-Kilter Algorithm 589

11.6 Insight into Changes in Primal and Dual Function Values 591

11.7 Relaxation Algorithms 593

Exercises 595

Notes and References 605

12 Maximal Flow, Shortest Path, Multicommodity Flow, And Network Synthesis Problems 607

12.1 The Maximal Flow Problem 607

12.2 The Shortest Path Problem 619

12.3 Polynomial-Time Shortest Path Algorithms for Networks Having Arbitrary Costs 635

12.4 Multicommodity Flows 639

12.5 Characterization of a Basis for the Multicommodity Minimal-Cost Flow Problem 649

12.6 Synthesis of Multiterminal Flow Networks 654

Exercises 663

Notes and References 678

Bibliography 681

Index 733

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >