Linear programming and network flows / Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali.

Format:

Book

Author/Creator:

Bazaraa, M. S., author.

Jarvis, John J., author.

Sherali, Hanif D., 1952- author.

Language:

English

Subjects (All):

Linear programming.

Physical Description:

1 online resource (764 p.)

Edition:

3rd ed.

Place of Publication:

Hoboken, New Jersey : Wiley, 2010.

Language Note:

English

Summary:

Linear Programming and Network Flows, now in its third edition, addresses the problem of minimizing or maximizing a linear function in the presence of linear equality or inequility constraints. This book:* Provides methods for modeling complex problems via effective algorithms on modern computers.* Presents the general theory and characteristics of optimization problems, along with effective solution algorithms.* Explores linear programming (LP) and network flows, employing polynomial-time algorithms and various specializations of the simplex method.

Contents:

Linear Programming and Network Flows; CONTENTS; Preface; ONE: INTRODUCTION; 1.1 The Linear Programming Problem; 1.2 Linear Programming Modeling and Examples; 1.3 Geometric Solution; 1.4 The Requirement Space; 1.5 Notation; Exercises; Notes and References; TWO: LINEAR ALGEBRA, CONVEX ANALYSIS, AND POLYHEDRAL SETS; 2.1 Vectors; 2.2 Matrices; 2.3 Simultaneous Linear Equations; 2.4 Convex Sets and Convex Functions; 2.5 Polyhedral Sets and Polyhedral Cones; 2.6 Extreme Points, Faces, Directions, and Extreme Directions of Polyhedral Sets: Geometric Insights; 2.7 Representation of Polyhedral Sets

ExercisesNotes and References; THREE: THE SIMPLEX METHOD; 3.1 Extreme Points and Optimality; 3.2 Basic Feasible Solutions; 3.3 Key to the Simplex Method; 3.4 Geometric Motivation of the Simplex Method; 3.5 Algebra of the Simplex Method; 3.6 Termination: Optimality and Unboundedness; 3.7 The Simplex Method; 3.8 The Simplex Method in Tableau Format; 3.9 Block Pivoting; Exercises; Notes and References; FOUR: STARTING SOLUTION AND CONVERGENCE; 4.1 The Initial Basic Feasible Solution; 4.2 The Two-Phase Method; 4.3 The Big-M Method; 4.4 How Big Should Big-M Be?

4.5 The Single Artificial Variable Technique4.6 Degeneracy, Cycling, and Stalling; 4.7 Validation of Cycling Prevention Rules; Exercises; Notes and References; FIVE: SPECIAL SIMPLEX IMPLEMENTATIONS AND OPTIMALITY CONDITIONS; 5.1 The Revised Simplex Method; 5.2 The Simplex Method for Bounded Variables; 5.3 Farkas' Lemma via the Simplex Method; 5.4 The Karush-Kuhn-Tucker Optimality Conditions; Exercises; Notes and References; SIX: DUALITY AND SENSITIVITY ANALYSIS; 6.1 Formulation of the Dual Problem; 6.2 Primal-Dual Relationships; 6.3 Economic Interpretation of the Dual

6.4 The Dual Simplex Method6.5 The Primal-Dual Method; 6.6 Finding an Initial Dual Feasible Solution: The Artificial Constraint Technique; 6.7 Sensitivity Analysis; 6.8 Parametric Analysis; Exercises; Notes and References; SEVEN: THE DECOMPOSITION PRINCIPLE; 7.1 The Decomposition Algorithm; 7.2 Numerical Example; 7.3 Getting Started; 7.4 The Case of an Unbounded Region X; 7.5 Block Diagonal or Angular Structure; 7.6 Duality and Relationships with other Decomposition Procedures; Exercises; Notes and References; EIGHT: COMPLEXITY OF THE SIMPLEX ALGORITHM AND POLYNOMIAL-TIME ALGORITHMS

8.1 Polynomial Complexity Issues8.2 Computational Complexity of the Simplex Algorithm; 8.3 Khachian's Ellipsoid Algorithm; 8.4 Karmarkar's Projective Algorithm; 8.5 Analysis of Karmarkar's Algorithm: Convergence, Complexity, Sliding Objective Method, and Basic Optimal Solutions; 8.6 Affine Scaling, Primal-Dual Path Following, and Predictor-Corrector Variants of Interior Point Methods; Exercises; Notes and References; NINE: MINIMAL-COST NETWORK FLOWS; 9.1 The Minimal Cost Network Flow Problem; 9.2 Some Basic Definitions and Terminology from Graph Theory; 9.3 Properties of the A Matrix

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

Notes:

Description based upon print version of record.

Includes bibliographical references and index.

Description based on online resource; title from PDF title page (ebrary, viewed August 1, 2016).

ISBN:

1-118-16444-X

1-118-21132-4

1-118-16445-8

1-283-29453-2

9786613294531

0-471-70377-X

0-471-70376-1

OCLC:

747540689