College aantekeningen

Introduction to Linear Optimization Solution Manual PDF

13 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.

[Meer zien]

Voorbeeld 3 van de 20 pagina's

Bekijk voorbeeld

Geupload op 13 maart 2024
Aantal pagina's 20
Geschreven in 2023/2024
Type College aantekeningen
Docent(en) Luis solari
Bevat Alle colleges

introductio
introduction to linear optimization solutions
introduction linear optimization solution manual
solutions introduction to linear optimization
introduction to linear optimization answers pdf

Titel boek:Introduction To Linear Optimization

Auteur(s):Dimitris Bertsimas, John N. Tsitsiklis

Uitgave:Onbekend
ISBN:9781886529199
Druk:Onbekend

Instelling
University of San Andrés (UdeSA )
Vak
MAPF

Volgen

SolutionsWizard

Lid sinds 6 jaar 291 documenten verkocht

€9,80

In winkelwagen

Op verlanglijstje

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

Solution Manual For:
Introduction to Linear Optimization
by Dimitris Bertsimas & John N. Tsitsiklis

John L. Weatherwax∗

November 22, 2007

Introduction

Acknowledgements

Special thanks to Dave Monet for helping find and correct various typos in these solutions.

Chapter 1 (Introduction)

Exercise 1.1

Since f (·) is convex we have that

f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) . (1)

Since f (·) is concave we also have that

f (λx + (1 − λ)y) ≥ λf (x) + (1 − λ)f (y) . (2)

Combining these two expressions we have that f must satisfy each with equality or

f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y) . (3)

This implies that f must be linear and the expression given in the book holds.
∗

1

,Exercise 1.2

Part (a): We are told that fi is convex so we have that

fi (λx + (1 − λ)y) ≤ λfi (x) + (1 − λ)fi (y) , (4)

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)

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

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,80. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 68175 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis

College aantekeningen

Introduction to Linear Optimization Solution Manual PDF

Document informatie

Onderwerpen

Gekoppeld boek

Geschreven voor

Verkoper

Ontvangen beoordelingen

Voorbeeld van de inhoud