This book covers all aspects of linear programming from the two-dimensional LPs and their extension to higher dimensional LPs, through duality and sensitivity analysis and finally to the examination of commented software outputs.The book is organised into three distinct parts: the first part studies the concepts of linear programming and presents its founding theorems complete with proofs and applications; the second part presents linear programming in the diversity of its variants (Integer Programming, Game Theory, Transportation Problem, Assignment Model), and highlights the modelling problems that are involved in network optimisation; the final part furthers the discussion on selected topics and presents an opening to nonlinear programming through quadratic programming.
PrefaceAcknowledgements1 Introduction1.1. Modelling using Linear Programming1.2. Solving linear programmes 1.2.1. The graphical solution and the importance of visual displays. 1.2.2. The Simplex Method and its main variants 1.2.3. Computer software packages 1.2.4. Complementary information and Sensitivity Analysis1.3. Linear Programming: the Approach par excellence for understanding modelling 1.3.1. The variants of Linear Programming 1.3.2. LP's related topics1.4. The Approach of the bookPart I Linear Programming and Sensitivity Analysis2 The Geometric Approach 2.1. The founding concepts of Linear Programming 2.2. The Maximization Form Application # 1: An advertising campaign [Aurel 2D] 2.2.1. The mathematical formulation 2.2.2. The graphical solution and the fundamental theorem of LP - Basic vs. non-basic variables - Basic solution vs. basic feasible solution - The Fundamental Theorem of Linear Programming 2.2.3. Interpreting the slack and surplus variables 2.2.4. Shadow prices Application # 2: Computer games 2.3. The Minimization Form Application # 3: A Portfolio selection Chapter 2 Exercises and applications 3 The Simplex Method3.1. The Maximization Form 3.1.1. The Standard Form 3.1.2. The simplex algorithm (using tableaux) 3.1.3. Shadow prices and reduced costs. 3.1.4. The algorithm (using matrix algebra) 3.1.5. Introduction of artificial variables 3.1.6. The remarkable features of the simplex algorithm 3.2. The Minimization Form 3.3. The Revised Simplex Method 3.3.1. The revised simplex algorithm 3.3.2. Using artificial variables: adjusting the algorithm Chapter 3 Exercises and applications4 Understanding Special Cases and Mixed Function Problems4.1. Identifying special cases: graphical and simplex approaches 4.1.1. Alternative optimal solutions 4.1.2. Unboundedness 4.1.3. Infeasibility versus point solution 4.1.4. Degenerate solutions 4.1.5. Special types of constraints4.2. The mixed function problemChapter 4 Exercises and applications5 Duality 5.1. Theorems of duality and relationships 5.1.1. The theorems of duality 5.1.2. Primal / dual relationships 5.1.3. Formulating duals using the general primal formats 5.1.4. Primal / dual interrelationships: the Complementary Slackness theorem 5.2. The Dual Simplex Method5.3. Particular Cases: 5.3.1. Unrestricted-in-sign variables (free variables) 5.3.2. Revisiting the special cases: study of the behaviour of their dualsChapter 5 Exercises and applications6 Sensitivity Analysis6.A A visual approach to Sensitivity Analysis6.1. The Maximization Form 6.1.1. The range of optimality: separate and simultaneous changes 6.1.2. The range of feasibility 6.1.3. Note on a few specific cases 6.2. The Minimization Form 6.B Sensitivity Analysis under the Simplex Method using Matrix Algebra 6.3. The Maximization Form 6.3.1. Ranges of optimality: simple changes 6.3.2. Optimality ranges: simultaneous changes and restoring optimality 6.3.3. Simple and simultaneous ranges of feasibility 6.3.4. Restoring feasibility 6.3.5. The 100% Rule: optimality and feasibility tests6.4. Introduction of a new variable or of a new constraint6.5. Note on the Minimization Form 6.6. Embedded modifications 6.C Revisiting mixed function problems6.7. Discussion on optimality ranges: simplex and graphical approachesChapter 6 Exercises and applications7 Understanding Computer Outputs and LP Applications 7.A Highlighting outputs 7.1. Using software packages for solving LP problems 7.1.1. Lindo: How to take advantage of its functions 7.1.2. The Management Scientist 7.1.3. Solving LP's with Excel 7.2. Study of outputs with respect to Chapters 3 and 6: the Simplex Method and Sensitivity Analysis7.3. Commented outputs with respect to Chapter 4 and 5: special cases and duality7.B The Various Fields of Application7.4. Production and make-or-buy 7.5. Purchase plans 7.6. Finance 7.7. Advertising 7.8. Staff scheduling7.9. Blending and nutrition7.10. Efficiency problems Chapter ApplicationsPart II Variants and Related Topics8 The Variants of Linear Programmes 8.1. Integer Programming 8.1.1. Pure and Mixed Integer Programming: the graphical insight 8.1.2. Binary Integer Programming 8.1.3. Formulating logical constraints8.2. Game Theory 8.2.1. Strictly determined Games and the theorems of GT 8.2.2. Non-Strictly determined games and solution approach by LP 8.3. The Transportation Problem 8.3.1. The balanced problem: solution approach through simplex multipliers 8.3.2. The unbalanced problem 8.3.3. Comment on the LP formulation of unbalanced problems: the feasibility requirement 8.3.4. Special Transportation Problems: LP formulation and solution approach 8.3.5. Maximization problems8.4. The Assignment Model 8.4.1. The Solution Approach: Koenig's Algorithm - The Balanced Problem - Alternative Assignments 8.4.2. The Maximization Problem (Example also displaying an unbalance) - Multiple Tableaux 8.4.3. Note on the LP Formulation and on Sensitivity Analysis: identifying alternative assignments Chapter 8 Exercises and applications 9 Related Topics: Graphs and Networks9.1. The main building concepts of Graph Theory. 9.1.1. Definitions and examples. 9.1.2. From the graph to the matrix: adjacency and incidence matrices 9.1.3. Directed graphs.9.2. Flow networks 9.2.1. The LP Formulation and solution 9.2.2. Solving the capacitated network graphically 9.2.3. The Max-Flow Min-Cut Theorem (Ford-Fulkerson) 9.2.3. Transshipments9.3. The Shortest Path 9.3.1. The LP formulation and solution 9.3.2. The graphical solution (Dijkstra's Algorithm) 9.3.3. Floyd's Algorithm9.4. The Minimal Spanning Tree 9.4.1. The graphical solution: Kruskal's and Prim's Algorithms 9.4.2. The limits of the LP FormulationChapter 9 Exercises and applicationsPart III Mathematical Corner and Note on Nonlinear Programming 10 Mathematical Corner10.1. Coping with infeasibility 10.1.1. Graphical insights 10.1.2. Discussion on changes 10.2. Flow networks: 10.2.1. Highlighting the cut on outputs 10.2.2. The cut revisited by duality10.3. The Shortest Route Algorithm: discussion on Sensitivity Analysis - Highlighting the leeway - Reading alternative optimal solutions on outputs10.4. The Minimal Spanning Tree 10.4.1. Minimal Spanning Trees and hierarchical clustering schemes 10.4.2. The LP formulation of Minimal Spanning Trees: a heuristic approach Note on Sensitivity AnalysisChapter 10 Exercises and applications11 Note on Nonlinear Programming 11.1. Quadratic Programming: definition 11.2. Illustrations and graphical displays: solution methltipliers11.3. Formulating the quadratic programme 11.4. Comment on shadow prices and on "RHS ranges". Chapter 11 ExercisesBasic Review ChapterR.1. Basic Matrix Algebra R.1.1on, subtraction and multiplication R.1.2. Matrices: types, addition and subtraction, multiplication and inverses R.1.3. Finding the inverse of mxm matrices by the Gauss-Jordan methodR.2. Derivatives and local extrema R.2.1. Brief review of derivatives in the single-variable case Comments on limits, continuity and differentiability. R.2.2. Partial derivativesAnswers to Selected Problems and ApplicationsStudy Applications Index