Textbook Notes
(363,082)

Canada
(158,181)

Wilfrid Laurier University
(7,615)

Business
(2,364)

BU385
(90)

Chapter

# assign6.sol.pdf

Unlock Document

Wilfrid Laurier University

Business

BU385

Barry Mc Clinchey

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