Introduction to Linear programming

Linear programming is a standard method of solving problems involving maximizing (or minimizing) an objective function in the face of linear constraints of nonnegative variables. Some applications of LP are the following.

Marketing

Media selection
Marketing research

Financial

Portfolio selection
Financial-mix selection

Production management

Scheduling
Labor planning
Blending

Let us continue with linear functions.

Linear programming is based on solving a system consisting of a linear objective functions and a set of linear constraints. In general,

y = f(x)

is not a linear function. Examples of nonlinear functions include the following.

y = f(x) = x2 y = f(x) = cos(x) y = f(x) = sqrt(x) y = f(x) = exp(x)

But, the specific form

y = f(x) = m * x + b

is a linear function, typically used when

x represents an independent variable,
y represents a dependent variable,
m is the slope of the line, and
b is the y-intercept of the line.

In linear programming, the dependent variable is the objective function and is usually represented by the variable z as in

z = f(x1, x2) = c1 * x1 + c2 * x2

where c1 and c2 are constants (i.e., named literals) and x1 and x2 are dependent variables. It is customary in linear programming to not write the multiplication sign "*", so the above objective function would be written as follows.

z = f(x1, x2) = c1 x1 + c2 x2

Since there may be tens or hundreds of independent variables, the variables x1, x2, x3, ..., etc., are used instead of the variable y, since y is often used in other contexts (e.g., linear regression) as a dependent variable.

z = c1 x1 + c2 x2

Is this a linear function? Yes. Does is represent a line? No. The linear function

z = f(x1) = c1 x1

is best represented as a line in the 2-D (two dimensional) (x1,z) plane, but the linear function

z = f(x1, x2) = c1 x1 + c2 x2

is best represented as a plane in the 3-D (three dimensional) (x1,x2,z) space, as can be seen by the following.

(XLC omitted)
(chart omitted)

Look at the chart. Given an x1 and an x2 value, the value for z is the vertical distance. The legend is color coded to show the height of z above the x1-x2 plane, just as the contour lines of a geographic map shows the elevation above sea level. It can be easily seen that for any given z value, the intersection of the plane with the x1-x2 axis is a straight line.

Three-dimensional surface plots be done with a spreadsheet. Consider graphing the objective function when c1 is 40 and c2 is 30 as follows.

z = f(x1,x2) = c1 x1 + c2 x2 = 40 x1 + 30 x2

One way to do this is as follows.

1. Put the x1 values into a column. For example,

put the increment value for x1 in cell C2,
put the starting value, in this case, 0.0, in cell A6,
put the increment formula of =A6+$C$2 in cell A7, and
copy the formula in A7 down the column as desired.

2. Put the x2 values into a row. For example,

put the increment value for x2 in C3,
put the starting value, in this case, 0.0, in cell B5,
put the increment formula of =B5+$C$3 in cell C6, and
copy the formula in C6 across the row as desired.

3. The upper left corner for the block of z values is now cell B6. So

put the value of c1 into cell F2,
put the value of c2 into cell F3, and
put the formula =$F$2*$A6+$F$3*B$5 in cell B6, and
copy the formula in cell B6 across the rows and down the columns as desired.

Note that the use of absolute and relative references in cell B6 makes it easy to copy the cell to the entire block while retaining the desired formula.

4. The range for the chart is block A5:K15 (or whatever bottom-right corner is desired).

The chart type is a 3-D surface chart. If the first row and column of the range are plotted, then the surface will not be a (flat) plane. The first row and column are for the x1 and x2 axis labels.

(XLS omitted)

Spreadsheet values:

(values omitted)

Spreadsheet formulas: (note: some of the right part omitted)

(formulas omitted)

A linear constraint is a constraint that can be expressed, in some form, as an equality or inequality involving a straight line. Returning to the linear equation

y = m * x + b

substituting x1 for x and x2 for y results in the following.

x2 = m * x1 + b

The standard form of an equation for most linear programming software systems requires that all variables be on the left and the intercept be on the right. Using algebra, the above can be rewritten as follows.

x2 - m * x1 = b

This equation is the equation of a (straight) line in the x1-x2 plane. To be more general, the above can be rewritten as

c1 * x1 + c2 * x2 = b

where c1 and c2 are constants. So, if c1 is m and c2 is 1, then the previous equation is obtained. Omitting the "*", the equation can be rewritten as follows.

c1 x1 + c2 x2 = b

