Textbook Notes (363,082)
BU385 (90)
Chapter

# assign6.sol.pdf

4 Pages
135 Views

School
Wilfrid Laurier University
Department
Course
BU385
Professor
Barry Mc Clinchey
Semester
Fall

Description
CO250 I NTRODUCTION TO O PTIMIZATION– HW 6 S OLUTIONS Exercise 1. (a) minimize (−1,8,4)y subject to (1,−1,4)y = 4 (0,2,5)y ≥ −5 (−3,3,−2)y ≤ 6 y ≤ 0 1 y ≥ 0 2 (b) minimize b y + e v subject toA y + D v = c B y + E v ≥ d v ≤ 0 Exercise 2. (a) Consider the primal-dual pair maximize x1 + x 2 subject tox1 − x 2 ≤ −2 (P) : −x 1 + x 2 ≤ 1 x1, x 2 ≥ 0 and minimize −2y1 + y2 subject to y1 − y2 ≥ 1 (D) : −y 1 + y2 ≥ 1 y1, y2 ≥ 0 Then (P) is infeasible, because adding the ﬁrst two constra1nts,2we get 0x + 0x ≤ −1, which cannot be satisﬁed. Also (D) is infeasible because adding the ﬁrst two cons1raints, we get 0y + 0y2≥ 2, which cannot be satisﬁed. (b) A simpler pair is maximize x minimize −y 1 1 (P) : subject to0x ≤ −1 and (D) : subject to0y ≥ 1 1 1 x ≥ 0 y ≥ 0 1 1 1 2 or, even a bit simpler: (P) : maximize x1 and (D) : minimize y1 subject to0x1 = 1 subject to0y1 = 1 Exercise 3. (a) The optimal value of (P) is the largest number that is less than or equal to every a . i This is equal to the leastiof the a . (b) The dual problem (D) is X Xm minimize ai isubject to yi= 1,y ≥ 0. i=1 i=1 Each feasible solution corresponds to a weighted 1ve2age ofma ,a ,...,a . The objective is to ﬁnd the least such weighted average. (c) Note that the dual obviously has a feasible solution, and is not unbounded, so it has an optimal solutio¯. Suppose thak a is the minimum ofithe a , and su¯j> 0 for some j for which aj> ak. Then, if we decr¯jby a small amount and incr¯kby the same amount, we will get a feasible solution with decreased objective value, con¯ is optimal. Therefi > 0y only ifia =ka . Therefore, the optimal objective value is X ak ¯i= ak, i=1 as required. Exercise 4. (a) The dual problem is Max 4y1 − 2y2 y1 + y2 ≥ 3 2y − y ≥ 1 1 2 2y + y ≥ 4 1 2 y1 − y2 ≥ 1
More Less

Related notes for BU385

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.