Авторизация
Поиск по указателям
Bazaraa M.S., Jarvis J.J. — Linear Programming and Network Flows
Обсудите книгу на научном форуме Нашли опечатку?
Название: Linear Programming and Network FlowsАвторы: Bazaraa M.S., Jarvis J.J. Аннотация: The authoritative guide to modeling and solving complex problems with linear programming—extensively revised, expanded, and updated
Язык: Рубрика: Технология /Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Год издания: 1977Количество страниц: 565Добавлена в каталог: 17.04.2010Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Kuhn — Tucker conditions for inequality constraints 213 Kuhn — Tucker conditions, geometric interpretation of 214 Kuhn — Tucker conditions, proof of 216 Kuhn — Tucker conditions, relationship, to duality 243 Kuhn — Tucker conditions, relationship, to simplex method 212 Labeling algorithm, maximal flow 480 Labeling algorithm, network simplex 423 Labeling algorithm, out-of-kilter 461 Labeling algorithm, shortest path 490 Lagrangian dual problem 303 Lagrangian multipliers 213 337 Legitimate variable 141 Lexicographic validation of cycling prevention rule 170 Lexicographically nonnegative vector 171 Lexicographically positive vector 170 Line segment 58 linear combination 42 Linear dependence 42 Linear equations, basic solution 55 Linear equations, Gaussian reduction 57 Linear equations, general solution 57 Linear equations, number of solutions 56 Linear equations, redundant (dependent) 55 Linear independence 42 Linear inequalities 2 4 Linear programming problem, assumptions in 3 Linear programming problem, canonical form 5 6 Linear programming problem, examples of 7 Linear programming problem, generalized 351 Linear programming problem, geometry of 14 Linear programming problem, standard form 5 6 Linear transformation 504 Link (arc) 364 Lower bounds, on objective function 310 331 Lower bounds, on variables 201 420 509 Lower triangular matrix 46 Machine scheduling problem 29 31 Manipulation of linear program 4 Master, array 309 Master, problem 306 Matrix, adjoint 54 Matrix, definition 44 Matrix, determinant of 52 Matrix, elementary 195 Matrix, identity 46 Matrix, inverse 49 Matrix, nonsingular 49 Matrix, operations 45 47 Matrix, partitioned 46 Matrix, rank of 54 Matrix, singular 49 Matrix, skew-symmetric 46 Matrix, symmetric 46 Matrix, transpose 46 Matrix, triangular 46 Matrix, zero 46 Maximal flow problem, algorithm 477 480 Maximal flow problem, basic solutions 480 Maximal flow problem, cut-sets and dual of 475 476 Maximal flow problem, formulation 474 Maximal flow problem, multicommodity 493 520 Maximal flow-minimal cut theorem 478 Menu planning problem 26 Minimal cost flow problem, algorithm 413 423 Minimal cost flow problem, basis characterization 409 411 Minimal cost flow problem, formulation 405 Minimal cost flow problem, initial solution 419 Minimal cost flow problem, lower-upper bounds on arc flows 420 Minimal cost flow problem, simplex tableau 425 Minimal cost-maximal flow problem 517 518 Minimum ratio test 110 253 Multicommodity, basis characterization 502 505 Multicommodity, decomposition algorithm 496 Multicommodity, maximal flow problem 493 520 Multicommodity, minimal cost flow problem 494 Multicommodity, minimal disconnecting set 521 Multicommodity, transportation problem 348 Network flow problem 404 440 473 Network simplex algorithm, computing, basic solution 413 Network simplex algorithm, computing, dual variables 416 Network simplex algorithm, determination, of entering variable 415 Network simplex algorithm, determination, of exit variable 417 Network simplex algorithm, initial basic feasible solution 419 Network simplex algorithm, labeling algorithm for 423 Network simplex algorithm, lower-upper bounds 420 Network simplex algorithm, pivoting 417 Network simplex algorithm, tableau associated with 425 Network, connected 407 Network, directed 404 New activity 271 Node, capacitated 432 Node, definition 364 404 Node-arc formulation, maximal flow problem 474 Node-arc formulation, multicommodity minimal cost flow problem 494 Node-arc incidence matrix 407 Nonbasic matrix 55 86 Nonbasic variables 86 Nonbinding constraint 214 Nonbreakthrough 459 462 478 Nondegeneracy 86 202 395 Nondegenerate basic feasible solution 86 202 Nonnegativity constraints 2 Nonsimple path 488 Nonsingular matrix 49 Norm of vector 41 Normal to hyperplane 59 Northwest corner rule 368 Notation 24 Number of basic feasible solutions 88 204 Objective contour 16 Objective function, definition 2 Objective function, parametric 278 Objective function, phase I 142 Objective function, phase II 142 Objective function, piecewise linear and convex 433 Objective function, unbounded optimal value 18 93 105 260 Objective function, value 2 Optimal basic feasible solution 218 Optimal control problem 8 Optimal extreme point 83 93 Optimal location problem 27 Optimality criterion 16 102 209 254 260 Origin in transportation problem 353 Origin-destination matrix 521 Out-of-kilter algorithm, dual of 441 Out-of-kilter algorithm, dual variable change 449 Out-of-kilter algorithm, finite convergence 457 Out-of-kilter algorithm, flow change 446 Out-of-kilter algorithm, formulation 441 Out-of-kilter algorithm, kilter numbers and states 444 445 Parametric analysis of cost vector 278 Parametric analysis of right-hand-side vector 282 Partitioned matrix 46 Path in graph, definition 406 Path in graph, nonsimple 488 Path in graph, simple 488 Payoff matrix 291 Personnel training problem 29 Perturbation method 187 296 Perturbation of cost vector 278 Perturbation of right-hand-side vector 282 Phase I problem 142 Phase II problem 142 Piecewise linear objective function 433 Pivot, block 122 Pivot, column 227 Pivot, definition 115 Pivot, element 115 Player, column 291 Player, row 291 Polyhedral cone 66 Polyhedral set 64 Post-optimality analysis 267 Price 249 Price-directive decomposition 352 Primal feasibility 213 Primal problem 2 236 Primal Simplex Method 109 114 Primal-dual method, case of unbounded dual 259 Primal-dual method, development of 257 Primal-dual method, dual of restricted primal problem 258 Primal-dual method, modifying dual solution 259 Primal-dual method, restricted primal problem 258 Primal-dual method, summary of 260 Primal-dual method, tableau format 263 Product form of inverse 128 195 Production scheduling problem 8 28 Production-transportation-inventory problem 435 Programming problem, generalized 351 Programming problem, large scale 305 Programming problem, linear 2 Project management 515 Project selection problem 28 Proportionality assumption 3 Pseudorooted spanning forest 434 Rank of matrix 54 Rank of network flow matrix 407 Rank of transportation matrix 356 Ray 60 62 105 Reduced assignment matrix 384 Redundant, constraints 55 Redundant, geometrically 89 Relationships, primal, versus dual objective values 242 Relationships, primal, versus dual problems 241 242 Replacing vector in the basis 43 Representation of nonbasis vector 120 365 411 Representation theorem, bounded sets 67 Representation theorem, unbounded sets 68 82 Requirement space 18 20 21 23 Resource-directive decomposition 352 Restricted primal problem 258 restrictions see "Constraints" Return arc 474 Revised simplex method, comparison to simplex method 194 Revised simplex method, summary 190 Right-hand-side vector 2 Rocket launching problem 27 Root arc (root) 364 409 Rooted spanning forest 434 Rooted spanning tree 364 411 503 505 Row operations 48 Row rank 54 Row zero 114 Saturated arc 509 Scalar multiplication of matrix 45 Scalar multiplication of vector 40 Schwartz inequality 41 Sensitivity analysis, addition, of new activity 271 Sensitivity analysis, addition, of new constraint 272 Sensitivity analysis, change, in constraint matrix 270 Sensitivity analysis, change, in cost vector 268 Sensitivity analysis, change, in right-hand-side vector 269 Separating hyperplane, definition 523 524 Separating hyperplane, theorem 523 Set, bounded 66 Set, closed 523 Set, convex 58 Set, operations 25 Shadow prices 229 249 Shortest path, algorithm, for arbitrary costs 485 490 Shortest path, algorithm, for nonnegative costs 484 Shortest path, problem 468 483 Simple path 488 Simplex method, bounded 201 Simplex method, dual 250 Simplex method, finite convergence 110 170 256 Simplex method, initial solution 137 265 368 419 Simplex method, interpretation through Kuhn — Tucker conditions 219 Simplex method, network 413 Simplex method, optimality criterion 102 209 254 Simplex method, pivoting 115 Simplex method, primal 108 Simplex method, transportation 367 Simplex tableau, bounded 204 Simplex tableau, dual 252 Simplex tableau, network 425 Simplex tableau, primal 114 Simplex tableau, transportation 382 Simultaneous equations see "System of linear equations" Single artificial constraint technique 265 Single artificial variable technique 163 Singular matrix 49 Sink 364 405 Skew-symmetric matrix 46 302 Slack variable 4 Solution, basic feasible 55 Solution, feasible 2 Solution, optimal 15 Solution, space 15 Source 364 405 Space, Euclidean 42 Space, requirement 18 Space, solution 14 Spanning, set 43 Spanning, tree 361 407 Standard form of dual 238 Standard form of linear program 5 6 State variable 9 Stepping stone method 403 Strict convex combination 58 Strong theorem of complementary slackness 303 subproblem 306 308 Sum vector 40 Symmetric matrix 46 System of linear equations, basic solution 55 System of linear equations, Gaussian reduction 57 System of linear equations, general solution 57 System of linear equations, number of solutions 56 System of linear equations, redundant (dependent) 55 Tableau, assignment 385 Tableau, bounded simplex 204 Tableau, dual simplex 252 Tableau, primal-dual 263 Tableau, revised simplex 189 Tableau, simplex 114 382 425 Tableau, transportation 367 Tableau, two-phase 153 Tanker scheduling problem 12 Technological coefficients 2 Termination criterion, infeasibility 18 19 142 157 160 254 260 Termination criterion, optimality 16 21 102 157 209 254 260 Termination criterion, unboundedness 18 24 104 159 209 254 260 Tie breaking rule 169 Tight constraint 246 Totally unimodular matrix 357 411 Tourism problem 300 Traffic assignment problem 33 492 Transportation problem, algorithm for 367 Transportation problem, characterization of basis for 361 364 Transportation problem, definition 10 353 Transportation problem, degeneracy in 378 Transportation problem, properties of constraint matrix 356 Transportation problem, representation of nonbasic vector 365 Transportation problem, simplex tableau associated with 382 Transposition of matrix 46 Transshipment, node 405 Transshipment, problem 391 Traveling salesman problem 432 Tree, correspondence to basis in network flows 361 411 Tree, definition 361 407
Реклама
|
|
О проекте