Imagine you run a small bakery. You can make two things: delicious chocolate cakes and classic vanilla cakes. You make more profit on chocolate cakes, but they take longer to bake and use more expensive ingredients. You only have so much oven time, flour, and sugar each day. How do you decide how many of each cake to bake to make the most money?

This is an optimization problem. You have a goal (maximize profit) and a set of limitations (ingredients, time). Linear programming is a mathematical tool for solving exactly this kind of puzzle.

It's called "linear" because the relationships between the different factors are represented by straight lines. There are no curves or exponents involved. Let's break down the key parts of any linear programming problem.

Every linear programming model has three core components: an objective function, decision variables, and constraints.

In our bakery example, let's say we make $10 profit for each chocolate cake and $8 for each vanilla cake. If $x$ is the number of chocolate cakes and $y$ is the number of vanilla cakes, our objective is to maximize our total profit, $P$. The objective function would look like this:

Next, we have our limitations, or constraints.

Let's say you only have enough flour for 30 cakes in total. And your oven can only run for 8 hours (480 minutes). A chocolate cake takes 20 minutes to bake, while a vanilla cake takes 15 minutes.

These limitations become our constraints:

So now we have a goal and a set of rules. How do we find the best answer? We can visualize the problem by graphing the constraints.

Each inequality represents a region on a graph. The area where all these regions overlap is called the feasible region. It contains every possible combination of chocolate and vanilla cakes we could bake without breaking any of our rules.

A key theorem in linear programming states that the optimal solution—the combination that maximizes profit—will always be at one of the corners (or vertices) of the feasible region. To solve the problem, you just need to test the objective function at each corner point.

For our bakery, the corners are (0,0), (24,0), (0,30), and (18,12). Let's plug them into our profit equation $P = 10x + 8y$:

• (0,0): $10(0) + 8(0) = \text{\textdollar}0$
• (24,0): $10(24) + 8(0) = \text{\textdollar}240$
• (0,30): $10(0) + 8(30) = \text{\textdollar}240$
• (18,12): $10(18) + 8(12) = 180 + 96 = \text{\textdollar}276$

The best choice is to bake 18 chocolate cakes and 12 vanilla cakes, which gives the maximum profit of $276.

This simple bakery example shows the power of linear programming. But this method is used to solve much more complex problems in many different fields.

Now that you understand the basic building blocks, let's review the key terms.

Time to check your understanding.

By defining a goal, setting clear limits, and analyzing the possibilities, linear programming provides a powerful framework for making optimal decisions.