Introduction to Mathematical Programming: Applications and Algorithms

by Winston, Wayne L.

• ISBN13: 9780534230463
• ISBN10: 0534230466
• Edition: 2nd
• Format: Hardcover
• Copyright: 1994-04-01
• Publisher: ITP DUXBURY

Summary

Focusing on deterministic models, this book is designed for the first half of an operations research course. A subset of Winston's best-selling Operations Research, Introduction to Mathematical Programing offers self-contained chapters that make it flexible enough for one- or two-semester courses ranging from advanced beginning to intermediate in level. Appropriate for undergraduate majors, MBAs, and graduate students, it emphasizes model-formulations and model-building skills as well as interpretation of computer software output. LINDO, GINO, and LINGO software packages are available with the book in Windows, Macintosh, or DOS versions. Linear algebra prerequisite.

Table of Contents

Introduction to Mathematical Programming	1	(3)
Examples of Mathematical Programming	1	(1)
Successful Applications of Mathematical Programming	2	(1)
Where to Read More About Mathematical Programming	3	(1)
Basic Linear Algebra	4	(41)
Matrices and Vectors	4	(10)
Matrices and Systems of Linear Equations	14	(2)
The Gauss-Jordan Method for Solving Systems of Linear Equations	16	(11)
Linear Independence and Linear Dependence	27	(4)
The Inverse of a Matrix	31	(6)
Determinants	37	(8)
Introduction to Linear Programming	45	(75)
What Is a Linear Programming Problem?	45	(7)
The Graphical Solution of Two-Variable Linear Programming Problems	52	(8)
Special Cases	60	(6)
A Diet Problem	66	(3)
A Work-Scheduling Problem	69	(4)
A Capital Budgeting Problem	73	(4)
Short-Term Financial Planning	77	(3)
Blending Problems	80	(10)
Production Process Models	90	(5)
Using Linear Programming to Solve Multiperiod Decision Problems: An Inventory Model	95	(5)
Multiperiod Financial Models	100	(4)
Multiperiod Work Scheduling	104	(16)
The Simplex Algorithm and Goal Programming	120	(87)
How to Convert an LP to Standard Form	120	(4)
Preview of the Simplex Algorithm	124	(6)
The Simplex Algorithm	130	(10)
Using the Simplex Algorithm to Solve Minimization Problems	140	(2)
Alternative Optimal Solutions	142	(3)
Unbounded LPs	145	(3)
The LINDO Computer Package	148	(4)
Matrix Generators, LINGO, and Scaling of LPs	152	(5)
Degeneracy and the Convergence of the Simplex Algorithm	157	(4)
The Big M Method	161	(6)
The Two-Phase Simplex Method	167	(5)
Unrestricted-in-Sign Variables	172	(6)
Karmarkar's Method for Solving LPs	178	(1)
Multiattribute Decision Making in the Absence of Uncertainty: Goal Programming	179	(13)
Solving LPs with Spreadsheets	192	(15)
Sensitivity Analysis: An Applied Approach	207	(37)
A Graphical Introduction to Sensitivity Analysis	207	(5)
The Computer and Sensitivity Analysis	212	(15)
Managerial Use of Shadow Prices	227	(2)
What Happens to the Optimal z-Value If the Current Basis Is No Longer Optimal?	229	(15)
Sensitivity Analysis and Duality	244	(105)
A Graphical Introduction to Sensitivity Analysis	244	(6)
Some Important Formulas	250	(8)
Sensitivity Analysis	258	(15)
Sensitivity Analysis When More Than One Parameter Is Changed: The 100% Rule	273	(6)
Finding the Dual of an LP	279	(7)
Economic Interpretation of the Dual Problem	286	(3)
The Dual Theorem and Its Consequences	289	(10)
Shadow Prices	299	(10)
Duality and Sensitivity Analysis	309	(3)
Complementary Slackness	312	(4)
The Dual Simplex Method	316	(6)
Data Envelopment Analysis	322	(27)
Transportation, Assignment, and Transshipment Problems	349	(56)
Formulating Transportation Problems	349	(13)
Finding Basic Feasible Solutions for Transportation Problems	362	(10)
The Transportation Simplex Method	372	(8)
Sensitivity Analysis for Transportation Problems	380	(3)
Assignment Problems	383	(8)
Transshipment Problems	391	(14)
Network Models	405	(72)
Basic Definitions	405	(1)
Shortest Path Problems	406	(6)
Maximum Flow Problems	412	(14)
CPM and PERT	426	(22)
Minimum Cost Network Flow Problems	448	(7)
Minimum Spanning Tree Problems	455	(4)
The Network Simplex Method	459	(18)
Integer Programming	477	(90)
Introduction to Integer Programming	477	(3)
Formulating Integer Programming Problems	480	(35)
The Branch-and-Bound Method for Solving Pure Integer Programming Problems	515	(13)
The Branch-and-Bound Method for Solving Mixed Integer Programming Problems	528	(1)
Solving Knapsack Problems by the Branch-and-Bound Method	529	(3)
Solving Combinatorial Optimization Problems by the Branch-and-Bound Method	532	(14)
Implicit Enumeration	546	(6)
The Cutting Plane Algorithm	552	(15)
Advanced Topics in Linear Programming	567	(52)
The Revised Simplex Algorithm	567	(5)
The Product Form of the Inverse	572	(3)
Using Column Generation to Solve Large-Scale LPs	575	(7)
The Dantzig-Wolfe Decomposition Algorithm	582	(18)
The Simplex Method for Upper-Bounded Variables	600	(4)
Karmarkar's Method for Solving LPs	604	(15)
Game Theory	619	(45)
Two-Person Zero-Sum and Constant-Sum Games: Saddle Points	619	(4)
Two-Person Zero-Sum Games: Randomized Strategies, Domination, and Graphical Solution	623	(9)
Linear Programming and Zero-Sum Games	632	(13)
Two-Person Nonconstant-Sum Games	645	(4)
Introduction to n-Person Game Theory	649	(2)
The Core of an n-Person Game	651	(4)
The Shapley Value	655	(9)
Nonlinear Programming	664	(101)
Review of Differential Calculus	664	(7)
Introductory Concepts	671	(12)
Convex and Concave Functions	683	(9)
Solving NLPs with One Variable	692	(8)
Golden Section Search	700	(6)
Unconstrained Maximization and Minimization with Several Variables	706	(6)
The Method of Steepest Ascent	712	(4)
Lagrange Multipliers	716	(7)
The Kuhn-Tucker Conditions	723	(11)
Quadratic Programming	734	(8)
Separable Programming	742	(6)
The Method of Feasible Directions	748	(3)
Pareto Optimality and Tradeoff Curves	751	(14)
Deterministic Dynamic Programming	765
Two Puzzles	765	(2)
A Network Problem	767	(7)
An Inventory Problem	774	(6)
Resource Allocation Problems	780	(12)
Equipment Replacement Problems	792	(3)
Formulating Dynamic Programming Recursions	795	(13)
Using Spreadsheets to Solve Dynamic Programming Problems	808
Answers to Selected Problems	A1
Index	A27