Introduction to Mathematical Programming Applications and Algorithms, Volume 1 (with CD-ROM and InfoTrac)

by Winston, Wayne L.; Venkataramanan, Munirpallam

• ISBN13: 9780534359645
• ISBN10: 0534359647
• Additional ISBN(s): 9780534230463
• Edition: 4th
• Format: Hardcover
• Copyright: 2002-10-28
• Publisher: INGRAM
• More Book Details
• Purchase Benefits

Summary

Authors Wayne Winston and Munirpallam Venkataramanan emphasize model-formulation and model-building skills as well as interpretation of computer software output. Focusing on deterministic models, this book is designed for the first half of an operations research sequence. A subset of Winston's best-selling OPERATIONS RESEARCH, INTRODUCTION TO MATHEMATICAL PROGRAMMING offers self-contained chapters that make it flexible enough for one- or two-semester courses ranging from advanced beginning to intermediate in level. The book has a strong computer orientation and emphasizes model-formulation and model-building skills. Every topic includes a corresponding computer-based modeling and solution method and every chapter presents the software tools needed to solve realistic problems. LINDO, LINGO, and Premium Solver for Education software packages are available with the book.

Table of Contents

Preface	ix
An Introduction to Model-Building	1	(10)
An Introduction to Modeling	1	(4)
The Seven-Step Model-Building Process	5	(1)
CITGO Petroleum	6	(1)
San Francisco Police Department Scheduling	7	(2)
GE Capital	9	(2)
Basic Linear Algebra	11	(38)
Matrices and Vectors	11	(9)
Matrices and Systems of Linear Equations	20	(2)
The Gauss-Jordan Method for Solving Systems of Linear Equations	22	(10)
Linear Independence and Linear Dependence	32	(4)
The Inverse of a Matrix	36	(6)
Determinants	42	(7)
Introduction to Linear Programming	49	(78)
What Is a Linear Programming Problem?	49	(7)
The Graphical Solution of Two-Variable Linear Programming Problems	56	(7)
Special Cases	63	(5)
A Diet Problem	68	(4)
A Work-Scheduling Problem	72	(4)
A Capital Budgeting Problem	76	(6)
Short-Term Financial Planning	82	(3)
Blending Problems	85	(10)
Production Process Models	95	(5)
Using Linear Programming to Solve Multiperiod Decision Problems: An Inventory Model	100	(5)
Multiperiod Financial Models	105	(4)
Multiperiod Work Scheduling	109	(18)
The Simplex Algorithm and Goal Programming	127	(100)
How to Convert an LP to Standard Form	127	(3)
Preview of the Simplex Algorithm	130	(4)
Direction of Unboundedness	134	(2)
Why Does an LP Have an Optimal bfs	136	(4)
The Simplex Algorithm	140	(9)
Using the Simplex Algorithm to Solve Minimization Problems	149	(3)
Alternative Optimal Solutions	152	(2)
Unbounded LPs	154	(4)
The LINDO Computer Package	158	(5)
Matrix Generators, LINGO, and Scaling of LPs	163	(5)
Degeneracy and the Convergence of the Simplex Algorithm	168	(4)
The Big M Method	172	(6)
The Two-Phase Simplex Method	178	(6)
Unrestricted-in-Sign Variables	184	(6)
Karmarkar's Method for Solving LPs	190	(1)
Multiattribute Decision Making in the Absence of Uncertainty: Goal Programming	191	(11)
Using the Excel Solver to Solve LPs	202	(25)
Sensitivity Analysis: An Applied Approach	227	(35)
A Graphical Introduction to Sensitivity Analysis	227	(5)
The Computer and Sensitivity Analysis	232	(14)
Managerial Use of Shadow Prices	246	(2)
What Happens to the Optimalz-Value If the Current Basis Is No Longer Optimal?	248	(14)
Sensitivity Analysis and Duality	262	(98)
A Graphical Introduction to Sensitivity Analysis	262	(5)
Some Important Formulas	267	(8)
Sensitivity Analysis	275	(14)
Sensitivity Analysis When More Than One Parameter Is Changed: The 100% Rule	289	(6)
Finding the Dual of an LP	295	(7)
Economic Interpretation of the Dual Problem	302	(2)
The Dual Theorem and Its Consequences	304	(9)
Shadow Prices	313	(10)
Duality and Sensitivity Analysis	323	(2)
Complementary Slackness	325	(4)
The Dual Simplex Method	329	(6)
Data Envelopment Analysis	335	(25)
Transportation, Assignment, and Transshipment Problems	360	(53)
Formulating Transportation Problems	360	(13)
Finding Basic Feasible Solutions for Transportation Problems	373	(9)
The Transportation Simplex Method	382	(8)
Sensitivity Analysis for Transportation Problems	390	(3)
Assignment Problems	393	(7)
Transshipment Problems	400	(13)
Network Models	413	(62)
Basic Definitions	413	(1)
Shortest Path Problems	414	(5)
Maximum Flow Problems	419	(12)
CPM and PERT	431	(19)
Minimum Cost Network Flow Problems	450	(6)
Minimum Spanning Tree Problems	456	(3)
The Network Simplex Method	459	(16)
Integer Programming	475	(87)
Introduction to Integer Programming	475	(2)
Formulating Integer Programming Problems	477	(35)
The Branch-and-Bound Method for Solving Pure Integer Programming Problems	512	(11)
The Branch-and-Bound Method for Solving Mixed Integer Programming Problems	523	(1)
Solving Knapsack Problems by the Branch-and-Bound Method	524	(3)
Solving Combinatorial Optimization Problems by the Branch-and-Bound Method	527	(13)
Implicit Enumeration	540	(5)
The Cutting Plane Algorithm	545	(17)
Advanced Topics in Linear Programming	562	(48)
The Revised Simplex Algorithm	562	(5)
The Product Form of the Inverse	567	(3)
Using Column Generation to Solve Large-Scale LPs	570	(6)
The Dantzig-Wolfe Decomposition Algorithm	576	(17)
The Simplex Method for Upper-Bounded Variables	593	(4)
Karmarkar's Method for Solving LPs	597	(13)
Game Theory	610	(43)
Two-Person Zero-Sum and Constant-Sum Games: Saddle Points	610	(4)
Two-Person Zero-Sum Games: Randomized Strategies, Domination, and Graphical Solution	614	(9)
Linear Programming and Zero-Sum Games	623	(11)
Two-Person Nonconstant-Sum Games	634	(5)
Introduction to n-Person Game Theory	639	(2)
The Core of an-Person Game	641	(3)
The Shapley Value	644	(9)
Nonlinear Programming	653	(97)
Review of Differential Calculus	653	(6)
Introductory Concepts	659	(14)
Convex and Concave Functions	673	(7)
Solving NLPs with One Variable	680	(12)
Golden Section Search	692	(6)
Unconstrained Maximization and Minimization with Several Variables	698	(5)
The Method of Steepest Ascent	703	(3)
Lagrange Multipliers	706	(7)
The Kuhn-Tucker Conditions	713	(10)
Quadratic Programming	723	(8)
Separable Programming	731	(5)
The Method of Feasible Directions	736	(2)
Pareto Optimality and Tradeoff Curves	738	(12)
Deterministic Dynamic Programming	750	(50)
Two Puzzles	750	(1)
A Network Problem	751	(7)
An Inventory Problem	758	(5)
Resource Allocation Problems	763	(11)
Equipment Replacement Problems	774	(4)
Formulating Dynamic Programming Recursions	778	(12)
Using EXCEL to Solve Dynamic Programming Problems	790	(10)
Heuristic Techniques	800	(23)
Complexity Theory	800	(4)
Introduction to Heuristic Procedures	804	(1)
Simulated Annealing	805	(3)
Genetic Search	808	(7)
Tabu Search	815	(6)
Comparison of Heuristics	821	(2)
Solving Optimization Problems with the Evolutionary Solver	823	(43)
Price Bundling, Index Function, Match Function, and Evolutionary Solver	823	(7)
More Nonlinear Pricing Models	830	(6)
Locating Warehouses	836	(3)
Solving Other Combinatorial Problems	839	(2)
Production Scheduling at John Deere	841	(5)
Assigning Workers to Jobs with the Evolutionary Solver	846	(5)
Cluster Analysis	851	(6)
Fitting Curves	857	(3)
Discriminant Analysis	860	(6)
Neural Networks	866	(25)
Introduction to Neural Networks	866	(4)
Examples of the Use of Neural Networks	870	(1)
Why Neural Nets Can Beat Regression: The XOR Example	871	(3)
Estimating Neural Nets with PREDICT	874	(8)
Using Genetic Algorithms to Optimize a Neural Network	882	(2)
Using Genetic Algorithms to Determine Weights for a Back Propagation Network	884	(7)
Appendix: Cases	891	(22)
Case 1 Help, I'm Not Getting Any Younger	892	(1)
Case 2 Solar Energy for Your Home	892	(1)
Case 3 Golf-Sport: Managing Operations	893	(3)
Case 4 Vision Corporation: Production Planning and Shipping	896	(1)
Case 5 Material Handling in a General Mail-Handling Facility	897	(3)
Case 6 Selecting Corporate Training Programs	900	(3)
Case 7 Best Chip: Expansion Strategy	903	(2)
Case 8 Emergency Vehicle Location in Springfield	905	(1)
Case 9 System Design: Project Management	906	(1)
Case 10 Modular Design for the Help-You Company	907	(2)
Case 11 Brite Power: Capacity Expansion	909	(4)
Index	913