Linear Programming and Extensions

Front Cover
Princeton University Press, Aug 10, 2016 - Mathematics - 656 pages

In real-world problems related to finance, business, and management, mathematicians and economists frequently encounter optimization problems. In this classic book, George Dantzig looks at a wealth of examples and develops linear programming methods for their solutions. He begins by introducing the basic theory of linear inequalities and describes the powerful simplex method used to solve them. Treatments of the price concept, the transportation problem, and matrix methods are also given, and key mathematical concepts such as the properties of convex sets and linear vector spaces are covered.


George Dantzig is properly acclaimed as the "father of linear programming." Linear programming is a mathematical technique used to optimize a situation. It can be used to minimize traffic congestion or to maximize the scheduling of airline flights. He formulated its basic theoretical model and discovered its underlying computational algorithm, the "simplex method," in a pathbreaking memorandum published by the United States Air Force in early 1948. Linear Programming and Extensions provides an extraordinary account of the subsequent development of his subject, including research in mathematical theory, computation, economic analysis, and applications to industrial problems.


Dantzig first achieved success as a statistics graduate student at the University of California, Berkeley. One day he arrived for a class after it had begun, and assumed the two problems on the board were assigned for homework. When he handed in the solutions, he apologized to his professor, Jerzy Neyman, for their being late but explained that he had found the problems harder than usual. About six weeks later, Neyman excitedly told Dantzig, "I've just written an introduction to one of your papers. Read it so I can send it out right away for publication." Dantzig had no idea what he was talking about. He later learned that the "homework" problems had in fact been two famous unsolved problems in statistics.

 

What people are saying - Write a review

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

Contents

CHAPTER 1 THE LINEAR PROGRAMMING CONCEPT
1
CHAPTER 2 ORIGINS AND INFLUENCES
12
CHAPTER 3 FORMULATING A LINEAR PROGRAMMING MODEL
32
CHAPTER 4 LINEAR EQUATION AND INEQUALITY SYSTEMS
69
CHAPTER 5 THE SIMPLEX METHOD
94
CHAPTER 6 PROOF OF THE SIMPLEX ALGORITHM AND THE DUALITY THEOREM
120
CHAPTER 7 THE GEOMETRY OF LINEAR PROGRAMS
147
CHAPTER 8 PIVOTING VECTOR SPACES MATRICES AND INVERSES
173
CHAPTER 17 NETWORKS AND THE TRANSSHIPMENT PROBLEM
352
CHAPTER 18 VARIABLES WITH UPPER BOUNDS
368
CHAPTER 19 MAXIMAL FLOWS IN NETWORKS
385
CHAPTER 20 THE PRIMALDUAL METHOD FOR TRANSPORTATION PROBLEMS
404
CHAPTER 21 THE WEIGHTED DISTRIBUTION PROBLEM
413
CHAPTER 22 PROGRAMS WITH VARIABLE COEFFICIENTS
433
CHAPTER 23 A DECOMPOSITION PRINCIPLE FOR LINEAR PROGRAMS
448
CHAPTER 24 CONVEX PROGRAMMING
471

CHAPTER 9 THE SIMPLEX METHOD USING MULTIPLIERS
210
CHAPTER 10 FINITENESS OF THE SIMPLEX METHOD UNDER PERTURBATION
228
CHAPTER 11 VARIANTS OF THE SIMPLEX ALGORITHM
240
CHAPTER 12 THE PRICE CONCEPT IN LINEAR PROGRAMMING
254
CHAPTER 13 GAMES AND LINEAR PROGRAMS
277
CHAPTER 14 THE CLASSICAL TRANSPORTATION PROBLEM
299
CHAPTER 15 OPTIMAL ASSIGNMENT AND OTHER DISTRIBUTION PROBLEMS
316
CHAPTER 16 THE TRANSSHIPMENT PROBLEM
335
CHAPTER 25 UNCERTAINTY
499
CHAPTER 26 DISCRETE VARIABLE EXTREMUM PROBLEMS
514
AN EXAMPLE OF FORMULATION AND SOLUTION
551
CHAPTER 28 THE ALLOCATION OF AIRCRAFT TO ROUTES UNDER UNCERTAIN DEMAND
568
BIBLIOGRAPHY
592
INDEX
617
Copyright

Other editions - View all

Common terms and phrases

About the author (2016)

George B. Dantzig is Professor Emeritus in the Department of Engineering-Economic Systems and Operations Research at Stanford University.

Bibliographic information