Linear and Integer Programming: Theory and Practice, Second Edition

Front Cover
CRC Press, Nov 1, 2001 - Mathematics - 656 pages
1 Review
"Combines the theoretical and practical aspects of linear and integer programming. Provides practical case studies and techniques, including rounding-off, column-generation, game theory, multiobjective optimization, and goal programming, as well as real-world solutions to the transportation and transshipment problem, project scheduling, and decentralization."
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

LINEAR PROGRAMMING BASIC CONCEPTS
1
12 THE COMPANY DOVETAIL
2
122 The Graphical Solution Method
3
13 THE DEFINITION OF LPMODEL
7
132 Types of Optimal Solutions and Feasible Regions
10
14 BASIC FEASIBLE SOLUTIONS
12
142 Basic Feasible Solutions and Degeneracy
13
143 The Rowcolumn Complementarity Theorem
18
65 EXERCISES
254
LINEAR NETWORK MODELS
269
712 Total I nimodularity and Incidence Matrices
273
713 ILPmodels having Totally Unimodular Matrices
277
72 THE NETWORK SIMPLEX METHOD
288
722 Basis Network Matrices and Feasible Tree Solutions
290
723 Formulation of the Network Simplex Method
293
73 EXERCISES
307

15 ADJACENCY AND OPTIMALITY
21
152 Basic Feasible Solutions and Vertices of the Feasible Region
24
153 Degenerate Vertices and Basic Feasible Solutions
28
154 Adjacent Vertices Optimal Vertex Theorem
31
16 ALTERNATIVES OF THE STANDARD LPMODEL
36
162 Basic Feasible Solutions for Models with Equality Constraints
37
17 EXERCISES
38
DANTZIGS SIMPLEX METHOD
43
22 THE SIMPLEX ALGORITHM
46
23 SIMPLEX TABLEAUS SIMPLEX ADJACENCY GRAPHS
52
24 CYCLING THE PERTURBATION PROCEDURE
55
25 INITIALIZATION
61
251 The BigM Procedure
62
252 The Twophase Procedure
65
26 MULTIPLE AND UNBOUNDED OPTIMAL SOLUTIONS
68
27 THE REVISED SIMPLEX METHOD
73
271 Formulating the Algorithm
74
272 The Product Form of the Inverse
76
273 Applying the Revised Simplex Algorithm
77
28 EXERCISES
79
DUALITY AND OPTIMALITY
87
321 Formulating the Dual Model
88
322 Economic Interpretation
89
33 DUALITY AND OPTIMALITY
90
332 Dualizing Nonstandard LPmodels
92
333 Optimality and Optimal Dual Basic Feasible Solutions
95
34 COMPLEMENTARY SLACKNESS RELATIONS FARKAS LEMMA
99
342 Strong Complementary Slackness
103
343 Determining the Optimality of a Given Solution
108
35 INFEASIBILITY AND UNBOUNDEDNESS
109
36 THE SIMPLEX METHOD AND THE DUAL MODEL
112
37 EXERCISES
113
SENSITIVITY ANALYSIS
117
411 Perturbing the Objective Coefficients
118
412 Perturbing Righthand Sides of Constraints Shadow Prices The Nondegenerate Case
126
413 Perturbation on the Nonnegativities Shadow Costs The Nondegenerate Case
133
414 Perturbation of the Technology Matrix
139
42 SENSITIVITY ANALYSIS FOR THE DEGENERATE CASE
142
422 Left and Rightshadow PricesCosts
147
43 SHADOW PRICESCOSTS AND REDUNDANCY OF EQUALITY CONSTRAINTS
159
44 EXERCISES
163
KARMARKARS INTERIOR PATH METHOD
175
512 The Lagrange Multiplier Method
176
52 THE INTERIOR PATH
178
522 The Logarithmic Barrier Function and the Interior Path
180
523 Monotonicity and Duality
185
53 FORMULATION OF THE INTERIOR PATH METHOD
186
532 Projections on Null Space and Row Space
187
533 Dikins Affine Scaling Procedure
189
534 Determining the Search Direction
191
54 CONVERGENCE TO THE INTERIOR PATH MAINTAINING FEASIBILITY
195
542 Approximations of Interior Paths
197
543 Maintaining Feasibility the Interior Path Algorithm
198
55 TERMINATION AND INITIALIZATION
199
552 Initialization
201
56 EXERCISES
204
INTEGER LINEAR PROGRAMMING
209
611 The Roundingoff Procedure
210
612 The Company Cheemi
211
62 THE BRANCHANDBOUND METHOD
213
622 The General Form of the Branchandbound Method
217
623 The Knapsack Problem
220
624 A Machine Scheduling Problem
224
63 LINEARIZING LOGICAL FORMS WITH BINARY VARIABLES
229
631 The Binary Variables Theorem
230
632 Introduction to the Theory of Logical Variables
231
633 Logical Forms Represented by Binary Variables
233
634 A Decentralization Problem
239
64 SPECIAL METHODS FOR INTEGER AND MIXED INTEGER MODELS
241
641 Gomorys Cuttingplane Method for ILPmodels
242
642 Gomorys Mixedinteger Cuttingplane Method
246
643 Benders Decomposition Method for MILPmodels
248
COMPUTATIONAL COMPLEXITY ISSUES
317
82 COMPUTATIONAL ASPECTS OF DANTZIGS SIMPLEX METHOD
320
83 POLYNOMIALITY OF THE INTERIOR PATH METHOD
324
84 COMPUTATIONAL ASPECTS OF THE BRANCHANDBOUND METHOD
326
85 EXERCISES
329
MODEL BUILDING CASE STUDIES AND ADVANCED TECHNIQUES
331
911 The Art of Building and Implementing Mathematical Models
333
92 PRODUCTION PLANNING A SINGLE PRODUCT CASE
336
922 Regular Employees and Regular Workinghours
339
923 Overtime
342
924 Sensitivity Analysis
346
93 THE PRODUCTION OF SEVERAL DESIGNS OF COFFEE MACHINES
348
931 The Parameters and the Input Data of the Model
349
932 Minimizing Shortages
350
933 Old and Recent Shortages
353
934 Full Week Productions
357
935 Sensitivity Analysis
358
94 MINIMIZING TRIMLOSS WHEN CUTTING CARDBOARD
361
942 GilmoreGomorys Solution Method
364
943 Transformation into a 01 Knapsack Problem
367
944 Calculating an Optimal Solution
370
95 DESIGNING A RESERVOIR FOR IRRIGATION
372
951 The Parameters and the Input Data
373
952 Maximizing the Irrigation Area
377
953 Changing the Input Parameters of the Model
379
96 ROUTING HELICOPTERS FOR CREW EXCHANGES ON OFFSHORE LOCATIONS
382
961 Problem Description
383
962 The Offshore Transportation Problem as Vehicle Routing Problem
385
963 Decreasing the Number of Platform Visits
387
964 Integer Linear Programming Formulation
390
965 The Column Generation Procedure a Knapsack and Traveling Salesman Problem
391
966 Dual Values as Price Indicators for Crew Exchanges
396
967 A Roundingoff Procedure for Determining an Integer Solution
399
968 Computational Experiments
401
97 THE CATERING SERVICE PROBLEM
402
972 The Transshipment Problem Formulation
405
973 Applying the Network Simplex Method
408
974 Sensitivity Analysis
412
PRODUCING OR IMPORTING
415
981 Problem Description and Input Data
416
982 Modeling the Two Conflicting Objectives Paretooptimal Points
417
983 Goal Programming for Conflicting Objectives
420
984 The LPmodel of the Goal Programming Problem
421
985 The Computer Solution for Conflicting Objectives
423
986 Soft and Hard Constraints Computer Solutions
424
987 Sensitivity Analysis
426
988 Alternative Solution Techniques
429
989 A Comparison of the Solutions
434
99 COALITION FORMATION AND PROFIT DISTRIBUTION
435
992 Game Theory Linear Production Games
436
993 How to Distribute the Total Profit among the Farmers?
440
994 Profit Distribution in the Case of pReplica Games
443
995 Sensitivity Analysis
446
910 EXERCISES
449
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 1
461
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 2
465
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 3
481
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 4
487
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 5
505
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 6
515
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 7
529
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 8
537
SOLUTIONS TO SELECTED EXERCISES OF CHAPTER 9
539
LINEAR ALGEBRA
553
CONVEXITY
571
GRAPH THEORY
581
COMPUTER PACKAGE INTPM
593
BIBLIOGRAPHY
603
LIST OF SYMBOLS
611
INDEX
615
Copyright

Common terms and phrases

Bibliographic information