CO250 I NTRODUCTION TO O PTIMIZATION – HW 6
Due Date: Friday, March 2, by 2PM, in the drop box outside the Tutorial Centre.
LATE 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
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 drop box 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. It will be returned in class. If you still have concerns
after this, 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.
Exercise 1 (20 marks).
For each of the following LP problems, write the dual problem.
subject to(1,0,−3)x ≥ −1
(−1,2,3)x ≤ 8
(4,5,−2)x = 4
x2 ≥ 0
x3 ≤ 0
maximize c x + d u
subject toAx + Bu = b
Dx + Eu ≥ e
u ≥ 0
(Here A is m by n, B is m by p, D is q by n, E is q by p, and c ∈ R , d ∈ R , b ∈ R , and
e ∈ R .)
Exercise 2 (20 marks).
It is possible for both (P) and (D) to be infeasible, where (P) and (D) are a primal-dual pair.
(a) Construct such a pair, each having two variables, following the suggestion made in