Imagine you run a small bakery. You sell two types of cookies: chocolate chip and oatmeal raisin. You want to make as much profit as possible, but you have limits. You only have a certain amount of flour, sugar, and oven time.

How do you decide how many of each cookie to bake to maximize your profit without running out of ingredients or time? This is an optimization problem. Linear programming is a mathematical way to solve problems just like this.

It's a powerful tool used in all sorts of fields, from scheduling flights to managing supply chains and routing data over the internet. At its core, it's a formal method for making smart decisions when faced with constraints. To use it, we need to break our problem down into a few key parts.

Every linear programming problem has the same basic components. Let's explore them using our bakery example.

We can represent these with symbols. Let's say:

• $x$ = the number of dozens of chocolate chip cookies • $y$ = the number of dozens of oatmeal raisin cookies

Our goal is to find the best values for $x$ and $y$.

Suppose you make a profit of $3 on each dozen of chocolate chip cookies and $4 on each dozen of oatmeal raisin cookies. Your total profit, which we'll call $P$, would be the sum of the profits from each type of cookie. The objective function is:

We want to make $P$ as large as possible.

Let's say you have 100 cups of flour and 80 cups of sugar.

• A dozen chocolate chip cookies ($x$) requires 2 cups of flour and 1 cup of sugar. • A dozen oatmeal raisin cookies ($y$) requires 1 cup of flour and 2 cups of sugar.

This gives us two constraints:

1. Flour: The total flour used for both types of cookies can't exceed 100 cups.
2. Sugar: The total sugar used can't exceed 80 cups.

We also have two more obvious constraints: we can't bake a negative number of cookies. These are called non-negativity constraints: $x \ge 0$ and $y \ge 0$.

Once we have our constraints, we can visualize all the possible solutions. The set of all combinations of $x$ and $y$ that satisfy all the constraints is called the feasible region. Any point inside this region is a valid production plan, but any point outside is not.

The shaded area in the graph represents every possible combination of cookie dozens we can bake given our resources. The solution that maximizes our profit will be one of the corners (vertices) of this feasible region. By testing our objective function, $P = 3x + 4y$, at each of these corners, we can find the single best combination.

For example, at the point (40, 20), we bake 40 dozen chocolate chip and 20 dozen oatmeal raisin cookies. Our profit would be $3(40) + 4(20) = 120 + 80 = \text{\textdollar}200$. This turns out to be the optimal solution!

Now, let's test your understanding of these core concepts.

Understanding these building blocks is the first step. Next, we'll see how to systematically solve these problems using algorithms and software.