APPLIED LINEAR PROGRAMMING

By V. FAIRR

CONTENTS INTRODUCTION AN EXAMPLE: THE PROFESSOR’S DAIRY THE SETUP FORMULATING THE PROBLEM AND A GRAPHICAL SOLUTION CHANGING THE PROBLEM DISCUSSION FORMULATIONS APPLICATIONS THE DIET PROBLEM LINEAR SURFACE FITTING LOAD BALANCING PROBLEM RESOURCE ALLOCATION CLASSI?CATION MINIMUM-COST NETWORK FLOW ALGORITHMS AND COMPLEXITY THE SIMPLEX METHOD INTERIOR-POINT METHODS LINEAR ALGEBRA: A CONSTRUCTIVE APPROACH JORDAN EXCHANGE LINEAR INDEPENDENCE MATRIX INVERSION EXACT SOLUTION OF M EQUATIONS IN N UNKNOWNS SOLVING LINEAR EQUATIONS EF?CIENTLY LU DECOMPOSITION A SIMPLE EXAMPLE VERTICES THE PHASE II PROCEDURE THE PHASE I PROCEDURE FINITE TERMINATION THE NONDEGENERATE CASE CYCLING THE GENERAL CASE LINEAR PROGRAMS IN NONSTANDARD FORM TRANSFORMING CONSTRAINTS AND VARIABLES SCHEME I SCHEME II SUMMARY DUALITY DUALITY AND RANK IN LINEAR SYSTEMS DUALITY IN LINEAR PROGRAMMING INTERPRETATION OF LINEAR PROGRAMMING DUALITY DUALITY THEORY KKT OPTIMALITY CONDITIONS DUAL SIMPLEX METHOD GENERAL LINEAR PROGRAMS BIG M METHOD APPLICATIONS OF DUALITY SOLVING LARGE LINEAR PROGRAMS FOUNDATIONS BASIC FEASIBLE SOLUTIONS AND BASIS MATRICES GEOMETRIC VIEWPOINT THE REVISED SIMPLEX METHOD UPPER AND LOWER BOUNDS GENERATING BASIC FEASIBLE SOLUTIONS BASIS UPDATES ADVANCED PIVOT SELECTION MECHANISMS NETWORK FLOW PROBLEMS SHORTEST-PATH PROBLEM MAX-FLOW PROBLEM TRANSPORTATION PROBLEM ASSIGNMENT PROBLEM NETWORK SIMPLEX METHOD SENSITIVITY AND PARAMETRIC LINEAR PROGRAMMING SENSITIVITY ANALYSIS ADDING NEW VARIABLES OR CONSTRAINTS PARAMETRIC OPTIMIZATION OF THE OBJECTIVE FUNCTION PARAMETRIC OPTIMIZATION OF THE RIGHT-HAND SIDE QUADRATIC PROGRAMMING AND COMPLEMENTARITY PROBLEMS NONLINEAR PROGRAMS: OPTIMALITY CONDITIONS QUADRATIC PROGRAMMING BASIC EXISTENCE RESULT KKT CONDITIONS LINEAR COMPLEMENTARITY PROBLEMS LEMKE’S METHOD BIMATRIX GAMES COMPUTING NASH EQUILIBRIA ZERO-SUM GAMES AS DUAL LINEAR PROGRAMS MOTIVATION AND OUTLINE NEWTON’S METHOD PRIMAL-DUAL METHODS AN AF?NE-SCALING APPROACH PATH-FOLLOWING METHODS SOLUTION OF THE LINEAR SYSTEM AT EACH INTERIOR-POINT ITERATION PRACTICAL PRIMAL-DUAL METHODS INTERIOR-POINT VS SIMPLEX EXTENSION TO QUADRATIC PROGRAMMING APPROXIMATION AND CLASSI?CATION MINIMAX PROBLEMS APPROXIMATION CHEBYSHEV APPROXIMATION L1 APPROXIMATION APPROXIMATE SOLUTIONS TO SYSTEMS WITH INEQUALITY CONSTRAINTS LEAST-SQUARES PROBLEMS HUBER ESTIMATION CLASSI?CATION PROBLEMS