Linear programming and extensions /
副标题：无
分类号：
ISBN：9780691059136
微信扫一扫,移动浏览光盘
简介
Summary:
Publisher Summary 1
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 Extensionsprovides 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.
目录
Table Of Contents:
Preface vii
CHAPTER 1 THE LINEAR PROGRAMMING CONCEPT 1(11)
1-1. Introduction 1(1)
1-2. The Programming Problem 1(5)
1-3. Linear Programming Defined 6(1)
1-4. Classification of Programming Problems 7(3)
1-5. Mathematical Programming and Automation 10(2)
CHAPTER 2 ORIGINS AND INFLUENCES 12(20)
2-1. World War II Influences 12(4)
2-2. Economic Models and Linear Programming 16(4)
2-3. Mathematical Origins and Developments 20(8)
2-4. Industrial Applications of Linear Programming 28(4)
CHAPTER 3 FORMULATING A LINEAR PROGRAMMING MODEL 32(37)
3-1. Basic Concepts 32(2)
3-2. Building the Model 34(1)
3-3. A Transportation Problem 35(7)
3-4. Examples of Blending 42(8)
3-5. A Product Mix Problem 50(5)
3-6. A Simple Warehouse Problem 55(2)
3-7. On-the-job Training 57(3)
3-8. The Central Mathematical Problem 60(2)
3-9. Problems 62(7)
CHAPTER 4 LINEAR EQUATION AND INEQUALITY SYSTEMS 69(25)
4-1. Systems of Equations with the Same Solution Set 69(6)
4-2. Canonical Systems 75(6)
4-3. Linear Inequalities 81(3)
4-4. Fourier-Motzkin Elimination Method 84(1)
4-5. Linear Programs in Inequality Form 85(4)
4-6. Problems 89(5)
CHAPTER 5 THE SIMPLEX METHOD 94(26)
5-1. Simplex Algorithm 94(6)
5-2. The Two Phases of the Simplex Method 100(11)
5-3. Problems 111(9)
CHAPTER 6 PROOF OF THE SIMPLEX ALGORITHM AND THE DUALITY THEOREM 120(27)
6-1. Inductive Proof of the Simplex Algorithm 120(3)
6-2. Equivalent Dual Forms 123(5)
6-3. Proof of the Duality Theorem 128(6)
6-4. Basic Theorems on Duality 134(6)
6-5. Lagrange Multipliers 140(4)
6-6. Problems 144(3)
CHAPTER 7 THE GEOMETRY OF LINEAR PROGRAMS 147(26)
7-1. Convex Regions 147(9)
7-2. The Simplex Method Viewed as the Steepest Descent Along Edges 156(4)
7-3. The Simplex Interpretation of the Simplex Method 160(6)
7-4. Problems 166(7)
CHAPTER 8 PIVOTING, VECTOR SPACES, MATRICES, AND INVERSES 173(38)
8-1. Pivot Theory 173(4)
8-2. Vector Spaces 177(6)
8-3. Matrices 183(6)
8-4. Inverse of a Matrix 189(6)
8-5. The Simplex Algorithm in Matrix Form 195(7)
8-6. Problems 202(9)
CHAPTER 9 THE SIMPLEX METHOD USING MULTIPLIERS 211(17)
9-1. An Illustration Using Multipliers 211(6)
9-2. The General Method Using Multipliers 217(4)
9-3. Computational Rules Using Multipliers 221(5)
9-4. Problems 226(2)
CHAPTER 10 FINITENESS OF THE SIMPLEX METHOD UNDER PERTURBATION 228(13)
10-1. The Possibility of Circling in the Simplex Algorithm 228(3)
10-2. Perturbing Constants To Avoid Degeneracy 231(6)
10-3. Problems 237(4)
CHAPTER 11 VARIANTS OF THE SIMPLEX ALGORITHM 241(13)
11-1. Complementary Primal and Dual Bases 241(2)
11-2. The Dual Simplex Method 243(2)
11-3. A Self-Dual Parametric Algorithm 245(2)
11-4. The Primal-Dual Algorithm 247(5)
11-5. An Alternative Criterion for Phase I 252(1)
11-6. Problems 253(1)
CHAPTER 12 THE PRICE CONCEPT IN LINEAR PROGRAMMING 254(23)
12-1. The Price Mechanism of the Simplex Method 254(6)
12-2. Examples of Dual Problems 260(4)
12-3. The Sign Convention on Prices 264(1)
12-4. Sensitivity Analysis Illustrated 265(10)
12-5. Problems 275(2)
CHAPTER 13 GAMES AND LINEAR PROGRAMS 277(22)
13-1. Matrix Games 277(9)
13-2. Equivalence of Matrix Games and Linear Programs; The Minimax Theorem 286(5)
13-3. Constructive Solution to a Matrix Game (Alternative Proof of Minimax Theorem) 291(6)
13-4. Problems 297(2)
CHAPTER 14 THE CLASSICAL TRANSPORTATION PROBLEM 299(17)
14-1. Historical Summary 299(1)
14-2. Elementary Transportation Theory 300(8)
14-3. Computational Algorithm for the Transportation Problem 308(6)
14-4. Problems 314(2)
CHAPTER 15 OPTIMAL ASSIGNMENT AND OTHER DISTRIBUTION PROBLEMS 316(19)
15-1. The Optimal Assignment Problem 316(6)
15-2. Allocation with Surplus and Deficit 322(8)
15-3. Fixed Values and Inadmissible Squares 330(2)
15-4. Problems 332(3)
CHAPTER 16 THE TRANSSHIPMENT PROBLEM 335(17)
16-1. Equivalent Formulations of the Model 335(7)
16-2. The Equivalence of Transportation and Transshipment Problems 342(4)
16-3. Solving a Transshipment Problem by the Simplex Method 346(5)
16-4. Problems 351(1)
CHAPTER 17 NETWORKS AND THE TRANSSHIPMENT PROBLEM 352(16)
17-1. Graphs and Trees 352(5)
17-2. Interpreting the Simplex Method on the Network 357(4)
17-3. The Shortest Route Problem 361(5)
17-4. Problems 366(2)
CHAPTER 18 VARIABLES WITH UPPER BOUNDS 368(17)
18-1. The General Case 368(9)
18-2. The Bounded Variable Transportation Problem and Generalizations 377(6)
18-3. Problems 383(2)
CHAPTER 19 MAXIMAL FLOWS IN NETWORKS 385(19)
19-1. Ford-Fulkerson Theory 385(13)
19-2. The Tree Method for Solving Maximal Flow Problems 398(5)
19-3. Problems 403(1)
CHAPTER 20 THE PRIMAL-DUAL METHOD FOR TRANSPORTATION PROBLEMS 404(9)
20-1. Introduction 404(1)
20-2. The Ford-Fulkerson Algorithm 405(6)
20-3. Problems 411(2)
CHAPTER 21 THE WEIGHTED DISTRIBUTION PROBLEM 413(20)
21-1. The Near-Triangularity of the Basis 413(7)
21-2. Linear Graph Structure of the Basis 420(4)
21-3. A Subclass with Triangular Optimium Bases 424(7)
21-4. Problems 431(2)
CHAPTER 22 PROGRAMS WITH VARIABLE COEFFICIENTS 433(15)
22-1. Wolfe's Generalized Program 433(7)
22-2. Notes on Special Cases 440(6)
22-3. Problems 446(2)
CHAPTER 23 A DECOMPOSITION PRINCIPLE FOR LINEAR PROGRAMS 448(23)
23-1. The General Principle 448(7)
23-2. Decomposition Principle, Animated 455(7)
23-3. Central Planning without Complete Information at the Center 462(4)
23-4. Decomposing Multi-stage Programs 466(3)
23-5. Problems 469(2)
CHAPTER 24 CONVEX PROGRAMMING 471(28)
24-1. General Theory 471(8)
24-2. Homogeneous Objectives and the Chemical Equilibrium Problem 479(3)
24-3. Separable Convex Objectives 482(8)
24-4. Quadratic Programming 490(7)
24-5. Problems 497(2)
CHAPTER 25 UNCERTAINTY 499(15)
25-1. Scheduling To Meet Variable Cost 499(4)
25-2. Scheduling To Meet an Uncertain Demand 503(4)
25-3. On Multi-stage Problems 507(4)
25-4. Problems 511(3)
CHAPTER 26 DISCRETE VARIABLE EXTREMUM PROBLEMS 514(37)
26-1. Survey of Methods 514(7)
26-2. Gomory's Method of Integer Forms 521(14)
26-3. On the Significance of Solving Linear Programming Problems with Some Integer Variables 535(16)
CHAPTER 27 STIGLER'S NUTRITION MODEL: AN EXAMPLE OF FORMULATION AND SOLUTION 551(17)
27-1. Problems in Formulating a Model 551(6)
27-2. Numerical Solution of the Nutrition Problem 557(9)
27-3. Problems 566(2)
CHAPTER 28 THE ALLOCATION OF AIRCRAFT TO ROUTES UNDER UNCERTAIN DEMAND 568(24)
28-1. Statement and Formulation 568(12)
28-2. Numerical Solution of the Routing Problem 580(12)
BIBLIOGRAPHY References to the Bibliography are given in text and at the end of each chapter (see in particular the end of Chapter 2). 592(25)
INDEX 617
Preface vii
CHAPTER 1 THE LINEAR PROGRAMMING CONCEPT 1(11)
1-1. Introduction 1(1)
1-2. The Programming Problem 1(5)
1-3. Linear Programming Defined 6(1)
1-4. Classification of Programming Problems 7(3)
1-5. Mathematical Programming and Automation 10(2)
CHAPTER 2 ORIGINS AND INFLUENCES 12(20)
2-1. World War II Influences 12(4)
2-2. Economic Models and Linear Programming 16(4)
2-3. Mathematical Origins and Developments 20(8)
2-4. Industrial Applications of Linear Programming 28(4)
CHAPTER 3 FORMULATING A LINEAR PROGRAMMING MODEL 32(37)
3-1. Basic Concepts 32(2)
3-2. Building the Model 34(1)
3-3. A Transportation Problem 35(7)
3-4. Examples of Blending 42(8)
3-5. A Product Mix Problem 50(5)
3-6. A Simple Warehouse Problem 55(2)
3-7. On-the-job Training 57(3)
3-8. The Central Mathematical Problem 60(2)
3-9. Problems 62(7)
CHAPTER 4 LINEAR EQUATION AND INEQUALITY SYSTEMS 69(25)
4-1. Systems of Equations with the Same Solution Set 69(6)
4-2. Canonical Systems 75(6)
4-3. Linear Inequalities 81(3)
4-4. Fourier-Motzkin Elimination Method 84(1)
4-5. Linear Programs in Inequality Form 85(4)
4-6. Problems 89(5)
CHAPTER 5 THE SIMPLEX METHOD 94(26)
5-1. Simplex Algorithm 94(6)
5-2. The Two Phases of the Simplex Method 100(11)
5-3. Problems 111(9)
CHAPTER 6 PROOF OF THE SIMPLEX ALGORITHM AND THE DUALITY THEOREM 120(27)
6-1. Inductive Proof of the Simplex Algorithm 120(3)
6-2. Equivalent Dual Forms 123(5)
6-3. Proof of the Duality Theorem 128(6)
6-4. Basic Theorems on Duality 134(6)
6-5. Lagrange Multipliers 140(4)
6-6. Problems 144(3)
CHAPTER 7 THE GEOMETRY OF LINEAR PROGRAMS 147(26)
7-1. Convex Regions 147(9)
7-2. The Simplex Method Viewed as the Steepest Descent Along Edges 156(4)
7-3. The Simplex Interpretation of the Simplex Method 160(6)
7-4. Problems 166(7)
CHAPTER 8 PIVOTING, VECTOR SPACES, MATRICES, AND INVERSES 173(38)
8-1. Pivot Theory 173(4)
8-2. Vector Spaces 177(6)
8-3. Matrices 183(6)
8-4. Inverse of a Matrix 189(6)
8-5. The Simplex Algorithm in Matrix Form 195(7)
8-6. Problems 202(9)
CHAPTER 9 THE SIMPLEX METHOD USING MULTIPLIERS 211(17)
9-1. An Illustration Using Multipliers 211(6)
9-2. The General Method Using Multipliers 217(4)
9-3. Computational Rules Using Multipliers 221(5)
9-4. Problems 226(2)
CHAPTER 10 FINITENESS OF THE SIMPLEX METHOD UNDER PERTURBATION 228(13)
10-1. The Possibility of Circling in the Simplex Algorithm 228(3)
10-2. Perturbing Constants To Avoid Degeneracy 231(6)
10-3. Problems 237(4)
CHAPTER 11 VARIANTS OF THE SIMPLEX ALGORITHM 241(13)
11-1. Complementary Primal and Dual Bases 241(2)
11-2. The Dual Simplex Method 243(2)
11-3. A Self-Dual Parametric Algorithm 245(2)
11-4. The Primal-Dual Algorithm 247(5)
11-5. An Alternative Criterion for Phase I 252(1)
11-6. Problems 253(1)
CHAPTER 12 THE PRICE CONCEPT IN LINEAR PROGRAMMING 254(23)
12-1. The Price Mechanism of the Simplex Method 254(6)
12-2. Examples of Dual Problems 260(4)
12-3. The Sign Convention on Prices 264(1)
12-4. Sensitivity Analysis Illustrated 265(10)
12-5. Problems 275(2)
CHAPTER 13 GAMES AND LINEAR PROGRAMS 277(22)
13-1. Matrix Games 277(9)
13-2. Equivalence of Matrix Games and Linear Programs; The Minimax Theorem 286(5)
13-3. Constructive Solution to a Matrix Game (Alternative Proof of Minimax Theorem) 291(6)
13-4. Problems 297(2)
CHAPTER 14 THE CLASSICAL TRANSPORTATION PROBLEM 299(17)
14-1. Historical Summary 299(1)
14-2. Elementary Transportation Theory 300(8)
14-3. Computational Algorithm for the Transportation Problem 308(6)
14-4. Problems 314(2)
CHAPTER 15 OPTIMAL ASSIGNMENT AND OTHER DISTRIBUTION PROBLEMS 316(19)
15-1. The Optimal Assignment Problem 316(6)
15-2. Allocation with Surplus and Deficit 322(8)
15-3. Fixed Values and Inadmissible Squares 330(2)
15-4. Problems 332(3)
CHAPTER 16 THE TRANSSHIPMENT PROBLEM 335(17)
16-1. Equivalent Formulations of the Model 335(7)
16-2. The Equivalence of Transportation and Transshipment Problems 342(4)
16-3. Solving a Transshipment Problem by the Simplex Method 346(5)
16-4. Problems 351(1)
CHAPTER 17 NETWORKS AND THE TRANSSHIPMENT PROBLEM 352(16)
17-1. Graphs and Trees 352(5)
17-2. Interpreting the Simplex Method on the Network 357(4)
17-3. The Shortest Route Problem 361(5)
17-4. Problems 366(2)
CHAPTER 18 VARIABLES WITH UPPER BOUNDS 368(17)
18-1. The General Case 368(9)
18-2. The Bounded Variable Transportation Problem and Generalizations 377(6)
18-3. Problems 383(2)
CHAPTER 19 MAXIMAL FLOWS IN NETWORKS 385(19)
19-1. Ford-Fulkerson Theory 385(13)
19-2. The Tree Method for Solving Maximal Flow Problems 398(5)
19-3. Problems 403(1)
CHAPTER 20 THE PRIMAL-DUAL METHOD FOR TRANSPORTATION PROBLEMS 404(9)
20-1. Introduction 404(1)
20-2. The Ford-Fulkerson Algorithm 405(6)
20-3. Problems 411(2)
CHAPTER 21 THE WEIGHTED DISTRIBUTION PROBLEM 413(20)
21-1. The Near-Triangularity of the Basis 413(7)
21-2. Linear Graph Structure of the Basis 420(4)
21-3. A Subclass with Triangular Optimium Bases 424(7)
21-4. Problems 431(2)
CHAPTER 22 PROGRAMS WITH VARIABLE COEFFICIENTS 433(15)
22-1. Wolfe's Generalized Program 433(7)
22-2. Notes on Special Cases 440(6)
22-3. Problems 446(2)
CHAPTER 23 A DECOMPOSITION PRINCIPLE FOR LINEAR PROGRAMS 448(23)
23-1. The General Principle 448(7)
23-2. Decomposition Principle, Animated 455(7)
23-3. Central Planning without Complete Information at the Center 462(4)
23-4. Decomposing Multi-stage Programs 466(3)
23-5. Problems 469(2)
CHAPTER 24 CONVEX PROGRAMMING 471(28)
24-1. General Theory 471(8)
24-2. Homogeneous Objectives and the Chemical Equilibrium Problem 479(3)
24-3. Separable Convex Objectives 482(8)
24-4. Quadratic Programming 490(7)
24-5. Problems 497(2)
CHAPTER 25 UNCERTAINTY 499(15)
25-1. Scheduling To Meet Variable Cost 499(4)
25-2. Scheduling To Meet an Uncertain Demand 503(4)
25-3. On Multi-stage Problems 507(4)
25-4. Problems 511(3)
CHAPTER 26 DISCRETE VARIABLE EXTREMUM PROBLEMS 514(37)
26-1. Survey of Methods 514(7)
26-2. Gomory's Method of Integer Forms 521(14)
26-3. On the Significance of Solving Linear Programming Problems with Some Integer Variables 535(16)
CHAPTER 27 STIGLER'S NUTRITION MODEL: AN EXAMPLE OF FORMULATION AND SOLUTION 551(17)
27-1. Problems in Formulating a Model 551(6)
27-2. Numerical Solution of the Nutrition Problem 557(9)
27-3. Problems 566(2)
CHAPTER 28 THE ALLOCATION OF AIRCRAFT TO ROUTES UNDER UNCERTAIN DEMAND 568(24)
28-1. Statement and Formulation 568(12)
28-2. Numerical Solution of the Routing Problem 580(12)
BIBLIOGRAPHY References to the Bibliography are given in text and at the end of each chapter (see in particular the end of Chapter 2). 592(25)
INDEX 617
Linear programming and extensions /
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
