Optimization models so far
The earlier network problems can be written as optimization models: choose decision variables, impose constraints, and optimize a linear objective function.
Max flow
Decision variable: f(i,j) for each arc.
Subject to flow conservation at intermediate nodes and capacity bounds 0 ≤ f(i,j) ≤ u(i,j).
Assignment
Decision variable: xij, equal to 1 when worker i is assigned to task j.
The LP relaxation replaces xij∈{0,1} by 0≤xij≤1.
Linear function
A function is linear when it can be written as a constant plus a weighted sum of the variables.
No products of variables, powers, ratios of variables, or nonlinear functions appear.
Linear programming
Definition
A linear program is an optimization problem with a linear objective function and constraints of type ≤, ≥, or =, with linear functions on both sides.
The chapter focuses on LPs that can be put in the standard simplex form used here:
subject to Ax ≤ b, x ≥ 0, b ≥ 0.
This is narrower than general linear programming, but it is enough to explain the simplex method clearly. Other forms can be transformed into this one by standard modeling steps.
What an LP solver needs
- Objective coefficients c.
- Constraint coefficients A.
- Right-hand sides b.
- A rule for moving between feasible corner solutions.
A one-variable LP
The chapter first solves a one-variable example by inspection and with a number-line picture.
Try the interval constraints
Result
Graphical solution in two variables
For two variables, each linear inequality cuts out a half-plane. The feasible region is the intersection of these half-planes. Objective values form parallel lines, and the best line touches the feasible region at a corner.
subject to x≤4, y≤2, 2x+y≤6, y−x≤1, x,y≥0.
LP data
Feasible region and optimum
Vertices
Simplex dictionary workbench
The simplex method rewrites the same LP in a sequence of dictionaries. Each dictionary has an associated feasible solution: set all nonbasic variables to zero and read off the basic variables.
Dictionary form
Every constraint is an equality, every variable is nonnegative, each constraint has one unique basic variable on the left, and the objective uses only the nonbasic variables on the right.
Build an LP
Current dictionary
Dictionary table
Pivot status
Ratio test
Associated solution
Simplex path for two-variable LPs
When the loaded LP has two original variables, the path below shows the corner points visited by the dictionaries.
Pivot log
Chapter simplex walkthrough
The chapter’s three-variable LP is a compact example where each pivot has a visible algebraic meaning.
subject to x1≤4, x2≤4, x1+x2≤6, −x1+2x3≤4, x≥0.
First dictionary
Geometry of the simplex method
In two dimensions, the dictionary solutions are corner points of the feasible region. A pivot increases one nonbasic variable until a constraint becomes tight. Geometrically, this moves along an edge of the polygon until the next corner is reached.
For the chapter’s two-variable example, the path described by the chosen pivots is:
The final point has objective value 3·2 + 2·2 = 10. Once the objective dictionary has no positive coefficient, the constant term gives an upper bound that is met by the associated feasible solution.
Corner-point intuition
The simplex method does not search the whole feasible region. It moves between special feasible solutions represented by dictionaries. For bounded LPs with an optimum, this is enough because a best solution can be found at a corner of the feasible region.
Summary of the simplex method
Algorithm
- Set up the first dictionary. Replace each ≤ constraint by an equality using a new nonnegative slack variable.
- Improve if possible. Choose a nonbasic variable with positive objective coefficient.
- Apply the ratio test. Increase that variable until some basic variable would become zero; that basic variable leaves.
- Pivot. Solve the leaving equation for the entering variable and substitute everywhere.
- Stop when no positive objective coefficient remains. The current associated solution is optimal.
Optimality argument
The pivot steps are algebraic rewritings, so they do not change the feasible region or objective function. In the final dictionary, the objective has the form z = z0 − nonnegative terms. Since all variables are nonnegative, no feasible solution can have objective value above z0. The associated dictionary solution reaches exactly z0, so it is optimal.
