Basic Linear Programming

While there are many exciting prescriptive analytic case studies that I’d love to show you, I can’t really get there in good conscience without first showcasing some other examples that set the foundation to the structure behind solving these types of problems.

Okay, so, basic linear programming! This is probably as basic as you can get, so don’t get up for a break just yet – this’ll be quick. Here’s an example of a problem I had in a course (modified slightly to not step on any toes):

A manufacturer produces two popular mini RC cars: the Model R and the Model C. In the coming week, the manufacturer wants to produce up to 700 cars and wants to ensure the number of Model Rs produced does not exceed the number of Model Cs by more than 300. Each Model R produced and sold results in a profit of $70 while each Model C results in a profit of $40. The cars only differ by the metal trim around the fuel tank and seat. Each Model R’s trim requires 2 pounds of aluminum and 3 hours of production time while each Model C requires 1 pound of aluminium and 4 hours of production time. Assume that 900 pounds of aluminum and 2,400 labor hours are available for production of these items in the coming week. What is the optimal solution?

So LP problems generally tend to follow a certain structure.

• They have a decision to make (how many Model R and Model C cars to produce)

• They are seeking an optimal solution (defined as making the most profit)

• They have constraints (they have limitation and resource constraints – they want to produce up to 700 cars, want Model Rs to not exceed the number of Model Cs by more than 300, and there are only 900 lbs of aluminum and 2400 labor hours available)

This setup seems eerily similar to problems you run into back in good ol’ microeconomics. You have two decision variables (how many Model Rs and how many Model Cs to produce), which makes it’s expression a simple 2-dimension graph. Then, on each point in the graph, one can calculate an objective function’s value, in this case it would be profit ($70 Model R + $40 Model C). Lastly, resource constraints can be expressed as lines on the graph, where one can no longer produce past that line. Here would be an example layout:

Decision Variables:

X = # of Model Rs to produce

Y = # of Model Cs to produce

Objective:

Maximize the following function: Profit = 70X + 40Y

subject to the following constraints:

2X + Y <= 900 (This is the aluminum constraint)

3X + 4Y <= 2400 (This is the labor hours constraint)

X + Y <= 700 (Limitation constraint)

X – Y <= 300 (Limitation constraint)

X and Y >= 0 (You can’t produce negative cars)

You can calculate the intercepts of each constraint equation, with some basic linear equations using knowledge from common middle and high school algebra curriculum, and actually graph this visually if you’d like:

The darkest red section from all of the overlapping lighter red sections indicates the feasible region of this problem: if you try to produce any bundle of Model R and Model C cars outside of this region, you will be violating one of the initial constraints presented by this problem.

Furthermore, since the objective function is relatively simple, we can actually also make one more deduction – the optimal bundle will be found at the edge of the feasible region. So, while we could run this in a program, or solve it with excel solver, you could also just calculate the profit function at all of the intersecting points on the constraint lines, and choose the one with the highest profit. I did the work below:

Corner points => Profit Yield

(0,0) => $0

(0,600) => $24000

(300,0) => $21000

(240,420) => $33600

(400,100) => $32000

So in this case, the optimal solution is to produce 240 Model Rs and 420 Model Cs, which yields a total profit of $33,600.

While the approach to this problem is very simple and does not even require a computer, linear programming becomes much more cumbersome for the human brain when the problems increase in complexity, whether it’s the objective function, the number of decision variables, the number of constraints, etc. At that point, you’d have to utilize the processing power of a computer. However, a computer is only as smart as its user, so it’s very important to understand the basics behind what you need the computer to be doing before jumping over to more complex problems. Furthermore, the importance of linear programming and optimization becomes more important as the size of the problem increases as well – instead of making a decision that changes your overall profit by several thousand dollars, the decisions that a large business could be facing may result in a difference of several million dollars, or several billion dollars.