The first step in using linear programming is to recognize a problem for which linear programming provides a possible solution and then to formulate that problem in a form that can be solved using the linear programming method. For two dependent variables, a graphical method can be used. For more than two dependent variables, a computer software for solving linear programming problems must be used.

The key to using linear programming is being able to recognize linear objective functions and linear constraints. We will now look at a common linear programming problem known generically as a resource allocation problem.

• A company produces two products, Galaxy bars (lots), and Continental bars (lots).
• Each product requires three principal ingredients, milk (tons), cocoa (tons), and sugar (tons).
• There are 18 available tons of milk (tons).
• There are 12 available tons of cocoa (tons).
• There are 21 available tons of sugar (tons).
• A production lot of Galaxy bars (lots) requires 3 tons of milk (tons), 1 tons of cocoa (tons), and 3 tons of on sugar (tons).
• A production lot of Continental bars (lots) requires 1 tons of milk (tons), 2 tons of cocoa (tons), and 3 tons of sugar (tons).
• The profit (contribution) for producing one lot of Galaxy bars (lots) is $2. That is, $2 over and above any fixed and/or variable costs.
• The profit (contribution) for producing one lot of Continental bars (lots) is $3. That is, $3 over and above any fixed and/or variable costs.
• The goal is to maximize profit (contribution).
• How much of Galaxy bars (lots) and how much of Continental bars (lots) should be produced in order to maximize profit (contribution)?
• What is the profit (contribution)?

(Note: the numbers have been fabricated for example purposes and may or may not represent actual values).

The goal, or objective, is to maximize profit (contribution). Any costs not mentioned are assumed to not be relevant to the problem of how much to produce. But what is profit? From the problem, the profit is $2 for each production lot of Galaxy bars (lots) produced plus $3 for each production lot of Continental bars (lots) produced. But, how many lots of Galaxy bars (lots) should be produced and how many lots of Continental bars (lots) should be produced? We do not know. That is the question to be answered. In order to formulate and solve the problem, let us introduce variable x1 to represent the number of lots of Galaxy bars (lots) produced and variable x2 to represent the number of lots of Continental bars (lots) produced. Then profit (contribution) z is

We are assuming that we can sell everything that can be produced. How would you handle the situation where not everything that could be produced could be sold? (Hint: Do not produce it if it cannot be sold.)

What are the constraints? Obviously, production cannot be negative. So the following hold.

What about the constraints on the amount of each ingredient that is available? For example, there are only 18 tons of milk (tons) available. For each lot of Galaxy bars (lots) produced, 3 tons of milk (tons) are required. For each lot of Continental bars (lots) produced, 1 tons of Continental bars (lots) are required. Thus

Likewise, for the other ingredients.

This can be expressed in matrix notation as follows. (omitted).

(XLS omitted)

The linear programming problem, be expressed in "LPSolves" textual specification format, appears as follows.

Note the following.

• The keywords linear and program introduce a linear programming problem.
• The keyword var means "variables".
• The keyword max means "maximize", as opposed to min for "minimize".
• The keyword st means "such that".
• The keyword end marks the end of the linear programming specification.
• Character strings, delimited quotes, are used to supply informative textual information about the problem.
• All variables are assumed nonnegative. Thus, there is no need to indicate that x1 is greater than or equal to zero and that x2 is greater than or equal to zero.

Since there are only two dependent variables, we will use the graphical method to solve the problem. Then, a computer solution to the same problem will be presented.

The graphical method of linear programming can only be used for two independent variables (i.e., x1 and x2) and one dependent variable (i.e., z), since people have great difficulty visualizing 3-D space, let alone 4-D space (i.e., hyperspace) or, in the case of n dependent variables, n-D space. However, there is great value in learning the graphical method of linear programming in that the intuition developed with the graphical method can be used to intelligently interpret data received from the output of a computer program that solves a linear programming system of hundreds, or thousands, of variables. Later sections will give some examples of important linear programming problems that do have a large number of variables.

The general method for the graphical solution of a linear programming problem with two independent variables is as follows.

1. Plot the constraints.
• Find two points for each constraint, converted to an equality.
• Determine the scale for the graph.
• Plot the lines.
• Determine the feasible region by proper handling of the inequalities.
2. Plot the projection of the object function on the (x1,x2) plane.
• Pick a value of z.
• Plot the line.
• Pick another value of z.
• Plot the line.
• Determine the increase/decrease from one z-line to another z-line. Picking a good value for z can make the task easier.
3. Find the optimum point.

4. Determine the value of the objective function at that point.

This method will now be used to solve the problem.

The constraints, numbered for convenience, are as follows.

Converted to equalities, the constraints appear as follows.

Two points are needed for each line. The points, expressed in the form (x₁, x₂) are as follows.

The scale can be determined as follows.

• The maximum value for the x1 value is 12.0.
• The maximum value for the x2 value is 18.0.

(XLC omitted)
Plot the lines. (omitted)

To determine the feasible region, determine which side of the line is feasible for each inequality. Since the point (0.0, 0.0) is not on any of the lines, evaluate the inequalities for that point.

Thus, the point (0.0, 0.0) is on the feasible side of all three constraints. The feasible region thus appears as follows. (omitted)

(XLC omitted)
The feasible region is a convex region. A convex region is a region in which any point in the region can be connected by a line segment to any other point in the region without any point on that line segment falling outside the region.

(XLC omitted)
It follows that the optimal solution, if it exists, must be on the boundary of the convex region.

To plot the projection of the objective function

in the x1-x2 plane, pick a value of z, then plot the line. Do this for two values of z.

Picking z as 12, the objective function is

which, using algebra, is the line

Two points on this line are (0.0, 4.0) and (6.0, 0.0).

Picking z as 24, the objective function is

which, using algebra, is the line

Two points on this line are (0.0, 8.0) and (12.0, 0.0).

After plotting the lines for two values of z, determine in which direction the line is increasing. This line can be moved in the increasing direction for maximization problems until it leaves the feasible region. For minimization problems, move the line in the decreasing direction. This can be seen in the following chart (omitted).

(XLC omitted)
The point at which the z-line leaves the feasible region must be either

• a point on the feasible region boundary, or
• a line connecting to adjacent points on the feasible region boundary.

In this case, the intersection is the point at which the lines

and

intersect. The intersection point must satisfy both equations simultaneously. There are two equations and two unknowns. Therefore, mathematically, one of three possibilities exist.

• The lines are the same line, in which case there are an infinite number of solutions (i.e., the line itself).
• The lines are parallel and not the same line, in which case there are no solutions.
• The lines intersect at a point. This is the case that applies here.

In this case, we know from the structure of the problem that the lines intersect at a single point. One way to determine the point is as follows.

• Solve for one of the two variables in terms of the other.
• Substitute the value of that variable for the other in the other equation.
• After solving for one of the variables, substitute that value in one of the two equations to determine the value of the other variable.

For example, since

then

Note that we could just as easily have solved for x2 in terms of x1.

Substitute this result for x1 into

to get

Since variable x1 has been removed, there is now one equation and one unknown. (Aside: This method is a simple example of the divide and conquer problem solving method).

Algebra can be used to obtain the following.

Since x2 is 5, this result can be substituted into

to obtain

So, the objective function

is maximized then x1 is 2 and x2 is 5. The value of the objective function at that point is determined by substituting the optimum values for x1 and x2 into the objective function, as follows.

Returning to the original problem, 19 is the total profit contribution.

1. What is a convex region? Draw a simple convex region.