We're sorry but this app doesn't work properly without JavaScript enabled. Please enable it to continue.

This lesson's interactive features are locked, please to keep using them

Linear Programming

Linear programming is a technique where we depict complex relationships through linear functions and then find the optimal inputs to maximize a given output. The real relationships might be much more complex – but we can simplify them to linear relationships.

In LP we're given some variables, and we want to assign real values to them in order to:

  1. Satisfy a related set of linear equations and/or linear inequalities
  2. Maximize or minimize a given linear function

Example: Maximizing a Baker's Profits

A baker has two desserts for sale: chocolate cake and sugar cookies. How much of each should she produce to maximize profits? Let's say she sells num_cakes cakes per day at a profit (in dollars) of 5 each, and num_cookies cookies per day at a profit of 1 each.

num_cakes and num_cookies are the variables whose optimal values the baker wants to find. If she knows how many of each to make in order to maximize profit, her business will flourish.

You may be thinking:

She should make as many as she can! More volume -> more profit!

Not so! We have some constraints to consider.

  1. On any given day, she has at most 250 customers interested in chocolate cakes.
  2. On any given day, she has at most 200 customers interested in sugar cookies.
  3. The employees in her shop can produce no more than 300 total desserts per day.

Mathing It Out

Given the scenario above, our function is:

profit = (num_cakes * 5) + num_cookies

Remember, cakes are 5x more profitable than cookies.

The constraints can be modeled as follows:

num_cakes <= 250
num_cookies <= 200
num_cakes + num_cookies <= 300
0 <= num_cakes
0 <= num_cookies

We can then graph these constraints on an x/y coordinate plane: