Simplex Algorithm

This is a continuation of Linear Programming as it uses the same problem statement.

Simplex algorithm is a method of solving linear programming problems, it is a polynomial time algorithm that doesn’t evaluate infeasible solutions and explores progressively better solutions, telling you when the optima has been reached and stops, tells you when the optima has been reached and stops.

There are two forms:

1. Algebraic form of simplex: this will give you the insights of what it really is doing
2. Tabular (or tableau) form of simplex: this will allow you to crank-turn rather easily and implement a program

Simplex: Algebraic Form

The goal is to maximise the objective function $z=6x+4y$ subjected to the constraints $x+y+s=5$ and $3x+2y+t=12$ where $x,y,s,t\ge 0$.

What simplex is doing is finding a connected path from a starting corner to another corner, in a way such that you will always increase the objective function from one corner to another. Effectively jumping one vertex to another vertex of the convex polyhedron.

Start by choosing $x$ and $y$ as non-basic variables (i.e., variables that are set to zero.). This gives the solutions to $s$ and $t$ as $s=5$ and $t=12$ respectively. This only works if the RHS is non-negative.

Note that its not always true that fixing a decision variable is $0$ will be in the feasible region. But there are ways of to get a feasible start point. In our case, we are assuming canonical form, where the RHS is non-negative, so it always ensures that when decision variables are set to 0, it will be at a corner point in the feasible region.

Now to find a connected path from one vertex to another in a systematic way where your growing the objective function

Note that fixing the decision variables leads to the point $(0,0)$ on the graph, from this point we can only jump to $(4,0)$ or $(0,5)$. We want to choose a jump such that we have the steepest increase in the objective. In this way, its a greedy algorithm that at every position, we find a point of jump so that the my objective function of all the choices I have locally gives me the steepest increase in the objective.

First Iteration

First, for a better visual understanding, rewrite the constraints making the basic variables $s$ and $t$ the subjects each with coefficient of $1$. This isn’t required but helps with visualisation.

$s=5-x-y$

$t=12-3x-2y$

And the objective function is simply:

$z=6x+5y$

Recall, currently $x=0$ and $y=0$. Therefore the objective function, substituting these values, is $z=0$.

There are two ways to increase $z$ in this case, by increasing the value of x or y. Note in simplex, we can only improve one variable at a time

Additionally to increase the objective function, if the coefficient of the variable in the objective function is positive, you increase the variable. Else, if its coefficient is negative you decrease the variable.

Between the two variables, choose the one that gives the steepest increase. In this case, As $z=6x+5y$, for each unit $x$ is increased, $z$ is increased by $6$ ($1:6$ ratio) whereas $y$ and $z$ have a $1:5$ ratio.

Thus we choose to increase $x$ (since it has a larger coefficient of the two choices, hence gives higher increase of the objective).

To increase $x$, we want to increase it, and convert it to a basic variable, to do that $s$ or $t$ have to be turned into non basic (fixed) variables. To do that:

• Start from $x=0$ and $y=0$ for equation $s$ and $t$
  • $s=5-(x=0)-(y=0)$
  • $t=12-3(x=0)-2(y=0)$
• We want $s$ to be a non basic variable, thus we need $s=0$ , as $y$ is fixed, the only thing we can do is increase $x$ to $5$
  • $s=5-(x=5)-(y=0)=0$
• We do the same for $t$:
  • $t=12-3(x=0)-2(y=0)$
  • $t=12-3(x=4)=0$

This allows the increase to be such that the constraints are still satisfied. In this case, it can be increased from either:

1. $x=0$ to $x=5$ according to the first constraint. Anything more will violate the non-negativity constraint for the slack variable s.
2. $x=0$ to $x=4$ according to the second constraint. Anything more will violate the non-negativity constraint for t.

Choosing the minimum of $x=5$ and $x=4$ will ensure that both $s,t\ge 0$

By choosing the minimum increase $x=0->x=4$, $x$ enters the basis, whilst $t$ exists it. The new set of non-basic variables are $y=0$ and $t=0$, and the basic variable are $x=4$ and $s=1$,

Second Iteration

First rewrite the constraints in making the new basic variables $x$ and $s$ the subjects:

• The first constraint would be $s=5-x-y$, but we want $x$ to be a subject, not a term in the formula
• The second constraingt would be $x=4-\frac{2}{3}y-\frac{1}{3}t$
• Use the second constraint to replace $x$ in the first
  • $s=1-\frac{1}{3}y+\frac{1}{3}t$

This results in constraints:

1. $s=1-\frac{1}{3}y+\frac{1}{3}t$
2. $x=4-\frac{2}{3}y-\frac{1}{3}t$

The objective function $z=6x+5y$ is still in terms of the basic variable $x$, so substitute $x$ so that it is in terms of the non-basic variables:

$z=24+y-2t$

Notice how the objective function is growing as previously $z=0$ with $x=0$ and $y=0$ as the non-basic variables, and now $z=24$ when $y=0$ and $t=0$ are the non-basic variables

