Class Notes
(809,120)

Canada
(493,535)

University of Waterloo
(18,180)

Computer Science
(752)

CS 115
(43)

Christine Dupont
(2)

Lecture

# hw1.pdf

Unlock Document

University of Waterloo

Computer Science

CS 115

Christine Dupont

Fall

Description

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 qualiﬁes as cheating. For more details review the
ofﬁcial university guidelines at http://www.math.uwaterloo.ca/navigation/Current/cheating 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 ﬁle, see http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm for information about
penalties.
If you have complaints about the marking of assignments, then you should ﬁrst 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 ofﬁce 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 deﬁning 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 satisﬁed 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 sufﬁcient to satisfy three out of the four constraints (1)-(4).
Formulate, this problem as an integer

More
Less
Related notes for CS 115