Theoretical books on linear programming.

545 Views Asked by At

I recently took a course on linear programming, and the professor of the course focuses on technical part, while I'm studing mathematics and need to know more theoretical things on the subject.

So it'll be good if you can suggest to me some books which mainly focus on the theoretical aspect of linear programming.

2

There are 2 best solutions below

1
On BEST ANSWER

I think that linear programming has a fundamental theorem, something that give the subject it's consistency. By "theoretical" I meant this.

The fundamental theorem of linear programming (depending on which sources you're using) says something like:

For every linear programming problem in standard form, the LP is either infeasible, has an optimal basic feasible solution, or is unbounded.

It's easy to prove this by reference to the simplex method and showing the simplex method always terminates in one of these three states with a result that acts as a certificate of infeasibility, optimality, or unboundedness.

You do need to show that degenerate cycling doesn't occur, but it's relatively easy to prove this doesn't occur if you are using Bland's rule or the lexicographic rule to select your pivots.

This is discussed in many textbooks on linear programming. Chvatal's Linear Programming is out of print but does a nice job of proving this in the first 3 chapters. You can also find this in Vanderbei's textbook on LP.

This particular "fundamental theorem of LP" does focus on what the simplex method can accomplish. You could certainly argue that the complementary slackness conditions are more fundamental and independent of the simplex method as one way to solve linear programming problems. For example, interior point methods for LP find optimal solutions that satisfy the complementary slackness conditions but aren't necessarily basic feasible solutions.

1
On

I had referred to the following books:

  1. Linear programming and network flows by Bazaraa, Jarvis and Sherali
  2. Understanding and Using Linear programming by Matousek and Gartner

I hope this helps!