All Matches

Solution Library

Expert Answer

Textbooks

Search Textbook questions, tutors and Books

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Tutors
Study Help
Hire a Tutor
AI Study Help New

Search
Sign In
Register

study help
business
operations research an introduction

Questions and Answers of Operations Research An Introduction

Every year the city of Montreal14 must remove large quantities of snow from sectors i = 1,c, 60 of the city. Each sector is assigned to one of sites j = 1,c, 20 as its primary disposal point. From
Highway maintenance in Australia15 is performed by crews operating out of maintenance depots. The Victoria region is planning a major realignments of its depots to provide more effective service to
Mobil Oil Corporation16 serves 600,000 customers with 430 tanktrucks operating out of 120 bulk terminals. As illustrated in the following figure, tanktrucks have several compartments c = 1,c, n of
Each of the 11 nurses17 at Rosey Retirement Home works a total of 10 days within each 2-week period, alternating between a compatible pair of weekly schedules taken from those depicted in the
Regional Bell telephone operating companies, 18 which buy many products from a much smaller number of suppliers, often solicit discounts based on the total dollar volume of business awarded to
The small Adele19 textile company knits products p = 1,c, 79 on a variety of machines m = 1,c, 48 to meet known output quotas qp pounds for the next week. The variable cost per pound of making
Mail Order Mart (MOM)20 will ship qj pounds of small-order novelty goods over the next week to regions j = 1,c, 27 of the United States. MOM’s distribution facility is located in New England region
Gas turbine engines21 have the following radial assembly of nozzle guides located immediately upstream from each rotor. The purpose of the vanes is to spread flow uniformly over the rotor, which
A new freight airline22 is designing a huband-spoke system for its operations. From a total of 34 airports to be served, 3 will be selected as hubs. Then (one-way) airport-to-airport freight
In an area with many suburban communities, telephone listings are usually grouped into several different books.23 Patrons in each community i = 1,c, n are covered in exactly one directory k = 1,c, m.
Solve each of the following discrete optimization models by total enumeration.(a) min 2x1 + x2 + 4x3 + 10x4 s.t. x1 + x2 + x3 … 2 3x1 + 7x2 + 19x3 + x4 Ú 20 x1, x2, x3 = 0 or 1 x4 Ú 0(b) max 30x1
Suppose that you have been asked to solve a mixed-integer ILP with 10,000 continuous and n binary decision variables. Determine the largest n’s for which the problem could be totally enumerated in
Consider the ILP max 14x1 + 2x2 - 11x3 + 17x4 s.t. 2x1 + x2 + 4x3 + 5x4 … 12 x1 - 3x2 - 3x3 - 3x4 … 0 x1 Ú 0 x2, x3, x4 = 0 or 1 Determine whether each of the following is a constraint
Form the linear programming relaxation of each of the following ILPs.(a) min 12x1 + 45x2 + 67x3 + 1x4 s.t. 4x1 + 2x2 - x4 … 10 6x1 + 19x3 Ú 5 x2, x3, x4 Ú 0 x1 = 0 or 1 x3 integer(b) max 3x1 +
Each of the following ILPs has no feasible solutions. Solve the corresponding LP relaxation graphically and indicate whether your relaxation results are sufficient to show that the ILP is
Determine the best bound on the optimal solution value of an ILP with each of the following objective functions that is available from the specified LP relaxation optima x .(a) max 24x1 + 13x2 + 3x3
Determine whether each of the following LP relaxation optima x is optimal in the corresponding ILP over the specified variable type constraints.(a) xj = 0 or 1, j = 1,c, 4 x = a1, 0, 13 , 23 b (b)
The ILP max 3x1 + 6x2 + 4x3 + 10x4 + 3x5 s.t. 2x1 + 4x2 + x3 + 3x4 + 7x5 … 10 x1 + x3 + x4 … 2 4x2 + 4x4 + 4x5 … 7 x1,c, x5 = 0 or 1 has LP relaxation optimal solution x =10, 0.75, 1, 1,
Do Exercise 12-8 for the ILP min 12x1 + 5x2 + 4x3 + 6x4 + 7x5 s.t. 6x1 + 8x2 + 21x3 + 6x4 + 5x5 Ú 11 x1 + x2 + 2x3 + x4 Ú 1 2x2 + 5x3 + x5 Ú 2 x1,c, x5 = 0 or 1 and LP relaxation optimum x = 10,
Do Exercise 12-8 for the ILP min 17x1 + 12x2 + 24x3 + 2x4 + 8x5 s.t. 3x1 + 5x3 + 7x4 + 9x5 Ú 13 7x2 + 4x4 + 11x5 Ú 5 2x1 + 3x2 + 2x3 + 3x4 Ú 7 x2, x3, x4 = 0 or 1 x1, x5 Ú 0 and LP relaxation
Do Exercise 12-8 for the ILP min 50x1 + 25x2 + 100x3 + 300x4+ 200x5 + 500x6 s.t. 10x1 + 6x2 + 2x3 = 45 2x1 + 3x2 + x3 Ú 12 0 … x1 … 5x4 0 … x2 … 5x5 0 … x3 … 5x6 x4, x5, x6 = 0 or 1 and
Consider the ILP min 10x1 + 20x2 + 40x3 + 80x4 - 144y s.t. x1 + x2 + x3 + x4 Ú 4y x1,c, x4, y = 0 or 1(a) Solve the full ILP model by inspection.(b) Verify by inspection that its LP relaxation has
Do Exercise 12-12 for ILP min 16x1 + 14x2 + 15x3 s.t. x1 + x2 Ú 1 x2 + x3 Ú 1 x1 + x3 Ú 1 x1,c, x3 = 0 or 1 LP relaxation optimum x = 112, 12, 12 2 and revised main constraint x1 + x2 + x3 Ú 2
Consider the Fixed Charge Network Flow instance displayed below (see Section 11.6).Numbers on arcs are fixed charges fij. All variable costs cij = 0.(a) Formulate the instance as in 11.31 using
The fixed-charge ILP min 60x1 + 78x2 + 200y1 + 400y2 s.t. 12x1 + 20x2 Ú 64 15x1 + 10x2 … 60 x1 + x2 … 10 0 … x1 … 100y1 0 … x2 … 100y2 y1, y2 = 0 or 1 has LP relaxation optimum x = 10,
Do Exercise 12-15 for the averagecompletion-time, single-machine scheduling ILP min 0.51x1 + 12 + x2 + 82 s.t. x1 + 12 … x2 + 7511 - y2 x2 + 8 … x1 + 75y x1, x2 Ú 0 y = 0 or 1 with LP relaxation
Suppose that an integer linear program has decision variables x1, x2, x3 = 0 or 1. List all completions of the following partial solutions.(a) (#, 0, #)(b) (1, 0, #)
The following is the complete branch and bound tree for an ILP over decision variables x1,c, x4 = 0 or 1.(a) List the partial solutions associated with each node of the tree.(b) Which nodes were
Do Exercise 12-18 for the branch and bound tree x=1 0 x4=0 1 2 x2=1 x2=0 4 3
Suppose that the ILP of Exercise 12-8 is being solved by branch and bound. State the candidate problem associated with each of the following partial solutions.(a) (#, 1, #, #, 0)(b) (#, 1, 0, 1, #)
Suppose that a minimizing ILP is being solved by LP-based branch and bound Algorithm 12A over decision variables x1, x2, x3 = 0 or 1, x4 Ú 0. Show how the search should process the node with x2 = 1
The following table shows the LP relaxation outcomes for all possible combinations of fixed and free variables in branch and bound solution of a minimizing integer linear program over decision
Do Exercise 12-22 for a minimizing mixedinteger linear program over binary variables w1, w2, w3, and w4 Ú 0. W1 W2 10'3 LP Optimum LP Value ######### # # 0 # # # 0 # 0 0 1 1 1 0 # 0 # 0 # 0 0 0 0 0
Consider a maximizing MILP over x1 Ú 0, and x2, x3, x4 = 0 or 1.(a) Solve the problem by LP-based Branch and Bound Algorithm 12A, using the given table of candidate problem solutions, and record
Consider a minimizing MILP over x1, x2, x3 binary and x4 Ú 0.(a) Solve the problem by LP-based Branch and Bound Algorithm 12A, using the given table of candidate problem solutions, and record your
Consider a maximizing mixed-integer liner program with x1 Ú 0, x2, x3, x4 = 0 or 1.(a) Solve the problem by LP-based Branch and Bound Algorithm 12A, using the given table of candidate problem
Students often mistakenly believe ILPs are more tractable than LPs because the straightforward rules of Algorithm 12A seem less complex than the simplex and interior point methods of Chapters
In most applications, LP based Branch and Bound Algorithm 12A actually investigates only a tiny fraction of the possible partial solutions.Still, this is not always the case. Consider the family of
The branch and bound tree Figure 12.10 records solution of the knapsack model min 90x1 + 50x2 + 54x3 s.t. 60x1 + 110x2 + 150x3 Ú 50 x1, x2, x3 = 0 or 1 by LP-based Algorithm 12A under rules of
Do Exercise 12-29 for max 51x1 + 72x2 + 41x3 s.t. 17x1 + 10x2 + 14x3 … 19 x1, x2, x3 = 0 or 1 and tree in Figure 12.11figurE 12.10 Branch and Bound Tree for Exercise 12-29 x3=1 6)(0,0,1) 54 0 (0,
Return to the knapsack problem of Exercise 12-29.(a) Explain why LP relaxation optimal solutions can be rounded to integer-feasible solutions by setting xn jd
Do Exercise 12-31 on the knapsack model of Exercise 12-30, this time rounding solutions xn jd :x j;.
For each of the following branch and bound trees determine the best lower and upper bounds on the value of an optimal solution known from parent bounds and incumbent solutions after processing of
The branch and bound tree that follows shows the incomplete solution of a maximizing ILPby LP-based Algorithm 12A, with numbers next to nodes indicating LP relaxation solution values.Node 4 has just
The branch and bound tree that follows shows the incomplete solution of a minimizing ILP by LP-based Algorithm 12A, with numbers next to nodes indicating LP relaxation solution values.Node 4 has just
Repeat Exercise 12-22, following the same rules except:(a) Use the best-first enumeration sequence and allow termination by parent bounds.(b) Use the depth-forward best-back enumeration sequence and
Do Exercise 12-36 for the branch and bound of Exercise 12-26.
Three company trucks must be assigned to pickup 7 miscellaneous loads on the way back from their regular deliveries. Truck capacities and load sizes (cubic yards) are shown in the following table,
Return to the ILP of Exercise 12-12 with LP relaxation optimum x = 11, 1, 0, 02, y = 12.Determine whether each of the following is a valid inequality for the ILP, and if so, whether it would
Return to the ILP of Exercise 12-13 with LP relaxation optimum x = 112, 12, 1 22. Determine whether each of the inequality for the ILP, and if so, whether it would strengthen the original LP
The ILP max 40x1 + 5x2 + 60x3 + 8x4 s.t. 18x1 + 3x2 + 20x3 + 5x4 … 25 x1,c, x4 = 0 or 1 has LP relaxation optimum x = 1 5 18, 0, 1, 02. Determine whether each of the following is a valid
The following tree records solution of a maximizing ILP over x1, x2, x3 = 0 or 1 by branch and cut Algorithm 12B. LP relaxations solutions show next to each node.Briefly describe the processing,
Do Exercise 12-42 for the following tree of a minimizing ILP over x1, x2, x3 = 0 or 1. (0) (0.2, 0, 0.6) 50 x2+2x32 1) (0.2, 0.5, 0.75) 57 x=1 3 (1,0,1) 63 solve 2) (0.6, 0.4, 1) 58 x=0 4 (0, 1, 0.5)
The tree below shows the evolution of a hypothetical Branch and Cut Algorithm 12B solution of a given minimizing, all-binary ILP.Relaxation solutions are shown next to nodes, and both fixed variables
The LP relaxation of a standard form ILP over constraints Ax =b, x Ú 0, x integer, with 3 rows and 7 variables, has been solved for basic variables x1, x2, and x5 to obtain the dictionary form (see
Consider the binary knapsack polytope 18x1 + 3x2 + 20x3 + 17x4 + 6x5+ 10x6 + 5x7 + 12x8 … 25 x1,c, x8 = 0 or 1(a) Identify 5 minimal cover inequalities valid for this knapsack polytope, including
Air National Guard planners are loading a cargo plane with crates of supplies and equipment needed to help victims of the recent wave of floods in the Northeast. The table below shows the criticality
Consider the binary ILP max 21x1 + 21x2 + 48x3 + 33x4 + 18x5+ 17x6 + 39x7 s.t. 5x1 + 14x2 + 12x3 + 21x4 + 1x5+ 6x6 + 13x7 … 30 [i]x1 + x2 + x3 … 1 [ii]xj binary for all j [iii](a) Use class
The plot below depicts the solution space of pure binarary ILP min 3x1 + 4x2 s.t. 4x1 + 2x2 Ú 1 5x1 + 10x2 Ú 4 x1, x2 = 0 or 1Coordinates and solution values of important points are pre-computed in
Consider a pure-integer program over constraints-1x1 + 2x2 … 4 5x1 + 1x2 … 20-2x1 - 2x2 … -7 x1, x2 Ú 0 and integer(a) Draw a 2-dimensional plot of the LPrelaxation feasible set.(b) Identify
Return to the ILP of Exercises 12-13 and 12-40.(a) Draw a 3-dimensional sketch of the convex hull of feasible solutions to this model(b) Determine the dimension of the convex hull.(c) For each of
The following plot shows the feasible space for an ILP over nonnegative integer variables x1 and x2.(a) Identify the convex hull of integer-feasible solutions.(b) Determine the dimension of the
Consider solving an ILP of the following form by Delayed Column Generation Algorithm 13A.min aj cj xj s.t. aj ai, j xj Ú bi i = 1,c, 5 all xj Ú 0 and integer where right-hand sides are given
Emergency relief agency ERNow is planning flights of small helicopters to deliver medical, food, and housing supplies for populations cutoff by a recent hurricane. The following table shows the
The Silo State IE faculty is dividing its 12 members into 4 teams of 3 to develop ideas for a long-term strategic plan. Like all faculties, the professors are not all equally compatible with each
The tree below shows the hypothetical evolution of a Branch and Price Algorithm 13B solution of an all-binary ILP in original variables x1, x2, and x3. Relaxation solutions are shown next to nodes,
Do Exercise 13-4 for the Branch-and-Price below on an all-binary ILP over original variables x1, x2, x3 and x4. (no initial incumbent) x=1 add x5 add x (0, 1/2, 1, 2/3) 40 (1, 1, 0, 1, 2/3) 35 2)(0,
Consider the ILP max 30x1 + 55x2 + 20x3 s .t. 40x1 - 12x2 + 11x3 … 55 19x1 + 60x2 + 3x3 Ú 20 3x1 + 2x2 + 2x3 = 5 x1, x2, x3 = 0 or 1 Form the Lagrangian relaxations obtained by dualizing each of
Consider the facilities location ILP min 3x1,1 + 6x1,2 + 5x2,1 + 2x2,2+250y1 + 300y2 s .t . 30x1,1 + 20x1,2 … 30y1 30x2,1 + 20x2,2 … 50y2 x1,1 + x2,1 = 1 x1,2 + x2,2 = 1 0 … x1,1, x1,2, x2,1,
Add to Exercise 13-7(a)-(f) the following:(g) Compute the subgradient direction of Algorithm 13C at your solution of (f)and take a step using lambda = 500 to update the dual solution. Then re-solve
Do Exercise 13-7 for the generalized assignment model min 15x1,1 + 10x1,2 + 30x2,1 + 20x2,2 s .t. x1,1 + x1, 2 = 1 x2,1 + x2,2 = 1 30x1,1 + 50x2,1 … 80 30x1,2 + 50x2,2 … 60 x1,1, x1,2, x2,1, x2,2
Consider the binary integer program min 5x1 - 2x2 s .t. 7x1 - x2 Ú 5 x1, x2 binary(a) Formulate and justify a Lagrangian relaxation dualizing the only main constraint with multiplier v.(b) Briefly
Consider the following binary ILP:max 13x1 + 22x2 + 18x3 + 17x4 + 11x5 + 19x6 + 25x7 s.t. a 7j = 1xj … 3 3x1 + 7x2 + 5x3 … 15 12x4 + 9x5 + 8x6 + 6x7 … 11 xj binary, j = 1,c, 7(a) State the
Consider the tiny LP constraint set-w1 + w2 … 1 w1 + 2w2 Ú 1 w1, ww Ú 0(a) Sketch the feasible set of these constraints in a 2-dimensional plot.(b) Establish that the feasible set is convex.(c)
Consider solving the following 4-variable LP by Dantzig-Wolfe Decomposition Algorithm 13D. Constraints 1 and 2 will constitute the linking problem, numbers 3-5 the first subproblem, and numbers 6-8
Do Exercise 13-13 on the following LP starting with extreme points 1x1, x22 = 10, 02 and 1x3, x42 = 136, 02 in part (e). min 200x1 +350x2 +450x3 +220x4 s.1. 2x1 + 1x2 + 4x3 + 3x4 100 5x1 + 5x2 + 9x3
Consider solving the following MILP by Benders Decomposition Algorithm 13E. Treat the y variables as the complicating ones, and begin with y102 = 10, 02.max 60x1 + 50x2 - 25y1 - 100y2 s.t. 20x1 +
Consider solving the the following minimum total cost facilities location model with Benders Decomposition Algorithm 13E, taking numbers on supply nodes as the fixed cost and capacity (if opened),
Consider the following Binary Knapsack Problem (BKP) instance max 7x1 + 9x2 + 21x3 + 15x4 s.t. 8x1 + 4x2 + 12x3 + 7x4 … 19 1BKP2 x1,c, x4 = 0 or 1(a) Construct the corresponding Dynamic Programming
Return to the (BKP) of Exercise 14-l.(a) Define a finite alphabet of symbols, and then show a binary encoding of that instance in terms of your alphabet.(b) Establish that your encoding of (a) has
is an instance of the Binary Knapsack Problem (BKP) form max a nj = 1cjxj s.t. a nj = 1ajxj … b x1,c, xn = 0 or 1(d) The Dynamic Programming algorithm of 14-1 solves instances of (BKP) by computing
Return to the Facilities Location Problem(FLP) of Chapter 11, definition 11.29 , and assume all parameters are integer.(a) Consider the following instance:Define a finite alphabet of symbols, and
Now return to the Fixed Charge Network Flow Problem (FCNP) of Chapter 11, definition 11.31 , and assume all data are integer.(a) Develop and justify an expression for the length of a binary encoding
(c) to your threshold problem 1FCNP…2 of (b).(e) How do (b), (c), and NP-Completeness of 1FLP…2 (Exercise 14-3(e)) lead to the conclusion that the threshold version 1FCNP…2 also belongs to
The Capital Budgeting Problem (CapBud)of Section 11.2 over a set of n proposed projects j using decision variables xj = 1 if project j is chosen and = 0 otherwise can be formulated as follows:max a
The Multi-dimensional Knapsack Problem(MKP) over n decision variables xj = 1 is object j is chosen and = 0 otherwise, can be formulated:max a nj = 1rjxj (maximize total return)s.t. a nj = 1aijxj …
Given a digraph G(V, E), the Vertex Cover problem (VCover) seeks a minimum cardinality subset of vertices that together touch every edge of E.(a) Show that the problem can be modeled in terms of
Return to the cardinality Vertex Cover problem (VCover) of Exercise 14-7(a). One algorithm to construct an approximately optimum set VQ ! 5i V: xi = 16 for the problem can be stated as follows: (i)
Return to the Traveling Salesman Problem(TSP) and the Twice-Around heuristic of Application 14.5. Then consider an instance on the 5 points in the following plot:Arcs can be assumed to exist between
Return to the lists of problems in Table 14.1. For each of the following pairs of problems in the table, establish that the first, polynomially solvable one is a special case of the NP-Hard second,
Consider solving (approximately) the following knapsack problem by constructive search Algorithm 15A.max 11x1 + 1x2 + 9x3 + 17x4 s.t. 9x1 + 2x2 + 7x3 + 13x4 … 17 x1,c, x4 = 0 or 1(a) Determine a
Do Exercise 15-1 for the knapsack model(this time with increasing ratio order)min 55x1 + 150x2 + 54x3 + 180x4 s.t. 25x1 + 30x2 + 18x3 + 45x4 Ú 40 x1,c, x4 = 0 or 1
Now consider knapsack instance max 30x1 + 20x2 + 20x3 s.t. 21x1 + 20x2 + 20x3 … 40 x1, x2, x3 = 0 or 1(a) Determine a global optimum by inspection(b) Now apply Constructive Search Algorithm l5A
Do Exercise 15-3 for the knapsack instance min 10x1 + 10x2 + 3x3 s.t. 10x1 + 10x2 + 6x3 Ú 20 x1, x2, x3 = 0 or 1
Recall the Traveling Salesman Problem(TSP) of Section 11.5, which seeks a minimum total length cycle (or tour) of a given graph G(V, E) that includes all nodes of V. One constructive algorithm for
Return to the (TSP) instance of Exercise 15-5(b). This time construct an approximately optimal tour by the Greedy Insertion strategy used on the KI Truck Routing application in Figure 15.1.
Consider a simplified Vehicle Routing Problem (VRP) over the customer sites in the following plot (refer to Section 11.5).Two 5-customer routes are to be designed, both originating and returning to
Classic Bin Packing (BP) considers the task of packing a collection of items j = 1,c, n of varying sizes aj into a minimum number N of bins of capacityb. The first-fit algorithm to solve instances
Consider solving (approximately) the ILP max 5x1 + 7x2 - 2x3 s.t. x2 + x3 … 1 x1, x2, x3 = 0 or 1 by a version of discrete improving search Algorithm 15B that employs move set M = 511, 0, 02, 10,
Repeat Exercise 15-9 for the ILP min 2x1 - 11x2 + 14x3 s.t. x1 + x2 + x3 Ú 1 x1, x2, x3 = 0 or 1

Showing 2800 - 2900 of 4620

First
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Last

Services

Sitemap
Fun
Definitions
Become Tutor
Study Help Categories
Recent Questions
Expert Questions

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Campus Ambassador

Secure Payment

Download Our App

© 2024 SolutionInn. All Rights Reserved