Muutke küpsiste eelistusi

E-raamat: Linear and Integer Optimization: Theory and Practice, Third Edition

(Google, London, United Kingdom), (University of Groningen, The Netherlands)
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 136,50 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Linear and Integer Optimization: Theory and Practice, Third EditionSuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

Presenting a strong and clear relationship between theory and practice, Linear and Integer Optimization: Theory and Practiceis divided into two main parts. The first covers the theory of linear and integer optimization, including both basic and advanced topics. Dantzig’s simplex algorithm, duality, sensitivity analysis, integer optimization models, and network models are introduced.

More advanced topics also are presented including interior point algorithms, the branch-and-bound algorithm, cutting planes, complexity, standard combinatorial optimization models, the assignment problem, minimum cost flow, and the maximum flow/minimum cut theorem.

The second part applies theory through real-world case studies. The authors discuss advanced techniques such as column generation, multiobjective optimization, dynamic optimization, machine learning (support vector machines), combinatorial optimization, approximation algorithms, and game theory.

Besides the fresh new layout and completely redesigned figures, this new edition incorporates modern examples and applications of linear optimization. The book now includes computer code in the form of models in the GNU Mathematical Programming Language (GMPL). The models and corresponding data files are available for download and can be readily solved using the provided online solver.

This new edition also contains appendices covering mathematical proofs, linear algebra, graph theory, convexity, and nonlinear optimization. All chapters contain extensive examples and exercises. This textbook is ideal for courses for advanced undergraduate and graduate students in various fields including mathematics, computer science, industrial engineering, operations research, and management science.

Arvustused

Praise for the first edition: "...very recommendable as a textbook and to anybody wishing to learn the topic." Optimization (1997)

"...the book is a nice balance between theory and applications...and gives a sound background for the techniques used and for investigating real problems." Zentralblatt für Mathematik (1998)

