Building and Solving Mathematical Programming Models in Engineering and Science

by Castillo, Enrique; Conejo, Antonio J.; Pedregal, Pablo; Garcí; a, Ricardo; Alguacil, Natalia

• ISBN13: 9780471150435
• ISBN10: 0471150436
• Edition: 1st
• Format: Hardcover
• Copyright: 2001-11-01
• Publisher: Wiley-Interscience

Summary

Fundamental concepts of mathematical modeling Modeling is one of the most effective, commonly used tools in engineering and the applied sciences. In this book, the authors deal with mathematical programming models both linear and nonlinear and across a wide range of practical applications. Whereas other books concentrate on standard methods of analysis, the authors focus on the power of modeling methods for solving practical problems-clearly showing the connection between physical and mathematical realities-while also describing and exploring the main concepts and tools at work. This highly computational coverage includes: * Discussion and implementation of the GAMS programming system * Unique coverage of compatibility * Illustrative examples that showcase the connection between model and reality * Practical problems covering a wide range of scientific disciplines, as well as hundreds of examples and end-of-chapter exercises * Real-world applications to probability and statistics, electrical engineering, transportation systems, and more Building and Solving Mathematical Programming Models in Engineering and Science is practically suited for use as a professional reference for mathematicians, engineers, and applied or industrial scientists, while also tutorial and illustrative enough for advanced students in mathematics or engineering.

Author Biography

ENRIQUE CASTILLO, PhD, is Full Professor of Applied Mathematics at the University of Cantabria in Santander, Spain.

Table of Contents

Preface	xiii
I Models	1	(70)
Linear Programming	3	(22)
Introduction	3	(1)
The Transportation Problem	4	(2)
The Production Scheduling Problem	6	(3)
Production Scheduling Problem 1	6	(3)
The Diet Problem	9	(2)
The Network Flow Problem	11	(2)
The Portfolio Problem	13	(2)
Scaffolding System	15	(3)
Electric Power Economic Dispatch	18	(7)
Exercises	21	(4)
Mixed-Integer Linear Programming	25	(22)
Introduction	25	(1)
The 0-1 Knapsack Problem	25	(2)
Identifying Relevant Symptoms	27	(2)
The Academy Problem	29	(3)
School Timetable Problem	32	(3)
Models of Discrete Location	35	(3)
Unit Commitment of Thermal Power Units	38	(9)
Exercises	43	(4)
Nonlinear Programming	47	(24)
Introduction	47	(1)
Some Geometrically Motivated Examples	47	(4)
The Postal Package Example	47	(1)
The Tent Example	48	(1)
The Lightbulb Example	48	(2)
The Surface Example	50	(1)
The Moving Sand Example	50	(1)
Some Mechanically Motivated Examples	51	(4)
The Cantilever Beam Example	51	(1)
The Two-Bar Truss Example	51	(2)
The Column Example	53	(1)
Scaffolding System	54	(1)
Some Electrically Motivated Examples	55	(7)
Power Circuit State Estimation	56	(2)
Optimal Power Flow	58	(4)
The Matrix Balancing Problem	62	(2)
The Traffic Assignment Problem	64	(7)
Exercises	69	(2)
II Methods	71	(212)
An Introduction to Linear Programming	73	(24)
Introduction	73	(1)
Problem Statement and Basic Definitions	73	(5)
Linear Programming Problem in Standard Form	78	(3)
Transformation to Standard Form	79	(2)
Basic Solutions	81	(2)
Sensitivities	83	(1)
Duality	84	(13)
Obtaining the Dual from a Primal in Standard Form	85	(1)
Obtaining the Dual Problem	86	(1)
Duality Theorems	87	(5)
Exercises	92	(5)
Understanding the Set of All Feasible Solutions	97	(20)
Introduction and Motivation	97	(4)
Convex Sets	101	(4)
Linear Spaces	105	(2)
Polyhedral Convex Cones	107	(2)
Polytopes	109	(1)
Polyhedra	110	(3)
General Representation of Polyhera	112	(1)
Bounded and Unbounded LPP	113	(4)
Exercises	114	(3)
Solving the Linear Programming Problem	117	(44)
Introduction	117	(1)
The Simplex Method	118	(22)
Motivating Example	118	(2)
General Description	120	(1)
Initialization Stage	121	(1)
Elemental Pivoting Operation	122	(3)
Identifying an Optimal Solution	125	(1)
Regulating Iteration	126	(1)
Detecting Unboundedness	126	(1)
Detecting Infeasibility	127	(1)
Standard Iterations Stage	127	(2)
The Revised Simplex Algorithm	129	(2)
Some Illustrative Examples	131	(9)
The Exterior Point Method	140	(21)
Initial Stage	142	(1)
Regulating Stage	143	(1)
Detecting Infeasibility and Unboundedness	144	(1)
Standard Iterations Stage	144	(2)
The EPM Algorithm	146	(2)
Some Illustrative Examples	148	(9)
Exercises	157	(4)
Mixed-Integer Linear Programming	161	(22)
Introduction	161	(1)
The Branch-Bound Method	162	(10)
Introduction	162	(1)
The BB Algorithm for MILPP	163	(1)
Branching and Processing Strategies	164	(8)
Other Mixed-Integer Liner Programming Problems	172	(1)
The Gomory Cuts Method	172	(11)
Introduction	172	(1)
Cut Generation	173	(1)
The Gomory Cuts Algorithm for an ILPP	174	(6)
Exercises	180	(3)
Optimality and Duality in Nonlinear Programming	183	(52)
Introduction	183	(5)
Necessary Optimality Conditions	188	(19)
Differentiability	188	(2)
Karush-Kuhn-Tucker Optimality Conditions	190	(17)
Optimality Conditions: Sufficiency and Convexity	207	(9)
Convexity	207	(4)
Sufficiency of the Karush-Kuhn-Tucker Conditions	211	(5)
Duality Theory	216	(5)
Practical Illustrations of Duality and Separability	221	(5)
Centralized or Primal Approach	222	(3)
Competitive Market or Dual Approach	225	(1)
Conclusion	226	(1)
Constraint Qualifications	226	(9)
Exercises	227	(8)
Computational Methods for Nonlinear Programming	235	(48)
Unconstrained Optimization Algorithms	236	(18)
Line Search Methods	236	(5)
Multidimensional Unconstrained Optimization	241	(13)
Constrained Optimization Algorithms	254	(29)
Dual Methods	254	(7)
Penalty Methods	261	(8)
The Interior Point Method	269	(9)
Exercises	278	(5)
III Software	283	(86)
The GAMS Package	285	(26)
Introduction	285	(1)
Illustrative Example	286	(4)
Language Features	290	(21)
Sets	291	(2)
Scalars	293	(1)
Parameters and Tables	293	(3)
Mathematical Expression Rules in Assignments	296	(1)
Variables	296	(3)
Equations	299	(1)
Model	299	(1)
Solve	300	(3)
Asterisk Facility	303	(1)
Display	303	(1)
Conditional Statements	304	(1)
Dynamic Sets	305	(1)
Iterative Structures	306	(3)
Writing Output Files	309	(1)
Output File: Nonlinear Equation Listing	310	(1)
Some Examples Using GAMS	311	(58)
Introduction	311	(1)
Linear Programming Examples	311	(19)
The Transportation Problem	311	(4)
Production Scheduling Problem 1	315	(2)
The Diet Problem	317	(2)
The Network Flow Problem	319	(5)
The Portfolio Problem	324	(1)
The Scaffolding System	325	(3)
Electric Power Economic Dispatch	328	(2)
Mixed-Integer LPP Examples	330	(14)
The 0-1 Knapsack Example	331	(2)
Identifying Relevant Symptoms	333	(1)
The Academy Problem	334	(3)
The School Timetable Problem	337	(1)
Models of Discrete Location	338	(3)
Unit Commitment of Thermal Power Units	341	(3)
Nonlinear Programming Examples	344	(25)
The Postal Package Example	344	(1)
The Tent Example	345	(1)
The Lightbulb Example	346	(1)
The Surface Example	346	(1)
The Moving Sand Example	347	(1)
The Cantilever Beam Example	348	(1)
The Two-Bar Truss Example	348	(2)
The Column Example	350	(1)
The Scaffolding Example	351	(2)
Power Circuit State Estimation	353	(2)
Optimal Power Flow	355	(4)
The Water Supply Network Problem	359	(2)
The Matrix Balancing Problem	361	(2)
The Traffic Assignment Problem	363	(1)
Exercises	364	(5)
IV Applications	369	(108)
Applications	371	(80)
Applications to Artificial Intelligence	371	(7)
Learning the Neural Functions	373	(5)
Applications to CAD	378	(9)
Automatic Mesh Generation	381	(6)
Applications to Probability	387	(8)
Compatibility of Conditional Probability Matrices	387	(4)
ε Compatibility	391	(4)
Regression Models	395	(6)
Applications to Optimization Problems	401	(16)
Variational Problems	403	(7)
Optimal Control Problems	410	(7)
Transportation Systems	417	(25)
Introduction	417	(1)
Elements of a Road Transportation Network	418	(4)
The Traffic Assignment Problem	422	(7)
Side-Constrained Assignment Models	429	(3)
The Variable-Demand Case	432	(6)
Combined Distribution and Assignment	438	(4)
Short-Term Hydrothermal Coordination	442	(9)
Problem Formulation and the LR Solution Procedure	443	(4)
Dual-Problem Solution: Multiplier Updating Techniques	447	(1)
Economical Meaning of the Multipliers	448	(3)
Some Useful Modeling Tricks	451	(26)
Introduction	451	(1)
Some General Tricks	451	(15)
Dealing with Unrestricted Variables	452	(1)
Converting Inequalities into Equalities	453	(1)
Converting Equalities into Inequalities	454	(1)
Converting Maximization into Minimization Problems	455	(1)
Converting Nonlinear Objective Functions into Linear	455	(1)
Nonlinear Functions Treated as Linear Functions	455	(3)
Linear Space as a Cone	458	(2)
Alternative Sets of Constraints	460	(2)
Dealing with Conditional Constraints	462	(1)
Dealing with Discontinuous Functions	462	(1)
Dealing with Piecewise Nonconvex Functions	463	(3)
Some GAMS Tricks	466	(11)
Assigning Values to a Matrix	466	(1)
Defining a Symmetric Matrix	467	(1)
Defining a Sparse Matrix	467	(2)
Splitting a Separable Problem	469	(1)
Adding Constraints Iteratively to a Problem	470	(1)
Dealing with Initial and Final States	471	(1)
Performing a Sensitivity Analysis	471	(1)
Making the Model Dependent on Problem States	472	(1)
Exercises	473	(4)
A Compatibility and Set of All Feasible Solutions	477	(40)
The Dual Cone	478	(2)
Cone Associated with a Polyhedron	480	(3)
The T Procedure	483	(5)
Compatibility of Linear Systems	488	(3)
Solving Linear Systems	491	(3)
Applications to Several Examples	494	(23)
The Transportation Problem	494	(5)
Production Scheduling Problem	499	(6)
The Input-Output Tables	505	(2)
The Diet Problem	507	(1)
The Network Flow Problem	508	(5)
Exercises	513	(4)
B Notation	517	(16)
Bibliography	533	(8)
Index	541