CO327W13_a5_soln.pdf

11 Pages
95 Views
Unlock Document

Department
Combinatorics and Optimization
Course
CO 250
Professor
Christine Dupont
Semester
Winter

Description
Assignment 5 Due: Wednesday April 3 at the BEGINNING of class 1. A power plant has two boilers, which produce steam, and two turbines, which produce power from steam. The following two tables give the speci▯cations of the boilers and the turbines. The ▯rst table lists the ▯xed cost incurred in operating a boiler, the cost of producing a ton of steam on each boiler. The ▯rst table also lists the range in which the steam produced from the boiler must lie, if the boiler is operated. The second table lists the range of the amount of steam that can be processed on a turbine, the power generated by the turbine, and the cost of processing steam on the turbine. Boiler Steam produced Fixed Cost Steam Production Cost (range in tons) To Operate (per ton) 1 [600, 1200] 1100 11 2 [400, 800] 850 9 Turbine Steam Capacity Power Generated Processing Cost (range in tons) (kWh/ton) (per ton) 1 [500, 700] 5 3 2 [550, 950] 6 4 To prevent damage to any equipment, any steam produced by the boilers must be processed by the turbines. Write an integer program to minimize the cost of generating exactly 6400 kWh or power. Solution: Let x a1d x be 2he amount of steam produced by boilers 1 and 2 respec- tively. Let 1 and y2be the amount of steam processed by turbines 1 and 2 respectively. Let z1and z 2e variables to indicate if boiler 1 and 2 respectively are operating or not. Let w 1nd w be2variables to indicate if turbine 1 and 2 respectively are operating or not. To minimize cost, the objective function is: minimize 1100z 1 850z +211x + 91 + 3y2+ 4y 1 2 For the constraints: ▯ To generate the required amount of power: 5y + 61 = 6420. ▯ The amount of steam produced in each boiler depends on whether we are using the boiler or not. We’ll use big-M constraints to express this: 600z 1 x ▯11200z 1 400z 2 x ▯2800z 2 (We used the range of the steam bounds for each boiler as the big-M’s.) ▯ The amount of steam processed in each turbine depends on whether we are using the turbine or not. We’ll use big-M constraints to express this: 500w ▯ y ▯ 700w 550w ▯ y ▯ 950w 1 1 1 2 2 2 We need to ensure that enough steam is produced for the turbines to process: x 1 x =2y + y1. 2 The entire IP is therefore: minimize 1100z 1 850z + 21x + 9x1+ 3y 2 4y 1 2 subject to 5y1+ 6y 2 = 6400 x1 ▯ 600z 1 x1 ▯ 1200z 1 x2 ▯ 400z 2 x2 ▯ 800z 2 y1 ▯ 500w 1 y1 ▯ 700w 1 y2 ▯ 550w 2 y2 ▯ 950w 2 x1+ x 2 = y + 1 2 z1;z2;w 1w 2 ▯ 1 x 1x 2y 1y 2z ;1 ;2 ;w1 2 ▯ 0 z1;z2;w 1w 2 integer 2. The Waterloo Maple Leafs is a local hockey team that has asked you to decide who should be playing during a power play. There are 10 members that can play positions Winger (W), Center (C), and/or Defense (D). The starting lineup needs exactly 5 play- ers where the number of players that can play each position is at least 2 for Winger, at least 1 for Center, and at least 1 for Defense (you can have a player represent more than one of these required positions). Players on the team are also ranked on their scoring ability from 1 to 5 (5 being the best). Each player’s number, position, scoring ability is listed below: Player # Player Positions Scoring Ability 1 W. Belak W, D 2 2 T. Bozak C 4 3 C. Franson D 3 4 M. Frazer D 1 5 N. Kadri W, C 5 6 P. Kessel W 5 7 J. McClement W, C 3 8 C. Orr W 1 9 D. Phaneuf D 3 10 D. Steckel W, C 1 There are some addition issues that need to be taken into account: ▯ D. Steckel doesn’t like J. McClement. To prevent any issues, the coach wants if D. Steckel plays, then J. McClement to not play. ▯ The coach usually prefers to play with at most one player who can play Defense. As well, he likes letting P. Kessel play. However, P. Kessel is a defensive liability. If he is playing, the coach would like there to be at least 3 players who can play Defense playing. ▯ T. Bozak doesn’t seem to score unless he is playing with P. Kessel. The coach only wants T. Bozak to play if P. Kessel is playing. ▯ The coach wants to make sure some players with size are playing but also keep some players with size on the bench. He would like exaclty one of the following two possibilities to occur: either 1) C. Orr to play and both W. Belak and M. Frazer to not play OR 2) both W. Belak and M. Frazer to play and C. Orr to not play. Write an integer program that can be solved to put the best total scoring ability to- gether to play during a power play. Solution: Let variable x be ised to indicate if the player with player # i is playing on the power play or not. To get the best total scoring ability, the objective function is: maximize 2x + 4x + 3x + x + 5x + 5x + 3x + x + 3x + x 1 2 3 4 5 6 7 8 9 10 For the constraints: 10 X ▯ To ensure there are exactly 5 players playing: x i 5. i=1 ▯ To ensure at least each position has the minimum required number of players that can play each position: x + x + x + x + x + x ▯ 2 for Winger 1 5 6 7 8 10 x + x + x + x ▯ 1 for Center 2 5 7 10 x 1 x +3x + x4 9 ▯ 1 for Defense ▯ To ensure J. McClement is not playing when D. Steckel is playing: x ▯ 1 ▯ x 10 7 or x7+ x 10▯ 1. ▯ To ensure there is either at most one player who can play Defense unless P. Kessel is playing then there is at least 3 players who can play Defense: we will use big-M constraints. We want if more than one player who can play Defense to play, then it must be because P. Kessel is playing so x 1 x +3x + x4▯ 4x 9 1 or 6 + x + x 1 4x +3x ▯ 14 6 9 (We choose 4 for big-M since we know at most 4 people that can play Defense.) We only want P. Kessel playing when there are at least 3 people who can play Defense playing so x1+ x +3x + 4 ▯ 3x9or x +6x + x1▯ 3x 3 x ▯40 6 9 ▯ To ensure T. Bozak plays only when P. Kessel is playing: x ▯ x or 2 ▯x ▯60. 2 6 ▯ For the scenarios involving C. Orr, W. Belak, and M. Frazer, we can use big-M constraints. Normally we indicate bigger situations with 1 and smaller situation with 0. However, we want x = 18when x +x = 0 1nd x4= 0 when x +8 = 2. 1 4 We can use 1 ▯ x to8reverse the interpretation of x . 8 As long as both W. Belak and M. Frazer are both playing, then C. Orr is not playing: x 1 x ▯42(1 ▯ x ) or8x + x 1 2x ▯42 8 We only want C. Orr not playing when W.Belak and M. Frazer are both playing: x1+ x ▯42(1 ▯ x ) o8 x + x1+ 2x 4 2 8 Combining both constraints gives: x + x 1 2x 4 2. 8 The entire IP is therefore: maximize 2x 1 4x +23x + 3 + 54 + 5x 5 3x +6x + 37 + x8 9 10 X10 subject to xi = 5 i=1 x1+ x +5x + 6 + x7+ x 8 10 ▯ 2 x 2 x +5x + 7 10 ▯ 1 x 1 x +3x + 4 9 ▯ 1 x7+ x 10 ▯ 1 x1+ x 3 x ▯44x + x6 9 ▯ 1 x1+ x 3 x ▯43x + x6 9 ▯ 0 x 2 x 6 ▯ 0 x1+ x +42x 8 = 2 0 ▯ x i 1 8i 2 f1;:::;10g x i integer 8i 2 f1;:::;10g 3. Give an integer program that can be used to ▯nd the maximum y value of the following function: 8 ▯4x ▯ 40 ▯40 ▯ x ▯ ▯20 < ▯3x ▯ 20 ▯20 ▯ x ▯ ▯10 y = > x + 15 ▯10 < x ▯ 20 : 2x + 10 20 < x ▯ 35 Solution: Let ▯ ;▯ ;▯ ;▯ be variables where 1 2 3 4 x = ▯40+▯ +▯ +▯ +▯ and 0 ▯ ▯ ▯ 20;0 ▯ ▯ ▯ 10;0 ▯ ▯ ▯ 30;0 ▯ ▯ ▯ 15 1 2 3 4 1 2 3 4 This breaks the values of x into 4 regions. For i = 1;2;3, let uibe a variable to indicate if x is past region i. To enforce
More Less

Related notes for CO 250

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit