Linear and Nonlinear Programming with Maple: An Interactive, Applications-Based Approach

by Fishback; Paul E.

• ISBN13: 9781420090642
• ISBN10: 142009064X
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-12-09
• Publisher: Chapman & Hall/

Summary

Using Maple'„¢ throughout, this innovative text is based on the multiplication of partitioned matrices as opposed to the older, more traditional approach that becomes bogged down with summation formulas as special cases. Endorsed by the Linear Algebra Curriculum Study Group, the multiplication of partitioned matrices is considered an important idea in a first course on linear algebra. Each chapter contains pedagogical devices where readers can check their understanding of the material by performing basic computations or responding to short answer questions. The book also presents various activities for group assignments and in-class assessments of applications, such as game theory, breast cancer diagnosis, and waste management.

Table of Contents

List of Figures	p. xiii
List of Tables	p. xv
Foreword	p. xix
Linear Programming	p. 1
An Introduction to Linear Programming	p. 3
The Basic Linear Programming Problem Formulation	p. 3
A Prototype Example: The Blending Problem	p. 4
Maple's LPSolve Command	p. 7
The Matrix Inequality Form of an LP	p. 8
Exercises	p. 10
Linear Programming: A Graphical Perspective in R2	p. 13
Exercises	p. 17
Basic Feasible Solutions	p. 19
Exercises	p. 25
The Simplex Algorithm	p. 29
The Simplex Algorithm	p. 29
An Overview of the Algorithm	p. 29
A Step-by-Step Analysis of the Process	p. 30
Solving Minimization Problems	p. 33
A Step-by-Step Maple Implementation of the Simplex Algorithm	p. 34
Exercises	p. 38
Alternative Optimal/Unbounded Solutions and Degeneracy	p. 39
Alternative Optimal Solutions	p. 40
Unbounded Solutions	p. 41
Degeneracy	p. 42
Exercises	p. 45
Excess and Artificial Variables: The Big M Method	p. 47
Exercises	p. 53
A Partitioned Matrix View of the Simplex Method	p. 54
Partitioned Matrices	p. 54
Partitioned Matrices with Maple	p. 55
The Simplex Algorithm as Partitioned Matrix Multiplication	p. 56
Exercises	p. 61
The Revised Simplex Algorithm	p. 62
Notation	p. 62
Observations about the Simplex Algorithm	p. 63
An Outline of the Method	p. 63
Application to the FuelPro LP	p. 64
Exercises	p. 67
Moving beyond the Simplex Method: An Interior Point Algorithm	p. 68
The Origin of the Interior Point Algorithm	p. 68
The Projected Gradient	p. 69
Affine Scaling	p. 72
Summary of the Method	p. 75
Application of the Method to the FuelPro LP	p. 75
A Maple Implementation of the Interior Point Algorithm	p. 76
Exercises	p. 79
Standard Applications of Linear Programming	p. 81
The Diet Problem	p. 81
Eating for Cheap on a Very Limited Menu	p. 81
The Problem Formulation and Solution, with Help from Maple	p. 82
Exercises	p. 85
Transportation and Transshipment Problems	p. 85
A Coal Distribution Problem	p. 85
The Integrality of the Transportation Problem Solution	p. 87
Coal Distribution with Transshipment	p. 89
Exercises	p. 91
Basic Network Models	p. 92
The Minimum Cost Network Flow Problem Formulation	p. 92
Formulating and Solving the Minimum Cost Network Flow Problem with Maple	p. 94
The Shortest Path Problem	p. 95
Maximum Flow Problems	p. 98
Exercises	p. 99
Duality and Sensitivity Analysis	p. 103
Duality	p. 103
The Dual of an LP	p. 103
Weak and Strong Duality	p. 105
An Economic Interpretation of Duality	p. 110
A Final Note on the Dual of an Arbitrary LP	p. 111
The Zero-Sum Matrix Game	p. 112
Exercises	p. 116
Sensitivity Analysis	p. 119
Sensitivity to an Objective Coefficient	p. 121
Sensitivity to Constraint Bounds	p. 125
Sensitivity to Entries in the Coefficient Matrix A	p. 130
Performing Sensitivity Analysis with Maple	p. 133
Exercises	p. 135
The Dual Simplex Method	p. 137
Overview of the Method	p. 138
A Simple Example	p. 139
Exercises	p. 143
Integer Linear Programming	p. 145
An Introduction to Integer Linear Programming and the Branch and Bound Method	p. 145
A Simple Example	p. 145
The Relaxation of an ILP	p. 146
The Branch and Bound Method	p. 147
Practicing the Branch and Bound Method with Maple	p. 154
Binary and Mixed Integer Linear Programming	p. 155
Solving ILPs Directly with Maple	p. 156
An Application of Integer Linear Programming: The Traveling Sales person Problem	p. 157
Exercises	p. 162
The Cutting Plane Algorithm	p. 167
Motivation	p. 167
The Algorithm	p. 168
A Step-by-Step Maple Implementation of the Cutting Plane Algorithm	p. 172
Comparison with the Branch and Bound Method	p. 175
Exercises	p. 175
Nonlinear Programming	p. 177
Algebraic Methods for Unconstrained Problems	p. 179
Nonlinear Programming: An Overview	p. 179
The General Nonlinear Programming Model	p. 179
Plotting Feasible Regions and Solving NLPs with Maple	p. 180
A Prototype NLP Example	p. 183
Exercises	p. 185
Differentiability and a Necessary First-Order Condition	p. 187
Differentiability	p. 188
Necessary Conditions for Local Maxima or Minima	p. 190
Exercises	p. 193
Convexity and a Sufficient First-Order Condition	p. 193
Convexity	p. 194
Testing for Convexity	p. 196
Convexity and The Global Optimal Solutions Theorem	p. 199
Solving the Unconstrained NLP for Differentiable, Convex Functions	p. 200
Multiple Linear Regression	p. 201
Exercises	p. 204
Sufficient Conditions for Local and Global Optimal Solutions	p. 206
Quadratic Forms	p. 207
Positive Definite Quadratic Forms	p. 209
Second-Order Differentiability and the Hessian Matrix	p. 210
Using Maple to Classify Critical Points for the Unconstrained NLP	p. 218
The Zero-Sum Matrix Game, Revisited	p. 219
Exercises	p. 222
Numeric Tools for Unconstrained NLPs	p. 225
The Steepest Descent Method	p. 225
Method Derivation	p. 225
A Maple Implementation of the Steepest Descent Method	p. 229
A Sufficient Condition for Convergence	p. 231
The Rate of Convergence	p. 234
Exercises	p. 236
Newton's Method	p. 238
Shortcomings of the Steepest Descent Method	p. 238
Method Derivation	p. 239
A Maple Implementation of Newton's Method	p. 241
Convergence Issues and Comparison with the Steepest Descent Method	p. 243
Exercises	p. 247
The Levenberg-Marquardt Algorithm	p. 249
Interpolating between the Steepest Descent and Newton Methods	p. 249
The Levenberg Method	p. 250
The Levenberg-Marquardt Algorithm	p. 251
A Maple Implementation of the Levenberg-Marquardt Algorithm	p. 253
Nonlinear Regression	p. 255
Maple's Global Optimization Toolbox	p. 257
Exercises	p. 258
Methods for Constrained Nonlinear Problems	p. 261
The Lagrangian Function and Lagrange Multipliers	p. 261
Some Convenient Notation	p. 262
The Karush-Kuhn-Tucker Theorem	p. 263
Interpreting the Multiplier	p. 267
Exercises	p. 269
Convex NLPs	p. 272
Solving Convex NLPs	p. 273
Exercises	p. 276
Saddle Point Criteria	p. 278
The Restricted Lagrangian	p. 278
Saddle Point Optimality Criteria	p. 280
Exercises	p. 282
Quadratic Programming	p. 284
Problems with Equality-type Constraints Only	p. 284
Inequality Constraints	p. 289
Maple's QPSolve Command	p. 291
The Bimatrix Game	p. 293
Exercises	p. 297
Sequential Quadratic Programming	p. 300
Method Derivation for Equality-type Constraints	p. 300
The Convergence Issue	p. 306
Inequality-Type Constraints	p. 306
A Maple Implementation of the Sequential Quadratic Programming Technique	p. 310
An Improved Version of the SQPT	p. 312
Exercises	p. 315
Projects	p. 319
Excavating and Leveling a Large Land Tract	p. 319
The Juice Logistics Model	p. 322
Work Scheduling with Overtime	p. 325
Diagnosing Breast Cancer with a Linear Classifier	p. 327
The Markowitz Portfolio Model	p. 330
A Game Theory Model of a Predator-Prey Habitat	p. 334
Important Results from Linear Algebra	p. 337
Linear Independence	p. 337
The Invertible Matrix Theorem	p. 337
Transpose Properties	p. 338
Positive Definite Matrices	p. 338
Cramer's Rule	p. 339
The Rank-Nullity Theorem	p. 339
The Spectral Theorem	p. 339
Matrix Norms	p. 340
Getting Started with Maple	p. 341
The Worksheet Structure	p. 341
Arithmetic Calculations and Built-in Operations	p. 343
Expressions and Functions	p. 344
Arrays, Lists, Sequences, and Sums	p. 347
Matrix Algebra and the LinearAlgebra Package	p. 349
Plot Structures with Maple	p. 353
Summary of Maple Commands	p. 363
Bibliography	p. 383
Index	p. 387
Table of Contents provided by Ingram. All Rights Reserved.