Student Solution Manual For Deterministic Operations Research

14 CHAPTER 3. TotWorkers : sum(i in Products, j in Lines) Workers(i,j) maxWorkers forall(j in Lines) do WL(j) : sum(i in Products) Workers(i,j) maxWorkers * OpenLine(j) OpenLine(j) is binary end-do forall(i in Products) do Prod(i) : sum(j in Lines) ProdAmts(i,j) * Workers(i,j) Demand(i) forall(j in Lines) Workers(i,j) is integer end-do TotCost : sum(i in Products, j in Lines) WorkerCost(j) * Workers(i,j) sum(j in Lines) SetupCost(j) * OpenLine(j) minimize(TotCost) The optimal cost is 30,500, obtained by opening Line 2, with 5 workers on Product 2 and 8 workers on Product 3, and Line 3, with 5 workers on Product 1 and 2 workers on Product 2. This solution produces 600 units of Product 1, 810 units of Product 2, and 1000 units of Product 3. 3.7 Let x(i, j) denote whether reactor i is set to setting j. Our model is then given below. forall(i in Reactors) do SelectSetting(i) : sum(j in Settings) x(i,j) 1 forall(j in Settings) do x(i,j) is binary end-do end-do AnnualProduction : sum(i in Reactors, j in Settings) Pounds(i,j) * x(i,j) Demand TotCost : sum(i in Reactors, j in Settings) Cost(i,j) * x(i,j) minimize(TotCost) The optimal cost is 425, found by setting Reactor 1 to setting 4, Reactor 2 to setting 1, Reactor 3 to setting 2, and Reactor 4 to setting 4. 3.10 The optimal tour is 1 3 2 7 6 4 8 5 1 with length 67. The MTZ model is given below. ! Objective: minimize the total delay TotalDist: sum(i,j in Holes i j) Dist(i,j)*x(i,j) ! Visit every city once

15 forall(i in Holes) sum(j in Holes i j) x(i,j) 1 forall(j in Holes) sum(i in Holes i j) x(i,j) 1 forall(i,j in Holes i j) x(i,j) is binary forall(i, j in Holes i 1 and j 1 and i j) uij(i,j) : u(j) u(i) 1 - (NHoles-1)*(1 - x(i,j)) u(1) 1 forall(i in Holes i 1) do u(i) 2 u(i) NHoles end-do ! Solve the problem minimize(TotalDist) 3.22 Let Build(i) denote whether Depot i is built and x(i, j) denote whether customer j’s demand is satisfied by depot i. Our model is then as follows: forall(j in Customers) sum(i in Depots) x(i, j) 1 forall(i in Depots) do sum(j in Customers) Demands(j) * x(i,j) Capacity(i) Build(i) is binary end-do forall(i in Depots, j in Customers) do x(i, j) Build(i) x(i,j) is binary end-do TotCost : sum(i in Depots) Cost(i) * Build(i) sum(i in Depots, j in Customers) DelivCosts(i,j) * Demands(j) * x(i,j) minimize(TotCost) Our optimal cost is 95,022,025.00. We are to build Depots 5 and 6, with Depot 5 servicing customers 5, 6, 9, 10, and 11, while Depot 6 servicing customers 1, 2, 3, 4, 7, 8. 3.36 We will assume that the coefficients aj and b are integers, and that M is chosen so that M n X j 1 aj b M.

16 CHAPTER 3. The inequalities n X aj b M (1 y) j 1 b 1 n X aj M y j 1 satisfy the condition. When y 1 we must have n X j 1 n X j 1 aj b 1. aj b, while when y 0 we must have

Chapter 4 4.1 Errata: Distances d25 d52 should be 35 instead of 40. Since our total capacity is 335, we need 3 trucks to satisfy these routes. The initial tours included routes 1 2 3 1, 1 4 5 1, 1 6 7 1; unfortunately, the demand on the first route exceeds that truck capacity. Our subtour elimination constraint is then x23 2 2 0, since at least two different trucks are needed for customers 2, 3. Adding this constraint generates the tour 1 2 4 1, which again violates the truck capacity. Adding the constraint x24 0 and resolving generates the feasible tours 1 2 7 1, 1 4 6 1, 1 3 5 1 which has length 175 miles. 4.4 The is the Set Covering Location Model (Integer Program 4.2). We need 2 facilities: facility 5, which can service customers {1, 2, 4, 5, 8, 10} and facility 6, which can service customers {1, 2, 3, 6, 7, 8, 9, 10}. 4.7 This is a p-median problem (Integer Program 4.5). If we locate the facility at 6, the total weighted distance is 2610. 4.9 This is a Fixed-Charge Location Problem (Integer Program 4.6). The optimal cost is 9335 incurred by opening facilities 6 and 7, where 6 serves customers {1, 2, 5, 6, 8, 9, 10} and 7 serves {3, 4, 7}. 17

