CO327mid_soln.pdf

12 Pages
148 Views
Unlock Document

Department
Combinatorics and Optimization
Course
CO 250
Professor
Christine Dupont
Semester
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

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