Mathematical programming

S. M. Sinha813120376X, 9788131203767, 9780080535937

Mathematical Programming, a branch of Operations Research, is perhaps the most efficient technique in making optimal decisions. It has a very wide application in the analysis of management problems, in business and industry, in economic studies, in military problems and in many other fields of our present day activities. In this keen competetive world, the problems are getting more and more complicated ahnd efforts are being made to deal with these challenging problems. This book presents from the origin to the recent developments in mathematical programming. The book has wide coverage and is self-contained. It is suitable both as a text and as a reference. * A wide ranging all encompasing overview of mathematical programming from its origins to recent developments * A result of over thirty years of teaching experience in this feild * A self-contained guide suitable both as a text and as a reference

---

Table of contents :
Front cover ……Page 1
Preface ……Page 2
Table of Contents ……Page 3
1.1. Background and Historical Sketch ……Page 6
1.2. Linear Programming ……Page 7
1.3. Illustrative Examples ……Page 8
1.4. Graphical Solutions ……Page 10
1.5. Nonlinear Programming ……Page 14
PART-1 MATHEMATICAL FOUNDATIONS ……Page 15
2.1. Sets ……Page 16
2.2. Vectors ……Page 18
2.3. Topological Properties of $R^n$ ……Page 19
2.4. Sequences and Subsequences ……Page 21
2.5. Mappings and Functions ……Page 22
2.7. Infimum and Supremum of Functions ……Page 23
2.8. Minima and Maxima of Functions ……Page 24
2.9. Differentiable Functions ……Page 25
3.2. Vector Spaces ……Page 29
3.3. Subspaces ……Page 30
3.4. Linear Dependence ……Page 31
3.5. Basis and Dimension ……Page 34
3.6. Inner Product Spaces ……Page 37
4.1. Matrices ……Page 41
4.2. Relations and Operations ……Page 42
4.3. Partitioning of Matrices ……Page 44
4.4. Rank of a Matrix ……Page 45
4.5. Determinants ……Page 46
4.7. Minors and Cofactors ……Page 47
4.8. Determinants and Rank ……Page 48
4.9.1. Definition and General Properties ……Page 49
4.9.2. Inversion by Partitioning ……Page 50
4.9.3. Product Form of the Inverse ……Page 51
5.1. Linear Transformations and Rank ……Page 53
5.2. Product of Linear Transformations ……Page 54
5.3. Elementary Transformations ……Page 55
5.3.1. Elementary Matrices ……Page 56
5.4. Echelon Matrices and Rank ……Page 57
6.1. Quadratic Forms ……Page 59
6.2. Definite Quadratic Forms ……Page 60
6.3. Characteristic Vectors and Characteristic Values ……Page 62
7.2. Existence Theorems for Systems of Linear Equations ……Page 66
7.3. Basic Solutions and Degeneracy ……Page 69
7.4. Theorems of the Alternative ……Page 71
8.2. Convex Sets and their Properties ……Page 79
8.3. Convex Hulls ……Page 82
8.4. Separation and Support of Convex Sets ……Page 84
8.5. Convex Polytopes and Polyhedra ……Page 90
8.6. Convex Cones ……Page 94
9.1. Definitions and Basic Properties ……Page 97
9.2. Differentiable Convex Functions ……Page 104
9.3. Generalization of Convex Functions ……Page 107
9.4. Exercises ……Page 116
10.2. Equivalent Formulations ……Page 120
10.4. Basic Solutions of Linear Programs ……Page 123
10.5. Fundamental Properties of Linear Programs ……Page 124
10.6. Exercises ……Page 129
11.2. Theory of the Simplex Method ……Page 135
11.3. Method of Computation: The Simplex Algorithm ……Page 139
11.4. The Simplex Tableau ……Page 140
11.5. Replacement Operation ……Page 141
11.5.1 Replacement Rule ……Page 143
11.6. Example ……Page 144
11.7. Exercises ……Page 145
12.2. The Two-Phase Method ……Page 148
12.3.1. ……Page 150
12.3.2. ……Page 152
12.4. The Method of Penalties ……Page 153
12.5.1 ……Page 155
12.5.2 ……Page 157
12.6. Inconsistency and Redundancy ……Page 158
12.7. Exercises ……Page 159
13.1. Introduction ……Page 161
13.2. Charnes’ Perturbation Method ……Page 162
13.3. Example ……Page 165
13.4. Exercises ……Page 166
14.2. Outline of the Procedure ……Page 168
14.2.1 Case 1: Initial basis is known ……Page 169
14.2.2 Case 2. Initial basis consists of artificial variables ……Page 170
14.3. Example ……Page 175
14.4. Exercises ……Page 178
15.2. Cannonical Dual Programs and Duality Theorems ……Page 180
15.3. Equivalent Dual Forms ……Page 185
15.4. Other Important Results ……Page 188
15.5. Lagrange Multipliers and Duality ……Page 192
15.6. Duality in the Simplex Method ……Page 193
15.6.1. Optimal solution of the dual ……Page 194
15.7. Example ……Page 195
15.8. Applications ……Page 197
15.9. Economic interpretation of Duality ……Page 198
15.9. Exercises ……Page 200
16.2. The Dual Simplex Method ……Page 202
16.3. The Dual Simplex Algorithm ……Page 205
16.4.2. Dantzig’s Method ……Page 206
16.4.4. A General Method: The Artificial Constraint Technique ……Page 207
16.5. Example ……Page 211
16.6. The Primal – Dual Algorithm ……Page 213
16.7. Summary of the Primal-Dual Algorithm ……Page 218
16.8. Example ……Page 219
16.9. The Initial Solution to the Dual Problem: The Artificial Constraint Technique ……Page 221
16.10. Exercises ……Page 222
17.2. Sensitivity Analysis ……Page 225
17.3. Changes in the Cost Vector ……Page 226
17.4. Changes in the Requirement Vector ……Page 227
17.5. Changes in the Elements of the Technology Matrix ……Page 228
17.6. Addition of a Constraint ……Page 232
17.9. Parametric Changes in the Cost Vector ……Page 233
17.10. Parametric Changes in the Requirement Vector ……Page 235
17.11. Exercises ……Page 236
18.2. Bounded from Below ……Page 239
18.3. Bounded from Above ……Page 240
18.4. The Optimally Criterion ……Page 241
18.5. Improving a Basic Feasible Solution ……Page 242
18.6. Example ……Page 244
18.7. Exercises ……Page 247
19.2. The Mathematical Formulation ……Page 248
19.3. Fundamental Properties of Transportation Problems ……Page 251
19.4. Initial Basic Feasible Solution ……Page 254
19.5. Duality and Optimality Criterion ……Page 258
19.6. Improvement of a Basic Feasible Solution ……Page 259
19.7. The Transportation Algorithm ……Page 260
19.8. Degeneracy ……Page 261
19.9. Examples ……Page 262
19.10. Unbalanced Transportation Problem ……Page 265
19.11. The Transhipment Problem ……Page 269
19.12. Exercises ……Page 273
20.1. Introduction and Mathematical Formulation ……Page 278
20.2. The Hungarian Method ……Page 279
20.3. The Assignment Algorithm ……Page 280
20.4. Variations of the Assignment Model ……Page 282
20.5. Some Applications of the Assignment Model ……Page 283
20.6. Exercises ……Page 291
21.2. The Original Problem and its Equivalent ……Page 294
21.3 The Decomposition Algorithm ……Page 297
21.4. Initial Basic Feasible Solution ……Page 298
21.5. The Case of Unbounded $S_j$ ……Page 299
21.7. Example ……Page 301
21.8. Exercises ……Page 304
22.2. Computational Complexity of Linear Programs ……Page 306
22.3. Khachiyan’s Ellipsoid Method ……Page 307
22.4. Solving Linear Programming Problems by the Ellipsoid Method ……Page 310
22.5. Karmarkar’s Polynomial-Time Algorithm ……Page 311
22.6. Convergence and Complexity of Karmarkar’s Algorithm ……Page 314
22.7. Conversion of a General Linear Program into Karmarkar’s Form ……Page 319
22.8 Exercises ……Page 323
23.1. Introduction ……Page 326
23.2. Unconstrained Optimization ……Page 327
23.3. Constrained Optimization ……Page 329
23.4. Kuhn-Tucker Optimality Conditions ……Page 331
23.5. Kuhn-Tucker Constraint Qualification ……Page 333
23.6. Other Constraint Qualifications ……Page 336
23.7. Lagrange Saddle Point Problem and Kuhn-Tucker Conditions ……Page 338
23.8. Exercises ……Page 341
24.1. Introduction ……Page 343
24.2. Wolfe’s Method ……Page 345
24.2.1. The Computation ……Page 346
24.3. Dantzig’s Method ……Page 352
24.4. Beale’s Method ……Page 353
24.4.1 Summary of Beale’s Algorithm ……Page 356
24.4.2. Example ……Page 357
24.5.1. The Linear Complementarity Problem ……Page 359
24.5.2. Example ……Page 362
24.5.3. Solving Quadratic Programs by Complementary Pivoting Algorithm ……Page 364
24.6. Exercises ……Page 367
25.1. Separable Programming ……Page 369
25.1.1. Approximating the Problem ……Page 370
25.1.2. Solution of the Problem ……Page 372
25.1.4. Example ……Page 375
25.1.5. Mixed Integer Programming Formulation ……Page 376
25.2. Kelley’s Cutting Plane Method ……Page 377
25.2.1. Summary of the Algorithm ……Page 378
25.2.2. Convergence of the Algorithm ……Page 379
25.2.3. Example ……Page 380
25.3. Zoutendijk’s Method of Feasible Directions ……Page 382
25.3.1. Direction Finding Problem ……Page 386
25.3.3. Finding an Initial Feasible Solution ……Page 390
25.3.4. Summary of the Algorithm ……Page 391
25.3.5. Convergence of the Procedure ……Page 392
25.3.7. The Case of Linear Constraints ……Page 393
25.3.8. Example ……Page 394
25.4. Rosen’s Gradient Projection Method ……Page 397
25.4.1. The Projection Matrix ……Page 398
25.4.2. Rosen’s Algorithm ……Page 399
25.4.3. Determination of Usable Feasible Directions ……Page 400
25.4.4. Determination of the Length of the Steps ……Page 401
25.4.5. Summary of the Algorithm ……Page 402
25.4.6. Example ……Page 403
25.5. Wolfe’s Reduced Gradient Method ……Page 406
25.5.2. Summary of the Algorithm ……Page 408
25.5.3. Example ……Page 409
25.6. Zangwill’s Convex-Simplex Method ……Page 412
25.6.1. Summary of the Convex-Simplex Method ……Page 413
25.6.2. Example ……Page 415
25.7. Dantzig’s Method for Convex Programs ……Page 417
25.8 Exercises ……Page 421
26.2. Duality Theorems ……Page 426
26.3.1. Duality in Nonlinear Programs with Linear Constraints ……Page 429
26.3.1.1. Duality in Quadratic Programming ……Page 430
27.1. Introduction ……Page 434
27.2.1. Mathematical Formulation ……Page 437
27.3.1. The problem and its Dual ……Page 441
27.3.2. Duality ……Page 442
27.3.3. Solution of the quadratic program ……Page 452
27.3.4 Solution of the Dual Problem ……Page 455
27.3.5. Solution of the Primal Problem ……Page 456
27.4 The General Case ……Page 457
27.4.1. The subproblem and its Dual ……Page 458
27.4.2. Duality ……Page 459
27.4.3. Solution of the “Subproblem” ……Page 461
27.5. Exercises ……Page 462
28.1. Goal Programming ……Page 465
28.1.1. The Archimedian Goal Programming ……Page 466
28.1.2. Preemptive Goal Programming ……Page 467
28.1.6. Sensitivity Analysis in Goal Programming ……Page 469
28.2. Multiple Objective Linear Programming ……Page 470
28.2.2. Ranking or Prioritizing Methods ……Page 471
28.2.3. Efficient Solution Methods ……Page 472
28.2.4. Finding Efficient Extreme Points ……Page 475
28.2.5. Determining the Set of All Efficient Points ……Page 481
28.3. Fractional Programming ……Page 482
28.3.1. Linear Fractional Programming ……Page 484
28.3.2. Nonlinear Fractional Programming ……Page 487
28.3.4. Other Fractional Programs ……Page 491
28.3.5. Indefinite Quadratic Programming ……Page 499
28.4. Exercises ……Page 500
29.2. Basic Features of Dynamic Programming Problems and the Principle of Optimality ……Page 505
29.3. The Functional Equation ……Page 506
29.4. Cargo Loading Problem ……Page 507
29.6. Shortest Route Problem ……Page 510
29.7. Investment Planning ……Page 512
29.8. Inventory Problem ……Page 515
29.9. Reliability Problem ……Page 518
29.10. Cases where Decision Variables are Continuous ……Page 519
29.11.1. Allocation Problems with Two Types of Resources and Two Decision Variables ……Page 522
29.11.2. Allocation Problems with Two Constraints and One Decision Variable ……Page 523
29.12. Reduction in Dimensionality ……Page 526
29.13.1 As an illustration, let us first consider a rephrased version of Bellman’s gold mining problem ……Page 529
29.13.2. Stochastic Inventory Problems ……Page 530
29.14. Infinite Stage Process ……Page 531
29.15. Exercises ……Page 532
Bibliography ……Page 537
Index ……Page 569