List of Figures xvii
List of Tables xxiii
Preface xxv
1 Basic concepts of linear optimization
1(50)
1.1 The company Dovetail
2(3)
1.1.1 Formulating Model Dovetail
2(1)
1.1.2 The graphical solution method
3(2)
1.2 Definition of an LO-model
5(7)
1.2.1 The standard form of an LO-model
5(4)
1.2.2 Slack variables and binding constraints
9(1)
1.2.3 Types of optimal solutions and feasible regions
10(2)
1.3 Alternatives of the standard LO-model
12(2)
1.4 Solving LO-models using a computer package
14(2)
1.5 Linearizing nonlinear functions
16(5)
1.5.1 Ratio constraints
16(1)
1.5.2 Objective functions with absolute value terms
17(2)
1.5.3 Convex piecewise linear functions
19(2)
1.6 Examples of linear optimization models
21(18)
1.6.1 The diet problem
22(2)
1.6.2 Estimation by regression
24(2)
1.6.3 Team formation in sports
26(3)
1.6.4 Data envelopment analysis
29(5)
1.6.5 Portfolio selection; profit versus risk
34(5)
1.7 Building and implementing mathematical models
39(3)
1.8 Exercises
42(9)
I Linear optimization theory: basic techniques
2 Geometry and algebra of feasible regions
51(32)
2.1 The geometry of feasible regions
51(12)
2.1.1 Hyperplanes and halfspaces
52(3)
2.1.2 Vertices and extreme directions of the feasible region
55(3)
2.1.3 Faces of the feasible region
58(2)
2.1.4 The optimal vertex theorem
60(2)
2.1.5 Polyhedra and polytopes
62(1)
2.2 Algebra of feasible regions; feasible basic solutions
63(16)
2.2.1 Notation; row and column indices
63(1)
2.2.2 Feasible basic solutions
64(4)
2.2.3 Relationship between feasible basic solutions and vertices
68(7)
2.2.4 Degeneracy and feasible basic solutions
75(2)
2.2.5 Adjacency
77(2)
2.3 Exercises
79(4)
3 Dantzig's simplex algorithm
83(68)
3.1 From vertex to vertex to an optimal solution
83(6)
3.2 LO-model reformulation
89(2)
3.3 The simplex algorithm
91(5)
3.3.1 Initialization; finding an initial feasible basic solution
92(1)
3.3.2 The iteration step; exchanging variables
92(3)
3.3.3 Formulation of the simplex algorithm
95(1)
3.4 Simplex tableaus
96(10)
3.4.1 The initial simplex tableau
99(1)
3.4.2 Pivoting using simplex tableaus
99(5)
3.4.3 Why the identity matrix of a simplex tableau is row-permuted
104(2)
3.5 Discussion of the simplex algorithm
106(16)
3.5.1 Simplex adjacency graphs
107(3)
3.5.2 Optimality test and degeneracy
110(2)
3.5.3 Unboundedness
112(2)
3.5.4 Pivot rules
114(1)
3.5.5 Stalling and cycling
115(3)
3.5.6 Anti-cycling procedures: the perturbation method
118(2)
3.5.7 Anti-cycling procedures: Bland's rule
120(1)
3.5.8 Correctness of the simplex algorithm
121(1)
3.6 Initialization
122(9)
3.6.1 The big-M procedure
123(4)
3.6.2 The two-phase procedure
127(4)
3.7 Uniqueness and multiple optimal solutions
131(5)
3.8 Models with equality constraints
136(3)
3.9 The revised simplex algorithm
139(5)
3.9.1 Formulating the algorithm
139(2)
3.9.2 The product form of the inverse
141(1)
3.9.3 Applying the revised simplex algorithm
142(2)
3.10 Exercises
144(7)
4 Duality, feasibility, and optimality
151(44)
4.1 The companies Dovetail and Salmonnose
152(2)
4.1.1 Formulating the dual model
152(1)
4.1.2 Economic interpretation
153(1)
4.2 Duality and optimality
154(8)
4.2.1 Dualizing the standard LO-model
154(1)
4.2.2 Dualizing nonstandard LO-models
155(4)
4.2.3 Optimality and optimal dual solutions
159(3)
4.3 Complementary slackness relations
162(9)
4.3.1 Complementary dual variables
162(2)
4.3.2 Complementary slackness
164(3)
4.3.3 Determining the optimality of a given solution
167(1)
4.3.4 Strong complementary slackness
168(3)
4.4 Infeasibility and unboundedness; Farkas' lemma
171(4)
4.5 Primal and dual feasible basic solutions
175(4)
4.6 Duality and the simplex algorithm
179(6)
4.6.1 Dual solution corresponding to the simplex tableau
180(2)
4.6.2 The simplex algorithm from the dual perspective
182(3)
4.7 The dual simplex algorithm
185(5)
4.7.1 Formulating the dual simplex algorithm
187(1)
4.7.2 Reoptimizing an LO-model after adding a new constraint
188(2)
4.8 Exercises
190(5)
5 Sensitivity analysis
195(52)
5.1 Sensitivity of model parameters
195(2)
5.2 Perturbing objective coefficients
197(8)
5.2.1 Perturbing the objective coefficient of a basic variable
197(5)
5.2.2 Perturbing the objective coefficient of a nonbasic variable
202(1)
5.2.3 Determining tolerance intervals from an optimal simplex tableau
203(2)
5.3 Perturbing right hand side values (nondegenerate case)
205(11)
5.3.1 Perturbation of nonbinding constraints
206(1)
5.3.2 Perturbation of technology constraints
207(6)
5.3.3 Perturbation of nonnegativity constraints
213(3)
5.4 Piecewise linearity of perturbation functions
216(3)
5.5 Perturbation of the technology matrix
219(2)
5.6 Sensitivity analysis for the degenerate case
221(13)
5.6.1 Duality between multiple and degenerate optimal solutions
222(3)
5.6.2 Left and right shadow prices
225(6)
5.6.3 Degeneracy, binding constraints, and redundancy
231(3)
5.7 Shadow prices and redundancy of equality constraints
234(3)
5.8 Exercises
237(10)
6 Large-scale linear optimization
247(32)
6.1 The interior path
248(7)
6.1.1 The Karush-Kuhn-Tucker conditions for LO-models
248(1)
6.1.2 The interior path and the logarithmic barrier function
249(5)
6.1.3 Monotonicity and duality
254(1)
6.2 Formulation of the interior path algorithm
255(8)
6.2.1 The interior path as a guiding hand
255(1)
6.2.2 Projections on null space and row space
256(2)
6.2.3 Dikin's affine scaling procedure
258(1)
6.2.4 Determining the search direction
259(4)
6.3 Convergence to the interior path; maintaining feasibility
263(4)
6.3.1 The convergence measure
263(2)
6.3.2 Maintaining feasibility; the interior path algorithm
265(2)
6.4 Termination and initialization
267(6)
6.4.1 Termination and the duality gap
267(1)
6.4.2 Initialization
268(5)
6.5 Exercises -
273(6)
7 Integer linear optimization
279(54)
7.1 Introduction
279(4)
7.1.1 The company Dairy Corp
280(1)
7.1.2 ILO-models
281(1)
7.1.3 MILO-models
281(1)
7.1.4 A round-off procedure
282(1)
7.2 The branch-and-bound algorithm
283(18)
7.2.1 The branch-and-bound tree
283(3)
7.2.2 The general form of the branch-and-bound algorithm
286(3)
7.2.3 The knapsack problem
289(4)
7.2.4 A machine scheduling problem
293(5)
7.2.5 The traveling salesman problem; the quick and dirty method
298(1)
7.2.6 The branch-and-bound algorithm as a heuristic
299(2)
7.3 Linearizing logical forms with binary variables
301(11)
7.3.1 The binary variables theorem
301(2)
7.3.2 Introduction to the theory of logical variables
303(2)
7.3.3 Logical forms represented by binary variables
305(5)
7.3.4 A decentralization problem
310(2)
7.4 Gomory's cutting-plane algorithm
312(7)
7.4.1 The cutting-plane algorithm
313(4)
7.4.2 The cutting-plane algorithm for MILO-models
317(2)
7.5 Exercises
319(14)
8 Linear network models
333(64)
8.1 LO-models with integer solutions; total unimodularity
333(12)
8.1.1 Total unimodularity and integer vertices
334(2)
8.1.2 Total unimodularity and ILO-models
336(2)
8.1.3 Total unimodularity and incidence matrices
338(7)
8.2 ILO-models with totally unimodular matrices
345(22)
8.2.1 The transportation problem
345(2)
8.2.2 The balanced transportation problem
347(2)
8.2.3 The assignment problem
349(1)
8.2.4 The minimum cost flow problem
350(3)
8.2.5 The maximum flow problem; the max-flow min-cut theorem
353(8)
8.2.6 Project scheduling; critical paths in networks
361(6)
8.3 The network simplex algorithm
367(18)
8.3.1 The transshipment problem
367(2)
8.3.2 Network basis matrices and feasible tree solutions
369(3)
8.3.3 Node potential vector; reduced costs; test for optimality
372(2)
8.3.4 Determining an improved feasible tree solution
374(1)
8.3.5 The network simplex algorithm
375(3)
8.3.6 Relationship between tree solutions and feasible basic solutions
378(2)
8.3.7 Initialization; the network big-M and two-phase procedures
380(1)
8.3.8 Termination, degeneracy, and cycling
381(4)
8.4 Exercises
385(12)
9 Computational complexity
397(16)
9.1 Introduction to computational complexity
397(3)
9.2 Computational aspects of Dantzig's simplex algorithm
400(3)
9.3 The interior path algorithm has polynomial running time
403(1)
9.4 Computational aspects of the branch-and-bound algorithm
404(3)
9.5 Exercises
407(6)
II Linear optimization practice: advanced techniques
10 Designing a reservoir for irrigation
413(10)
10.1 The parameters and the input data
413(4)
10.2 Maximizing the irrigation area
417(2)
10.3 Changing the input parameters of the model
419(1)
10.4 GMPL model code
420(1)
10.5 Exercises
421(2)
11 Classifying documents by language
423(18)
11.1 Machine learning
423(2)
11.2 Classifying documents using separating hyperplanes
425(3)
11.3 LO-model for finding separating hyperplanes
428(3)
11.4 Validation of a classifier
431(1)
11.5 Robustness of separating hyperplanes; separation width
432(2)
11.6 Models that maximize the separation width
434(4)
11.6.1 Minimizing the 1-norm of the weight vector
435(1)
11.6.2 Minimizing the infinity-norm of the weight vector
435(1)
11.6.3 Comparing the two models
436(2)
11.7 GMPL model code
438(2)
11.8 Exercises
440(1)
12 Production planning: a single product case
441(18)
12.1 Model description
441(3)
12.2 Regular working hours
444(3)
12.3 Overtime
447(2)
12.4 Allowing overtime and idle time
449(2)
12.5 Sensitivity analysis
451(3)
12.6 GMPL model code
454(1)
12.6.1 Model (PP2)
454(1)
12.6.2 Model (PP3)
454(1)
12.7 Exercises
455(4)
13 Production of coffee machines
459(14)
13.1 Problem setting
459(1)
13.2 An LO-model that minimizes backlogs
460(2)
13.3 Old and recent backlogs
462(4)
13.4 Full week productions
466(1)
13.5 Sensitivity analysis
467(2)
13.5.1 Changing the number of conveyor belts
467(1)
13.5.2 Perturbing backlog-weight coefficients
468(1)
13.5.3 Changing the weights of the 'old' and the 'new' backlogs
469(1)
13.6 GMPL model code
469(2)
13.7 Exercises
471(2)
14 Conflicting objectives: producing versus importing
473(20)
14.1 Problem description and input data
473(1)
14.2 Modeling two conflicting objectives; Pareto optimal points
474(3)
14.3 Goal optimization for conflicting objectives
477(4)
14.4 Soft and hard constraints
481(2)
14.5 Sensitivity analysis
483(1)
14.5.1 Changing the penalties
483(1)
14.5.2 Changing the goals
483(1)
14.6 Alternative solution techniques
484(5)
14.6.1 Lexicographic goal optimization
485(3)
14.6.2 Fuzzy linear optimization
488(1)
14.7 A comparison of the solutions
489(1)
14.8 GMPL model code
490(1)
14.9 Exercises
491(2)
15 Coalition formation and profit distribution
493(20)
15.1 The farmers cooperation problem
493(2)
15.2 Game theory; linear production games
495(4)
15.3 How to distribute the total profit among the farmers?
499(3)
15.4 Profit distribution for arbitrary numbers of farmers
502(4)
15.4.1 The profit distribution
503(2)
15.4.2 Deriving conditions such that a given point is an Owen point
505(1)
15.5 Sensitivity analysis
506(3)
15.6 Exercises
509(4)
16 Minimizing trimloss when cutting cardboard
513(10)
16.1 Formulating the problem
513(3)
16.2 Gilmore-Gomory's solution algorithm
516(3)
16.3 Calculating an optimal solution
519(2)
16.4 Exercises
521(2)
17 Off-shore helicopter routing
523(24)
17.1 Problem description
523(1)
17.2 Vehicle routing problems
524(2)
17.3 Problem formulation
526(3)
17.4 ILO formulation
529(1)
17.5 Column generation
530(6)
17.5.1 Traveling salesman and knapsack problems
533(1)
17.5.2 Generating 'clever' subsets of platforms
534(2)
17.6 Dual values as price indicators for crew exchanges
536(2)
17.7 A round-off procedure for determining an integer solution
538(2)
17.8 Computational experiments
540(2)
17.9 Sensitivity analysis
542(2)
17.10 Exercises
544(3)
18 The catering service problem
547(16)
18.1 Formulation of the problem
547(2)
18.2 The transshipment problem formulation
549(3)
18.3 Applying the network simplex algorithm
552(3)
18.4 Sensitivity analysis
555(3)
18.4.1 Changing the inventory of the napkin supplier
556(1)
18.4.2 Changing the demand
556(1)
18.4.3 Changing the price of napkins and the laundering costs
557(1)
18.5 GMPL model code
558(2)
18.6 Exercises
560(3)
Appendices
A Mathematical proofs
563(4)
A.1 Direct proof
564(1)
A.2 Proof by contradiction
565(1)
A.3 Mathematical induction
565(2)
B Linear algebra
567(18)
B.1 Vectors
567(3)
B.2 Matrices
570(1)
B.3 Matrix partitions
571(1)
B.4 Elementary row/column operations; Gaussian elimination
572(4)
B.5 Solving sets of linear equalities
576(2)
B.6 The inverse of a matrix
578(1)
B.7 The determinant of a matrix
579(3)
B.8 Linear and affine spaces
582(3)
C Graph theory
585(12)
C.1 Undirected graphs
585(1)
C.2 Connectivity and subgraphs
586(2)
C.3 Trees and spanning trees
588(1)
C.4 Eulerian tours, Hamiltonian cycles, and Hamiltonian paths
589(2)
C.5 Matchings and coverings
591(1)
C.6 Directed graphs
592(2)
C.7 Adjacency matrices and incidence matrices
594(1)
C.8 Network optimization models
595(2)
D Convexity
597(14)
D.1 Sets, continuous functions, Weierstrass' theorem
597(3)
D.2 Convexity, polyhedra, polytopes, and cones
600(2)
D.3 Faces, extreme points, and adjacency
602(6)
D.4 Convex and concave functions
608(3)
E Nonlinear optimization
611(16)
E.1 Basics
611(3)
E.2 Nonlinear optimization; local and global minimizers
614(1)
E.3 Equality constraints; Lagrange multiplier method
615(5)
E.4 Models with equality and inequality constraints; Karush-Kuhn-Tucker conditions
620(4)
E.5 Karush-Kuhn-Tucker conditions for linear optimization
624(3)
F Writing LO-models in GNU MathProg (GMPL)
627(8)
F.1 Model Dovetail
627(2)
F.2 Separating model and data
629(2)
F.3 Built-in operators and functions
631(2)
F.4 Generating all subsets of a set
633(2)
List of Symbols 635(4)
Bibliography 639(6)
Author index 645(2)
Subject index 647
Gerard Sierksma, PhD, University of Groningen, The Netherlands Yori Zwols, PhD, Google UK, London
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97814987431292e.html
Märksõnad: