Example:

We can make dough for 2 types of muffins (A or B). We can charge different prices for these:

• 60 cents for each 100g of Type A
• 50 cents for each 100g of Type B

The different doughs have different compositions:

• Dough A consists of 80% flour and 20% chocolate.
• Dough B consists of 50% flour and 50% chocolate.

We have the following amounts of ingredients available:

• 1500g Flour
• 900g Chocolate

How do we find out how much dough of which type we want to make for maximum revenue?

We can denote the amount of dough (in grams) of Type A with $x_1$ and the amount of dough of Type B with $x_2$.

We therefore want to determine the amount of dough of Type A and B that brings us the maximum revenue:

\[ \begin{aligned} \max \quad & 0.6 x_1 + 0.5 x_2 \\ \end{aligned} \] (Revenue in Cents)

We have 1500g flour. Dough A consists of 80% flour, Dough B of 50%.

What does this mean for $x_1$ and $x_2$?

$0.8 x_1 + 0.5 x_2 \leq 1500$

We can try to visualize this:

The line $0.8 x_1 + 0.5 x_2 = 1500$ crosses the $x_1$-axis at $x_1 = \frac{1500}{0.8} = 1875$ and the $x_2$-axis at $x_2 = \frac{1500}{0.5}=3000$.

We can, of course, use less than the total amount of flour:

$\color{blue} 0.8 x_1 + 0.5 x_2 \leq 1500$

Similarly, we have 900g of chocolate. Dough A consists of 20% chocolate, dough B of 50%.

$\color{red} 0.2 x_1 + 0.5 x_2 \leq 900$

Of course, we cannot produce less than 0 grams of any dough:

$ x_1 \geq 0\\ x_2 \geq 0 $

We now know the amount with all possible dough combinations we can make.

Which generates the highest revenue?

Our goal was:

All mix ratios in which we earn exactly 500 cents:
$0.6 x_1 + 0.5 x_2 = 500$

The direction in which we earn more is e.g., the vector \[ \begin{bmatrix} 0.6 \\ 0.5 \end{bmatrix} \qquad \text{or} \qquad \begin{bmatrix} 6 \\ 5 \end{bmatrix} \]

Graphically, we can now determine the best dough ratio:

What we can also see directly from the graphical solution:

• In the solution, we use 100% of the dough.
• There are only 3 possible solutions that are truly relevant.
• The prices for the doughs can change slightly without a different solution becoming optimal.

The entire problem taken together could be formulated as follows:

\[ \begin{aligned} \max \quad & 0.6 x_1 + 0.5 x_2 \\ \text{subject to} \quad & 0.8 x_1 + 0.5 x_2 \leq 1500 \\ & 0.2 x_1 + 0.5 x_2 \leq 900 \\ & x_1 \geq 0 \\ & x_2 \geq 0 \end{aligned} \]

This formulation is called a
Linear Program (LP).

An LP has the following structure:

• There are several real-valued variables.
• We want to maximize or minimize an objective function.
• We have several constraints with $=$, $\geq$, or $\leq$.
• Both the objective function and the constraints are linear.

Linear means that a term consists only of a sum, and each summand may contain at most one variable. The variable can be multiplied by a factor.

A linear term can always be graphically interpreted as a line or plane.

Linear:

• $0.6 x_1 + x_2 - 5 x_3$
• $7 x_1 \leq x_2 - 5 x_3 + 12$
• $x_2 \geq \log(5)$

Non-linear:

• $4 x_1 + x_2 x_3$
• $x_1^2 \leq 4$
• $\log(x_2) \geq 5$

What do we want to do with LPs?

• Model large industrial problems.
• Find optimal solutions.
• Generate additional knowledge about the solution.

We can also express LPs in a vectorized form.

The constraints as a matrix-vector product:

\[ \underbrace{ \begin{bmatrix} 0.8 & 0.5 \\ 0.2 & 0.5 \end{bmatrix} }_{A} \underbrace{ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} }_{x} \leq \underbrace{ \begin{bmatrix} 1500 \\ 900 \end{bmatrix} }_{b} \]

The objective function as a vector-vector product:

Every linear program can generally be written as:

What matters is what's in $A$, $b$, and $c$.

This notation is called canonical form.

Every LP can be converted into canonical form.

$$\min \; c^T x \quad \Leftrightarrow \quad \max\; -c^T x$$

What if we do not want $x_i \geq 0$?

We can simply replace $x_i$ with $x_i^+ - x_i^-$.

\[ \begin{aligned} \max \quad & \underbrace{\begin{bmatrix} c_1 & c_2 & \cdots & c_n \end{bmatrix}}_{\color{blue} c^T} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ \vdots\\ x_n \end{bmatrix}}_{\color{blue} x}\\ \text{subject to} \quad & \underbrace{\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}}_{\color{blue} A} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ \vdots\\ x_n \end{bmatrix}}_{\color{blue} x} \leq \underbrace{\begin{bmatrix} b_1\\ b_2 \\ \vdots\\ b_m \end{bmatrix}}_{\color{blue} b} \\ & x \geq 0 \end{aligned} \]

Suppose we now have a very general "Muffin" problem:

• We have $n$ possible recipes $r_1, \ldots, r_n$.
• We have $m$ possible ingredients $z_1, \ldots, z_m$.

\[ \begin{aligned} \max \quad & c^T x \\ \text{subject to} \quad & Ax \leq b \\ & x \geq 0 \end{aligned} \]

• $x_i$: How much dough from recipe $r_i$ do we produce?
• $c_i$: Yield for recipe $r_i$.
• $b_j$: Available amount of ingredient $z_j$.
• $a_{ij}$: Proportion of ingredient $z_j$ in recipe $r_i$.

With more than 3 recipes, we cannot proceed with the graphical method. We need a more general algorithm.