18 CHAPTER 4.

Chapter 5 Note: None of the algorithms presented here are the only solutions. Acceptable heuristics need only produce solutions based upon “reasonable” approaches to the problem. 5.1 Ordering the variables according to their ackk ratios gives the order x4 , x3 , x7 , x5 , x2 , x8 , x6 , x1 . In the first 4 iterations, we set x4 1, x3 1, x7 1, x5 1. After fixing x5 1 we find that there is only bb 4 units available in the right-hand side, which means that x1 and x8 must be set to 0. In the next iteration we fix x2 1, which then fixes x6 0. Our greedy heuristic generates the solution (0, 1, 1, 1, 1, 0, 1, 0). 5.2 One approach starts with the solution x (1, 1, . . . , 1), where the variables are ordered so that c1 c2 cn ··· . a1 a2 an At iteration k we set xk 0 if we can maintain feasibility. In our sample problem, the variables are considered in the order x1 , x6 , x2 , x8 , x5 , x7 , x3 , x4 , producing the solution (0, 0, 1, 1, 1, 0, 1, 0). 5.4 Our initial vector d (5, 2, 3, 4, 2, 2, 3, 4, 4, 3, 2, 2). We set x1 1 first, and so our updated d is d ( , 1, 0, 2, 0, 2, 0, 1, 1, 3, 2, 1). Setting x10 1 next we get d ( , 1, 0, 0, 0, 0, 0, 1, 1, , 0, 0). If we set x2 1 next, we get d 0, and so our greedy solution is (1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0). 5.9 (a) The Nearest Neighbor Heuristic finds the ordering 3 2 4 6 7 8 5 1 3 with distance 68. (b) The Cheapest Insertion Heuristic finds the ordering 1 3 2 4 7 6 8 5 1 with distance 69. 19

20 CHAPTER 5. (c) For the Nearest Neighbor solution, exchanging the edges (2, 4) and (7, 8) with (2, 7) and (4, 8) results in a tour of length 67. No other improvements are possible by exchange. For the Cheapest Insertion solution, exchanging the edges (4, 7) and (6, 8) with (4, 6) and (7, 8) results in the Nearest Neighbor solution, which then can be improved one more time. Each results in the ordering 3 2 7 6 5 8 5 1 3 with distance 67. (d) The optimal solution is the 2-opt solution in part (c). It needed 0 subtour elimination constraints: 5.11 One approach is to mimic the Cheapest Insertion Heuristic. For each pair of initial hole locations i1 , i2 , the next hole drilled is the cheapest inserted into either of the current subtours generated. 5.16 One approach is to schedule, at time t, the job that minimizes max{t pj , dj } among all unscheduled jobs j. For example, suppose Jb is the set of unscheduled jobs (so that initially Jb {1, . . . , 9}). Since min max{0 pj , dj } 23 j Jb for job j 6, job 6 is schedule first and Jb Jb {6}. Now starting at time t 8 (since job 6 has p6 8), min max{8 pj , dj } 35 j Jb for job j 1. Continuing this yields the job sequence 6 1 3 8 2 5 7 9 4.

Chapter 6 6.1(i) Note that f (3, 4, 6) for every x and we are maximizing our objective. (a) Not an improving direction since f T d 7 0. (b) Is an improving direction since f T d 15 0. (c) Is an improving direction since f T d 2 0. 6.2 (a) Starting at x0 (1, 0, 2), x 1 x 0 λ1 d1 (1, 0, 2) 2(3, 2, 1) (7, 4, 0). 2 x x 1 λ2 d2 (7, 4, 0) 4(1, 0, 3) (11, 4, 12). x 3 x 2 λ3 d3 1 (11, 4, 12) ( 1, 4, 0) 2 21 ( , 6, 12). 2 6.3 (a) We have f (6x 2y, 2y 2x), and so f (1, 3) (0, 4) with search direction d f . Our next solution is then x1 (1, 3) λ(0, 4) (1, 3 4λ). To find our step size, we find the smallest positive local minimum of g(λ) 3(1)2 2(1)(3 4λ) (3 4λ)2 10 16λ2 16λ 4. Since g ′ (λ) 32λ 16 0 at λ 12 , this is our step size. 6.5 (b) Our next solution is of the form x′ (3 2λ, 1 λ, 5 3λ), which remains 0 as long as λ 1 and λ 53 . Putting this solution into the constraint yields 2(3 2λ) 4(1 λ) (5 3λ) 5 3λ 20, 21

22 CHAPTER 6. which implies that λ 5 in order to remain feasible. Thus, the maximum step size in this direction is b min{1, 5 , 5} 1. λ 3 6.10 (a) Since only the first constraint and the bound x2 0 is active we need 2d1 d2 d3 12 0 6.1. One direction is given in Exercise 6.21. To show that a function that is both convex and concave must be affine means that we must show that the function h(x) f (x) f (0) is linear, i.e. that it satisfies h(αx βy) αh(x) βh(y). Note that f (x) satisfies f (λx (1 λ)y) λf (x) (1 λf (y) for all 0 λ 1. This can be done by showing each of the following: (a) h( 21 x 12 y) 21 h(x) 12 h(y). (b) h(αx) αh(x) for 0 α 1. (c) h(x y) h(x) h(y). (d) h( x) h(x). (e) h(βx) βh(x) for β 1. It follows from these notions that h(x) is linear.

Chapter 7 7.1 The extreme points are (0, 0), (0, 2), (4, 0), (4, 2), and ( 34 , 14 3 ), as noted below. 7.5 The convex hull of P is described by the constraints 4x y 13 x 3y 5 5x y 7 y 7. The extreme points are exactly the elements of P 23

24 CHAPTER 7. 7.7 (a) One possible objective function (note there are many) for each extreme point is given below: Extreme Point (0, 7) (1, 2) (4, 3) (5, 7) Objective max y x min x y max x y max x y 7.14 (c) max s.t. 4x1 2x2 7x3 2x1 x2 4x3 s1 18 4x1 2x2 5x3 s2 10 x1 , x2 , x3 , s1 , s2 0.

25 7.15 (c) max 4 2 7 0 s.t. 2 1 4 2 x1 x2 0 x3 s1 s2 4 1 5 0 0 x1 x2 0 x3 0 . s1 0 0 s2 x1 x2 0 x3 18 10 1 s1 s2 7.21 (c) Basic feasible solutions are: Basic Feasible Solution (0, 0, 29 , 0, 25 2 ) (0, 0, 2, 10, 0) (0, 5, 0, 23, 0) (9, 0, 0, 0, 26) ( 52 , 0, 0, 13, 0) Basic Variables x3 , s2 x3 , s1 x2 , s1 x1 , s2 x1 , s1 7.33 The feasible region is given below. (a) The extreme points are (0, 0), (0, 4), and (2, 0). Nonbasic variables x1 , x2 , s1 x1 , x2 , s2 x1 , x3 , s1 x2 , x3 , s2 x2 , x3 , s2 .

26 CHAPTER 7. (b) The extreme directions are ( 31 , 32 ) and ( 21 , 21 ). (c) The objective vector c (cx , cy ) for which there is a finite optimal solution must satisfy cT d 0 for every unbounded direction, or 1 cx 2 1 cx 3 1 cy 0 2 2 cy 0 3 (d) The objective vector c must satisfy cT d 0 for some unbounded direction d, which implies either 1 1 1 2 2 cx 2 cy 0 or 3 cx 3 cy 0.

Chapter 8 8.1 After adding slack variables s1 , s2 , s3 our initial basic feasible solution is x0 (0, 0, 0, 2, 3, 8) with B {s1 , s2 , s3 }. Iteration 1: The simplex direction for variable x1 is dx1 (1, 0, 0, ds1 , ds2 , ds3 ) (1, 0, 0, 1, 2, 6), where dB (ds1 , ds2 , ds3 ) is found by solving 1 1 0 0 ds1 0 1 0 ds2 2 . 6 ds3 0 0 1 Its reduced cost is cx1 8, and hence it is an improving direction. The simplex direction for variable x2 is dx2 (0, 1, 0, ds1 , ds2 , ds3 ) (0, 1, 0, 1, 3, 6), where dB (ds1 , ds2 , ds3 ) is found by solving 1 1 0 0 ds1 0 1 0 ds2 3 . 6 ds3 0 0 1 Its reduced cost is cx1 9, and hence it is an improving direction. The simplex direction for variable x3 is dx3 (0, 0, 1, ds1 , ds2 , ds3 ) (0, 0, 1, 2, 4, 2), where dB (ds1 , ds2 , ds3 ) is found by solving 2 1 0 0 ds1 0 1 0 ds2 4 . 2 ds3 0 0 1 Its reduced cost is cx1 3, and hence it is an improving direction. Using Dantzig’s rule, we choose x2 as our entering variable. By the Ratio Test, our step size is 3 8 2 , , λmax min ( 1) ( 3) ( 6) 1. 27

28 CHAPTER 8. Our leaving variable is then s2 . Our new basic feasible solution is 0 0 0 1 1 0 0 0 0 1 x 1 1 1 2 3 0 3 2 6 8 with basis B {x2 , s1 , s3 }. Iteration 2: The simplex direction for variable x1 is dx1 (1, dx2 , 0, ds1 , 0, ds3 ) (1, 23 , 0, 13 , 0, 2), where dB (dx2 , ds1 , ds3 ) is found by solving 1 1 0 1 dx 2 3 0 0 ds1 2 . 6 0 1 ds3 6 Its reduced cost is cx1 8 32 (9) 2, and hence it is an improving direction. The simplex direction for variable x3 is dx3 (0, dx2 , 1, ds1 , 0, ds3 ) (0, 43 , 1, 23 , 0, 6), where dB (dx2 , ds1 , ds3 ) is found by solving 1 1 0 2 dy 3 0 0 ds1 4 . 6 0 1 ds3 2 Its reduced cost is cx3 5 (9)( 43 ) 7, and hence it is not an improving direction. The simplex direction for variable s2 is ds2 (0, dx2 , 0, ds1 , 1, ds3 ) (0, 13 , 0, 31 , 1, 2), where dB (dx2 , ds1 , ds3 ) is found by solving 0 dy 1 1 0 3 0 0 ds1 1 . 0 ds3 6 0 1 Its reduced cost is cx3 0 (9)( 13 ) 3, and hence it is not an improving direction. Using Dantzig’s rule, we choose x1 as our entering variable. By the Ratio Test, our step size is 1 1 2 λmax min , , ( 23 ) ( 13 ) ( 2) 1. Our leaving variable is then s3 . Our new basic feasible solution is 1 1 0 1 2 1 3 3 0 0 0 2 x 1 1 2 1 3 3 0 0 0 2 2 0

29 with basis B {x1 , x2 , s1 }. Iteration 3: The simplex direction for variable x3 is 5 dx3 (dx1 , dx2 , 1, ds1 , 0, 0) (3, 10 3 , 1, 3 , 0, 0), where dB (dx1 , dx2 , ds1 ) is found by solving 1 1 1 2 dx 1 2 3 0 dx2 4 . ds1 6 6 0 2 Its reduced cost is cx3 5 8(3) 9( 10 3 ) 1, and hence it is not an improving direction. The simplex direction for variable s2 is ds2 (dx1 , dx2 , 0, ds1 , 1, 0) (1, 1, 0, 0, 1, 0), where dB (dx1 , dx2 , ds1 ) is found by solving 0 1 1 1 dx 1 2 3 0 dx2 1 . 0 ds1 6 6 0 Its reduced cost cs2 0 8(1) 9( 1) 1, and hence it is not an improving direction. The simplex direction for variable s3 is ds3 (dx1 , dx2 , 0, ds1 , 0, 1) ( 12 , 31 , 0, 61 , 0, 1), where dB (dx1 , dx2 , ds1 ) is found by solving 0 1 1 1 dx 1 2 3 0 dx2 0 . 1 ds1 6 6 0 Its reduced cost is cs3 0 8( 12 ) 9( 13 ) 1, and hence it is not an improving direction. Since there are no improving simplex directions, our current solution x2 (1, 31 , 0, 32 , 0, 0) is optimal. 8.1. (a) The Phase I linear program is min s.t. a2 a3 x1 x2 s1 2x1 x3 a2 3x2 5x3 s3 x 1 , x 2 , x 3 , s 1 , s 3 , a2 , a3 0 18 12 a3 15 (b) Starting with the basic variables B {s1 , a2 , a3 }, we have the following simplex method iterations when solving the Phase I problem:

30 CHAPTER 8. Iteration 1 2 3 Basis B {s1 , a2 , a3 } {x3 , s1 , a2 } {x1 , x3 , s1 } cN ( 2, 3, 4, 1) ( 2, 35 , 51 , 54 ) (0, 0, 1, 1) deB (0, 1, 5) ( 1, 2, 0) Entering var x3 x1 Leaving var a3 a2 21 The optimal solution the the Phase I problem has xB (x1 , x3 , s1 ) ( 15 2 , 3, 2 ) with value 0. Our initial problem has a feasible solution. (c) Starting from the Phase I solution (after removing a2 , a3 from the problem), we have the following simplex method iterations: Iteration 1 2 Basis B {x1 , x3 , s1 } {x1 , x3 , s3 } cN ( 5, 2) ( 19, 20) Entering var s3 deB 1 1 1 ) ( 10 , 5 , 10 Leaving var s1 The optimal solution the the Phase II problem (and to the original problem) has xB (x1 , x3 , s3 ) (18, 24, 105). 8.18 The feasible region is given below. The extended basic feasible solutions and partitions are as follows: Extended BFS (0, 0, 11, 26) (5, 0, 6, 11) (5, 2.2, 1.6, 0) (2, 4, 1, 0) (0, 4, 3, 6) (B, L, U ) ({s1 , s2 }, {x, y}, ) ({s1 , s2 }, {y}, {x}) ({y, s1 }, {s2 }, {x}) ({x, s1 }, {s2 }, {y}) ({s1 , s2 }, {x}, {y}) 8.20 The bounded simplex method iterations are given below. We start with the extended basic feasible solution (0, 0, 11, 26) (after adding slack variables).

31 Iteration 1 2 3 4 (B, L, U ) ({s1 , s2 }, {x, y}, ) ({s1 , s2 }, {x}, {y}) ({x, s1 }, {s2 }, {y}) ({y, s1 }, {s2 }, {x}) 8 The optimal solution is (5, 11 5 , 5 , 0). xB (11, 26) (3, 6) (2, 1) 8 ( 11 5 , 5) cN (2, 3) (2, 3) ( 13 , 23 ) ( 15 , 35 ) Entering var y x y deB ( 2, 5) ( 1, 3) ( 53 , 31 ) Leaving var y s2 x

32 CHAPTER 8.

Chapter 9 9.1 min s.t. 20y1 8y2 10y3 2y1 3y3 8 3y1 y2 y3 20 2y1 y2 4 y1 , y2 0, y3 0 9.6 (a) At this solution the basic variables are B {x1 , x2 , x3 } the reduced cost vector is then cTN cTN cTB B 1 N 0 2 0 0 9 14 1 4 2 7 5 0 1 1 3 1 0 4 1 0 1 2 0 0 0 (b) The dual is min s.t. 6y1 12y2 5y3 2y1 5y2 9 y1 4y2 2y3 14 3y1 y2 7 y1 , y2 , y3 0 (c) The optimal dual solution is cTB B 1 2 1 33 4 0 0 1

34 CHAPTER 9.

Chapter 10 10.1 (a) The optimal solution occurs at the intersection of two constraints whose slopes are 32 and 21 . Based upon this, the range of values are 5 cx 15 and 6 cy 18. (b) First consider constraint 1, which we alter to x 2y 30 . As we increase from 0, the optimal solution remains at the intersection of the first two constraints until the bound x 0 becomes active. Thus the largest value of for which the optimal solution lies at the intersection of the first two constraints is found by solving x 2y 30 3x 2y 42 x 0, which gives 12. Similarly, decreasing the value of from 0 has the optimal solution at the intersection of the first two constraints until the third constraint is also active. Solving these equations yields 8. Thus, for the optimal solution to be at the intersection of the first two constraints, we must have that the right-hand side value of the first constraint be between 30 8 22 and 30 12 42. For all values of in this range, the optimal solution is at x 6 21 and y 12 43 , and the objective value is 174 3 . This indicates that the shadow price for this constraint is 3. Similar analysis for the second constraint yields the range 42 12 30 b2 42 72 7 with a shadow price of 2. The third constraint is not active at the o

One solution is to never hire any additional employees and to fire 4 employees in month 1 and 1 in month 4. We produce 5000, 6400, 6600, 5000, 6000, and 5000 shoes in the respective months, which will produce inventory in months 2 (1400 shoes) and 4 (1000 shoes).