+612 9045 4394
Linear Programs and Related Problems : Computer Science and Scientific Computing - Evar D. Nering

Linear Programs and Related Problems

Computer Science and Scientific Computing

Hardcover Published: 1st October 1992
ISBN: 9780125154406
Number Of Pages: 584

Share This Book:


RRP $365.99
or 4 easy payments of $63.31 with Learn more
Ships in 7 to 10 business days

This text is concerned primarily with the theory of linear and nonlinear programming, and a number of closely-related problems, and with algorithms appropriate to those problems. In the first part of the book, the authors introduce the concept of duality which serves as a unifying concept throughout the book. The simplex algorithm is presented along with modifications and adaptations to problems with special structures. Two alternative algorithms, the ellipsoidal algorithm and Karmarker's algorithm, are also discussed, along with numerical considerations. the second part of the book looks at specific types of problems and methods for their solution. This book is designed as a textbook for mathematical programming courses, and each chapter contains numerous exercises and examples.

Linear Programsp. 1
Introductionp. 3
Sample Linear Programsp. 7
A Production Problemp. 7
A Diet Problemp. 14
A Transportation Problemp. 20
An Informal Algorithmp. 26
Graphical Representationp. 28
Tableau Algebrap. 43
Tableaux and the Duality Equationp. 43
Pivot Exchange, Row Equationsp. 48
Pivot Exchange, Column Equationsp. 56
Equivalent Tableauxp. 62
Basic Solutionsp. 67
Inversionp. 73
Block Pivotsp. 81
Expanded Tableauxp. 85
Canonical Dualityp. 95
Canonical Dual Linear Programsp. 95
Sufficient Conditions for Optimalityp. 99
Economic Interpretation of Dualityp. 102
Heuristic Pivotingp. 111
Optimal Solutions - Unique, Multiple, Nonep. 115
The Geometric Picturep. 120
Feasibility Algorithmp. 125
Priority Pivotingp. 132
The Simplex Algorithmp. 145
The Simplex Algorithmp. 145
Degeneracy and Cyclingp. 152
Bland's Anticycling Rulep. 156
Theorems of the Two Alternativesp. 161
The Dual Simplex Algorithmp. 163
The Theorem of the Four Alternativesp. 166
The Existence-Duality Theoremp. 170
General Linear Programsp. 177
General Dual Linear Programsp. 177
Reduction to Canonical Formp. 181
The Two-Phase Simplex Methodp. 185
Systems of Linear Inequalitiesp. 190
Complementary Slacknessp. 198
Numerical Considerationsp. 209
Numerical Considerationsp. 209
The Revised Simplex Methodp. 213
Gaussian Eliminationp. 221
Numerical Accuracyp. 229
The Ellipsoidal Algorithmp. 239
The Karmarkar Algorithmp. 241
Related Problemsp. 251
Matrix Gamesp. 253
Matching Gamesp. 253
Optimal Strategiesp. 258
Matrix Games and Linear Programsp. 261
Linear Programs and Symmetric Gamesp. 267
Assignment and Matching Problemsp. 275
The Assignment Problemp. 275
Kuhn's Hungarian Algorithmp. 280
Konig's Theoremp. 284
Matching and Hall's Theoremp. 293
Assignments and Linear Programsp. 298
Egervary's Theoremp. 305
Von Neumann's Hide-and-Seek Gamep. 307
Doubly Stochastic Matricesp. 310
The Transportation Problemp. 319
The Transportation Problemp. 319
Phase One of Dantzig's Methodp. 324
The Dual of the Transportation Problemp. 332
Dantzig's Methodp. 338
Economic Interpretation of the Dual Programp. 345
Graphs and Treesp. 349
Structure of Network Problemsp. 354
Pivoting in Graphsp. 359
Network Flow Problemsp. 373
Network Flow Problemsp. 373
The Ford-Fulkerson Algorithmp. 379
The Max-Flow, Min-Cut Theoremp. 385
The Transshipment Problemp. 395
The Transshipment Problemp. 395
Shortest Path Problemsp. 400
A Transshipment Algorithmp. 408
Nonlinear Programsp. 419
Karush-Kuhn-Tucker Theoremp. 419
The Constraint Qualificationp. 427
Least Squaresp. 433
Least Distancep. 439
Hybrid Problemsp. 444
Empirical Principal Pivotingp. 450
Quadratic Programsp. 455
Semidefinite Quadratic Programsp. 461
An Algorithm for Quadratic Programsp. 468
Noncanonical Quadratic Programsp. 481
A Answersp. 493
Selected Bibliographyp. 575
Indexp. 579
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9780125154406
ISBN-10: 0125154402
Series: Computer Science and Scientific Computing
Audience: Tertiary; University or College
Format: Hardcover
Language: English
Number Of Pages: 584
Published: 1st October 1992
Country of Publication: US
Dimensions (cm): 24.13 x 16.51  x 3.18
Weight (kg): 1.04