Introduction to Linear Optimization Solution Manual PDF
363 keer bekeken 6 keer verkocht
Vak
MAPF
Instelling
University Of San Andrés (UdeSA
)
Boek
Introduction To Linear Optimization
Complete Answers Solutions Manual PDF for Introduction to Linear Optimization by Dimitris Bertsimas and John N. Tsitsiklis. Includes the answers for all the exercises of the book.
for every i. For our function f (·) we have that
m
X
f (λx + (1 − λ)y) = fi (λx + (1 − λ)y) (5)
i=1
m
X
≤ λfi (x) + (1 − λ)fi (y) (6)
i=1
Xm m
X
= λ fi (x) + (1 − λ) fi (y) (7)
i=1 i=1
= λf (x) + (1 − λ)f (y) (8)
and thus f (·) is convex.
Part (b): The definition of a piecewise linear convex function fi is that is has a represen-
tation given by
fi (x) = Maxj=1,2,...,m (c′j x + dj ) . (9)
So our f (·) function is
n
X
f (x) = Maxj=1,2,...,m (c′j x + dj ) . (10)
i=1
Now for each of the fi (x) piecewise linear convex functions i ∈ 1, 2, 3, . . . , n we are adding
up in the definition of f (·) we will assume that function fi (x) has mi affine/linear functions
to maximize over. Now select a new set of affine values (c̃j , d˜j ) formed by summing elements
from each of the 1, 2, 3, . . . , n sets of coefficients from the individual fi . Each pair of (c̃j , d˜j )
is obtained by summing one of the (cj , dj ) pairs from each of the n sets. The number of
such coefficients can be determined as follows. We have m1 choices to make when selecting
(cj , dj ) from the first piecewise linear convex function, m2 choices for the second piecewise
linear convex function, and so on giving a total of m1 m2 m3 · · · mn total possible sums each
producing a single pair (c̃j , d˜j ). Thus we can see that f (·) can be written as
f (x) = Maxj=1,2,3,...,Qnl=1 ml c̃′j x + d˜j , (11)
since one of the (c̃j , d˜j ) will produce the global maximum. This shows that f (·) can be
written as a piecewise linear convex function.
Exercise 1.3 (minimizing a linear plus linear convex constraint)
We desire to convert the problem min(c′ x + f (x)) subject to the linear constraint Ax ≥ b,
with f (x) given as in the picture to the standard form for linear programming. The f (·)
, given in the picture can be represented as
−ξ + 1 ξ<1
f (ξ) = 0 1<ξ<2 (12)
2(ξ − 2) ξ > 2,
but it is better to recognize this f (·) as a piecewise linear convex function given by the
maximum of three individual linear functions as
f (ξ) = max (−ξ + 1, 0, 2ξ − 4) (13)
Defining z ≡ max (−ξ + 1, 0, 2ξ − 4) we see that or original problem of minimizing over the
term f (x) is equivalent to minimizing over z. This in tern is equivalent to requiring that z
be the smallest value that satisfies
z ≥ −ξ + 1 (14)
z ≥ 0 (15)
z ≥ 2ξ − 4 . (16)
With this definition, our original problem is equivalent to
Minimize (c′ x + z) (17)
subject to the following constraints
Ax ≥ b (18)
z ≥ −d′ x + 1 (19)
z ≥ 0 (20)
z ≥ 2d′ x + 4 (21)
where the variables to minimize over are (x, z). Converting to standard form we have the
problem
Minimize(c′ x + z) (22)
subject to
Ax ≥ b (23)
′
dx+z ≥ 1 (24)
z ≥ 0 (25)
′
−2d x + z ≥ 4 (26)
Exercise 1.4
Our problem is
Minimize(2x1 + 3|x2 − 10|) (27)
subject to
|x1 + 2| + |x2 | ≤ 5 . (28)
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper SolutionsWizard. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €9,69. Je zit daarna nergens aan vast.