In general, linear constraints can take any of the following form, where the constants c1 and c2 can be positive, zero, or negative.

c1 x1 + c2 x2 < b c1 x1 + c2 x2 <= b c1 x1 + c2 x2 = b c1 x1 + c2 x2 >= b c1 x1 + c2 x2 > b

Since the area of a line in a plane is zero, since the line has zero thickness, constraints with "<" for "less than" or "<=" for "less than or equal to" are equivalent. Likewise, constraints with ">" for "greater than" or ">=" for "greater than or equal to" are equivalent. The "LPSolves" software package only accepts constraints using "=", "<=", or ">=".

What is the meaning of each of the constraints? Obviously,

c1 x1 + c2 x2 = b

is the equation of a straight line. The inequality

c1 x1 + c2 x2 <= b

represents every point (i.e., half-plane) on one side of the line

c1 x1 + c2 x2 = b

while the inequality

c1 x1 + c2 x2 >= b

represents every point (i.e., half-plane) on the other side of the line

c1 x1 + c2 x2 = b.

That is, the line divides the plane into two half-planes.

But which side of the line? Recall that to plot a straight line, one must determine two different points. To determine which side of the line (i.e., half-plane) is represented by an inequality, first plot the line. Then pick any point not on the line. Evaluate the inequality for that point. If the inequality is true, then the half-plane is on that side of the line. If the inequality is false, then the half-plane is on the other side of the line.

Consider, for example, the following constraint.

x1

x2

x1

How is this to be converted into standard form? Well, the first approach would be to start creating definitions until the result falls out. Such as,

Total production is x1+x2 .
So, 25.0% of total production is 0.25*(x1+x2) .
Production of x1 must be at least 0.25*(x1+x2) .
So, x1 >= 0.25*(x1+x2) .

This is not in the form that many linear programming packages require. To put it into the correct form, we must do some algebra, whereupon we arrive at the form

3*x1 - x2 >= 0.0

which in linear programming standard form can be expressed as follows.

3 x1 - x2 >= 0.0

And this, it must be stressed, is exactly the purpose of algebra.

The primary purpose of algebra is to permit the construction of a model in terms that are easy for the human to understand, such as

x1 >= 0.25*(x1+x2) ,

which is very readable as, "The production of x1 should be greater than or equal to 25% of the production of both x1 and x2.", and mechanically, without using intuition, convert that model into an equivalent form that may not be as easy for a human to understand, such as

3 x1 - x2 >= 0.0 ,

which is very unreadable as, "3 times the production of x1 minus the production of x2 is greater than or equal to zero.". But since we have mechanically followed precise rules that leave the constraint unchanged, or invariant, we know that the result is the same as what we started out with. The content of each equation is same, but the form is very different (one is human friendly, the other is machine friendly).

We conclude that algebra is important, but in this context, another question arises. If the computer can recognize the constraint that is easier for the human to understand, and convert it, using algebra, into the form that is not so easy to understand, why doesn't the computer do it?

The "LPSolves" linear programming software package, like most other linear programming software packages, has been written to accept any form that can be converted to standard form, and standard form is the second of the above forms.

The constraint

3 x1 - x2 >= 0.0

has as its corresponding straight line

3 x1 - x2 = 0.0

and can be plotted as follows.

If x1 is 0.0, x2 is 0.0, then the line passes through the point (0.0, 0.0). If we pick x2 as 0.0, we obtain the same point, so we must pick another value for x2.
If x2 is 3.0, x1 is 1.0, then the line passes through the point (1.0, 3.0).

A point not on the line is (3.0, 0.0). Substituting 3.0 for x1 and 0.0 for x2 in the equation for the original constraint results in

3 * 3.0 - 0.0 >= 0.0

or

9.0 >= 0.0

which is true. Therefore, the half-plane that satisfies the original constraint is on the same side of the line as the point (3.0, 0.0).

Finally, in addition to permitting only linear objective functions and linear constraints, the linear programming method only works when all dependent variables are nonnegative. That is, x1 is greater than or equal to 0.0, x2 is greater than or equal to 0.0, etc. This can be expressed as follows.

x1 >= 0.0 x2 >= 0.0

1. What is the primary purpose of algebra? Give a specific example.

2. A company produces two products, x₁ and x₂. Management has stated that at least 1/6 of the total production of x₁ and x₂ must be of product x₂. Write an algebraic equation that exactly models this requirement. Then, using algebra, write a constraint equation of the form required by the linear programming model.