false

Study Guides
(248,457)

Canada
(121,562)

University of Waterloo
(5,732)

CO 250
(11)

Christine Dupont
(5)

Unlock Document

Combinatorics and Optimization

CO 250

Christine Dupont

Winter

Description

UNIVERSITY OF WATERLOO
MIDTERM EXAMINATION
WINTER TERM 2013
Student Name (Print Legibly)
(family name) (given name)
Signature
Student ID Number
COURSE NUMBER CO 327
COURSE TITLE Deterministic OR Models
COURSE SECTION 001
DATE OF EXAM Tuesday, March 5, 2013
TIME PERIOD 4:00 - 6:00 pm
DURATION OF EXAM 2 hours
NUMBER OF EXAM PAGES (Including cover page) 12 pages
INSTRUCTORS P. Roh
EXAM TYPE Closed Book
ADDITIONAL MATERIALS ALLOWED Calculator (Non-graphing)
Notes: Marking Scheme:
1. Fill in your name, ID number, and
Question Mark Out of
sign the paper.
2. Answer all questions in the space 1 18
provided. Indicate if you use the
back of a page if necessaryShow 2(a-c) 6
your work and give FORMAL solu- 2(d) 14
tions. Leave yopr answers in exact
form, such as 5 +7, 4=3▯ sin( ), 2(e-f) 7
10
etc. 2(g-h) 12
3. Check that the examination has 12
pages.
4. Your grade will be in
uenced 2(i-j) 8
by how clearly you express your 3 10
ideas, and how well you organize
your solutions. Total 75
DO NOT WRITE FORMULAS ON THE COVER PAGE. CO 327 - Midterm Examination Winter 2013 Page 2 of 12
1. For these questions, write a linear program to solve the given problem.
(a) (Assume all items are liquids.)
Roh Pharmaceuticals (RP) makes medicine by recycling expired drugs. They can
buy up to 50,000L of expired drugs from another company for $0.24 per L. They can
process one L of expired drugs to create 0.3 units of drug A and 0.4 units of drug B.
They can also process one unit of drug A further such that they obtain 2 units of
drug C. These drugs are mixed in di▯erent ways to produce the following products:
Product How to get one unit
X 0.2 units drug A, 0.8 units drug C
Y 0.3 units drug B, 0.7 units drug C
Z 0.4 units drug A, 0.4 units drug B, 0.2 units drug C
The demand and price for these products is the following:
Product X Product Y Product Z
Demand (in units) 20;000 25;000 30;000
Price (per unit) $1:12 $1:24 $2:02
Excess amounts of drugs can be stored for later use but any products that are made
must be sold.
What should RP do to make the most pro▯t?
(Include an explanation of what each variable/constraint in your LP represents.)
Solution:
1. Variables
Let s represent how much of expired drug in purchased in L.
Let xA;xBrepresent how much of drug A and B is produced after processing the
expired drugs, C represent how much of drug C is produced after processing
drug A.
Let k represent how much of drug A is used to make drug C.
Let wab represent how much of drug a is used to make product b.
Let vX;vY;vZrepresent how much of product X, Y and Z is produced.
All variables are non-negative.
2. Objective Function
maximize 1:12X + 1:24vY+ 2:02vZ▯ 0:24s
3. Constraints
There is a limit of how much expired drug can be purchased:
s ▯ 50;000
The amounts of drug A and B produced is based on how much expired drug is
purchased:
0:3s = xA 0:4s = B
To produce drug C, you use a certain amount of drug A:
x = 2k
C
We can only process and mix drugs if there is any:
k + wAX + wAZ ▯ x A wBY + w BZ ▯ xB w CX + wCY + w CZ▯ x C
We have to mix the drugs to produce the products:
wAX = 0:2vX w CX = 0:8vX w BY = 0:3Y wCY = 0:7vY
wAZ = 0:4vZ w BZ = 0:4Z wCZ = 0:2vZ
Amount of products made should not exceed demand:
vX ▯ 20;000 vY▯ 25;000 vZ▯ 30;000 CO 327 - Midterm Examination Winter 2013 Page 3 of 12
1.(a) (continued)
The resulting LP is
maximize 1:12X + 1:24Y + 2:02Z ▯ 0:24s
subject to s ▯ 50;000
0:3s = x
A
0:4s = x B
2k = x C
k + wAX+ w AZ ▯ x A
w BY+ w BZ ▯ x B
w CX + wCY+ w CZ ▯ x C
w AX = 0:2vX
wCX = 0:8vX
w BY = 0:3vY
w = 0:7v
CY Y
w = 0:4v
AZ Z
w BZ = 0:4vZ
w CZ = 0:2vZ
vX ▯ 20;000
vY ▯ 25;000
vZ ▯ 30;000
xA;xB;xC;k;s;vX;vY;vZ ▯ 0
wab ▯ 0 8a 2 fA;B;Cg;b 2 fX;Y;Zg
(Don’t really neabvariables, but put in to make the solution easier to understand.) CO 327 - Midterm Examination Winter 2013 Page 4 of 12
(b) A company CEO wants something done based on certain restrictions. These restric-
tions can be represented mathematically by the following system of linear equations:
2x + 3x + 4x = 5
1 2 3
▯x + x ▯ 3x = 7
1 2 3
x2+ 4x 3 = ▯9
3x1▯ x 2 = ▯1
But of course the silly CEO has made too many restrictions such that no solution
exists. Find the solution that comes closest to satisfying the restrictions.
(Include an explanation of what each variable represents.)
Solution:
Let z1= j2x + 1x + 4x2▯ 5j, 3 = j ▯ x2+ x ▯ 3x 1 7j, 2 = jx 3 4x + 9j3 2 3
z4= j3x 1 x + 2j.
The LP to ▯nd the solution that comes closest to satisfying the restrictions is:
minimize z + z + z + z
1 2 3 4
subject to 2x 1 3x + 2x ▯ 53▯ z 1
▯2x ▯13x ▯ 42 + 5 3 z 1
▯x 1 x ▯ 2x ▯ 73▯ z 2
x1▯ x +23x + 3 ▯ z 2
x 2 4x +39 ▯ z 3
▯x ▯24x ▯ 3 ▯ z 3
3x 1 x +21 ▯ z 4
▯3x +1x ▯ 2 ▯ z 4 CO 327 - Midterm Examination Winter 2013 Page 5 of 12
2. Roh So Sweet (RSS) is a candy company that makes 4 di▯erent kinds of candy. The candy
is made from 3 di▯erent ingredients: caramel, chocolate, and sugar.
The following LP is used by RSS to determine how to maximize revenue where x is ihe
number of pieces of candy i to make:
maximize 3x1+ 4x 2 6x +39x 4
subject to x1+ 2x 2 2x +32x 4 ▯ 1;000 (caramel)
2x1+ x 2 2x +33x 4 ▯ 1;200 (chocolate)
2x + 2x + x + x ▯ 2;000 (sugar)
1 2 3 4
x ▯ 0
The LP is converted into Standard Equality Form by adding the slack variables x ,5x ,6
and x7to the constraints for caramel, chocolate, and sugar respectively.
The optimal tableau looks like the following:
2 3
1 2:75 0 0:5 0 0:75 2:5 0 3750
6 7
6 0 ▯0:25 1 0:5 0 0:75 ▯0:5 0 150 7
4 0 0:75 0 0:5 1 ▯0:25 0:5 0 350 5
0 1:75 0 ▯0:5 0 ▯1:25 0:5 1 1350
(a) What is the optimal dual solution of the LP without determining the dual LP?
Solution:
Since the original LP was given in Standard Inequality Form, we can read the value
of the optimal dual variables using the tableau.
By reading the values in row zero for the slack variables, the optimal dual solution is
y 1 0:75, y 2 2:5, y 3 0.
(b) What are the shadow prices for caramel, chocolate, and sugar?
Solution:
Since our LP was given in Standard Inequality Form, the shadow prices are equal
to the corresponding dual solution. The shadow prices are 0.75 for caramel, 2.5 for
chocolate, and 0 for sugar.
(c) If you did NOT know the optimal tableau and only knew the optimal solution, could
you have determined any of the shadow prices in part (b)? Explain why.
Solution:
Since the optimal solution has slack variable x7= 1350 > 0, there is no need to
purchase any more sugar to make more candy. As a result, RSS would be unwilling
to pay for more sugar so the shadow price of sugar must be zero. CO 327 - Midterm Examination Winter 2013 Page 6 of 12
(d) For each coe▯cient cjin the objective function of the original LP, determine what
values c can be changed to and the optimal solution will NOT change.
j
Solution:
The optimal basis is B = f2;4;7g.
For j = 1, it is not in the optimal basis. Since the optimal tableau has 2.75 in (0,1),
we can change c1by ▯ 1 2:75 so c 1an stay in the range
▯1 ▯ c ▯15:75 = 3 + 2:75
For j = 2, it is in the optimal basis. Assuming we chang2 c b2 ▯ , then we have the
equivalent tableau:
2 3
1 2:75 ▯▯ 2 0:5 0 0:75 2:5 0 3750
6 0 ▯0:25 1 0:5 0 0:75 ▯0:5 0 150 7
4 0 0:75 0 0:5 1 ▯0:25 0:5 0 350 5
0 1:75 0 ▯0:5 0 ▯1:25 0:5 1 1350
Performing row operations we get the canonical form for the basis B = f2;4;7g:
2 3
1 2:75 ▯ 0:25▯2 0 0:5 + 0:5▯2 0 0:75 + 0:75▯2 2:5 ▯ 0:52 0 3750 + 150▯ 2
6 0 ▯0:25 1 0:5 0 0:75 ▯0:5 0 150 7
4 5
0 0:75 0 0:5 1 ▯0:25 0:5 0 350
0 1:75 0 ▯0:5 0 ▯1:25 0:5 1 1350
To have B remain an optimal basis, we require
2:75 ▯ 0:252 ▯ 0 ) ▯ ▯ 21
0:5 + 0:52 ▯ 0 ) ▯ ▯ 21
0:75 + 0:752 ▯ 0 ) ▯ ▯ 21

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.