Linear programming is a way to take liner constraints and find some optimum (maximum or minimum) value according to some value function.

The spreadsheet values for the line segments are as follows.

Note that column A contains the x1 point while there is one column for each of the line segments. Since two points are needed to specify a line segment, each of the other columns has to entries, one for each point.

A scatter plot with connected dots is used to plot the line segments. The chart appears as follows.

Here are the plotted lines.

A convex region is a region where any point in the region can be connected by a straight line (segment) to any other point in the region without leaving the region.

A straight line that passes through a convex region divides that convex region into two convex regions.

A linear constraint that is an inequality (i.e., "<=" or ">=") that splits a convex region into two convex regions has a feasible region that is one of those two convex regions.

Convex regions and linear constraints are the key idea that makes linear program work.

A non-convex region has at least one place where the straight line (segment) connecting two points inside the region has part of the line segment that lies outside the region.

Linear programming requires convex regions.

The feasible region of a linear programming problem is a convex region. That insight is what makes the linear programming method work, and also is why it works only for linear constraints and objective functions.

The value of the objective function z is the height above the x1:x2 plane. The z-lines, when projected onto the x1:x2 plane, are parallel. Note the lines for z=12 and z=24 (see the legend for ranges 0..12 and 12..24).

The z-lines, when projected onto the x1:x2 plane, are parallel. The projection is similar to like contour lines on a map that show the elevation above the plane, except that, for linear programming, the projected lines are straight and parallel.

The chart with the z-lines for z=12 and z=24 plotted in the x1:x2 plane appears as follows.

The optimum point must always be either a single vertex of the feasible region or any of the points on the line segment connecting two vertices of the feasible region.

The solution identification appears as follows. The optimum point is at the intersection of the lines for constraints (a) and (b).

Problem sizes involving more than 2 variables cannot be easily visualized, since we humans cannot easily visualize in more than 3 dimensions, and one dimension is needed for the objective function.

One way to abstract the linear programming problem to larger problem sizes is to use matrix algebra.

The linear constraints can be expressed in matrix form.

The matrix form can be expressed in symbolic form. In this case,

• A is a matrix,
• X is a column vector, and
• b is a column vector.

The general field is known as the field of combinatorial optimization and can involve real number approximations or integer constraints - called integer programming.

In general, integer programming is in general unbounded and not as restricted as constraint logic involving finite domains.

Linear programming is just one part of a field known as combinatorial optimization.