APPLIED MATHEMATICAL PROGRAMMING USING ALGEBRAIC SYSTEMS
CHAPTER I: INTRODUCTION 1 1 PRACTICAL PROBLEM ANALYSIS 1 2 MATHEMATICAL PROGRAMMING APPROACH 1 3 MATHEMATICAL PROGRAMMING IN USE 1 3 1 GENERATING PROBLEM INSIGHT 1 3 2 NUMERICAL MATHEMATICAL PROGRAMMING 1 3 3 ALGORITHMIC DEVELOPMENT 1 4 BOOK PLAN CHAPTER II: LINEAR PROGRAMMING 2 1 THE BASIC LP PROBLEM 2 2 BASIC LP EXAMPLE 2 3 OTHER FORMS OF THE LP PROBLEM 2 4 ASSUMPTIONS OF LP 2 4 1 OBJECTIVE FUNCTION APPROPRIATENESS 2 4 2 DECISION VARIABLE APPROPRIATENESS 2 4 3 CONSTRAINT APPROPRIATENESS 2 4 4 PROPORTIONALITY 2 4 5 ADDITIVITY 2 4 6 DIVISIBILITY 2 4 7 CERTAINTY CHAPTER III SOLUTION OF LP PROBLEMS: A MATRIX ALGEBRA APPROACH 3 1 MATRIX FORMULATION OF THE LINEAR PROGRAMMING PROBLEM 3 2 SOLVING LP'S BY MATRIX ALGEBRA 3 2 1 THE SIMPLEX ALGORITHM 3 2 2 EXAMPLE 3 3 SOLUTIONS AND THEIR INTERPRETATION 3 3 1 GENERAL SOLUTION INTERPRETATION 3 3 2 EXAMPLES OF SOLUTION INTERPRETATION 3 3 3 FINDING LIMITS OF INTERPRETATION 3 3 3 1 RANGING RIGHT-HAND-SIDES 3 3 3 2 RANGING OBJECTIVE FUNCTION COEFFICIENTS 3 3 3 3 CHANGES IN THE TECHNICAL COEFFICIENT MATRIX 3 3 4 FINDING THE SOLUTION 3 3 5 ALTERNATIVE OPTIMAL AND DEGENERATE CASES 3 3 6 FINDING SHADOW PRICES FOR BOUNDS ON VARIABLES 3 4 FURTHER DETAILS ON THE SIMPLEX METHOD 3 4 1 UPDATING THE BASIS INVERSE 3 4 2 ADVANCED BASES 3 4 3 2 PHASE I/PHASE II METHOD 3 4 4 THE REAL LP SOLUTION METHOD REFERENCES CHAPTER IV: DUALITY IN LINEAR PROGRAMMING 4 1 BASIC DUALITY 4 2 PRIMAL-DUAL SOLUTION INTER-RELATIONSHIPS 4 2 1 OBJECTIVE FUNCTION INTERRELATIONSHIPS 4 2 2 CONSTRUCTING DUAL SOLUTIONS 4 2 3 COMPLEMENTARY SLACKNESS 4 2 4 ZERO PROFITS 4 2 5 FINDING THE DUAL SOLUTION INFORMATION 4 3 DUALITY UNDER OTHER MODEL FORMS 4 4 THE CHARACTER OF DUAL SOLUTIONS 4 5 DEGENERACY AND SHADOW PRICES 4 6 PRIMAL COLUMNS ARE DUAL CONSTRAINTS CHAPTER V: LINEAR PROGRAMMING MODELING 5 1 INTRODUCTION TO ALGEBRAIC MODELING 5 1 1 DEFINING INDICES AND GAMS SETS 5 1 2 WRITING EQUATIONS 5 1 2 1 UNINDEXED EQUATIONS 5 1 2 2 INDEXED EQUATIONS 5 1 3 DATA DEFINITIONS 5 1 4 ENTERING DATA THROUGH CALCULATION 5 1 5 SPECIFICATION OF VARIABLES 5 1 6 EQUATIONS 5 1 7 WRITING MODEL EQUATIONS 5 1 7 1 OBJECTIVE FUNCTION EQUATIONS 5 1 7 2 CONSTRAINT EQUATIONS 5 1 8 SPECIFYING BOUNDS 5 1 9 FORMING AND SOLVING A MODEL 5 1 10 REPORT WRITING 5 1 11 ADDITIONAL GAMS TOPICS 5 2 PUTTING GAMS AND ALGEBRAIC MODELING TOGETHER -- THE RESOURCE ALLOCATION PROB5L-E1M3 5 2 1 EXAMPLE AND GAMS IMPLEMENTATION 5 2 2 MODEL SOLUTION 5 2 3 COMMENTS 5 3 THE TRANSPORTATION PROBLEM 5 3 1 EXAMPLE 5 3 2 COMMENTS 5 4 DIET/FEED MIX/BLENDING PROBLEM 5 5 JOINT PRODUCTS 5 5 1 EXAMPLE 5 5 2 COMMENTS 5 6 COMMENTS ON GAMS AND ALGEBRAIC MODELING 5 6 1 WHY USE ALGEBRAIC MODELING? 5 6 2 WHY USE GAMS TO SUPPORT MODELING? CHAPTER VI: TOWARD PROPER MODELING 6 1 STRUCTURAL COMPONENT IDENTIFICATION 6 1 1 DEVELOPMENT OF MODEL CONSTRAINTS 6 1 2 AVOIDING IMPROPER CONSTRAINT SPECIFICATIONS 6 1 3 VARIABLE IDENTIFICATION 6 1 4 OBJECTIVE FUNCTION 6 1 5 DEVELOPMENT OF MODEL STRUCTURE 6 2 THE PROPER USAGE OF VARIABLES AND CONSTRAINTS 6 2 1 IMPROPER AND PROPER HANDLING OF JOINT PRODUCTS 6 2 2 ALTERNATIVES FOR THE USE OF A PRODUCT 6 2 3 IMPROPER SPECIFICATION OF MULTIPLE FACTOR RELATIONSHIPS 6 2 4 ERRONEOUS IMPERFECT SUBSTITUTION 6 3 SIMPLE STRUCTURAL CHECKING 6 3 1 HOMOGENEITY OF UNITS 6 3 2 NUMERICAL MODEL ANALYSIS 6 4 DATA DEVELOPMENT 6 4 1 TIME FRAME 6 4 2 UNCERTAINTY 6 4 3 DATA SOURCES 6 4 4 CALCULATION METHODS 6 4 5 CONSISTENCY 6 4 6 SPECIFICATION OF INDIVIDUAL COMPONENTS 6 4 6 1 OBJECTIVE FUNCTION COEFFICIENTS 6 4 6 2 RIGHT HAND SIDE COEFFICIENTS 6 4 6 3 TECHNICAL COEFFICIENTS 6 5 PURPOSEFUL MODELING 6 5 1 MODEL STRUCTURE 6 5 2 REPORT WRITING CHAPTER VII: MORE LINEAR PROGRAMMING MODELING 7 1 ASSEMBLY PROBLEM 7 1 1 EXAMPLE 7 1 2 COMMENTS 7 2 DISASSEMBLY PROBLEMS 7 3 ASSEMBLY-DISASSEMBLY 7 3 1 EXAMPLE 7 3 2 COMMENTS 7 4 SEQUENCING PROBLEMS 7 4 1 EXAMPLE 7 4 2 EXAMPLE 7 4 3 COMMENTS 7 5 STORAGE PROBLEMS 7 5 1 EXAMPLE 7 5 2 COMMENTS 7 6 INPUT OUTPUT ANALYSIS 7 6 1 EXAMPLE 7 6 2 COMMENTS 7 7 BLOCK DIAGONAL 7 7 1 EXAMPLE 7 7 2 COMMENTS 7 8 CONCLUDING COMMENTS CHAPTER VIII: MULTI-YEAR DYNAMICS AND LINEAR PROGRAMMING 8-1 8 1 DYNAMICS BACKGROUND 8 1 1 SHOULD DYNAMICS BE EXPLICIT? 8 1 2 HOW LONG 8 1 3 TIME INTERVAL REPRESENTATION 8 1 4 INITIAL AND TERMINAL CONDITIONS 8 1 5 ENTERPRISE LIFE 8 1 6 TIME PREFERENCE 8 1 7 RISK 8 2 DYNAMIC LINEAR PROGRAMMING 8 2 1 DISEQUILIBRIUM - KNOWN LIFE 8 2 1 1 EXAMPLE 8 2 2 DISEQUILIBRIUM - UNKNOWN LIFE 8 2 2 1 EXAMPLE 8 2 2 2 COMMENTS 8 2 3 EQUILIBRIUM - KNOWN LIFE 8 2 3 1 EXAMPLE 8 2 3 2 EXAMPLE 8 2 3 3 COMMENTS 8 2 5 OVERALL COMMENTS ON DYNAMIC LINEAR PROGRAMMING 8 3 RECURSIVE PROGRAMMING 8 3 1 EXAMPLE 8 3 2 COMMENTS ON RECURSIVE PROGRAMMING CHAPTER IX: LINEAR PROGRAMMING MODELING NONLINEARITIES AND APPROXIMATION 9 1 TRANSFORMATIONS 9 1 1 MINIMIZATION OF THE SUM OF ABSOLUTE DEVIATIONS 9 1 1 1 EXAMPLE 9 1 1 2 COMMENTS 9 1 2 MINIMIZATION OF LARGEST ABSOLUTE DEVIATION 9 1 2 1 EXAMPLE 9 1 2 2 COMMENTS 9 1 3 OPTIMIZING A FRACTION 9 1 3 1 EXAMPLE 9 1 3 2 COMMENTS 9 2 APPROXIMATIONS 9 2 1 GRID POINT APPROXIMATIONS 9 2 1 2 FUNCTIONS WITH SEPARABLE VARIABLES 9 2 1 1 1 EXAMPLE 9 2 1 1 2 EXAMPLE 2: SEPARABLE TERMS IN THE CONSTRAINTS 9 2 1 2 GRIDPOINTS AND GRIDPOINT REFINEMENTS 9 2 1 3 GRIDPOINT APPROXIMATION OF FUNCTIONS OF MULTIPLE VARIABLES 9-14 9 2 1 3 1 HOMOGENEOUS OF DEGREE 9 2 1 3 2 HOMOGENEOUS OF DEGREE LESS THAN ONE 9 2 1 3 3 COMMENTS 9 2 2 ITERATIVE APPROXIMATIONS 9 2 3 OTHER APPROXIMATIONS CHAPTER X: MODELING SUMMARY 10 1 TYPES OF CONSTRAINTS AND VARIABLES IN LINEAR PROGRAMMING MODELS 10 1 1 TYPES OF CONSTRAINTS 10 1 1 1 RESOURCE LIMITATIONS 10 1 1 2 MINIMUM REQUIREMENTS 10 1 1 3 SUPPLY AND DEMAND BALANCE 10 1 1 4 RATIO CONTROL 10 1 1 5 BOUNDS 10 1 1 6 ACCOUNTING RELATIONS 10 1 1 7 DEVIATION CONSTRAINTS 10 1 2 1 PRODUCTION VARIABLES 10 1 2 2 SALES VARIABLES 10 1 2 3 PURCHASE VARIABLES 10 1 2 4 TRANSFORMATION VARIABLES 10 1 2 5 SLACK VARIABLES 10 1 2 6 SURPLUS VARIABLES 10 1 2 7 ARTIFICIAL VARIABLES 10 1 2 8 STEP VARIABLES 10 1 2 9 DEVIATION VARIABLES 10 1 2 10 ACCOUNTING VARIABLES 10 2 "VIOLATIONS" OF THE ALGORITHMIC ASSUMPTIONS 10 2 1 NONPROPORTIONAL EXAMPLE 10 2 2 NON-ADDITIVE EXAMPLE 10 2 3 UNCERTAINTY EXAMPLES 10 2 4 NONCONTINUOUS EXAMPLE CHAPTER XI: MULTI-OBJECTIVE PROGRAMMING 11 1 FORMULATIONS 11 1 1 LEXICOGRAPHIC UTILITY - TARGET VALUES 11 1 2 UTILITY TRADEOFF MODEL 11 1 3 UNKNOWN UTILITY FUNCTION 11 2 EXAMPLES 11 2 1 LEXICOGRAPHIC FORMULATION 11 2 2 WEIGHTED TRADEOFF - NO TARGETS 11 2 3 WEIGHTED OBJECTIVE AND TARGETS 11 3 CHOICE AMONG FORMULATIONS 11 4 DEVELOPING UTILITY FUNCTIONS 11 5 SHADOW PRICES 11 5 1 EXAMPLE CHAPTER XII: NONLINEAR OPTIMIZATION CONDITIONS 12 1 OPTIMALITY CONDITIONS 12 1 1 UNCONSTRAINED OPTIMIZATION 12 1 1 1 UNIVARIATE 12 1 1 2 MULTIVARIATE FUNCTIONS 12 1 2 GLOBAL OPTIMA-CONCAVITY AND CONVEXITY 12 1 3 CONSTRAINED OPTIMIZATION 12 1 3 1 EQUALITY CONSTRAINTS - THE LAGRANGIAN 12 1 3 1 1 SECOND ORDER CONDITIONS - CONSTRAINT QUALIFICATIONS CONVEXITY AND CONCAVITY 12 1 3 1 2 INTERPRETATION OF LAGRANGE MULTIPLIERS 12 1 3 2 2 EXAMPLE 12 1 4 USAGE OF OPTIMALITY CONDITIONS 12 2 NOTES ON SOLUTION OF NONLINEAR PROGRAMMING MODELS 12 3 EXPRESSING NONLINEAR PROGRAMS IN CONJUNCTION WITH GAMS CHAPTER XIII: PRICE ENDOGENOUS MODELING 13 1 SPATIAL EQUILIBRIUM 13 2 MULTI-MARKET CASE 13 3 IMPLICIT SUPPLY - MULTIPLE FACTORS/PRODUCTS 13 4 AGGREGATION 13 5 A DIGRESSION ON THE ASSUMPTIONS 13 6 IMPERFECT COMPETITION 13 7 CONCLUSION CHAPTER XIV: RISK MODELING 14 1 DECISION MAKING AND RECOURSE 14 2 AN ASIDE: DISCOUNTING COEFFICIENTS 14 3 STOCHASTIC PROGRAMMING WITHOUT RECOURSE 14 3 1 OBJECTIVE FUNCTION COEFFICIENT RISK 14 3 1 1 MEAN-VARIANCE ANALYSIS 14 3 1 1 1 EXAMPLE 14 3 1 1 2 MARKOWITZ'S E-V FORMULATION 14 3 1 1 3 FORMULATION CHOICE 14 3 1 1 4 CHARACTERISTICS OF E-V MODEL OPTIMAL SOLUTIONS 14 3 1 1 5 E-V MODEL USE - THEORETICAL CONCERNS 14 3 1 1 6 SPECIFICATION OF THE RISK AVERSION PARAMETER 14 3 1 2 A LINEAR APPROXIMATION - MOTAD 14 3 1 2 1 EXAMPLE 14 3 1 2 2 COMMENTS ON MOTAD 14 3 1 3 TOWARD A UNIFIED MODEL 14 3 1 4 SAFETY FIRST 14 3 1 4 1 EXAMPLE 14 3 1 4 2 COMMENTS 14 3 1 5 TARGET MOTAD 14 3 1 5 1 EXAMPLE 14 3 1 5 2 COMMENTS 14 3 1 6 DEMP 14 3 1 6 1 EXAMPLE 14 3 1 6 2 COMMENTS 14 3 1 7 OTHER FORMULATIONS 14 3 2 1 1 EXAMPLE 14 3 2 1 2 COMMENTS 14 3 2 2 A QUADRATIC PROGRAMMING APPROACH 14 3 3 TECHNICAL COEFFICIENT RISK 14 3 3 1 MERRILL'S APPROACH 14 3 3 2 WICKS AND GUISE APPROACH 14 3 3 2 1 EXAMPLE 14 3 3 2 2 COMMENTS 14 3 4 MULTIPLE SOURCES OF RISK 14 4 SEQUENTIAL RISK-STOCHASTIC PROGRAMMING WITH RECOURSE 14 4 1 TWO STAGE SPR FORMULATION 14 4 1 1 EXAMPLE 14 4 2 INCORPORATING RISK AVERSION 14 4 2 1 EXAMPLE 14 4 3 EXTENDING TO MULTIPLE STAGES 14 4 4 MODEL DISCUSSION 14 5 GENERAL COMMENTS ON MODELING UNCERTAINTY CHAPTER XV: APPLIED INTEGER PROGRAMMING 15 1 WHY INTEGER PROGRAMMING 15 1 1 FIXED COST 15 1 2 LOGICAL CONDITIONS 15 1 2 1 EITHER-OR-ACTIVE CONSTRAINTS 15 1 2 2 AN ASIDE: MUTUAL EXCLUSIVITY 15 1 2 3 MULTIPLE ACTIVE CONSTRAINTS 15 1 2 4 CONDITIONAL RESTRICTIONS 15 1 3 DISCRETE LEVELS OF RESOURCES 15 1 4 DISTINCT VARIABLE VALUES 15 1 5 NONLINEAR REPRESENTATIONS 15 1 6 APPROXIMATION OF NONLINEAR FUNCTIONS 15 2 FEASIBLE REGION CHARACTERISTICS AND SOLUTION DIFFICULTIES 15 2 1 EXTENSION TO MIXED INTEGER FEASIBLE REGIONS 15 3 SENSITIVITY ANALYSIS AND INTEGER PROGRAMMING 15 4 SOLUTION APPROACHES TO INTEGER PROGRAMMING PROBLEMS 15 4 1 ROUNDING 15 4 2 CUTTING PLANES 15 4 3 BRANCH AND BOUND 15 4 5 LAGRANGIAN RELAXATION 15 4 6 BENDERS DECOMPOSITION