/> /> Table of Contents - Linear Programming, Ignizio & Cavalier


Linear Programming by Ignizio & Cavalier


LP Book Cover LINEAR PROGRAMMING
by James P. Ignizio and Tom M. Cavalier
Prentice Hall International Series in Industrial and Systems Engineering
Prentice Hall, Englewood Cliffs, NJ, 666pp (1994).

ISBN 0-13-183757-5


TMC's Homepage | TMC's Selected Pubs | LP by Ignizio & Cavalier | Woodworking - TMC


LP Preface | LP Table of Contents | IIE LP Book Review | LP Purchasing Info


TABLE OF CONTENTS

PART 1: CONVENTIONAL LINEAR PROGRAMMING

PART 2: NETWORK AND INTEGER MODELS

PART 3: MULTIOBJECTIVE OPTIMIZATION


  1. up INTRODUCTION AND OVERVIEW

    • The Linear Decision Model
    • What is Linear Programming? A Preview
    • Purpose
    • Applications of Linear Programming: A Preview
      • Traditional Applications
      • Applications in Artificial Intelligence and Information
      • Technology
    • Dealing with Problems of Sizes and Complexity
    • Beyond the Capabilities of Linear Programming
    • Intended Audience and Prerequisites
    • What is Different About This Text?
    • Overview of Material to Follow
    • Course Structure Recommendations


    PART 1: CONVENTIONAL LINEAR PROGRAMMING

  2. up THE (CONVENTIONAL) LINEAR PROGRAMMING MODEL
    • Chapter Overview
    • Models and Model Types
    • General Guidelines in Model Building
    • Definitions
    • Basic Steps in Linear Programming Model Formulation
      • Determination of the Decision Variables
      • Formulation of the Objective
      • Formulation of the Constraints
    • The General Form of the Linear Programming Model
    • Assumptions of the Linear Programming Model
    • Examples of Linear Programming Model Formulation
    • Model Validity
      • An Evaluation of Model Structure
      • An Evaluation of Model Logic
      • An Evaluation of the Design and/or Input Data
      • An Evaluation of Model Response
    • Summary
    • Exercises


  3. up FOUNDATIONS OF THE SIMPLEX METHOD
    • Chapter Overview
    • Converting a Linear Program into Standard Form
      • Constraint Conversion
      • The Objective Function
      • Notation and Definitions
    • Graphical Solution of 2-dimensional Linear Programs
    • Convex Sets and Polyhedral Sets
    • Extreme Points, Extreme Directions, and Optimality
    • Basic Feasible Solutions and Extreme Points
    • Summary
    • Exercises


  4. up THE SIMPLEX METHOD: TABLEAU AND COMPUTATION
    • Chapter Overview
    • Algebra of the Simplex Method
      • Checking for Optimality
      • Determining the Entering Variable
      • Determining the Departing Variable
      • Optimality Conditions and Directions
      • Checking for an Unbounded Objective
    • The Simplex Method in Tableau Form
      • Identifying B-1 from the Simplex Tableau
    • Finding and Initial Basic Feasible Solution
      • The Two-Phase Method
      • The Big-M Method
    • Unrestricted Variables and Variables with Negative Lower Bounds
    • Degeneracy and Cycling
      • The Lexicographic Minimum Ratio Test and Finite Convergence
    • Summary
    • Exercises


  5. up SPECIAL SIMPLEX IMPLEMENTATIONS
    • Chapter Overview
    • The Revised Simplex Method
      • Suboptimization
    • The Product Form of the Inverse
      • Operations with Elementary Matrices
    • The Bounded Variables Simplex Method
      • Checking for Optimality
      • Determining the Entering Variable
      • Increasing a Nonbasic Variable xk from Its Lower Bound lk
      • Decreasing a Nonbasic Variable xk from Its Upper Bound lk
    • Decomposition
    • Summary
    • Exercises


  6. up DUALITY AND SENSITIVITY ANALYSIS
    • Chapter Overview
    • Formulation of the Linear Programming Dual
      • The Canonical Form of the Dual
      • General Duality
      • The Standard Form
    • Relationships in Duality
      • Primal-Dual Tableau Relationships
      • Complementary Slackness
    • Geometric Interpretation of Optimality Conditions
    • Economic Interpretation of the Dual
      • The Dual Variables as Rates of Change
    • The Dual Simplex Algorithm
      • An Extended Dual Simplex Algorithm
    • Sensitivity Analysis in Linear Programming
      • Changes in the Objective Coefficients
      • Changes in the Right-Hand Side
      • Changes in the Technological Coefficients, ai,j
      • Addition of a New Variable
      • Addition of a New Constraint
    • Parametric Programming
      • Systemic Variation of the Cost Vector c
      • Systemic Variation of the Right-Hand Side Vector b
      • Resource Values and Ranges
      • Objective Coefficients and Ranges
    • Summary
    • Exercises


  7. up ALTERNATIVES TO THE SIMPLEX ALGORITHM
    • Chapter Overview
    • Computational Complexity
    • Khachian's Ellipsoid Algorithm
    • Affine Scaling Algorithms
      • A Primal Affine Scaling Algorithm
      • Finding an Initial Strictly Positive Solution
    • Karmarkar's Projective Algorithm
    • Summary
    • Exercises


  8. up APPLICATIONS OF LP IN INFORMATION TECHNOLOGY
    • Chapter Overview
    • Problem Types
    • Methods in Information Technology
    • Prediction via Linear Programming
    • Pattern Classification via LP
    • Enhanced Approached to Pattern Classification
      • Baek & Ignizio Algorithm for Pattern Classification
      • Other Modifications
    • Cluster Analysis via Mathematical Programming
    • Input-Output Analysis and LP
    • Simulation of Continuous Processing Systems
    • Summary and Conclusions
    • Exercises


    PART 2: NETWORK AND INTEGER MODELS

  9. up THE NETWORK SIMPLEX METHOD
    • Chapter Overview
    • Network Terminology
    • Minimum Cost Network Flow Problems
      • Bases and Rooted Spanning Trees
      • Unimodularity
    • The Network Simplex Method
      • Brief Review of the Standard Primal Simplex Method
      • Computing the Flows
      • Checking for Optimality and Choosing the Entering Arc
      • Determining the Departing Arc
      • Finding an Initial Basic Feasible Solution
    • Degeneracy and Cycling
      • Strongly Feasible Trees
    • Network Flow Problems with Bounds on the Flows
      • Determining the Entering Variable
      • Increasing the Flow on a Nonbasic Arc from Its Lower Bound
      • Decreasing the Flow on a Nonbasic Arc from Its Upper Bound
    • Applications
    • Summary
    • Exercises


  10. up THE TRANSPORTATION AND ASSIGNMENT PROBLEMS
    • Chapter Overview
    • The Transportation Problem
      • Properties of the Coefficient Matrix
      • Feasibility of the Model
      • Finiteness of the Objective Value
      • Finding and Initial Basic Feasible Solution
      • Optimality Conditions
      • Determining the Dual Solution
      • Checking for Optimality
      • Determining the Departing Variable
    • The Assignment Problem
      • The Dual Problem and Complementary Slackness
      • A Basic Primal-Dual Strategy
      • Choosing an Initial Dual Feasible Solution
      • Identifying an Assignment Corresponding to a Reduced Matrix
      • Modifying the Dual Solution and the Reduced Matrix
    • Summary
    • Exercises


  11. up INTEGER PROGRAMMING
    • Chapter Overview
    • Introduction
    • Graphical Solution of 2-Dimensional Integer Programs
    • Computational Complexity
    • Formulating Integer Programing Problems
      • The Knapsack Problem
      • The Set Covering Problem
      • The Fixed-Charge Problem
      • The Traveling Salesman Problem
      • Either-Or Constraints
      • P out of M Constraints
      • Representing General Integer Variables Using Zero-One Variables
      • Transforming a Piecewise Linear Function
    • Branch-and-Bound Enumeration
      • Branching
      • Computing Bounds
      • Fathoming
      • Search Strategies
    • Implicit Enumeration
      • The Zero Completion at a Node
      • The Infeasibility Test
      • Refinements
    • Cutting Plane Methods
      • Dual Fractional Cuts for Pure Integer Programs
    • Summary
    • Exercises


  12. up HEURISTIC PROGRAMMING - AND AI
    • Chapter Overview
    • Terminology and Definitions
    • Attitudes, Opinions, and AI
    • Fundamental Heuristics Types
    • The Add-Drop Heuristic Programming Method for Cluster Analysis/Site Location
      • Observations and Extensions
    • The Exchange Heuristic Programming Method for Cluster Analysis/Site Location
      • Observations and Extensions
    • A Heuristic Program for Scheduling and Deployment Problems
      • Extensions to Problems of Deployment
    • A Heuristic Program for Minimal Conflict Scheduling
    • Genetic "Algorithms"
      • Some Observations
    • Tabu Search, Simulated Annealing, Expert Systems, and Neural Networks
      • Tabu Search
      • Simulated Annealing
      • Expert Systems
      • Neural Networks
    • Assessment of Heuristic Programming Methods
    • Summary and Conclusions
    • Exercises


    PART 3: MULTIOBJECTIVE OPTIMIZATION

  13. up MULTIOBJECTIVE OPTIMIZATION
    • Chapter Overview
    • The Familiar Versus the the Nonconventional
    • An Illustrative Example
      • Conversion of a Linear Program via Objective Function Transformation (or Deletion)
      • Conversion to a Linear Program via Utility Theory: A Method of Aggregation
      • Conversion to a Goal Program
      • Conversion to a Chebyshev Goal Program
      • The Generating Method: The (Nearly) Perfect Approach
      • The Lexicographic Vectormax (Vectormin) Approach
      • Interactive Methods
    • Myths and Misconceptions
    • The Multiplex Approach: A Preview
    • Overview of Material to Follow
    • Summary
    • Exercises


  14. up MULTIOBJECTIVE MODELS
    • Chapter Overview
    • Terminology
    • Modeling Basics
      • The Weighting of Objectives
      • The Establishment of Aspiration Levels
      • The Processing of Goals
      • The Weighting of Unwanted Goal Deviations
      • The Ranking of Goals and/or Objectives
      • Scaling and Normalization of Goals
      • The Development of an Achievement Vector
    • Multiplex Formulations
      • Multiplex Model: Linear Programs
      • Multiplex Model: Archimedean Linear Goal Programs
      • Multiplex Model: Non-Archimedean Linear Goal Programs
      • Multiplex Model: Chebyshev and Fuzzy Linear Goal Programs
      • Multiplex Model: Linear Lexicographic Vectormin Problems
    • Good and Poor Modeling Practices
    • Summary
    • Exercises


  15. up MULTIPLEX ALGORITHM
    • Chapter Overview
    • Reduced form of the Multiplex Model
      • Basic Solutions and Basic Feasible Solutions
      • Associated Conditions
    • Revised Multiplex Algorithm
      • Algorithm Steps
      • Explicit Form of the Inverse: Tableau Representation
    • Sequential Multiplex
      • The Sequential Algorithm: For Linear Multiplex
      • Observations
    • Computational Considerations
    • Summary
    • Exercises


  16. up DUALITY AND SENSITIVITY ANALYSIS IN LINEAR MULTIPLEX
    • Chapter Overview
    • The Formulation of the Multidimensional Dual
    • Economic Interpretation
    • MDD Algorithms
      • The General MDD Algorithm
      • The Restricted MDD Algorithm
    • Sensitivity Analysis in Linear Multiplex
      • Discrete Sensitivity Analysis
      • Range Analysis
      • Sensitivity Analysis in Sequential Linear Multiplex
    • Summary
    • Exercises


  17. up EXTENSIONS OF MULTIPLEX
    • Chapter Overview
    • Integer Models
    • Nonlinear Models
    • Intelligent Interfaces
    • Summary and Conclusions


    up APPENDIX: LINEAR ALGEBRA REVIEW

    • Vectors
      • Vector Addition
      • Multiplication of a Vector by a Scalar
      • Vector Multiplication
      • Norm of a Vector
      • Special Vector Types
      • Linear Dependence and Independence
      • Spanning Sets and Bases
    • Matrices
      • Matrix Addition
      • Multiplication by a Scalar
      • Matrix Multiplication
      • Special Matrices
      • Determinants
      • The Inverse of a Matrix
      • The Rank of a Matrix
    • The Solution of Simultaneous Linear Equations
      • A Unique Solution of Ax = b
      • An Infinite Number of Solutions to Ax = b



LP Preface | LP Table of Contents | IIE LP Book Review | LP Purchasing Info


TMC's Homepage | TMC's Selected Pubs | LP by Ignizio & Cavalier | Woodworking - TMC




Website developed by Oxygenesis Design.