Dantzig G., Thapa M. Linear programming. Vol.1. Introduction
Подождите немного. Документ загружается.
432 INDEX
Sherali, H., 98, 304
Sherman, D., 24
Sherman-Morrison-Woodbury, 330
Shor, N., 123
Shortest path, 303
Shortest route, 277, 303
Shulman, A., 24
Sign convention on prices, 183
Similar Matrices, 333
Simon, H., xxvi, xxviii
Simple warehouse problem, see
Formulation
Simplex ALgorithm, 187
Simplex Algorithm, 23, see Dantzig
Simplex Algorithm, 71–72
basic variables, 64–68
bounded variables, 86
canonical form, 64–68
finite termination, 76
graphical illustration, 64
improving a nonoptimal basic
feasible solution, 68–71
introducing nonbasic into basis,
70
key components, 70
optimality test, 70, 73
bounded variables, 84
theory, 73–76
Simplex Method, xxvi, xxviii, xxx,
xxxii, 23, 63, 76–83, 182,
198, 290
algorithm, 78–81
basis, 67
bounded variables, 83–89
economic interpretation, 174
example, 78
largest coefficient rule, 97
Phase I, 76, 81–83
Phase I/Phase II, 78
Phase II, 76
price mechanism, 172–183
examples, 175
manager of a machine tool
plant, 175–181
the ambitious industrialist,
181–183
probabilistic analysis, 98
the method, 77
versus interior-point methods,
114
worst-case example, 97
worst-case performance, 63
Simplex multipliers, 90
transportation problem, 222
Singh, S., 24
Singular matrix, 329
Sinha, G., 24
Sleator, D., 303
Smale, S., 98
Smith, K., 24
Soares, G., 26, 28
Software, 23
early stages, xxix
Sokolowsky, D., 122
Solution set, 341
empty, 343, 348
nonempty, 348
same, 343
Solutions, 349
Solvable, 43
Spanning tree, 257
Sparse matrices, 91
Spectral radius, 334
Spellman, R., 24
Sponk, J., 162
Stacy, C., 24
Standard form, 7, 63
dual, 7
with bounds, 64
Stanford, xxxii
Starfield, A., 24
Steepest descent direction, 115
Steiger, D., 24, 301
Steuer, R., 162
Stewart, G., 337
Stiemke, E., 138
Stigler, G., 23
Stochastic programming, xxix, xxxii,
23, 172
433
Stock, R., 24
Strang, G., 337
Strassen, V., 337
Strong Duality Theorem, 135
first known proof, 138
first rigorous proof, 138
originator, 138
Strongly connected, 257
Structural variables, see Artificial
variables, slack variables,
surplus variables
Substitution effect, 198
Sylvanus, M., 24
Symmetric matrix, 329
tableau, 7
Tableau form, 7
Tarjan, R., 245, 303
Tendick, P., 24
Thapa, M., 24
Theorems of the Alternatives, 138
Thompson, W., 24
Threadgill, J., 24
Tilanus, C., 162
Tomlin, J., 123
Tompkins, C., 122
Toth, P., 245
Traaen, T., 24
Trace, 335
Tracing-back node, 274
Trafton, L., 24
Transportation and assignment
problem, 205–252
Transportation problem, 4–6
basis triangularity, 210, 211
better basic solution, 224
bounded variables, 240
capacitated, 240
example, 241
integral property, 242, 244
optimality, 240
classical, 205–212
feasibility, 208
mathematical statement, 206
properties, 206
rank, 209
computer code, 245
continuous version, 244
conversion to assignment, 232
cost preprocessing, 219
dual, 224
excess and shortage, 233–237
basis triangularity, 236
conversion, 236
mathematical statement, 234
multipliers, 238
properties, 236
rank, 236
reduced cost, 238
fundamental theorem, 211
illustration, 225
inadmissible squares, 239
initial solution, 214
integer property, 6
integral property, 212
Least Remaining Cost Rule, 217
Northwest Corner Rule, 214, 216
optimality, 222, 223
pre-fixed values, 239
prototype, 207
reduced costs, 223
Russel’s approximation method,
218
Simplex Algorithm, 222
simplex multipliers, 222
standard transportation array,
212
theta-adjustments, 222
Triangularity Rule, 214
Vogel’s approximation method,
217
Transshipment, 254
Trapezoidal, 328
Traveling salesman problem, xxix
Tree, 257
rooted, 291
spanning, 257
Triangular matrix, 210, 328
Triangularity Rule, 214
Tucker diagram, 130
434 INDEX
Tucker, A., xxvii, xxviii, 98, 138,
162, 245
Turner, A., 24
Twice continuously differentiable,
158
Two-equation problem, 37–43
algebraic check of optimality, 41
dual linear program, 41–43
graphical solution, 38–41
Two-variable problem, 35–37, 64
Unbounded class of solutions, 71
Undirected network, 254
Unique minimum, 71
Unit lower triangular, 328
Unrestricted variables, 84, 146–147
Unsolvable, 43, 344
Upper triangular matrix, 327
Vacuous equation, 344, 355
Vajda, S., 167
van Kooten, G., 24
van Loan, C., 337
Van Mieghen, J., 164
Vanderbei & Lagarias, 123
Vanderbei, R., 123
Vector, 315
1-norm, 322
2-norm, 322
∞-norm, 322
addition
associativity, 319
commutativity, 319
dot product, 318
inner product, 318
linear combination, 319
linear independence, 320
norm, 322
norm with a positive definite
matrix, 336
orthogonal, 321
orthonormal, 321
outer product, 318
scalar product, 318
commutativity, 320
Vector space, 324
basis, 325
closed, 325
dimension, 325
null space, 325
span, 325
subspace, 325
complementary, 325
orthogonal complement, 325
Veiga, G., 123
Vertinsky, I., 24
Ville, J., 138
Vogel’s approximation method, 217,
230
Vogel, W., 244
von Neumann & Morgenstern, 162
von Neumann Duality Theorem, see
Strong Duality Theorem
von Neumann symmetric form, 129,
175
von Neumann, J., xxii, xxiii,
xxv–xxviii, 42, 122, 138,
162, 245
Wald, A., xxvi
Walter, J., 24
Wang, Z., 245
Waren, A., 24
Watanabe, K., 24
Weak Duality Theorem, 134
Weakly connected, 257
Wets, R., xxix
Whiting, P., 303
Wiegman, N., 122
Wiliams, H., 24
Wilkinson, J., 337
Willard, D., 303
Wirth, R., 24, 301
Wolfe, P., xxviii, xxix
Wood, M., xxiii, xxviii
Wright, M., 123
Ye, Y., 123
Young, W., 24, 301
Zadeh, N., 304
435
Zaki, H., 245
Zero Symposium, xxviii
Ziemba, W., 24
Zoutendijk, G., xxviii