CO250 I NTRODUCTION TO O PTIMIZATION – HW 8
Due Date: Friday, March 16, by 2PM, in the drop box outside the Tutorial Centre.
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
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 questions 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).
Let (P) denote the LP problem max(c x : Ax ≤ b, x ≥ 0), and let (D) be the dual of (P). The goal of
this exercise is to prove the strong Duality Theorem for (P) and (D). (In the Course Notes we proved strong
duality only for problems in SEF.)
(a) Convert (P) into an equivalent problem (P ) in SEF.
(b) Find the dual (D ) of (P ).′
(c) Suppose that (P) has an optimal solution x ¯. Construct an optimal solution x of (P ). ′
(d) Using the Strong Duality Theorem for problems in SEF, deduce that there exists an optimal solution
y to (D ) where the value of x for (P ) is equal to the value of y for (D ). ′
(e) Deduce that there exists an optimal solution¯ for (D) where the value of ¯ for (P) is equal to the
value of ¯ for (D).
Exercise 2 (20 marks).
Let (P) denote the problem max(c x : Ax ≤ b).
(a) Suppose that (P) has a feasible solution, and that there exists a vect