Class notes

Introduction to Linear Optimization Solution Manual PDF

14 purchases

Course
MAPF

Institution
University Of San Andrés (UdeSA )

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

[Show more]

Preview 3 out of 20 pages

View example

Uploaded on March 13, 2024
Number of pages 20
Written in 2023/2024
Type Class notes
Professor(s) Luis solari
Contains All classes

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

Book Title:Introduction To Linear Optimization

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

Edition:Unknown
ISBN:9781886529199
Edition:Unknown

Institution
University of San Andrés (UdeSA )
Course
MAPF

SolutionsWizard

Member since 6 year 310 documents sold

R186,70

Add to cart

Save

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

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)

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.

Quick and easy check-out

You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.

Focus on what matters

Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!

Frequently asked questions

What do I get when I buy this document?

You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.

Satisfaction guarantee: how does it work?

Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.

Who am I buying this summary from?

Stuvia is a marketplace, so you are not buying this document from us, but from seller SolutionsWizard. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy this summary for R186,70. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

66184 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy summaries for 15 years now

Start selling

Class notes

Introduction to Linear Optimization Solution Manual PDF

Document information

Subjects

Connected book

Written for

Seller

Reviews received

Content preview