## Linear Programming and its ApplicationsBased on earlier work by a variety of authors in the 1930s and 1940s, the simplex method for solving linear programming problems was developed in 1947 by the American mathematician George B. Dantzig. Helped by the computer revolution, it has been described by some as the overwhelmingly most significant mathematical development of the last century. Owing to the simplex method, linear programming (or linear optimization, as some would have it) is pervasive in modern society for the planning and control of activities that are constrained by the availability of resources such as manpower, raw materials, budgets, and time. The purpose of this book is to describe the field of linear programming. While we aim to be reasonably complete in our treatment, we have given emphasis to the modeling aspects of the field. Accordingly, a number of applications are provided, where we guide the reader through the interactive process of mathematically modeling a particular practical situation, analyzing the consequences of the model formulated, and then revising the model in light of the results from the analysis. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

5 | |

A3 Convexity | 23 |

B1 Algorithms and Time Complexity Functions | 31 |

B2 Examples of Time Complexity Functions | 37 |

B3 Classes of Problems and Their Relations | 41 |

11 A Short History of Linear Programming | 45 |

12 Assumptions and the Main Components of Linear Programming Problems | 48 |

53 Column Generation | 219 |

6 POSTOPTIMALITY ANALYSES | 225 |

61 Graphical Sensitivity Analysis | 227 |

62 Changes of the RightHand Side Values | 232 |

63 Changes of the Objective Function Coefficients | 240 |

64 Sensitivity Analyses in the Presence of Degeneracy | 245 |

65 Addition of a Constraint | 248 |

66 Economic Analysis of an Optimal Solution | 252 |

13 The Modeling Process | 53 |

14 The Three Phases in Optimization | 57 |

15 Solving the Model and Interpreting the Printout | 60 |

21 The Diet Problem | 67 |

22 Allocation Problems | 71 |

23 Cutting Stock Problems | 75 |

24 Employee Scheduling | 80 |

25 Data Envelopment Analysis | 82 |

26 Inventory Planning | 85 |

27 Blending Problems | 89 |

28 Transportation Problems | 91 |

29 Assignment Problems | 102 |

A Case Study | 107 |

31 Graphical Concepts 311 The Graphical Solution Technique | 129 |

312 Four Special Cases | 138 |

321 The Algebraic Solution Technique | 143 |

322 Four Special Cases Revisited | 158 |

41 The Fundamental Theory of Duality | 166 |

42 PrimalDual Relations | 183 |

43 Interpretations of the Dual Problem | 198 |

5 EXTENSIONS OF THE SIMPLEX METHOD | 203 |

52 The Upper Bounding Technique | 212 |

7 NONSIMPLEX BASED SOLUTION METHODS | 261 |

71 Alternatives to the Simplex Method | 262 |

72 Interior Point Methods | 273 |

81 Reformulations of Variables 811 Lower Bounding Constraints | 295 |

812 Variables Unrestricted in Sign | 296 |

82 Reformulations of Constraints | 298 |

831 Minimize the Weighted Sum of Absolute Values | 301 |

832 Bottleneck Problems | 306 |

833 Minimax and Maximin Problems | 313 |

834 Fractional Hyperbolic Programming | 320 |

9 MULTIOBJECTIVE PROGRAMMING | 325 |

91 Vector Optimization | 327 |

921 The Weighting Method | 337 |

922 The Constraint Method | 339 |

93 Models with Exogenous Achievement Levels | 341 |

931 Reference Point Programming | 342 |

932 Fuzzy Programming | 346 |

933 Goal Programming | 351 |

94 Bilevel Programming | 359 |

REFERENCES | 363 |

377 | |

### Other editions - View all

### Common terms and phrases

ai•x algorithm artificial variables assignment problem assume basic variables bottleneck computational consider the following convex convex combination costs Dantzig decision maker decision variables defined denote determine dual feasibility dual problem dual variables Eiselt ellipsoid method exists extreme points feasible set feasible solution Figure formulation given Go to Step goal programming gradient halfspaces hence hyperplane i-th includes indicates input integer interior point interior point methods inventory iteration left-hand side linear programming problem machine matrix maximize MCSMELL minimax minimize nonbasic variables objective function obtain ODDHEUR optimal solution optimal tableau original parameters period pivot column polytope possible primal degeneracy primal feasible procedure profit respectively right-hand side value s.t. Ax sensitivity analyses shadow price shown simplex algorithm simplex method slack variable solve system of simultaneous technique transformation transportation problem units upper bound variable xj vector zero

### Popular passages

Page 370 - Possibilistic Linear Programming: A Brief Review of Fuzzy Mathematical Programming and a Comparison with Stochastic Programming in Portfolio Selection Problem, Fuzzy Sets and Systems, Vol.

Page 371 - Research 117 (3) 565577. Jensen, A., 1980. Traffic, Operational Research, Futurology, North-Holland, Amsterdam. Powell, MJD, 1991. A view of nonlinear optimization. In: Lenstra, JK, Rinnooy Kan, AHG, Schrijver, A. (Eds.), History of Mathematical Programming, Elsevier Publishers, Amsterdam, pp.

Page 375 - Solving multiple objective programming problems using feed-forward artificial neural networks: The interactive FFANN procedure. Management Science 42 (6).

Page 371 - KOOPMANS, TC, ED., Activity Analysis of Production and Allocation. Wiley, New York, 1951. Cbwels Commission Monograph No. 13. 22. AND BECKMAN, MJ, "Assignment Problems and the Location of Economic Activities,

Page 369 - ... PROCESSING, Vol. II, 1959Jaeger, A., INTRODUCTION TO ANALYTIC GEOMETRY AND LINEAR ALGEBRA, HoltRinehart and Winston Inc., New York, 1960. Karlin, S., MATHEMATICAL METHODS AND THEORY IN GAMES, PROGRAMMING, AND ECONOMICS, Vol. I, Addison-Wesley, 1959, Reading, Mass.; Vol. II, THE THEORY OF INFINITE GAMES. Koopmans, TC, ed. ACTIVITY ANALYSIS OF PRODUCTION AND ALLOCATION, Cowles Commission Monograph No. 13, Wiley, 1951Kuhn, HW and Tucker, AW, CONTRIBUTIONS TO THE THEORY OF GAMES, Annals of Mathematics...