false

Class Notes
(838,800)

Canada
(511,100)

University of Waterloo
(18,599)

CO 250
(44)

Christine Dupont
(9)

Lecture

Unlock Document

Combinatorics and Optimization

CO 250

Christine Dupont

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.