deteministic model in operation researsh

University of Miami, Department of Industrial Engineering Assignments 5-6

1

Due Date: April 24 – in class Problem No. 1

A book salesperson who lives in Basin must call once a month on four customers located in Wald, Bon, Mena, and Kiln before returning home to Basin. The following table gives the distances in miles among the different cities.

Basin Wald Bon Mena Kilm Basin 0 120 220 150 210 Wald 120 0 80 110 130 Bon 220 80 0 160 185 Mena 150 110 160 0 190 Kilm 210 130 185 190 0

The objective is to minimize the total distance traveled by the salesperson. Develop the full LP associated with this problem. Do not use algebraic form for the constraints.

University of Miami, Department of Industrial Engineering Assignments 5-6

2

Problem 2. The ABC Mall conducts special events to attract potential patrons. Among the events that seem to attract teenagers, the young/middle aged group, the senior citizens, the two most popular are band concerts and art shows. Their costs per presentation are $ 2000 and $4500, respectively. The total (strict) annual budget allocated to the two events is $20,000. The mall manager estimates the attendance as follows: Number attending per presentation: Event Teenagers Young/middle age seniors Band concert 150 90 10 Art Show 60 350 250 The manager has set minimum goals of 900, 1500 and 800 for the attendance of teenagers, the young/middle-aged group, and seniors, respectively. Formulate the problem as a goal programming (GP) model (use the Weights method to develop the objective function of the GP, feel free to make any reasonable assumption).

University of Miami, Department of Industrial Engineering Assignments 5-6

3

Problem 3.

University of Miami, Department of Industrial Engineering Assignments 5-6

4

University of Miami, Department of Industrial Engineering Assignments 5-6

5

Problem 5

A contractor estimates that the size of the workforce needed over the next 6 weeks is 4, 7, 9, 7, 6, and 8 workers, respectively. Excess labor kept on the force will cost $400 per worker per week, and new hiring (including week 1) in any week will incur a fixed cost of $300 plus $220 per worker. The cost of firing is $50 per worker. a) Find the optimal hiring schedule using Backward Recursion DP. You need to

include all steps.

b) Write down the LP for the above problem (extra credit).

University of Miami, Department of Industrial Engineering Assignments 5-6

6

Problem No. 6. Consider the following LP. Min z = 30x1+40x2+7x3 2x1 +4x2 ≤ 3 -2x1+4x2 + x3 ≥ -4 2x1+3x2 +4x3 = 9 x1≥ 0, x2 ≥ 0, x3:urs a) Find the Dual of the above LP.

University of Miami, Department of Industrial Engineering Assignments 5-6

7

Problem 7.

The LP and the final simplex Tableau for Problem No. 4 on page 119 of the textbook (the problem description is attached) are as follows:

a) Use the dual prices to prioritize the three processes for possible expansion. Explain why? b) If additional production hours can be allocated, what would be a fair cost per additional hour for each process?

© 2011 Pearson Education, Inc., Upper Saddle River, NJ. All rights reserved. This publication is protected by Copyright and written permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permission(s), write to: Rights and Permissions Department, Pearson Education, Inc., Upper Saddle River, NJ 07458.

© 2011 Pearson Education, Inc., Upper Saddle River, NJ. All rights reserved. This publication is protected by Copyright and written permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permission(s), write to: Rights and Permissions Department, Pearson Education, Inc., Upper Saddle River, NJ 07458.

University of Miami, Department of Industrial Engineering Assignments 5-6

8

Problem No. 8.

Consider the following LP.

a) Develop the dual LP associated with this problem.

b) We know that the optimal solution of primal is x1 = 5/3, x2 = 8/3, x3 =0. Use Complementary Slackness to find the optimal dual solutions.

Using Complementary Slackness to Solve LPs

If the optimal solution to the primal or dual is known, complementary slackness can sometimes be used to determine the optimal solution to the complementary problem. For example, suppose we were told that the optimal solution to the Dakota problem was z ! 280, x1 ! 2, x2 ! 0, x3 ! 8, s1 ! 24, s2 ! 0, s3 ! 0. Can we use Theorem 2 to help us find the optimal solution to the Dakota dual? Because s1 " 0, (40) tells us that the opti- mal dual solution must have y1 ! 0. Because x1 " 0 and x3 " 0, (43) implies that the optimal dual solution must have e1 ! 0, and e3 ! 0. This means that for the optimal dual solution, the first and third constraints must be binding. We know that y1 ! 0, so we know that the optimal values of y2 and y3 may be found by solving the first and third dual con- straints as equalities (with y1 ! 0). Thus, the optimal values of y2 and y3 must satisfy

4y2 # 2y3 ! 60 and 1.5y2 # 0.5y3 ! 20

Solving these equations simultaneously shows that the optimal dual solution must have y2 ! 10 and y3 ! 10. Thus, complementary slackness has helped us find the optimal dual solution y1 ! 0, y2 ! 10, y3 ! 10. (From the Dual Theorem, we know, of course, that the optimal dual solution must have w! ! 280.)

P R O B L E M S Group A

328 C H A P T E R 6 Sensitivity Analysis and Duality

1 Glassco manufactures glasses: wine, beer, champagne, and whiskey. Each type of glass requires time in the molding shop, time in the packaging shop, and a certain amount of glass. The resources required to make each type of glass are given in Table 32. Currently, 600 minutes of molding time, 400 minutes of packaging time, and 500 oz of glass are available. Assuming that Glassco wants to maximize revenue, the following LP should be solved: max z ! 6x1 # 10x2 # 9x3 # 20x4 s.t. 4x1 # 9x2 # 7x3 # 10x4 $ 600 (Molding

constraint) s.t. x1 # x2 # 3x3 # 40x4 $ 400 (Packaging

constraint) s.t. 3x1 # 4x2 # 2x3 # x4 $ 500 (Glass

constraint) x1, x2, x3, x4 % 0

It can be shown that the optimal solution to this LP is z ! &283 00&,

x1 ! & 40

3 0

&, x4 ! & 2 3 0 &, x2 ! 0, x3 ! 0, s1 ! 0, s2 ! 0, s3 ! &&

28 3 0

&.

a Find the dual of the Glassco problem. b Using the given optimal primal solution and the The- orem of Complementary Slackness, find the optimal so- lution to the dual of the Glassco problem. c Find an example of each of the complementary slack- ness conditions, (40)–(43). As in the text, interpret each example in terms of shadow prices.

2 Use the Theorem of Complementary Slackness to show that in the LINDO output, the SLACK or SURPLUS and DUAL PRICE entries for any row cannot both be positive.

3 Consider the following LP: max z ! 5x1 # 3x2 # x3 s.t. 2x1 # x2 # x3 $ 6 s.t. x1 # 2x2 # x3 $ 7

x1, x2, x3 % 0 Graphically solve the dual of this LP. Then use comple- mentary slackness to solve the max problem.

TA B L E 32

Glass

x1 x2 x3 x4 Wine Beer Champagne Whiskey

Molding time 4 minutes 9 minutes 7 minutes 10 minutes Packaging time 1 minute 1 minute 3 minutes 40 minutes Glass 3 oz 4 oz 2 oz 1 oz Selling price $6 $10 $9 $20