---

The Simplex Algorithm: A Wedding Planning Example

Imagine you're planning a wedding and need to decide how many vegan and meat dishes to prepare to minimize costs while satisfying all guests. Let's use the Simplex Algorithm to find the optimal solution.

Step 1: Formulating the Problem

Objective: Minimize the cost of preparing meals.

Constraints:

1. Each guest has indicated their preference: vegan, meat, or indifferent.
2. You need to satisfy all preferences with the available dishes.
3. Costs for vegan and meat dishes are different.

• $x_1$​: Number of vegan dishes
• $x_2$​: Number of meat dishes
• $c_1$​: Cost per vegan dish
• $c_2$​: Cost per meat dish

Let's assume:

• Cost of a vegan dish, $c_1$​ = $10
• Cost of a meat dish, $c_2$​ = $15
• Total guests: 200
• Vegan preferences: 80 guests
• Meat preferences: 70 guests
• Indifferent guests: 50 guests

The objective function to minimize is the total cost $Z$:

$$ \color{tomato} Z = 10x_1 + 15x_2 $$

Constrains

• Vegan dishes for vegan and indifferent guests: $x_1 ≥ 80$
• Meat dishes for meat and indifferent guests: $x_2 ≥ 70$
• The total number of dishes should cover all guests: $x_1 + x_2 ≥ 200$

To convert inequalities into equalities, we introduce slack variables: s1=x1−80 s2=x2−70 s3=x1+x2−200

\color{#52BFDD}
\begin{aligned}
s_1=x_1−80 \\
s_2=x_2−70 \\
s_3=x_1+x_2−200 
\end{aligned}

The constraints become:

\color{#52BFDD}
\begin{aligned}
80 = x_1 − s_1 \\
70 = x_2 − s_2 \\
200 = x_1 + x_2 − s_3 
\end{aligned}

To solve this we start by assuming we start in the Origin. Therefor, the formulas look like this:

\color{aquamarine}
\begin{aligned}
80     & = & x_1      &&         && − s_1 &&       &&       \\
70     & = &          &&   x_2   &&       && − s_2 &&        \\
200    & = & x_1      && + x_2   &&       &&       && − s_3  \\
Z      & = & 10 x_1   && + 15x_2  
\end{aligned}

We are here assuming the $\color{red}x_i$ variables are set to zero, and the $\color{gold}s_i$ can take any values that satisfy the equations.

\color{silver}
\begin{aligned}
\text{Tight} && \text{Loose} \\
\color{red}{x_1,x_2} && \color{gold}{s_1,s_2,s_3}
\end{aligned}

\color{aquamarine}
\begin{aligned}
\color{gold}{s_1} & =  - 80     && + \color{red}{x_1}    &&                        \\
\color{gold}{s_2} & =  - 70     &&                       && + \color{red}{x_2}     \\
\color{gold}{s_3} & =  - 200    && + \color{red}{x_1}    && + \color{red}{x_2}      \\
 Z                & =           && \color{red}{10 x_1}   && + \color{red}{15x_2}  
\end{aligned}

We can see that if \color{red}{x} is set to zero, the \color{gold}{s} variables are negative, so they don't satisfy the conditions.

We need to find another vertex where the problem is satisfied. We need to move in the direction of the minimum (for minimization) growth, which is $\color{red}{10x_1}$ (as is the smallest growth in $Z$).

For it we need to check how much we can increase $x_1$ to make the right side zero. The first value of $x_1$ to make the equation 0 is 80, fixing $s_1$.

Therefor, we can get rid of $x_1$ in the other lines by adding the equation of $s_1$ (escalated if needed) to the equation where we don't want it, as both sides can be displaced to equal 0, so we are not really changing anything. Just rewriting.

The resulting table is as follows:

\color{silver}
\begin{aligned}
\text{Tight} && \text{Loose} \\
\color{red}{s_1,x_2} && \color{gold}{x_1,s_2,s_3}
\end{aligned}

\color{aquamarine}
\begin{aligned}
\color{gold}{x_1} & =  - 80     && + \color{tomato}{(s_1 + 80)}    &&                        \\
                  & =  0        && + \color{red}{s_1}              &&                        \\\
color{gold}{s_2} & =  - 70      &&                                 && + \color{red}{x_2}     \\
\color{gold}{s_3} & =  - 200    && + \color{tomato}{(80+s_1)}      && + \color{red}{x_2}      \\
                  & =  - 120    && + \color{red}{s_1}              && + \color{red}{x_2}      \\
 Z                & =           && + \color{red}{10 ·\color{tomato}{(80+s_1)}} && \color{red}{15x_2}  \\
                  & =    800    && + \color{red}{10s_1}    && + \color{red}{15x_2}  
\end{aligned}

\color{aquamarine}
\begin{aligned}
\color{gold}{x_1} & =  0        && + \color{red}{s_1}    &&                        \\
\color{gold}{s_2} & =  - 70     &&                       && + \color{red}{x_2}     \\
\color{gold}{s_3} & =  - 120    && + \color{red}{s_1}    && + \color{red}{x_2}      \\
 Z                & =    800    && + \color{red}{10s_1}  && + \color{red}{15x_2}  
\end{aligned}

Now the smallest coeficient is $10s_1$. We pivot on its column. The smallest coeficient is 120. We take $s_3$ out.

\color{silver}
\begin{aligned}
\text{Tight} && \text{Loose} \\
\color{red}{s_3,x_2} && \color{gold}{x_1,s_2,s_1}
\end{aligned}

\color{aquamarine}
\begin{aligned}
\color{gold}{x_1} & =  0        && + \color{red}{s_1}    &&                        \\
\color{gold}{s_2} & =  - 70     &&                       && + \color{red}{x_2}     \\
\color{red}{s_3} & =  - 120    && + \color{gold}{s_1}    && + \color{red}{x_2}      \\
 Z                & =    800    && + \color{red}{10s_1}  && + \color{red}{15x_2}  
\end{aligned}