Now here, there is are two ways to increase $z$, which is by increasing $y$ or decreasing $t$. However, $t$ cannot be decreased because currently $t=0$ and slack variables must be greater than or equal to $0$. So if we decrease $t$ we result in an infeasible solution.

So we can only increase $y$. To do this, we are turning into a basic variable, this means one of the basic variable $x$ or $s$ must be turned into non-basic:

1. $s=1-\frac{1}{3}y+\frac{1}{3}t$
2. $x=4-\frac{2}{3}y-\frac{1}{3}t$

First of all, we know $t=0$ as its a non-basic variable

1. $s=1-\frac{1}{3}y$
2. $x=4-\frac{2}{3}y$

To make $s$ or $x$ non-basic, we want it to equal $0$

1. $0=1-\frac{1}{3}y$ — $\frac{1}{3}y=1$ — $y=3$ for $s$
2. $0=4-\frac{2}{3}y$ — $\frac{2}{3}y=4$ — $y=6$ for $x$

This allows the increase to be such that the constraints are still satisfied. In this case, it can be increased from either:

1. $y=0$ —> $y=3$ according to the first constraint. Anything more will violate the non-negativity constraint of $s$.
2. $y=0$ —> $y=6$ according to the second constraint. Anything more will violate the non-negativity constraint of $x$.

Choosing the minimum of $y=3$ and $y=6$ will ensure that both $s,x\ge 0$

Thus by choosing $y=0$ —> $y=3$, $y$ enters the basis and becomes a basic variable and $s$ exists it and becomes non-basic.

• The set of non-basic (fixed) variables are $s=0$ and $t=0$
• The set of basic (free) variables are $y=3$ and $x=4-\frac{2}{3}\times 3=2$

Third Iteration

Again, rewrite the constraints so that they are in terms of the non-basic (fixed) variables, and the basic (free) variables are the subjects

• The first constraint $s=1-\frac{1}{3}y+\frac{1}{3}t$ needs to be rewritten so $y$ is the subject
  • $y=3-3s+t$
• The second constraint $x=4-\frac{2}{3}y-\frac{1}{3}t$ already has a basic variable as a subject ($x$), but it also has one in the body ($y$), we can substitute $y$ from the first constraint to get:
  • $x=2+2s-t$

The objective function $z=24+y-2t$ is still in terms of basic variables, so substiting $y$ results in:

• $z=27-3s-t$

From the previous iteration, $z$ has increased from $24$ to $27$ (recall $s=0$, $t=0$).

However, to increase it further, $s$ and $t$ have to be decreased, as they are already $0$, this cannot be done without violating the non-negativity constraints.

As both these choices are infeasible, the algorithm stops.

When simplex method stops, the values of the basic variables are:

• $x=2+2(0)-(0)=2$ and
• $y=3-3(0)+(0)=3$

Therefore, the optimum values of the decision variables $(x,y)$ are $(2,3)$

