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 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 grading. All academic offenses are reported to the Associate Dean for Undergraduate Studies and are recorded in the student’s file, 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 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 ($) per serving

Calories per serving

Fat (g) per serving

Protein (g) per serving

Carbohydrade (g) 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