\contentsline {chapter}{\hbox to\@tempdima {\hfil }List of Figures}{xiii}
\contentsline {chapter}{\hbox to\@tempdima {\hfil }List of Tables}{xv}
\contentsline {chapter}{\hbox to\@tempdima {\hfil }Foreword}{xix}
\contentsline {part}{I\hspace {1em}Linear Programming}{1}
\contentsline {chapter}{\numberline {1}An Introduction to Linear Programming}{3}
\contentsline {section}{\numberline {1.1}The Basic Linear Programming Problem Formulation}{3}
\contentsline {subsection}{\numberline {1.1.1}A Prototype Example: The Blending Problem}{4}
\contentsline {subsection}{\numberline {1.1.2}Maple's {\ttfamily {\upshape {LPSolve}}} Command}{7}
\contentsline {subsection}{\numberline {1.1.3}The Matrix Inequality Form of an LP}{8}
\contentsline {subsection}{Exercises}{10}
\contentsline {section}{\numberline {1.2}Linear Programming: A Graphical Perspective in $\mathbb R^2$}{13}
\contentsline {subsection}{Exercises}{17}
\contentsline {section}{\numberline {1.3}Basic Feasible Solutions}{19}
\contentsline {subsection}{Exercises}{25}
\contentsline {chapter}{\numberline {2}The Simplex Algorithm}{29}
\contentsline {section}{\numberline {2.1}The Simplex Algorithm}{29}
\contentsline {subsection}{\numberline {2.1.1}An Overview of the Algorithm}{29}
\contentsline {subsection}{\numberline {2.1.2}A Step-By-Step Analysis of the Process}{30}
\contentsline {subsection}{\numberline {2.1.3}Solving Minimization Problems}{33}
\contentsline {subsection}{\numberline {2.1.4}A Step-by-Step Maple Implementation of the \unhbox \voidb@x \hbox {Simplex} \unhbox \voidb@x \hbox {Algorithm}}{34}
\contentsline {subsection}{Exercises}{38}
\contentsline {section}{\numberline {2.2}Alternative Optimal/Unbounded Solutions and Degeneracy}{39}
\contentsline {subsection}{\numberline {2.2.1}Alternative Optimal Solutions}{39}
\contentsline {subsection}{\numberline {2.2.2}Unbounded Solutions}{41}
\contentsline {subsection}{\numberline {2.2.3}Degeneracy}{42}
\contentsline {subsection}{Exercises}{45}
\contentsline {section}{\numberline {2.3}Excess and Artificial Variables: The Big M Method}{47}
\contentsline {subsection}{Exercises}{52}
\contentsline {section}{\numberline {2.4}A Partitioned Matrix View of the Simplex Method}{53}
\contentsline {subsection}{\numberline {2.4.1}Partitioned Matrices}{53}
\contentsline {subsection}{\numberline {2.4.2}Partitioned Matrices with Maple}{55}
\contentsline {subsection}{\numberline {2.4.3}The Simplex Algorithm as Partitioned Matrix Multiplication}{55}
\contentsline {subsection}{Exercises}{61}
\contentsline {section}{\numberline {2.5}The Revised Simplex Algorithm}{61}
\contentsline {subsection}{\numberline {2.5.1}Notation}{62}
\contentsline {subsection}{\numberline {2.5.2}Observations about the Simplex Algorithm}{62}
\contentsline {subsection}{\numberline {2.5.3}An Outline of the Method}{63}
\contentsline {subsection}{\numberline {2.5.4}Application to the \emph {FuelPro }LP}{64}
\contentsline {subsection}{Exercises}{67}
\contentsline {section}{\numberline {2.6}Moving beyond the Simplex Method: An Interior Point \unhbox \voidb@x \hbox {Algorithm}}{68}
\contentsline {subsection}{\numberline {2.6.1}The Origin of the Interior Point Algorithm}{68}
\contentsline {subsection}{\numberline {2.6.2}The Projected Gradient}{69}
\contentsline {subsection}{\numberline {2.6.3}Affine Scaling}{71}
\contentsline {subsection}{\numberline {2.6.4}Summary of the Method}{74}
\contentsline {subsection}{\numberline {2.6.5}Application of the Method to the \emph {FuelPro }LP}{75}
\contentsline {subsection}{\numberline {2.6.6}A Maple Implementation of the Interior Point \unhbox \voidb@x \hbox {Algorithm}}{76}
\contentsline {subsection}{Exercises}{78}
\contentsline {chapter}{\numberline {3}Standard Applications of Linear Programming}{81}
\contentsline {section}{\numberline {3.1}The Diet Problem}{81}
\contentsline {subsection}{\numberline {3.1.1}Eating for Cheap on a Very Limited Menu}{81}
\contentsline {subsection}{\numberline {3.1.2}The Problem Formulation and Solution, with Help from Maple}{82}
\contentsline {subsection}{Exercises}{85}
\contentsline {section}{\numberline {3.2}Transportation and Transshipment Problems}{85}
\contentsline {subsection}{\numberline {3.2.1}A Coal Distribution Problem}{85}
\contentsline {subsection}{\numberline {3.2.2}The Integrality of the Transportation Problem Solution}{87}
\contentsline {subsection}{\numberline {3.2.3}Coal Distribution with Transshipment}{89}
\contentsline {subsection}{Exercises}{91}
\contentsline {section}{\numberline {3.3}Basic Network Models}{92}
\contentsline {subsection}{\numberline {3.3.1}The Minimum Cost Network Flow Problem Formulation}{92}
\contentsline {subsection}{\numberline {3.3.2}Formulating and Solving the Minimum Cost Network Flow Problem with Maple}{94}
\contentsline {subsection}{\numberline {3.3.3}The Shortest Path Problem}{95}
\contentsline {subsection}{\numberline {3.3.4}Maximum Flow Problems}{98}
\contentsline {subsection}{Exercises}{99}
\contentsline {chapter}{\numberline {4}Duality and Sensitivity Analysis}{103}
\contentsline {section}{\numberline {4.1}Duality}{103}
\contentsline {subsection}{\numberline {4.1.1}The Dual of an LP}{103}
\contentsline {subsection}{\numberline {4.1.2}Weak and Strong Duality}{105}
\contentsline {subsection}{\numberline {4.1.3}An Economic Interpretation of Duality}{110}
\contentsline {subsection}{\numberline {4.1.4}A Final Note on the Dual of an Arbitrary LP}{111}
\contentsline {subsection}{\numberline {4.1.5}The Zero-Sum Matrix Game}{112}
\contentsline {subsection}{Exercises}{117}
\contentsline {section}{\numberline {4.2}Sensitivity Analysis}{120}
\contentsline {subsection}{\numberline {4.2.1}Sensitivity to an Objective Coefficient}{121}
\contentsline {subsection}{\numberline {4.2.2}Sensitivity to Constraint Bounds}{125}
\contentsline {subsection}{\numberline {4.2.3}Sensitivity to Entries in the Coefficient Matrix $A$}{130}
\contentsline {subsection}{\numberline {4.2.4}Performing Sensitivity Analysis with Maple}{133}
\contentsline {subsection}{Exercises}{135}
\contentsline {section}{\numberline {4.3}The Dual Simplex Method}{137}
\contentsline {subsection}{\numberline {4.3.1}Overview of the Method}{138}
\contentsline {subsection}{\numberline {4.3.2}A Simple Example}{139}
\contentsline {subsection}{Exercises}{143}
\contentsline {chapter}{\numberline {5}Integer Linear Programming}{145}
\contentsline {section}{\numberline {5.1}An Introduction to Integer Linear Programming and the Branch and Bound Method}{145}
\contentsline {subsection}{\numberline {5.1.1}A Simple Example}{145}
\contentsline {subsection}{\numberline {5.1.2}The Relaxation of an ILP}{146}
\contentsline {subsection}{\numberline {5.1.3}The Branch and Bound Method}{147}
\contentsline {subsection}{\numberline {5.1.4}Practicing the Branch and Bound Method with Maple}{154}
\contentsline {subsection}{\numberline {5.1.5}Binary and Mixed Integer Linear Programming}{155}
\contentsline {subsection}{\numberline {5.1.6}Solving ILPs Directly with Maple}{156}
\contentsline {subsection}{\numberline {5.1.7}An Application of Integer Linear Programming: The Traveling Salesperson Problem}{157}
\contentsline {subsection}{Exercises}{162}
\contentsline {section}{\numberline {5.2}The Cutting Plane Algorithm}{167}
\contentsline {subsection}{\numberline {5.2.1}Motivation}{167}
\contentsline {subsection}{\numberline {5.2.2}The Algorithm}{167}
\contentsline {subsection}{\numberline {5.2.3}A Step-by-Step Maple Implementation of the Cutting Plane Algorithm}{171}
\contentsline {subsection}{\numberline {5.2.4}Comparison with the Branch and Bound Method}{174}
\contentsline {subsection}{Exercises}{175}
\contentsline {part}{II\hspace {1em}Nonlinear Programming}{177}
\contentsline {chapter}{\numberline {6}Algebraic Methods for Unconstrained Problems}{179}
\contentsline {section}{\numberline {6.1}Nonlinear Programming: An Overview}{179}
\contentsline {subsection}{\numberline {6.1.1}The General Nonlinear Programming Model}{179}
\contentsline {subsection}{\numberline {6.1.2}Plotting Feasible Regions and Solving NLPs with Maple}{180}
\contentsline {subsection}{\numberline {6.1.3}A Prototype NLP Example}{183}
\contentsline {subsection}{Exercises}{185}
\contentsline {section}{\numberline {6.2}Differentiability and a Necessary First-Order Condition}{187}
\contentsline {subsection}{\numberline {6.2.1}Differentiability}{188}
\contentsline {subsection}{\numberline {6.2.2}Necessary Conditions for Local Maxima or Minima}{190}
\contentsline {subsection}{Exercises}{193}
\contentsline {section}{\numberline {6.3}Convexity and a Sufficient First-Order Condition}{194}
\contentsline {subsection}{\numberline {6.3.1}Convexity}{195}
\contentsline {subsection}{\numberline {6.3.2}Testing for Convexity}{197}
\contentsline {subsection}{\numberline {6.3.3}Convexity and \emph {The Global Optimal Solutions Theorem}}{198}
\contentsline {subsection}{\numberline {6.3.4}Solving the Unconstrained NLP for Differentiable, \unhbox \voidb@x \hbox {Convex} \unhbox \voidb@x \hbox {Functions}}{200}
\contentsline {subsection}{\numberline {6.3.5}Multiple Linear Regression}{202}
\contentsline {subsection}{Exercises}{205}
\contentsline {section}{\numberline {6.4}Sufficient Conditions for Local and Global Optimal Solutions}{207}
\contentsline {subsection}{\numberline {6.4.1}Quadratic Forms}{207}
\contentsline {subsection}{\numberline {6.4.2}Positive Definite Quadratic Forms}{209}
\contentsline {subsection}{\numberline {6.4.3}Second-order Differentiability and the Hessian Matrix}{211}
\contentsline {subsection}{\numberline {6.4.4}Using Maple To Classify Critical Points for the \unhbox \voidb@x \hbox {Unconstrained} NLP}{219}
\contentsline {subsection}{\numberline {6.4.5}The Zero-Sum Matrix Game, Revisited}{220}
\contentsline {subsection}{Exercises}{222}
\contentsline {chapter}{\numberline {7}Numeric Tools for Unconstrained NLPs}{225}
\contentsline {section}{\numberline {7.1}The Steepest Descent Method}{225}
\contentsline {subsection}{\numberline {7.1.1}Method Derivation}{225}
\contentsline {subsection}{\numberline {7.1.2}A Maple Implementation of the Steepest Descent Method}{229}
\contentsline {subsection}{\numberline {7.1.3}A Sufficient Condition for Convergence}{231}
\contentsline {subsection}{\numberline {7.1.4}The Rate of Convergence}{234}
\contentsline {subsection}{Exercises}{236}
\contentsline {section}{\numberline {7.2}Newton's Method}{237}
\contentsline {subsection}{\numberline {7.2.1}Shortcomings of the Steepest Descent Method}{237}
\contentsline {subsection}{\numberline {7.2.2}Method Derivation}{238}
\contentsline {subsection}{\numberline {7.2.3}A Maple Implementation of Newton's Method}{240}
\contentsline {subsection}{\numberline {7.2.4}Convergence Issues and Comparison with the Steepest Descent Method}{242}
\contentsline {subsection}{Exercises}{247}
\contentsline {section}{\numberline {7.3}The Levenberg-Marquardt Algorithm}{248}
\contentsline {subsection}{\numberline {7.3.1}Interpolating between the Steepest Descent and Newton \newline Methods}{248}
\contentsline {subsection}{\numberline {7.3.2}The Levenberg Method}{249}
\contentsline {subsection}{\numberline {7.3.3}The Levenberg-Marquardt Algorithm}{250}
\contentsline {subsection}{\numberline {7.3.4}A Maple Implementation of the \unhbox \voidb@x \hbox {Levenberg-Marquardt} \unhbox \voidb@x \hbox {Algorithm}}{252}
\contentsline {subsection}{\numberline {7.3.5}Nonlinear Regression}{254}
\contentsline {subsection}{\numberline {7.3.6}Maple's {\ttfamily {\upshape {Global Optimization Toolbox}}}}{256}
\contentsline {subsection}{Exercises}{257}
\contentsline {chapter}{\numberline {8}Methods for Constrained Nonlinear Problems}{261}
\contentsline {section}{\numberline {8.1}The Lagrangian Function and Lagrange Multipliers}{261}
\contentsline {subsection}{\numberline {8.1.1}Some Convenient Notation}{262}
\contentsline {subsection}{\numberline {8.1.2}The Karush-Kuhn-Tucker Theorem}{263}
\contentsline {subsection}{\numberline {8.1.3}Interpreting the Multiplier}{267}
\contentsline {subsection}{Exercises}{269}
\contentsline {section}{\numberline {8.2}Convex NLPs}{272}
\contentsline {subsection}{\numberline {8.2.1}Solving Convex NLPs}{273}
\contentsline {subsection}{Exercises}{276}
\contentsline {section}{\numberline {8.3}Saddle Point Criteria}{278}
\contentsline {subsection}{\numberline {8.3.1}The Restricted Lagrangian}{279}
\contentsline {subsection}{\numberline {8.3.2}Saddle Point Optimality Criteria}{281}
\contentsline {subsection}{Exercises}{283}
\contentsline {section}{\numberline {8.4}Quadratic Programming}{284}
\contentsline {subsection}{\numberline {8.4.1}Problems with Equality-type Constraints Only}{284}
\contentsline {subsection}{\numberline {8.4.2}Inequality Constraints}{290}
\contentsline {subsection}{\numberline {8.4.3}Maple's {\ttfamily {\upshape {QPSolve}}} Command}{291}
\contentsline {subsection}{\numberline {8.4.4}The Bimatrix Game}{293}
\contentsline {subsection}{Exercises}{298}
\contentsline {section}{\numberline {8.5}Sequential Quadratic Programming}{301}
\contentsline {subsection}{\numberline {8.5.1}Method Derivation for Equality-type Constraints}{301}
\contentsline {subsection}{\numberline {8.5.2}The Convergence Issue}{306}
\contentsline {subsection}{\numberline {8.5.3}Inequality-Type Constraints}{306}
\contentsline {subsection}{\numberline {8.5.4}A Maple Implementation of the Sequential \unhbox \voidb@x \hbox {Quadratic} \unhbox \voidb@x \hbox {Programming} Technique}{310}
\contentsline {subsection}{\numberline {8.5.5}An Improved Version of the SQPT}{312}
\contentsline {subsection}{Exercises}{315}
\contentsline {chapter}{\numberline {A}Projects}{319}
\contentsline {section}{\numberline {A.1}Excavating and Leveling a Large Land Tract}{319}
\contentsline {section}{\numberline {A.2}The Juice Logistics Model }{321}
\contentsline {section}{\numberline {A.3}Work Scheduling with Overtime}{324}
\contentsline {section}{\numberline {A.4}Diagnosing Breast Cancer with a Linear Classifier}{326}
\contentsline {section}{\numberline {A.5}The Markowitz Portfolio Model}{329}
\contentsline {section}{\numberline {A.6}A Game Theory Model of a Predator-Prey Habitat}{332}
\contentsline {chapter}{\numberline {B}Important Results from Linear Algebra}{337}
\contentsline {section}{\numberline {B.1}Linear Independence}{337}
\contentsline {section}{\numberline {B.2}The Invertible Matrix Theorem}{337}
\contentsline {section}{\numberline {B.3}Transpose Properties}{338}
\contentsline {section}{\numberline {B.4}Positive Definite Matrices}{338}
\contentsline {section}{\numberline {B.5}Cramer's Rule}{339}
\contentsline {section}{\numberline {B.6}The Rank-Nullity Theorem}{339}
\contentsline {section}{\numberline {B.7}The Spectral Theorem}{339}
\contentsline {section}{\numberline {B.8}Matrix Norms}{340}
\contentsline {chapter}{\numberline {C}Getting Started with Maple}{341}
\contentsline {section}{\numberline {C.1}The Worksheet Structure}{341}
\contentsline {section}{\numberline {C.2}Arithmetic Calculations and Built-In Operations}{343}
\contentsline {section}{\numberline {C.3}Expressions and Functions}{344}
\contentsline {section}{\numberline {C.4}Arrays, Lists, Sequences, and Sums}{347}
\contentsline {section}{\numberline {C.5}Matrix Algebra and the {\ttfamily {\upshape {LinearAlgebra}}} Package}{349}
\contentsline {section}{\numberline {C.6}Plot Structures with Maple}{353}
\contentsline {chapter}{\numberline {D}Summary of Maple Commands}{361}
\contentsline {chapter}{Bibliography}{381}
\contentsline {chapter}{Index}{385}