发帖
雷达卡
1 Introduction ................................................................. 1
1.1 Chapter Objectives ................................................... 1
1.2 Linear Programming ................................................. 1
1.3 Why Another Book on Linear Programming? Why Linear
Programming Using MATLAB?..................................... 5
1.4 Our Approach: Organization of the Book ........................... 7
1.5 Chapter Review....................................................... 10
References.................................................................... 10
2 Linear Programming Algorithms......................................... 13
2.1 Chapter Objectives ................................................... 13
2.2 Introduction ........................................................... 13
2.3 Linear Programming Problem ....................................... 15
Constraints .................................................. 25
2.4 Modeling Linear Programming Problems........................... 29
2.5 Geometry of Linear Programming Problems ....................... 33
2.6 Duality ................................................................ 53
2.7 Linear Programming Algorithms .................................... 62
2.8 Chapter Review....................................................... 71
References.................................................................... 71
3 Linear Programming Benchmark and Random Problems ............ 73
3.1 Chapter Objectives ................................................... 73
3.2 Introduction ........................................................... 73
3.3 Mathematical Programming System Format ........................ 74
3.4 Convert MAT2MPS and MPS2MAT Format ....................... 81
3.5 Generate Random Sparse and Dense Linear Programming
Problems .............................................................. 100
3.6 Linear Programming Benchmark Problems......................... 117
3.7 Chapter Review....................................................... 133
References.................................................................... 133
4 Presolve Methods ........................................................... 135
4.1 Chapter Objectives ................................................... 135
4.2 Introduction ........................................................... 136
4.3 Background ........................................................... 137
4.4 Eliminate Zero Rows ................................................. 138
4.4.1 Mathematical Formulation ................................. 138
4.4.2 Numerical Example ........................................ 140
4.4.3 Implementation in MATLAB .............................. 142
4.5 Eliminate Zero Columns ............................................. 144
4.6 Eliminate Singleton Equality Constraints ........................... 148
4.7 Eliminate kton Equality Constraints................................. 154
4.8 Eliminate Singleton Inequality Constraints ......................... 166
| 4.9 Eliminate Dual Singleton Inequality Constraints ................... 173 |
| 4.10 Eliminate Implied Free Singleton Columns......................... 179 |
| 4.11 Eliminate Redundant Columns ...................................... 185 |
| 4.12 Eliminate Implied Bounds on Rows ................................. 189 |
| 4.13 Eliminate Redundant Rows .......................................... 193 |
| 4.14 Make Coefficient Matrix Structurally Full Rank ................... 201 |
| 4.15 MATLAB Code for the Presolve Analysis .......................... 204 |
| 4.16 Postsolve .............................................................. 207 |
| 4.17 Computational Study ................................................. 208 |
| 4.18 Chapter Review....................................................... 216 |
| References.................................................................... 217 |
| 5 Scaling Techniques ......................................................... 219 |
| 5.1 Chapter Objectives ................................................... 219 |
| 5.2 Introduction ........................................................... 220 |
| 5.3 Mathematical Preliminaries.......................................... 221 |
| 5.4 Arithmetic Mean ..................................................... 222 |
| 5.5 de Buchet ............................................................. 227 |
| 5.6 Entropy ............................................................... 239 |
| 5.6.1 Mathematical Formulation ................................. 239 |
| 5.6.2 Numerical Example ........................................ 239 |
| 5.6.3 Implementation in MATLAB .............................. 241 |
| 5.7 Equilibration .......................................................... 243 |
| 5.7.1 Mathematical Formulation ................................. 243 |
| 5.7.2 Numerical Example ........................................ 243 |
| 5.7.3 Implementation in MATLAB .............................. 245 |
| 5.8 Geometric Mean ...................................................... 247 |
| 5.8.1 Mathematical Formulation ................................. 247 |
| 5.8.2 Numerical Example ........................................ 247 |
| 5.8.3 Implementation in MATLAB .............................. 249 |
| 5.9 IBM MPSX ........................................................... 251 |
| 5.10 L p-Norm .............................................................. 257 |
| 5.11 Computational Study ................................................. 268 |
| 5.12 Chapter Review....................................................... 274 |
| References.................................................................... 275 |
| 6 Pivoting Rules ............................................................... 277 |
References.................................................................... 301
7 Basis Inverse and Update Methods ....................................... 303
References.................................................................... 327
8 Revised Primal Simplex Algorithm ....................................... 329
9 Revised Dual Simplex Algorithm ......................................... 383
| 10 Exterior Point Simplex Algorithm ........................................ 437 |
| 11 Interior Point Methods..................................................... 491 |
| 12 Sensitivity Analysis ......................................................... 541 |
| A MATLAB’s Optimization Toolbox Algorithms.......................... 565 |
| A.1 Chapter Objectives ................................................... 565 |
| A.2 Introduction........................................................... 565 |
A.3 MATLAB’s Optimization Toolbox Linear
Programming Algorithms ............................................ 567
A.3.1 Interior Point Method....................................... 567
A.3.2 Primal Simplex Algorithm ................................. 569
A.3.3 Dual Simplex Algorithm ................................... 570
A.3.4 Active-Set Algorithm ....................................... 571
A.4 MATLAB’s Linear Programming Solver ........................... 572
A.5 MATLAB’s Optimization App ...................................... 575
A.6 Solving Linear Programming Problems with MATLAB’s
Optimization Toolbox ................................................ 577
A.6.1 Solving Linear Programming Problems by
Converting Them to Solver’s Form ........................ 578
A.6.2 Solving Linear Programming Problems Using
MATLAB’s Optimization App ............................. 585
A.6.3 Solving Linear Programming Problems
Using Custom Code ........................................ 591
A.7 MATLAB Code to Solve LPs Using the linprog Solver ........ 596
A.8 Computational Study ................................................. 599
A.9 Chapter Review....................................................... 600
References.................................................................... 601
State-of-the-Art Linear Programming Solvers: CLP and CPLEX ... 603
B.1 Chapter Objectives ................................................... 603
B.2 Introduction........................................................... 603
B.3 CLP ................................................................... 604
B.4 CPLEX................................................................ 609
B.5 Computational Study ................................................. 613
B.6 Chapter Review....................................................... 624
References.................................................................... 629
ist of Codes ...................................................................... 631
ndex ............................................................................... 635
京公网安备 11010802022788号
