Preface |
|
xiii | |
I Models |
|
1 | (70) |
|
|
3 | (22) |
|
|
3 | (1) |
|
The Transportation Problem |
|
|
4 | (2) |
|
The Production Scheduling Problem |
|
|
6 | (3) |
|
Production Scheduling Problem 1 |
|
|
6 | (3) |
|
|
9 | (2) |
|
|
11 | (2) |
|
|
13 | (2) |
|
|
15 | (3) |
|
Electric Power Economic Dispatch |
|
|
18 | (7) |
|
|
21 | (4) |
|
Mixed-Integer Linear Programming |
|
|
25 | (22) |
|
|
25 | (1) |
|
|
25 | (2) |
|
Identifying Relevant Symptoms |
|
|
27 | (2) |
|
|
29 | (3) |
|
|
32 | (3) |
|
Models of Discrete Location |
|
|
35 | (3) |
|
Unit Commitment of Thermal Power Units |
|
|
38 | (9) |
|
|
43 | (4) |
|
|
47 | (24) |
|
|
47 | (1) |
|
Some Geometrically Motivated Examples |
|
|
47 | (4) |
|
The Postal Package Example |
|
|
47 | (1) |
|
|
48 | (1) |
|
|
48 | (2) |
|
|
50 | (1) |
|
|
50 | (1) |
|
Some Mechanically Motivated Examples |
|
|
51 | (4) |
|
The Cantilever Beam Example |
|
|
51 | (1) |
|
The Two-Bar Truss Example |
|
|
51 | (2) |
|
|
53 | (1) |
|
|
54 | (1) |
|
Some Electrically Motivated Examples |
|
|
55 | (7) |
|
Power Circuit State Estimation |
|
|
56 | (2) |
|
|
58 | (4) |
|
The Matrix Balancing Problem |
|
|
62 | (2) |
|
The Traffic Assignment Problem |
|
|
64 | (7) |
|
|
69 | (2) |
II Methods |
|
71 | (212) |
|
An Introduction to Linear Programming |
|
|
73 | (24) |
|
|
73 | (1) |
|
Problem Statement and Basic Definitions |
|
|
73 | (5) |
|
Linear Programming Problem in Standard Form |
|
|
78 | (3) |
|
Transformation to Standard Form |
|
|
79 | (2) |
|
|
81 | (2) |
|
|
83 | (1) |
|
|
84 | (13) |
|
Obtaining the Dual from a Primal in Standard Form |
|
|
85 | (1) |
|
Obtaining the Dual Problem |
|
|
86 | (1) |
|
|
87 | (5) |
|
|
92 | (5) |
|
Understanding the Set of All Feasible Solutions |
|
|
97 | (20) |
|
Introduction and Motivation |
|
|
97 | (4) |
|
|
101 | (4) |
|
|
105 | (2) |
|
|
107 | (2) |
|
|
109 | (1) |
|
|
110 | (3) |
|
General Representation of Polyhera |
|
|
112 | (1) |
|
Bounded and Unbounded LPP |
|
|
113 | (4) |
|
|
114 | (3) |
|
Solving the Linear Programming Problem |
|
|
117 | (44) |
|
|
117 | (1) |
|
|
118 | (22) |
|
|
118 | (2) |
|
|
120 | (1) |
|
|
121 | (1) |
|
Elemental Pivoting Operation |
|
|
122 | (3) |
|
Identifying an Optimal Solution |
|
|
125 | (1) |
|
|
126 | (1) |
|
|
126 | (1) |
|
|
127 | (1) |
|
Standard Iterations Stage |
|
|
127 | (2) |
|
The Revised Simplex Algorithm |
|
|
129 | (2) |
|
Some Illustrative Examples |
|
|
131 | (9) |
|
The Exterior Point Method |
|
|
140 | (21) |
|
|
142 | (1) |
|
|
143 | (1) |
|
Detecting Infeasibility and Unboundedness |
|
|
144 | (1) |
|
Standard Iterations Stage |
|
|
144 | (2) |
|
|
146 | (2) |
|
Some Illustrative Examples |
|
|
148 | (9) |
|
|
157 | (4) |
|
Mixed-Integer Linear Programming |
|
|
161 | (22) |
|
|
161 | (1) |
|
|
162 | (10) |
|
|
162 | (1) |
|
The BB Algorithm for MILPP |
|
|
163 | (1) |
|
Branching and Processing Strategies |
|
|
164 | (8) |
|
Other Mixed-Integer Liner Programming Problems |
|
|
172 | (1) |
|
|
172 | (11) |
|
|
172 | (1) |
|
|
173 | (1) |
|
The Gomory Cuts Algorithm for an ILPP |
|
|
174 | (6) |
|
|
180 | (3) |
|
Optimality and Duality in Nonlinear Programming |
|
|
183 | (52) |
|
|
183 | (5) |
|
Necessary Optimality Conditions |
|
|
188 | (19) |
|
|
188 | (2) |
|
Karush-Kuhn-Tucker Optimality Conditions |
|
|
190 | (17) |
|
Optimality Conditions: Sufficiency and Convexity |
|
|
207 | (9) |
|
|
207 | (4) |
|
Sufficiency of the Karush-Kuhn-Tucker Conditions |
|
|
211 | (5) |
|
|
216 | (5) |
|
Practical Illustrations of Duality and Separability |
|
|
221 | (5) |
|
Centralized or Primal Approach |
|
|
222 | (3) |
|
Competitive Market or Dual Approach |
|
|
225 | (1) |
|
|
226 | (1) |
|
Constraint Qualifications |
|
|
226 | (9) |
|
|
227 | (8) |
|
Computational Methods for Nonlinear Programming |
|
|
235 | (48) |
|
Unconstrained Optimization Algorithms |
|
|
236 | (18) |
|
|
236 | (5) |
|
Multidimensional Unconstrained Optimization |
|
|
241 | (13) |
|
Constrained Optimization Algorithms |
|
|
254 | (29) |
|
|
254 | (7) |
|
|
261 | (8) |
|
The Interior Point Method |
|
|
269 | (9) |
|
|
278 | (5) |
III Software |
|
283 | (86) |
|
|
285 | (26) |
|
|
285 | (1) |
|
|
286 | (4) |
|
|
290 | (21) |
|
|
291 | (2) |
|
|
293 | (1) |
|
|
293 | (3) |
|
Mathematical Expression Rules in Assignments |
|
|
296 | (1) |
|
|
296 | (3) |
|
|
299 | (1) |
|
|
299 | (1) |
|
|
300 | (3) |
|
|
303 | (1) |
|
|
303 | (1) |
|
|
304 | (1) |
|
|
305 | (1) |
|
|
306 | (3) |
|
|
309 | (1) |
|
Output File: Nonlinear Equation Listing |
|
|
310 | (1) |
|
|
311 | (58) |
|
|
311 | (1) |
|
Linear Programming Examples |
|
|
311 | (19) |
|
The Transportation Problem |
|
|
311 | (4) |
|
Production Scheduling Problem 1 |
|
|
315 | (2) |
|
|
317 | (2) |
|
|
319 | (5) |
|
|
324 | (1) |
|
|
325 | (3) |
|
Electric Power Economic Dispatch |
|
|
328 | (2) |
|
Mixed-Integer LPP Examples |
|
|
330 | (14) |
|
|
331 | (2) |
|
Identifying Relevant Symptoms |
|
|
333 | (1) |
|
|
334 | (3) |
|
The School Timetable Problem |
|
|
337 | (1) |
|
Models of Discrete Location |
|
|
338 | (3) |
|
Unit Commitment of Thermal Power Units |
|
|
341 | (3) |
|
Nonlinear Programming Examples |
|
|
344 | (25) |
|
The Postal Package Example |
|
|
344 | (1) |
|
|
345 | (1) |
|
|
346 | (1) |
|
|
346 | (1) |
|
|
347 | (1) |
|
The Cantilever Beam Example |
|
|
348 | (1) |
|
The Two-Bar Truss Example |
|
|
348 | (2) |
|
|
350 | (1) |
|
|
351 | (2) |
|
Power Circuit State Estimation |
|
|
353 | (2) |
|
|
355 | (4) |
|
The Water Supply Network Problem |
|
|
359 | (2) |
|
The Matrix Balancing Problem |
|
|
361 | (2) |
|
The Traffic Assignment Problem |
|
|
363 | (1) |
|
|
364 | (5) |
IV Applications |
|
369 | (108) |
|
|
371 | (80) |
|
Applications to Artificial Intelligence |
|
|
371 | (7) |
|
Learning the Neural Functions |
|
|
373 | (5) |
|
|
378 | (9) |
|
Automatic Mesh Generation |
|
|
381 | (6) |
|
Applications to Probability |
|
|
387 | (8) |
|
Compatibility of Conditional Probability Matrices |
|
|
387 | (4) |
|
|
391 | (4) |
|
|
395 | (6) |
|
Applications to Optimization Problems |
|
|
401 | (16) |
|
|
403 | (7) |
|
|
410 | (7) |
|
|
417 | (25) |
|
|
417 | (1) |
|
Elements of a Road Transportation Network |
|
|
418 | (4) |
|
The Traffic Assignment Problem |
|
|
422 | (7) |
|
Side-Constrained Assignment Models |
|
|
429 | (3) |
|
|
432 | (6) |
|
Combined Distribution and Assignment |
|
|
438 | (4) |
|
Short-Term Hydrothermal Coordination |
|
|
442 | (9) |
|
Problem Formulation and the LR Solution Procedure |
|
|
443 | (4) |
|
Dual-Problem Solution: Multiplier Updating Techniques |
|
|
447 | (1) |
|
Economical Meaning of the Multipliers |
|
|
448 | (3) |
|
Some Useful Modeling Tricks |
|
|
451 | (26) |
|
|
451 | (1) |
|
|
451 | (15) |
|
Dealing with Unrestricted Variables |
|
|
452 | (1) |
|
Converting Inequalities into Equalities |
|
|
453 | (1) |
|
Converting Equalities into Inequalities |
|
|
454 | (1) |
|
Converting Maximization into Minimization Problems |
|
|
455 | (1) |
|
Converting Nonlinear Objective Functions into Linear |
|
|
455 | (1) |
|
Nonlinear Functions Treated as Linear Functions |
|
|
455 | (3) |
|
|
458 | (2) |
|
Alternative Sets of Constraints |
|
|
460 | (2) |
|
Dealing with Conditional Constraints |
|
|
462 | (1) |
|
Dealing with Discontinuous Functions |
|
|
462 | (1) |
|
Dealing with Piecewise Nonconvex Functions |
|
|
463 | (3) |
|
|
466 | (11) |
|
Assigning Values to a Matrix |
|
|
466 | (1) |
|
Defining a Symmetric Matrix |
|
|
467 | (1) |
|
|
467 | (2) |
|
Splitting a Separable Problem |
|
|
469 | (1) |
|
Adding Constraints Iteratively to a Problem |
|
|
470 | (1) |
|
Dealing with Initial and Final States |
|
|
471 | (1) |
|
Performing a Sensitivity Analysis |
|
|
471 | (1) |
|
Making the Model Dependent on Problem States |
|
|
472 | (1) |
|
|
473 | (4) |
A Compatibility and Set of All Feasible Solutions |
|
477 | (40) |
|
|
478 | (2) |
|
Cone Associated with a Polyhedron |
|
|
480 | (3) |
|
|
483 | (5) |
|
Compatibility of Linear Systems |
|
|
488 | (3) |
|
|
491 | (3) |
|
Applications to Several Examples |
|
|
494 | (23) |
|
The Transportation Problem |
|
|
494 | (5) |
|
Production Scheduling Problem |
|
|
499 | (6) |
|
|
505 | (2) |
|
|
507 | (1) |
|
|
508 | (5) |
|
|
513 | (4) |
B Notation |
|
517 | (16) |
Bibliography |
|
533 | (8) |
Index |
|
541 | |