Class Notes (809,120)
Canada (493,535)
CS 115 (43)


5 Pages
Unlock Document

University of Waterloo
Computer Science
CS 115
Christine Dupont

CO250 I NTRODUCTION TO O PTIMIZATION – HW 1 Due Date: Friday, January 13th, by 2PM, in the drop box outside the Tutorial Center. L ATE ASSIGNMENTS WILL NOT BE GRADED . Important information: While it is acceptable to discuss the course material and the assignments, you are expected to do the assignments on your own. Copying or paraphrasing a solution from some fellow student or old solutions from previous offerings of related courses qualifies as cheating. For more details review the official university guidelines at policy.shtml. We will instruct the TAs to actively look for suspicious similarities and evidence of academic offenses when grad- ing. All academic offenses are reported to the Associate Dean for Undergraduate Studies and are recorded in the student’s file, see for information about penalties. If you have complaints about the marking of assignments, then you should first check your solutions against the posted solutions. After that if you see any marking error, then you should return your assignment paper to the Head Teaching Assistants (see syllabus) within one week and with written notes on all the marking errors; please write the notes on a new sheet and attach it to your assignment paper. If you still have concerns after talking to the TA then contact your instructor. You may ask question about assignments on the discussion board available on the course webpage. We also provide tutorials and office hours, for more information consult the syllabus. Please USE THE COVER SHEET that is available at the end of the assignment. It is imperative that you indicate your full name and student ID (as we have many students with the same last name). Failure to use the cover sheet will result in a 5% deduction on the assignment mark. For each of these questions you are asked to formulate the problem as either a linear program, or an integer program. You are NOT asked to actually solve the formulation, i.e. compute the optimal values. Your solutions should be easy to modify if we change the constants defining the problems. Exercise 1 (20 marks). The director of the CO-Tech startup needs to decide what salaries to offer to its employees for the year 2012. In order to keep the employees satisfied she needs to satisfy the following constraints: 1. Tom wants at least 20’000$ or he will quit; 2. Peter, Nina, and Samir want each to be paid at least 5000$ more than Tom; 3. Gary wants his salary to be at least as high as the combined salary of Tom and Peter; 4. Linda wants her salary to be 200$ more than Gary; 1 2 5. The combined salary of Nina and Samir should be at least twice the combined salary of Tom and Peter; 6. Bob’s salary is at least has high as that of Peter and at least as high as that of Samir; 7. The combined salary of Bob and Peter should be at least 60’000$; 8. Linda should make less money than the combined salary of Bob and Tom. a) Write a linear program that will determine salaries for the employee of CO-tech that satisfy each of these constraints while minimizing the total salary expenses. b) Write a linear program that will determine salaries for the employee of CO-tech that satisfy each of these constraints while minimizing the salary of the highest paid employee of CO-tech. Exercise 2 (20 marks). Consider the following table indicating the nutritional value of different food types. Foods Price ($) Calories Fat (g) Protein (g) Carbohydrade (g) per serving per serving per serving per serving per serving Raw Carrots 0.14 23 0.1 0.6 6 Baked Potatoes 0.12 171 0.2 3.7 30 Wheat Bread 0.2 65 0 2.2 13 Cheddar Cheese 0.75 112 9.3 7 0 Peanut Butter 0.15 188 16 7.7 2 You need to decide how many servings of each food to buy each day so that you minimize the total cost of buying your food while satisfying the following daily nutritional requirements: 1. calories must be at least 2000, 2. fat must be at least 50g, 3. protein must be at least 100g, 4. carbohydrates must be at least 250g. (a) Write a linear program that will decide how many servings of each of the aforementioned foods we need to meet all the nutritional requirement, while minimizing the total cost of the food (you may buy fractional numbers of servings). (b) Similar as part (a), but now assume that it is sufficient to satisfy three out of the four constraints (1)-(4). Formulate, this problem as an integer
More Less

Related notes for CS 115

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


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.