When simplex method stopped, the values of basic variables were x = 2 and y = 3 (we get these by substituting s = 0 and t = 0 (non-basic variables) into the constraints in the previous slide.

Simplex: Tableau Form

The Tableau form of Simplex follows the same process, but in a more convenient tabular fashion, enabling the process to be converted into a computer program.

First convert the problem into slack form, the objective function and constraints go from:

&\begin{cases} z = 6x + 5y \\ x + y \leq 5 \\ 3x + 2y \leq 12 \\ x, y \geq 0 \end{cases} \quad \Rightarrow \quad \begin{cases} z = 6x + 5y + 0s + 0t \\ x + y + s = 5 \\ 3x + 2y + t = 12 \\ x, y, s, t \geq 0 \end{cases} \end{aligned}$$

First, create a table where the second row contains each variable from the objective function as a column, and the first row lists the corresponding objective function coefficients $C_j$

Then list the basic (free) variables and their coefficient in the objective function, recalling that the slack variables are always initially in the basis, i.e. the non-basics variables are $x=0$ and $y=0$.

Write down the coefficients on the LHS of the constraints and the RHS of the constraints (add an additional column for the RHS). This effectively describes the equations of $s$ and $t$ in a tabular form.

Note columns s to make

1 0 0 1

this is what is meant by in basis

First Iteration

A new variable $Z_j$ is defined for each column $j$ as the dot product of two vectors: the coefficients of the basic variables in the objective function, and the corresponding coefficients at column $j$ in the constraint rows. That is,

$$Z_j=(C_{b_1},C_{b_2},\dots )\cdot (a_{1j},a_{2j},\dots )$$

Where $C_{b_i}$ is the coefficient of the $i$-th basic variable in the objective function, and $a_{ij}$ is the coefficient of column $j$ in row $i$ of the constraint matrix.

Step 1: Express The Objective Function In Terms Of Non-Basic Variables

The new row $C_j-Z_j$ represents the coefficients of the variables in the objective function when expressed in terms of the non-basic variables, indicating its net contribution to the objective function.

The RHS column has no $C_j$, so it simply stores $Z_j$. It represents the current value of the objective function when $x$ and $y$ are non-basic variables (e.g., $x=0$, $y=0$).

Algebraically, this reflects the initial expression of the objective function in terms of non-basic variables: $z=6x+5y+0s+0t$. Just as the algebraic form, the first iteration results in no change in the function nor its value.

Step 2: Select The Largest Contributing Non-Basic Variable To Enter The Basis

Choose to increase the non-basic variable with the largest positive coefficient in the objective function row to get the maximal objective function increase.

Here, the largest is $6$ in column $x$, so $x$ enters the basis.

Step 3: Select The Leaving Variable

To determine which basic variable leaves the basis, divide each RHS value by the corresponding positive entry in the entering column. This gives the $\theta$ values.

The row with the smallest positive $\theta$ indicates the leaving variable, ensuring constraints are enforced and feasibility is maintained.

Therefore, $t$ leaves the basis and $x$ enters it, resulting in the basic variables $x$ and $s$, and the non-basic variables $y$ and $t$.

Second Iteration

Step 1: Express The Objective Function In Terms Of Non-Basic Variables

Now we need to rewrite our constraint so that they are in terms of our non-basic variables, this is done by rewriting it so that the coefficient of the variable entering the bases ($x$) is $1$.

This can be done by dividing each column of the variable leaving the basis ($t$) with the intersection between the variable entering the basis and the one leaving.

This can be done by dividing each column at $t$ by the column $x$ at row $t$, i.e. dividing $t$ by the intersection between $x$ and $t$ .

Note the coefficient of $s$ and $x$ were written to the left.

Similarly, the constraint $x+y+s=5$ must be expressed in terms of the new non-basic variables $(y,t)$. This can be done by substituting in our expression at row $x$ for the new basic variable $x$ in row $s$.

This is done by performing some row operation on the previous row $s_{\text{old}}$ with the row $x$ such that the basic variable $x$ at $s_{\text{new}}$ is $0$ and $s$ is $1$, i.e. $x$ has been substituted and $s$ is has a one coefficient.

Here it is $s_{{\text{old}}_j}-x_j$ for each column $j$

Note that this is equivalent to rewriting the constraint as:

1. $s=1-\frac{1}{3}y+\frac{1}{3}t$
2. $x=4-\frac{2}{3}y-\frac{1}{3}t$

Through this, you can see the importance of ensuring the basic variable coefficient are $1$ and the how substitution leads to $x$ having a $0$ coefficient.

Now to express the objective function in terms of the non-basis variables calculate $C_j-Z_j$

This is equivalent to $z=y-2t+24$, where as $y$ and $t$ are the non-basic variables ($y=0$, $t=0$), the objective function is equal to $z$ and is increasing.

Step 2: Select The Largest Contributing Non-Basic Variable To Enter The Basis

To increase the objective function further, the only option we have is to increase $y$, this means $y$ enters the basis.

Step 3: Select The Leaving Variable

Compute the maximum value θ that y can be increased to based on each constraint, and choose the minimum of such values in order to satisfy both constraints.

Recall this is calculated by dividing each basic rows RHS by the corresponding value at column $y$.

The minimum variable $\theta =3$ is at row $s$, so that would be leaving the basis.

Third Iteration

Step 1: Express The Objective Function In Terms Of Non-Basic Variables

Now $y$ enters the basis and $s$ leaves it. The new pair of basic variables are $x,y$ and non-basic variables are $s,t$. Create two new rows for the basic variables and rewrite them in terms of the non-basic variables.

As $y$ enters the basis, write that one first, calculate each column by first finding the intersection of the entering and exiting variables which is at row $s$ column $y$ = $1/3$, and write the equation of $y$ by dividing the whole leaving row ($s$) by $1/3$

Note that we always write the row of the variable entering the basis first, this is because we need it to substitute into the row staying in the basis to get that in terms of the new non-basic variabels (substitute $y$ in row $x$ )

So do that, subsittue $y$ in row $x$ by doing row operations on row $x_{\text{old}}$ and $y$ such that $x_{\text{new}}$ has its basic variables of the form

0 1 1 0

i.e. at row $x_{\text{new}}$ column $x=1$ and column $y=0$

Here, $x_{\text{new}}=x_{\text{old}}-\frac{2}{3}y$

Finally, we express the objective function (z = 6x + 5y) in terms of (s,t) and we can see that the objective function cannot be increased further without violating our constraints and so we stop.

The constraints algebraically are equivalent to:

• $y=3-3s+t$
• $x=2+2s-t$

And the objective function to

• $z=27-3s-t$

The maximal value for $z$ is the final RHS

In general, linear programming formulations often present themselves in a non-standard form, as against the canonical formulation handled in this lecture. Often simple algebraic manipulations will change a non-standard LP formulation to a canonical form, such as those given in the table below: