[管理学]Decision Analysis_Chapter 06.ppt

? 2007 South-Western College Publishing Spreadsheet Modeling  Decision Analysis A Practical Introduction to Management Science 5th edition Cliff T. Ragsdale Integer Linear Programming Introduction When one or more variables in an LP problem must assume an integer value we have an Integer Linear Programming (ILP) problem. ILPs occur frequently… Scheduling workers Manufacturing airplanes Integer variables also allow us to build more accurate models for a number of common business problems. Integrality Conditions Relaxation Original ILP MAX: 2X1 + 3X2 S.T.: X1 + 3X2 = 8.25 2.5X1 + X2 = 8.75 X1, X2 = 0 X1, X2 must be integers LP Relaxation MAX: 2X1 + 3X2 S.T.: X1 + 3X2 = 8.25 2.5X1 + X2 = 8.75 X1, X2 = 0 Integer Feasible vs. LP Feasible Region Solving ILP Problems When solving an LP relaxation, sometimes you “get lucky” and obtain an integer feasible solution. This was the case in the original Blue Ridge Hot Tubs problem in earlier chapters. But what if we reduce the amount of labor available to 1520 hours and the amount of tubing to 2650 feet? See file Fig6-2.xls Bounds The optimal solution to an LP relaxation of an ILP problem gives us a bound on the optimal objective function value. For maximization problems, the optimal relaxed objective function values is an upper bound on the optimal integer value. For minimization problems, the optimal relaxed objective function values is a lower bound on the optimal integer value. Rounding It is tempting to simply round a fractional solution to the closest integer solution. In general, this does not work reliably: The rounded solution may be infeasible. The rounded solution may be suboptimal. How Rounding Down Can Result in an Infeasible Solution Branch-and-Bound The Branch-and-Bound (BB) algorithm can be used to solve ILP problems. Requires the solution of a series of LP problems termed “candidate problems”. Theoretically, this can solve any ILP. Practically, it often takes LOTS of computational effort