I only recently learned about linear programming. I started with PuLP and Python to get a grasp. It was one of those "How did I miss this??" moments as a developer.
The Google OR-tools library is also a good starting point.
I learned about linear programming in uni, but alas I don't think a mathematician's course on linear programming would be a good starting point for practical programmers.
For positive integers m and n,
have a m x n matrix A of real numbers. Then also have n x 1 x, 1 x n c, and m x 1 b. Seek x to solve
LP1:
maximize z = cx
subject to
Ax = b
x >= 0
Instead just as easily can do minimize.
Instead of =, might be given >= and/or <=, but use slack and/or surplus variables to get the problem in the form of LP1.
Any x so that
Ax = b
x >= 0
is feasible. If there is such an x, then LP1 is feasible; else LP1 is infeasible. If LP1 is feasible and for any feasible x we have z bounded above, then LP1 is bounded and has an optimal x (z as large as possible) solution. Else feasible LP1 is unbounded above.
So, LP1 is feasible or not. If feasible, then it is bounded or not. If bounded, then there is at least one optimal solution.
Regard n x 1 x as a point in R^n for the real numbers R.
Cute: If all the numbers in LP1 are rational, then have no need for the reals.
The set of all feasible x is the feasible region and is closed (in the usual topology of R^n) and convex. If LP1 is bounded, then there is at least one optimal x that is an extreme point of the feasible region. So, it is sufficient to look only at the extreme points.
To determine if LP1 is feasible or not, and if feasible bounded or not, and
if bounded to find an optimal x, can use the simplex algorithm which is just some carefully selected linear algebra elementary row operations on
z = cx
Ax = b
The iterations of the simplex algorithm have x move from one extreme point to an adjacent one and as good or better on z.
A LOT is well known about LP1 and the simplex algorithm. There is a simpler version for a least cost network flow problem where move from one spanning tree to another.
If insist that the components of x be integers, then are into integer linear programming and the question of P = NP. In practice there is a lot known about ILP, e.g., via G. Nemhauser.
I used to teach LP at Ohio State -- there are lots of polished books from very elementary to quite advanced.
I attacked some practical ILP problems successfully.
I got into ILP (set covering, a darned clever idea since get to handle lots of goofy, highly non-linear constraints, costs, etc. efficiently) for scheduling the fleet at FedEx. The head guy at FedEx wrote me a memo making that problem my work -- officially I reported to the Senior VP Planning, but for that ILP work in every real sense reported to the head guy. The promised stock was very late, so I went for a Ph.D. and got good at lots of math, including optimization, LP, and ILP, etc.
Conclusion: A career in LP or ILP is a good way to need charity or sleep on the street -- literally, no exaggeration.
For some of what AI is doing or trying to do now, LP/ILP stands to be tough competition, tough to beat. And same for lots more in the now old applied math of optimization. Bring a strong vacuum cleaner to get the thick dust off the best books.
