Homepage › Solution manuals › Dimitris Bertsimas › Introduction to Linear Optimization

Dimitris Bertsimas

Introduction to Linear Optimization

Introduction to Linear Optimization

This book provides a unified, insightful, and modern treatment of linear optimization, that is, linear programming, network flow problems, and discrete optimization. It includes classical topics as well as the state of the art, in both theory and practice.

1. Introduction

Exercise 1.1* (Concave convex functions are affine)

Exercise 1.10 (Production and inventory planning)

Exercise 1.11 (Optimal currency conversion)

Exercise 1.12 (Chebychev center)

Exercise 1.13 (Linear fractional programming)

Exercise 1.14

Exercise 1.15

Exercise 1.16 (Oil refinery problem)

Exercise 1.17 (Investment under taxation)

Exercise 1.18

Exercise 1.19

Exercise 1.2 (Sum of convex functions)

Exercise 1.20

Exercise 1.3

Exercise 1.4

Exercise 1.5 (Linear optimization problem with absolute values)

Exercise 1.6 (Rocket control)

Exercise 1.7 (The moment problem)

Exercise 1.8 (Road lighting)

Exercise 1.9 (Distance to school and student distribution)

2. The geometry of linear programming

Exercise 2.1

Exercise 2.10

Exercise 2.11

Exercise 2.12

Exercise 2.13

Exercise 2.14

Exercise 2.15 (Edges joining adjacent vertices)

Exercise 2.16

Exercise 2.17

Exercise 2.18

Exercise 2.19* (Dimension of polyhedra)

Exercise 2.2

Exercise 2.20*

Exercise 2.21

Exercise 2.22 (Sum of polyhedra)

Exercise 2.3 (Basic feasible solutions in standard form polyhedra with upper bounds)

Exercise 2.4

Exercise 2.5 (Extreme points of isomorphic polyhedra)

Exercise 2.6 (Carathéodory's theorem)

Exercise 2.7

Exercise 2.8

Exercise 2.9 (Degeneracy and bases)

3. The simplex method

Exercise 3.1 (Local minima of convex functions)

Exercise 3.10*

Exercise 3.12

Exercise 3.13 (Matrix inversion lemma)

Exercise 3.14

Exercise 3.15 (Perturbation approach to lexicography)

Exercise 3.16 (Lexicography and the revised simplex method)

Exercise 3.17

Exercise 3.18

Exercise 3.19

Exercise 3.2 (Optimality conditions)

Exercise 3.20

Exercise 3.21

Exercise 3.22 (Standard form optimization problem with one constraint)

Exercise 3.23

Exercise 3.24

Exercise 3.25

Exercise 3.26 (The big-$M$ method)

Exercise 3.27

Exercise 3.28 (Convexity constraint)

Exercise 3.29 (Basic points are affinely independent)

Exercise 3.3 (Feasibility conditions)

Exercise 3.30 (Distance from the dual plane is the reduced cost)

Exercise 3.33

Exercise 3.4

Exercise 3.5

Exercise 3.6 (Conditions for a unique optimum)

Exercise 3.7 (Optimality conditions)

Exercise 3.8*

Exercise 3.9 (Necessary and sufficient conditions for a unique optimum)

4. Duality theory

Exercise 4.1

Exercise 4.10 (Saddle points of the Lagrangean)

Exercise 4.11

Exercise 4.12* (Degeneracy and uniqueness - I)

Exercise 4.13* (Degeneracy and uniqueness - II)

Exercise 4.16

Exercise 4.19 (Null variables)

Exercise 4.2 (Self-dual problems)

Exercise 4.21* (Clark's theorem)

Exercise 4.26

Exercise 4.28

Exercise 4.3 (Solving linear programming problems is no harder than solving systems of linear inequalities)

Exercise 4.31 (Unit eigenvectors of stochastic matrices)

Exercise 4.35 (Separation of disjoint polyhedra)

Exercise 4.4

Exercise 4.5

Exercise 4.6* (Duality in Chebychev approximation)

Exercise 4.7 (Duality in piecewise linear convex optimization)

Exercise 4.8

5. Sensitivity analysis

Exercise 5.1

6. Large Scale Optimization

Exercise 6.8

7. Network Flows

Exercise 7.1 (The caterer problem)

Exercise 7.21 (Finding a feasible solution)

Exercise 7.30 (The primal-dual method as steepest dual ascent)

10 Integer programming formulations

Exercise 10.1 (Disjunctive constraints)

Exercise 10.2 (Selection of the dream team)