💭 The Simplex Method - Intuitively

Abstract

We will look at developing an intuitive understanding of the Simplex Method for Linear Programming.

knitr::opts_chunk$set(
  echo = FALSE,
  collapse = TRUE,
  #cache = TRUE, autodep = TRUE, 
  comment = "#",
  fig.show = "asis", 
  warning=FALSE, message=FALSE, fig.align = "center",
  scipen = 1, digits = 2)

library(tidyverse)
library(plotly)
library(gMOIP)

What is the Simplex Method?

To be written up.

A Random Walk with the Simplex Method

Let us try to form a geometric intuition for the Simplex method.

We will define an LP problem, and geometrically traverse the steps the Simplex method might take to solve for the optimum solution.

Let us define a problem:

$$Maximise7.75x_1+10x_2$$ $$\begin{gathered} Subjectto \\ \{\begin{array}{ll}C1:-3x_1+2x_2& <=3\\ C2:2x_1+4x_2& <=27\\ C3:9x_1+10x_2& <=90\\ x_1,x_2>=0\end{array} \end{gathered}$$

The Objective function is: $7.75x_1+10x_2$

The Constraints are defined by the three inequalities $C1::C3$. In order to plot these, we convert the inequalities to equalities and plot these as lines. Each line splits the $x_1:x_2$ plane into two half-planes. The inequality part is then taken into account by choosing the appropriate half-plane created by the equation. The intersection of all the half-planes defined by the constraints is the Feasibility Region.

The Feasibility region for this LP problem is plotted below:

The corner points of the Feasibility Region are:

ABCDEFGHIJ0123456789

name <chr>	x1 <dbl>	x2 <dbl>
A	0.000	0.0000
B	10.000	0.0000
C	5.625	3.9375
D	2.625	5.4375
E	0.000	1.5000

5 rows

Recall that:

• The optimum in an LP problem is found on the boundary, at one of the vertices
• At each of these vertices one or more constraints ($C1::C_n$) is tight, i.e. there is no slack.

Procedure

1. We start with an arbitrary point on the edge of the Feasibility Region. $A=(0,0)$ is a common choice. At this point, since all variables are $0$, the objective function is also $0$.

2. We (arbitrarily) decide to move along the boundary of the Feasibility Region, to another FSP. We arbitrarily chose the $x_1$ axis, and set/keep $x_2=0$. We now wish to find out the $x_1$ coordinate of the next FSP point. This would be at the intersection of the $x_1$ axis and one of the Constraint lines.
   All the three Constraint Lines would possibly intersect the $x_1$ axis. We need to choose that intercept point that has the smallest, non-negative $x_1$ intercept value. (Why?)
   So, which Constraint Line intersects the $x_1$ axis at the smallest value? Is it point B, or point F?
   To find out, we substitute $x_2=0$ in each of the Constraint equations, and solve for the $x_1$:
   $$\{\begin{array}{l}C1:-3x_1+2\times 0=3=>x_1=-1\\ C2:2x_1+4\times 0=27=>x_1=13.5PointF\\ \mathbf{C}\mathbf{3}:\mathbf{9}{\mathbf{x}}_{\mathbf{1}}\mathbf{+}\mathbf{10}\times \mathbf{0}\mathbf{=}\mathbf{90}\mathbf{=>}{\mathbf{x}}_{\mathbf{1}}\mathbf{=}\mathbf{10}\mathbf{Point}\mathbf{B}\end{array}$$
   Negative values for any variable are not permitted. So the smallest value of intercept is $x_1=10$ for Constraint $C3$. We therefore move to point $B(10,0)$. At this point the objective function has improved to:

$$Objective=7.75\times 10+10\times 0=77.5atPointB$$

3. We now start from Point B, and move to the next nearest point. In identical fashion to Step2, we “imagine” that we move along a new axis defined by:
   $$Intercept=PointB(10,0)$$ $$Equation=ConstraintC3:9x_1+10x_2=90$$ We express $x_1$ in terms of $x_2$ with $C3$: $$\hat{C}3:x_1=\frac{90-10x_2}{9}$$ As in Step 2, we substitute this equation $\hat{C}3$ into the other two constraints, $C1$ and $C2$: $$\{\begin{array}{l}C1:-3\times \frac{90-10x_2}{9}+2x_2=3=>x_2=6.18PointK\\ \mathbf{C}\mathbf{2}:\mathbf{2}\times \frac{\mathbf{90}\mathbf{-}\mathbf{10}{\mathbf{x}}_{\mathbf{2}}}{\mathbf{9}}\mathbf{+}\mathbf{4}{\mathbf{x}}_{\mathbf{2}}\mathbf{=}\mathbf{27}\mathbf{=>}{\mathbf{x}}_{\mathbf{2}}\mathbf{=}\mathbf{3.93}\mathbf{Point}\mathbf{C}\end{array}$$ As before we choose the smaller of the two intercepts, so $x_2=3.93$. Calculating for $x_1$, we get point $C(5.63,3.93)$. At this point the objective function has improved to:

$$7.75\times 5.63+10\times 3.93=82.9atPointC$$

4. We now proceed along the constraint line $C2$ towards the next point. In identical fashion to Step 2 and 3, we “imagine” that we move along a new axis defined by: $$Intercept=PointC(5.63,3.93)$$ $$Equation=ConstraintC2:2x_1+4x_2=27$$ Again, We express $x_1$ in terms of $x_2$ with $C2$ this time: $$\hat{C}2:x_1=\frac{27-4x_2}{2}$$ As in Step 2 and, we substitute this equation $\hat{C}2$ into the other constraint, the only remaining $C1$: $$\mathbf{C}1:-3\times \frac{27-4x_2}{2}+2x_2=3=>x_2=5.44PointD$$ Calculating for $x_1$, we get point $C(2.63,5.44)$. At this point the objective function has improved decreased to: $$7.75\times 2.63+10\times 5.44=74.8atPointD$$ Since this value for the Objective function is smaller than that at the previous point, our search terminates and we decide that Point $C(5.63,3.93)$ is the optimal point.
   So the final result is: $$x_1(max)=5.63$$ $$x_2(max)=3.93$$ $$MaximumObjectiveFunctionValue=82.9$$ The final result is plotted below:

Summary

The essence of this “intuitive method” can be captured as follows:

1. Start from a known simple point on the edge of Feasibility Region, e.g. (0,0), since the two coordinate axes frequently form two edges to the Feasibility Region.
   
2. Move along one of the axis to find a first adjacent edge point. This adjacent point corresponds to the “tightening” of one or other of the Constraint equations(i.e. slack = 0 for that Constraint)
   
3. Calculate the Objective function at that point.
   
4. Use this new point as the next starting point and move along the Constraint line from the previous step.
   
5. Repeat step 2 and 3, calculating the Objective function each time.
   
6. Keep the solution point where the objective function hits a maximum, i.e. when moving to the next point reduces the value of the Objective function.

---