Simplex Method

Table of Contents

Lecture 5

Getting the LPP (Linear programming problem) to reflect the standard form that allows us to use the SImplex method:

Slack variables
1. Less than and Greater Than Signs – get the inequality to reflect an equality
2. How: Minus an unknown variable or Add an unknown variable
3. FYI – you don’t know if these two are unknowns so make sure that’s represented
Unrestricted variables
1. Your variable is all things, greater than , less than and equal to so… deal this.
1. How: Make that variable equal to an unknown variable less another unknown variable
2. FYI – both variables are greater than zero
Negative RHS change
1. Remember inequalities, if there is a negative on the RHS which should not be there, multiplying by a negative symbol means the signs need to correct their direction
  1. Apply all row actions all the way through but when you are subtracting the coefficients with the multiple of the row operations, add on the RHS.

The visual explanation of the above

1. $$ “x_1\le 12” \text{ is changed to } “x_1 + x_2 = 12$$ $$x_2 \text{ the unknown}$$ 2. $$ “x_1\le\ge= 0” \text{ is changed to } “x_1= x_2-x_3, x_2\ge0, x_3\ge0$$ 3. $$ “x_1\le -24” \text{ is changed to } “-x_1\ge+24$$

Slack Variable Conversion

Change the inequalities to equalities using slack variables.

$$ “x_1\le 24” \text{ is changed to } “x_1 + x_2 = 24$$

Example to get this :

$$ \text{Maximise} 3x_1 + 4x_2 $$ $$\text{Constraints}$$ $$6x_1-3x_2\le15$$ $$2x_1+4x_2\ge 22$$ $$5x_1-3x_2=-40 $$ $$\text{All } x_i \ge 0 $$

To be completed. To Do.

$$ \text{Maximise} 3x_1 + 4x_2 $$ $$\text{Constraints}$$ $$6x_1-3x_2\le15………..6x_1-3x_2+x_3=15$$ $$5x_1-3x_2=-40 $$… $$\text{All } x_i \ge 0 $$…

System of Equations

$$ S_1: $$ $$x_1-2x_2-3x_3-4x_4=3 $$ $$-x_2+3x_3+4x_4+x_5=6 $$

Solving these using Matrices – see page on Matrix solutions https://iamnasirene.com/2022/08/21/matrix-elementary-row-operations/

Basic Feasible Solution

A basic feasible solution (bfs) can be found if those items with a coefficient of 1 within the constraints and thereafter 0 zero as a coefficient, can form part of the bfs. Above example:

$$x_1 =3, x_5=6$$ $$x_2=x_3=x_4 = 0 $$

Procedure of Simplex Method

Remember the point of intersection of the constraints is the solution for maximisation…, with the RHS right hand side being non-negative.

Eg.	Objective Function Co-efficients	7	5	3	-1#	1##
C0	Basis	x1	x2	x3	x4	x5	RHS
-1#	x that was equal to RHS	a	b	c	1	e	Number	16
1##	x that was equal to RHS	f	g	h	i	1	Number Other	22

	DEVIATION entries: Vector Subtractions…Scalar	7-(-1 1)(a f)^t			0	0		z
								Remember to add (16 * -1)+(22*1)=z

To-DO

Decisions Needed

Which variable will enter the next basis setup?

Use the largest deviation entry to determine which variable will enter.

This column now becomes the pivot column…

Which variable will leave the basis?

Calculate the minimum ratio test, using the entries on the Right Hand Side (RHS) and the variables on the pivot column…

RHS/ i.e. divided by the pivot column variable

Compare the answers. The minimum of this will be the one leaving the basis…

That means the largest variables are staying…

What do you do with the new entering variable – Reiterative process.

Restate its variable C0 in the first column.

Then whatever you need to do with basic operations to have the row resulting in a 1 for its constant, you do.

Then get the second row to represent a 0.

Once all that is done, calculate the deviations

then the objective function with the new numbers.

Finally,

the largest deviation becomes the entering variable for the next iteration, and the pivot.

you then work out the minimum ratio using the RHS divided by the pivot column, the minimum will leave.

Final Optimum Solution

When all the deviation entries are negative or zero, it then stops, and you have have achieved the optimal objective function.

Now breakfast.

Operations Research