Linear Programming Simplex Method

In Linear Programming Simplex Method is a method used for problem solving. This method is used for a problem of the form:
Minimize or maximize : c.x
Subject to
Ax=b, xi ≥0  
X is the variables of the problem (x1,x2…) while c is coefficients of the objective function (c1,c2,…). A is a matrix and b are constants≥0.
To solve the linear programming problems we must follow standard form which is achieved as:
A new variable should be added for all those variables whose upper bound is other than zero such that the new variable is the difference between original variable and upper bound.
For example: if x≥3 then introduce a new variable y such that
Y=x-3 and x=y+3.
For rest of the inequality constraints, new variable known as slack variable is introduced to remove inequalities. Like:
X+2y≤3 and –x+3y≥2 is replaced as:
X+2y+z=3 and –x+3y-z=2 such that z≥0.
Let us solve some problems using The Simplex Method

Question) Use Simplex Method to solve the following:
P=3x+4y subject to:
x+y≤4
2x+y≤5
x≥0,y≥0

Solution)  Since we have two constraints, we will introduce 2 slack variables p and q:
x+y+p=4
2x+y+q=5
We rewrite our objective function as −3x−4y+P=0 and thus system of equations become:
x+y+p=4
2x+y+q=5
−3x−4y+P=0
This gives initial simplex table:
X y p q P
1 1 1 0 0 4
2 1 0 1 0 5
-3 -4 0 0 1 0

Find the column with the most negative entry among x,y,p,q and P (here this is −4). Find pivot row by dividing each entry in the constant column by the entry in the corresponding in the pivot column. In this case, we get 4/1 as the ratio for the 1st row and 5/1 for the ratio in the 2nd row. The pivot row is the row corresponding to the smallest ratio which is 4 in this case. So our pivot element is in the 2nd column, 1st row =1.Now, perform the following row operations to convert the pivot column to a unit column:
R2→R2−R1
R3→R3+4R1
So, simplex table is changed to:
X Y p q P
1 1 1 0 0 4
1 0 -1 1 0 1
1 0 4 0 1 16
The variables are given the value in the constant column in the row where a value 1 is in the unit column. All variables above a non-unit column is given 0 value. So y=4, p=1, P=16, x=0, and q=0.
Thus, maximum occurs when x=0, y=4 and the maximum value is 16.
This is how Simplex Method Solver works.