# Linear and Integer Programming: Theory and Practice, Second Edition

CRC Press, Nov 1, 2001 - Mathematics - 656 pages
"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