Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Introduction to Management Science with Spreadsheets: Chapter 7S - Stevenson, Ozgur

Chapter 7 - Supplement "Branch and bound method of solving integer programming problems", after completing this chapter, you should be able to: Use the branch and bound method to solve integer programming problems, use the enumeration method to solve 0–1 integer programming problems. | Chapter 7 Supplement Branch and Bound Method of Solving Integer Programming Problems Part 2 Deterministic Decision Models Learning Objectives Use the branch and bound method to solve integer programming problems. Use the enumeration method to solve 0–1 integer programming problems. After completing this chapter, you should be able to: McGraw-Hill/Irwin 7S– Integer Programming Problems Bound An upper or lower limit on the value of the objective function at a given stage of the analysis of an integer programming problem. Branch Selection of an integer value of a decision variable to examine for a possible integer solution to a problem. McGraw-Hill/Irwin 7S– Solving Integer Programming Branch and Bound method Creates and solves a sequence of subproblems to the original problem that are increasingly more restrictive until an optimal solution is found. Enumeration Method A method used with 0–1 problems that involves listing every possible outcome in order to identify the optimal solution. McGraw-Hill/Irwin 7S– Integer Programming Problems Mixed-Integer Problem Requires that some, but not all, decision variables have integer values. Pure-Integer Problem requires that all decision variables have integer values. Mixed-Integer Problem requires that some, but not all, decision variables have integer values. McGraw-Hill/Irwin 7S– Figure 7S–1 Graph of an Integer Programming Problem McGraw-Hill/Irwin 7S– Example 7S-1 All-Integer Problem McGraw-Hill/Irwin 7S– Figure 7S–2 The LP Relaxation Solution McGraw-Hill/Irwin 7S– Figure 7S–3 Node I Summarizes the LP Relaxation Solution Figure 7S–4 Branching from the First Node McGraw-Hill/Irwin 7S– Figure 7S–5 Subproblems and Solution Points for Nodes 2 and 3 McGraw-Hill/Irwin 7S– Figure 7S–6 Solutions for Nodes 2 and 3 McGraw-Hill/Irwin 7S– Figure 7S–7 Subproblem and Solution Point for Node 4 McGraw-Hill/Irwin 7S– Figure 7S–8 Solutions for Nodes 4 and 5 McGraw-Hill/Irwin 7S– Figure 7S–9 . | Chapter 7 Supplement Branch and Bound Method of Solving Integer Programming Problems Part 2 Deterministic Decision Models Learning Objectives Use the branch and bound method to solve integer programming problems. Use the enumeration method to solve 0–1 integer programming problems. After completing this chapter, you should be able to: McGraw-Hill/Irwin 7S– Integer Programming Problems Bound An upper or lower limit on the value of the objective function at a given stage of the analysis of an integer programming problem. Branch Selection of an integer value of a decision variable to examine for a possible integer solution to a problem. McGraw-Hill/Irwin 7S– Solving Integer Programming Branch and Bound method Creates and solves a sequence of subproblems to the original problem that are increasingly more restrictive until an optimal solution is found. Enumeration Method A method used with 0–1 problems that involves listing every possible outcome in order to identify the optimal .