image

One can conveniently describe a linear programming problem by stating the goal as minimizing / maximizing a function given a set of constraints.

image

The word “linear” restricts the objective function and constraints to have a linear form. Despite this seemingly harsh restriction, LP can be used to attack a LOT of problems. This book is a Linear Programming 101 book and a book with visuals. I am a big fan of books with visuals. The first thing the author emphasizes is

It is rather difficult to optimize or even to determine an overall measure of effectiveness, and thus, one attempts to suboptimize— break up the problem into tractable subproblems, each subproblem consisting of an applicable measure of effectiveness and associated constraints.

Given this background, the author urges to look for subproblems and frame a mathematical model around it. The book gives some textbook type examples to illustrate the basics of LP. Subsequently it gives a description of a few generic problems that LP can solve:

  • Problems based on Graphs/Networks
  • Traveling Salesman Problem
  • Game theory problems that don’t have a saddle point

The appendix flushes out the math behind the simplex, integer programming, mixed integer programming etc. The theorems mentioned in the appendix can serve as a good motivation to look up more math oriented books on LP. This book can serve as a good supplementary read for a course on Linear/ Integer programming.

A nice quote from the book relevant to teachers :

Do not try to satisfy your vanity by teaching a great many things. Awake their curiosity. It is enough to open their minds, do not overload them. Put there just a spark. If there is some good inflammable stuff, it will catch fire.

-- Anatole France