Advances in Computational Science and Engineering

Springer - Advances in Computational Science and Engineering (12-2009) (ATTiCA)......Page 1
Linear Optimization......Page 3
1.1 The Diet Problem......Page 16
1.2 The Matching Problem......Page 19
1.3 Un Problema de la Pr´actica......Page 22
1.4 Standard Form and the Dual......Page 23
1.5 Exercises......Page 27
2.1 Geometric Lens......Page 43
2.2 Algebraic Lens......Page 46
2.3 Chinese for a Little Practice......Page 51
2.4 Infeasible Basis......Page 52
2.5 Shortcut Method......Page 55
2.6 Infeasibility......Page 59
2.7 Unboundedness......Page 61
2.8 Cycling......Page 62
2.9 The Fundamental Theorem......Page 63
2.10 Exercises......Page 64
3.1 Extreme Points......Page 72
3.2 Convexity......Page 74
3.3 小试牛刀......Page 77
3.4 Carath´eodory’s Theorem......Page 78
3.5 Exercises......Page 80
4.1 Primal-Dual Relationship......Page 86
4.2 Complementary Slackness Conditions......Page 90
4.3 Jizoezi, Jizoezi, Jizoezi......Page 92
4.4 Finding Optimal Certificates......Page 93
4.5 Exercises......Page 95
5.1 Format and Dictionaries......Page 101
5.2 Simplex Phases and Advantages......Page 103
5.3 Hebrew for Some Practice......Page 109
5.4 Basic Coefficients......Page 110
5.5 Exercises......Page 112
6.1 Nonstandard Duals......Page 118
6.2 General Simplex and Phase 0......Page 121
6.4 General Duality and Slackness......Page 124
6.5 Exercises......Page 126
7.1 Infeasible Certificates......Page 130
7.2 Inconsistency......Page 133
7.4 Unsolvable Subsystems......Page 135
8.1 Helly’s Theorem......Page 140
8.2 Permutation Matrices......Page 142
8.4 Cones......Page 145
8.5 Exercises......Page 148
9.1 Matrix Games......Page 155
9.2 Minimax Theorem......Page 157
9.3 Bitte Praxis......Page 160
9.4 Saddles......Page 161
9.5 Exercises......Page 165
10.1 Shipping......Page 173
10.2 Trees......Page 177
10.3 Nilai!......Page 182
10.4 Integrality......Page 183
10.5 Exercises......Page 184
11.1 Matchings......Page 192
11.2 Covers......Page 194
11.3 もっと練習しましょう......Page 197
11.4 Systems of Distinct Representatives......Page 198
12.1 Shadow Prices......Page 204
12.2 Reduced Costs......Page 209
12.3 Gyakoroljon egy Kicsit......Page 211
12.4 Dual Simplex......Page 212
12.5 Exercises......Page 215
13.1 Cutting Planes......Page 218
13.2 Branch-and-Bound......Page 224
13.3 Russian for Final Practice......Page 230
13.4 Integer Certificates......Page 231
13.5 Exercises......Page 232
A Linear Algebra Review......Page 239
B Equivalence of Auxiliaryand Shortcut Methods......Page 243
C.1 P versus NP......Page 249
C.2 Examples......Page 251
C.3 LO Complexity......Page 252
D.1 WebSim......Page 254
D.2 Algorithms......Page 255
D.3 MAPLE......Page 257
Index......Page 264