Dantzig G., Thapa M. Linear programming. Vol.1. Introduction
Подождите немного. Документ загружается.
422 INDEX
Barnes, E., 123
Basic activities, 67, 353
Basic columns, 67, 353
Basic solution, 66, 353
bounded variables, 83
degenerate, 67
Basic variables, 64
Basis, 67, 325, 353
Basis triangularity, 210
Bazaraa, M., 98, 304
Beale, E., xxix, 76, 103
Bellman, R., 303
Belz, M., 24
Ben-Dov, Y., 24
Benders, J., xxix
Bertsekas, D., 245, 301
Best fit, 154
Big-M method, 98, 107, 108, 121,
125, 239, 249
Birge, J., xxix
Birkhoff, G., 245
Bj
Υ
F orck,
˚
A, 337
Bland’s rule, 72
Blattner, W., 199
Bleloch, A., 24
Blending problem, 3–4
Blumenthal, L., 340
Boes, D., 162
Borel, E., 162
Borgwardt, K., 98
Bounded variables, 83
basic solution, 83
degenerate solution, 83
nonbasic solution, 83
Bounds, 21–22
nonnegativity, 21
upper and lower, 22
Bradley, G., 304
Bradley, S., 24, 98, 162, 199
Breadth-first unblocked search, 272,
274
Brickman, L., 98
Brown, G., 24, 304
Brown, S., 24
Canonical form, 64, 66, 345, 346, 349
equivalent, 352
feasible, 68
reduction to, 349
Canonical system, 352
identical, 352
uniqueness, 352
Capacitated transportation problem,
see Transportation problem
Capacity, 258
Cari˜no, D., 24
Carpento, G., 245
Cauchy-Schwartz, 322
Center
finding, 153
Center of gravity, 39
Chain, 255, 257
closed, 255
Chambers, J., 162
Chandrasekaran, B., 24
Characteristic
equation, 333
polynomial, 333
Charnes, A., xxviii, xxix, 24
Chebyshev Norm, 337
Cherkassky, B., 303
Choudhry, A., 24
Chv´atal, V., 98, 199, 245, 303, 304
Circuit, 255
Classical transportation problem, see
Transportation problem
Clements, D., 24
Closed chain, 255
Closed path, 255
Cofactor, 331
Column approach, see Formulation
Column elementary matrix, 329
Column space, 342
Combinatorial optimization, xxix
Commercial applications, xxviii, 23
Commutativity, 319
Complementary pivot theory, xxix,
xxx, 23
Complementary slackness, 135, 175
Complete graph, 257
423
Complex conjugate, 334
Computational complexity, xxx, 23
Concave functions, 157
Connected network, 257
strongly, 257
weakly, 257
Connected nodes, 257
Conservation of flows, 259
Consistent, 43
Converting equalities to inequalities,
52
Convex functions, 157
Convex programming, 123
Cooper, W., xxviii, xxix, 24
Cornfield, J., 23
Cost preprocessing, 219
Cost ranging, 188–190
Cottle, R., xxviii, xxx
Cowles Foundation, xxvi
Cox, L., 24
CPM, 253, 304
Crainic, T., 24
Cramer’s rule, 332
Crandall, H., 24
Cravener, T., 24
Cunningham, W., 304
Curve fitting, 154
least-squares, 157
minimizing the 1-norm, 155
minimizing the 2-norm, 157
minimizing the ∞-norm, 156
multiple linear regression, 162
one-sided fit, 156
Cut, 275, 287
in a network, see Maximal flow
separate, 275
value, 275
Cut value, 275
Cycle in a network, 255
Cycling, 72, 76, 97
D’Alfonso, T., 24
Dahlquist, G., 337
Dantzig & Hirsch, 162
Dantzig Simplex Algorithm, see
Simplex Algorithm
Dantzig Simplex Method, see
Simplex Method
Dantzig, G. B., xxi, xxviii–xxxi, 1,
23–25, 97, 98, 122, 123, 138,
162, 199, 244, 249, 301, 303,
306, 312, 357
Dantzig, T., xxxi, 138
Davis & McKeown, 168
Davis, K., 162
Decomposition, xxix, xxxii
Decomposition of flow, 262
DeGans, O., 162
Degeneracy, xxviii, 57, 67, 72
Degenerate solution, 57, 67
assignment problem, 230
bounded variables, 83
transportation problem, 213
Degenerate solutions, 353
Degree
in-degree, 255
of a node, 255
out-degree, 255
Denardo, E., 303
Dependent, 344
Detached coefficient form, 7, 67
Determinant, 331–332
Diagonal matrix, 326
Dial, R., 303
Digraph, 254
Dijkstra’s algorithm
number of operations, 282
shortest route, 281
validity, 282
Dijkstra, E., 303
Dikin’s method, 114, 117–121
Dikin, I., 114, 122, 123
Dinic, E., 303
Directed arcs, 254
Directed network, 254
Distributivity, 320
Dodge, J., 24
Dodson, D., 337
Doig, A., 24
424 INDEX
Dongarra, J., 337
Dorfman, R., xxvi, xxviii, xxxi
Dot product, 318
Doubly stochastic matrix, 245
Dual
of mixed systems, 130
of the standard form, 132
standard form, 7
transportation problem, 224
two-equation linear program, 41
Dual and primal problems, 129–133
Dual-Simplex Method, 199
Duality, xxvii, 129
Duality gap, 135
Duality Theorem
illustration, 135
Strong, 135
Weak, 134
Duality Theorems, 134–135
DuCroz, J., 337
Duffin, R., 54
Dutta, G., 24
Eaves, B., xxx
Ecker, J., 24
Economic interpretation of the
Simplex Method, 174
Edmonds, J., 303
Edmonds-Karp max-flow theorem,
274
Edmondson, J., xxviii
Egerv´ary, E., 244, 303
Eigensystem, 333
Eigenvalue, 333, 340
computation, 337
Eigenvector, 333
computation, 337
Eisemann, K., 24
Elementary matrix, 329
column, 329
row, 329
Elementary operation, 346
Type I, 347
Type II, 347
Elias, P., 266, 303
Elimination procedure, 345
Elmaghraby, S., 304
Equivalent formulations, 145
Equivalent systems, 43, 346, 356
Error variables, see Artificial
variables
Euclidean norm, 322
Expert system, xxiv
Fabian, T., 24
Fanning-out procedure, 272
Farkas’s Lemma, xxvii, 138
Farkas, J., 138
Feasible, 43
Feinstein, A., 266, 303
Feinstein, C., 24
Feller, W., 162
Ferguson, A., 24
Fiacco, A., xxviii, 122
Finite termination of the Simplex
Algorithm, 76
Fisher, W., 24
Fixed charge, 162, 165
Fixed-point, xxx
Flood, M., xxix
Flow
augmentation, 261
capacity, 258
decomposition, 261, 262
value, 264
vector, 258
FME process, see Fourier-Motzkin
Elimination
Ford & Fulkerson, xxix
Ford, L., 266, 301, 303
Ford-Fulkerson
augmenting path algorithm, 266
method, 245
Formulation, 8–12
column/recipe/activity, 9–11
examples, 12–21
items, 9
on-the-job training, 18–21
row/material balance, 11–12
425
simple warehouse problem,
16–18
Formulation examples, 2–7
blending problem, 3–4
homemaker’s problem, 3
on-the-job training, 2–3
product mix problem, 2
simple linear programs, 2
transportation problem, 4–5
Fourier, J., xxii, 53
Fourier-Motzkin Elimination, 43–51,
53
algorithm, 46
example, 44
reduced system, 48
theory, 47–51
infeasibility multipliers, 50–51
why it works, 47–50
Fox, B., 303
Fredman, M., 303
Free variables, see Unrestricted
variables
Freedman, B., 123
Frisch, K., 122
Frisch, R., xxviii, 122
Fritz-John conditions, xxviii
Frobenius norm, 324
Fulkerson, D., xxix, 24, 266, 301, 303
Gabow, H., 245, 303
Gainen, L., 24
Gale, D., xxvii, xxviii, 138
Galil, Z., 303
Gallo, G., 303
Galois, 337
Game theory, xxiii, 162, 166
Garvin, W., 24
Gass, S., 24, 98, 199
Gavurin, M., 244
Geisler, M., xxviii
Gentle, J., 162
Georgescu-Roegen, xxviii
Gilbert, R., 24
Gill, P., 123, 337
Glover, F., 245
Glynn, P., xxix
Goal programming, 150–152
applications, 162
numerical difficulties, 151
priority, 151
composite objective, 152
sequential solution, 151
weighted, 150
Goldberg, A., 303
Goldman, A., 138
Goldstein, L., 24
Golub, G., 337
Gomory, R., xxix
Gordan, P., 138
Grandzol, J., 24
Granfors, D., 24
Graph, 254
complete, 257
connected, 257
Graph theory, xxix
Graphical solution
product mix, 37
two-equation problem, 38
Graves, G., 304
Graybill, F., 162
Greedy algorithm, 283
Gustavson, F., 337
Hadley, G., 199
Hahn, G., 24
Hammarling, S., 337
Hanson, R., 337
Harrison, T., 24
Hax, A., 24, 98, 162, 199
Hayre, L., 24
Helgason, R., 304
Henderson, A., 24
Hermitian matrix, 334
Hessian matrix, 158
Hillier, F., 24, 98, 162, 304
Hillier, J., 303
Hitchcock transportation problem,
225
Hitchcock, D., xxii, xxiii
Hitchcock, F., 244
426 INDEX
Hitchcock-Koopmans transportation
problem, 244, 254
Hoffman, A., xxvii, xxix, 76, 122
Hogan, W., 30
Homemaker’s problem, 3
Homogeneous system, 138, 356
Hotelling, H., xxvii
Householder, A., 337
How systems are solved, 345
Howson, xxx
Hungarian Method, 245
Hurwicz, H., xxviii
Hurwicz, L., xxvi
Hyperplane, 153
Identity matrix, 326
Ignizio, J., 162
Importance sampling, xxix, xxxii
Inconsistencies, 77
Inconsistent
equation, 344, 355
solution set, 43
system, 344
Independent, 344
Infanger, G., xxix, 24
Infeasibility
form, 80
multipliers, 50
Infeasibility Theorem, xxxiv, 52–53,
138
Infeasible, 43
equation, 52
inequality, 46
linear program, 70
Inner product, 318
Integer programming, xxix, 23, 24
branch and bound, xxix
cutting planes, xxix
Interior-point methods, xxviii, 113
affine, 113
basic concepts, 115
centering, 117
computational results, 123
Dikin’s method, 114
initial solution, 121
maintaining feasibility, 116
path-following, 113
primal affine, 113
primal-dual methods, 123
projected Newton barrier
method, 123
projective, 113
staying in the interior, 117
steepest descent direction, 116
stopping rule, 117
versus Simplex Method, 114
Inverse, see Matrix
Items, see Formulation
Jack, C., 24
Jackson, J., 24
Jacobs, W., 312
Jarvis, J., 98, 304
John, J., 24
Johnson, D., 303
Johnson, L., 244
Johnson, S., xxix
Judin, D., 123
Juncosa, M., 24
Kai, S., 24
Kalaba, R., 24
Kantorivich, K., xxii
Kantorovich, L., xxii, 25, 244
Karush, Kuhn-Tucker Conditions,
xxviii
Karmarkar’s method, 113
Karmarkar, N., xxx, 113, 123
Karney, D., 245
Karp, A., 337
Karp, R., 303
Katz, P., 24
Kemeny, 25
Kennedy, W., 162
Kennington, J., 245, 304
Kent, T., 24
Khachian’s method, 113
Khachian, I., 122
Khachian, L., xxx, 113, 122
Khan, M., 306
427
Kincaid, D., 337
Kirchoff’s law, 259
Klee & Minty example, 97
Klee, V., xxx, 97
Klincewicz, J., 304
Klingman, D., 24, 245, 301
Klingman, et al., 301
Koopmans, T., xxii, xxvi–xxviii,
xxxi, 244
Krogh, F., 337
Kruskal, J., 303
Kuehner, 24
Kuhn, H., xxvii–xxx, 54, 76, 102,
138, 245, 303
Kumar, M., 303
Label, 281
permanent, 281
temporary, 281
Laderman, J., 23
Ladino, G., 24
Lagarias, J., 123
Lagrange multipliers, xxvi, 138
Lall, H., 304
Land, A., 24
Large-scale methods, xxix, 23
Lasdon, L., 24
Lawler, E., 301
Lawson, C., 337
Least-squares, see Curve fitting
Lebesgue integrals, xxvi
Lee, S., 162
Left inverse, 329
Lemke, C., xxx
Lenstra, J., 23, 162
Leontief
input/output model, xxiii
substitution model, 110
Leontief, W., xxii, xxiii
Levin, A., 123
Lewis, D., 306
Lewis, J., 337
Lewis, R., 24
Lieberman, G., 24, 98, 162, 304
Linear algebra, 315–340
implementation, 337
numerical, 337
Linear combination, 319, 344
multipliers, 344
weights, 344
Linear equations, 341–359
compatible, 343
consistent, 343
incompatible, 343
inconsistent, 343
solvable, 343
unsolvable, 343
Linear independence, 320
Linear program, 1
infeasible, 70
multiple minima, 71
unbounded class of solutions, 71
unique minimum, 71
Linear programming problem, 1–33
defined, 8
history, 23
mathematical statement, 7
Litty, C., 24
Lower trapezoidal, 328
Lower triangular matrix, 328
LP
large, 2
medium, 2
small, 2
LU factorization, 341, 345, 357
Luenberger, D., 54
Lustig, I., 123
Magnanti, M, 162
Magnanti, M., 24, 98, 199
Magnanti, T., 245, 301, 306, 308
Maheshwari, S., 303
Makuch, W., 24
Malhotra, V., 303
Manley, B., 24
Manne, A., 24
Mannos, M., 122
Marcus, M., 245
Marginal column, 212
Marginal row, 212
428 INDEX
Marginal value, 173
Marsten, R., 123
Martello, S., 245
Mass´e, P., 24
Mathematical programming, xxviii, 1
Matrix, 316
1-norm, 323
2-norm, 323
∞-norm, 323
addition
associativity, 319
commutativity, 319
cofactor, 331
column space, 342
determinant, 331–332
diagonal, 317
diagonal matrix, 326
eigenvalue, 333
eigenvector, 333
elementary, 329
column, 329
inverse, 330
row, 329
Frobenius norm, 324
identity matrix, 326
inverse, 329
left, 329
right, 329
special, 330
lower trapezoidal, 328
lower triangular, 210, 211, 328
minor, 331
multiplication, 319
associativity, 320
distributivity, 320
Strassen, 337
negative definite, 336
negative semidefinite, 336
nonsingular, 329
norm, 323
norm with a positive definite
matrix, 336
off-diagonal, 317
orthogonal, 328
orthonormal, 328
orthornormal inverse, 330
permutation matrix, 327
inverse, 330
positive semidefinite, 336
positive-definite, 336
product with a vector, 318
projection, 116
range space, 342
rank, 326
column rank, 326
full, 326
row rank, 326
rank one, 329
right triangular, 327
similar, 333
singular, 329
sub-diagonal, 317
super-diagonal, 317
symmetric, 329
transpose, 316
triangular, 210, 328
inverse, 330
unit lower triangular, 328
upper triangular, 210, 211, 327
vector induced norm, 323
with special structure, 326
Maximal flow
associated path, 261
Augmenting path algorithm, 267
augmenting path algorithm,
262–274
cuts in a network, 275–277
flow augmentation, 261
flow decomposition, 261
Maximal flow algorithm, 267
Maynard, H., 24
McCormick, G., xxviii
McKeown, P., 162
McMormick, G., 122
Megiddo, N., 123
Mehlhorn, K., 303
Meketon, M., 123
Mellon, B., xxviii, 24
Min-cut = max-flow, 276
MInimal spanning tree, 282
429
Minimal spanning tree
illustration, 283
Minimizing the maximum of linear
functions, 152
Minimizing the sum of infeasibilities,
186, 187, 199, 304
Minimum cost-flow problem, 286
assignment, 288
feasible flow, 287
maximal flow, 288
shortest route, 288
transportation, 288
Minty, G., xxx, 97
Mitter, N., 24
Mixed integer programming, 24
Monma, C., 123
Mood, A., 162
Moore, E., 303
Morgenstern, O., xxvii
Morin, G., 24
Morris, W., 24
Morton, A., 123
Motzkin, T., xxiii, xxvii, xxviii, xxxi,
53, 138
Muir, T., 337
Multiple linear regression, see Curve
fitting
Multiple minima, 71
Mulvey, J., 304
Murray, W., 123, 337
Murty, K., 98, 162, 199, 245
Myers, D., 24
Napier, A., 245
Negative cycle, 294
Negative definite, 158, 336
Negative semidefinite, 158, 336
Nemirovskii, A., 123
Nering, E., 98, 245
Network
connected, 257
directed, 254
undirected, 254
Network flow theory, xxix, 23
arc capacities, 258–262
connected networks and trees,
257
flows, 258–262
node-arc incidence matrix, 255
nodes and arcs, 253
paths, chains, circuits, cycles,
255
terminology, 253–258
Network Simplex Method, 288
bases, trees, 290
bounds, 299
conversion to standard form,
300
problem statement, 299
cycling, 304
efficiency, 304
flow adjustment, 294
implementation, 303
incoming variable, 294
initial solution, 298
integral property, 290
optimality, 293
pathological example, 304
pricing, 293
reduced costs, 293
solving for basics, 291
updating prices, 296
Neyman, J., xxvi
Neyman-Pearson Lemma, xxvi
Nobel Prize, xxii, xxiii, xxvi, xxviii
Node, 254
destination, 254
intermediate, 254
origin, 254
sink, 254
source, 254
terminal, 254
transshipment, 254
Node-arc incidence matrix, 255, 259,
260
Nonlinear programming, xxviii, 23,
122
Nonnegativity, 64
Nonsingular matrix, 329
Norm, 321
430 INDEX
Chebyshev, 337
matrix, 323
vector, 322
Northwest Corner Rule, 216
Null space, 325
Obtaining a dual solution, 136
On-the-job training, 2, see
Formulation
One-sided fit, see Curve fitting
Optimization theory, 1
Orchard-Hays, W., xxix, xxxi, 98
Orden, A., xxviii, 23
Ordered pairs, 254
Orlin, J., 245, 301, 303, 306, 308
Orthogonal matrix, 328
Orthogonality, 321
Orthonormal matrix, 328
Outer product, 318
Pallottino, S., 303
Pan, V., 337
Pape, U., 303
Parallel processors, xxix
Parametric programming, 199
Parrish, S., 24
Path, 255
closed, 255
flow, 261
non-simple, 255
simple, 255
Paull, A., 24
Permutation matrix, 245, 327
PERT, 253, 304
Phase I, 76
theory, 81–83
Phase I/Phase II, see Simplex
Method
Phase II, 76
Phillips, N., 24, 301
Pica, V., 24
Piecewise continuous linear functions,
159
breakpoints, 159
separable, 160
Piecewise linear approximations,
157–161
Pivot
element, 349
operation, 350
irreversibility, 354
steps, 64
term, 66, 350
theory, 354
Pivot term, 66, 69, 70
Pivotal subsystem, 355
Pivoting, 349, 350
Planning under uncertainty, see
Stochastic programming
Polynomial time
algorithms, xxx, 23
Positive definite, 158
Positive semidefinite, 158, 336
Positive-definite, 336
Post-optimality analysis, see
Sensitivity analysis
Poussin, xxii
Price, 90, 172, 173
sign convention, 183
Price mechanism, 172–183
Pricing out, 91
Primal affine method, 117–121
Primal-dual interior methods, see
Interior-point methods
Primal/Dual feasible-infeasible cases,
133
Product mix problem, 2, 12
column approach, 12–15
row approach, 15–16
Projected gradient direction, 116
Projected Newton barrier method,
see Interior-point methods
Projection matrix, 116
Putnam exam, 337, 339
Qiu, Y., 24
QR Factorization, 157
Quadratic problem, 165
Quadratic programs, xxx
431
Radzik, T., 303
RAND, xxix, xxxi
Random Choice Rule, 72, 230
Range space, 342
Rank, see Matrix
full, 67
of a node, 255
Rank one matrix, 318, 329
Reduced costs, 68
transportation problem, 223
Reduced system, 351, 352, 355
Redundancies, 77
Redundancy and Inconsistency
Tracing Theorem, 355
Redundancy detection, 54
Redundant, 344, 355
Reid, R., 24
Reinfield, N., 244
Relative cost factors, 68
Renegar, J., 123
Resende, M., 123
Restricted variables, 145
Revised Simplex Method, 89–97
algorithm, 93
computational remarks, 96
example, 92
motivation, 89
Representation in Terms of the
Basis, 91
Rice, J., 337
Rigby, B., 24
Right inverse, 329
Right triangular matrix, 327
Right-hand side ranging, 190–192
Rinnooy Kan, A., 23
Rivett, P., 24
Rockafellar, R., xxviii
Rocket scientists, xxii
Root node, 291
Rooted spanning tree, 291
Roush, W., 24
Roy, J., 24
Roy, P., 24
Rub, L., 164
Russel’s approximation method, 218
Russel, E., 244
Sadrian, A., 24
Salveson, M., 24
Same solution set, 348
Samelson, H., 337
Samuelson, P., xxvi, xxviii
shadow price, 173
Saturated arc, 275
Saunders, M., 123, 337
Scalar, 315
Scalar product, 318, 334
Scalars, vectors, and matrices,
315–317
Scale-invariant, 109
Scarf, H., xxvi, xxx
Schlaifer, R., 24
Schreier, H., 24
Schrijver, A., 23
Schruben, L., 24
Sensitivity analysis, 171
coefficient matrix, 58, 192–197
basic column, 194
nonbasic column, 192
cost ranging, 58, 188–190
basic variable, 189
nonbasic variable, 188
new constraint, 186–188
new variable, 184–186
bounded variable LP, 185
standard form, 184
right-hand side, 58, 190–192
Separable nonlinear programming,
151
Separable piecewise continuous linear
functions, 160
Shadow price, 59, 111, 173
under degeneracy, 174
under nondegeneracy, 173
Shanno, D., 123
Shannon, C., 266, 303
Shapiro, J., 199
Shapiro, R., 162
Shapley, L., xxvii
Shefi, A., 54