SIMPLEX METHOD
SIMPLEX METHOD
1. Formulate the problem
(i) Pick out important information
(ii) Formulate constraints
(iii) Formulate objective function
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
(i) Identify pivotal column
(ii) Find θ-values: the minimum ratio
(iii) Identify pivotal row
(iv) Identify pivot
(v) Pivot
5. Get the solution
THE PROBLEM
• A small factory produces two types of toys: cars and diggers. In the
manufacturing process two machines are used: the moulder and the colouriser.
A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs
1 hour on the moulder and 1 hour on the colouriser. The moulder can be
operated for 16 hours a day and the colouriser for 9 hours a day. Each digger
gives a profit of £16 and each car gives a profit of £14. The profit needs to be
maximised.
• How do we formulate this problem?
STEP BY STEP GUIDE
1. Formulate the problem
(i) pick out important information
(ii) formulate constraints
(iii) formulate objective function
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
5. Get the solution
PICKING OUT IMPORTANT INFORMATION
• A small factory produces two types of toys: cars and diggers. In the
manufacturing process two machines are used: the moulder and the colouriser.
• A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs
1 hour on the moulder and 1 hour on the colouriser.
• The moulder can be operated for 16 hours a day and the colouriser for 9 hours a
day.
• Each digger gives a profit of £16 and each car gives a profit of £14.
PICKING OUT IMPORTANT INFORMATION
• A small factory produces two types of toys: cars and diggers. In the
manufacturing process two machines are used: the moulder and the colouriser.
• A digger needs 2 hours on the moulder and 1 hour on the colouriser. A car needs
1 hour on the moulder and 1 hour on the colouriser.
• The moulder can be operated for 16 hours a day and the colouriser for 9 hours a
day.
• Each digger gives a profit of £16 and each car gives a profit of £14.
• A digger needs 2 hours on the moulder and 1 hour on the colouriser.
A car needs 1 hour on the moulder and 1 hour on the colouriser.
PICKING OUT IMPORTANT INFORMATION
• A small factory produces two types of toys: cars and diggers. In the
manufacturing process two machines are used: the moulder and the colouriser.
• The moulder can be operated for 16 hours a day and the colouriser for 9 hours a
day.
• Each digger gives a profit of £16 and each car gives a profit of £14.
• A digger needs 2 hours on the moulder and 1 hour on the
colouriser. A car needs 1 hour on the moulder and 1 hour
on the colouriser.
• The moulder can be operated for 16 hours a day and the
colouriser for 9 hours a day.
STEP BY STEP GUIDE
1. Formulate the problem
(i) pick out important information
(ii) formulate constraints
(iii) formulate objective function
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
5. Get the solution
• A digger needs 2 hours on the moulder and 1 hour on
the colouriser. A car needs 1 hour on the moulder and
1 hour on the colouriser.
• The moulder can be operated for 16 hours a day and
the colouriser for 9 hours a day.
• Using the decision variables
X1 = number of diggers
X2= number of cars
make two constraints from this information.
FORMING CONSTRAINT 1
THE MOULDER
• A digger needs 2 hours on the moulder and 1 hour on
the colouriser. A car needs 1 hour on the moulder and
1 hour on the colouriser.
• The moulder can be operated for 16 hours a day and
the colouriser for 9 hours a day.
2X1 + X2≤ 16
FORMING CONSTRAINT 2
THE COLOURISER
• A digger needs 2 hours on the moulder and 1 hour on
the colouriser. A car needs 1 hour on the moulder and
1 hour on the colouriser.
• The moulder can be operated for 16 hours a day and
the colouriser for 9 hours a day.
X1 + X2 ≤ 9
STEP BY STEP GUIDE
1. Formulate the problem
(i) pick out important information
(ii) formulate constraints
(iii) formulate objective function
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
5. Get the solution
PICKING OUT IMPORTANT INFORMATION
• A small factory produces two types of toys: cars and diggers. In the
manufacturing process two machines are used: the moulder and the colouriser.
• Each digger gives a profit of £16 and each car gives a profit of £14.
FORMING THE OBJECTIVE FUNCTION
• Each digger gives a profit of £16 and each car gives a profit
of £14.
• Let Z be the total profit; formulate the objective function
FORMING THE OBJECTIVE FUNCTION
• Each digger gives a profit of £16 and each car gives a profit of £14.
Z = 16X1 + 14X2
THE LINEAR PROGRAMMING PROBLEM
• MAXIMISE Z = 16X1 + 14X2
subject to the constraints:
(i) 2X1 + X2 ≤ 16
(ii) X1 + X2 ≤ 9
(iii) X1 ≥ 0 , X2 ≥ 0
• VERY IMPORTANT
• DON’T FORGET YOUR NON – NEGATIVITY CONSTRAINTS !
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
5. Get the solution
INTRODUCING SLACK VARIABLES
To change inequalities (i) and (ii) into equations we add slack variables s1
and s2
This gives:
(i) 2X1 + X2 + s1 = 16
(ii) X1 + X2 + s2 = 9
THE NEW LINEAR PROGRAMMING
PROBLEM
• MAXIMISE Z = 16X1 + 14X2 + 0s1 + 0s2
subject to the constraints:
2X1 + X2 + s1 + 0s2 = 16
X1 + X2 + 0s1 + s2 = 9
X1 ≥ 0 , X2 ≥ 0 , s1 ≥ 0 , s2 ≥ 0
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
5. Get the solution
We want to put all the information in the
form of a table. This is called the
initial tableau.
To form the initial tableau we need to
change the objective function from
Z = 16X1 + 14X2 + 0s1 + 0s2
to
Z – 16x1 – 14X2 – 0s1 – 0s2 = 0
FORMING THE INITIAL TABLEAU
Label the table with your basic variables, s1 and s2
and with your non – basic variables, X1 and X2.
BASIC
X1 X2 s1 s2 VALUE
VARIABLES
s1
s2
Z
FORMING THE INITIAL TABLEAU
2X1+ 1X2 + 1s1 + 0s2 = 16
1X1 + 1X2 + 0s1 + 1s2 = 9
Z – 16X1 – 14X2 – 0s1 – 0s2 = 0
BASIC
VARIABLES
X1 X2 s1 s2 VALUE
s1 2 1 1 0 16
s2 1 1 0 1 9
Z -16 -14 0 0 0
FORMING THE INITIAL TABLEAU
BASIC VALUE
VARIABLES
X1 X2 s1 s2
s1 2 1 1 0 16
s2 1 1 0 1 9
Z -16 -14 0 0 0
This is the objective row
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
(i) Identify pivotal column
(ii) Find θ-values
(iii) Identify pivotal row
(iv) Identify pivot
(v) Pivot
5. Get the solution
PIVOTAL COLUMN
• We now need to find where to pivot and we start by
entering the basis by choosing the column with the most
negative entry in the objective row.
BASIC VALUE
VARIABLES
X1 X2 s1 s2
s1 2 1 1 0 16
s2 1 1 0 1 9
Z -16 -14 0 0 0
This is the most negative coefficient with corresponding
variable X1 and it’s column is called the pivotal column. X1
is now called the entering variable.
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
(i) Identify pivotal column
(ii) Find θ-values
(iii) Identify pivotal row
(iv) Identify pivot
(v) Pivot
5. Get the solution
FINDING θ-VALUES
• You are now going to find the pivotal row and the leaving variable.
• You need to find θ-values.
1. Identify positive entries in the pivotal column.
2. Divide each entry in value column by the corresponding positive entry in the
pivotal column.
BASIC VALUE
VARIABLES
X1 X2 s1 s2
s1 2 1 1 0 16
s2 1 1 0 1 9
Z -16 -14 0 0 0
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
(i) Identify pivotal column
(ii) Find θ-values
(iii) Identify pivotal row
(iv) Identify pivot
(v) Pivot
5. Get the solution
PIVOTAL ROW
• For row (i) 16
2 8
• For row (ii) = 9
1 9
• The row with the smallest θ-value is called the
pivotal row.
• Here the pivotal row is row (i)
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
(i) Identify pivotal column
(ii) Find θ-values
(iii) Identify pivotal row
(iv) Identify pivot
(v) Pivot
5. Get the solution
THE PIVOT
The pivot!
BASIC VALUE
VARIABLES X1 X2 s1 s2
s1 2 1 1 0 16
The pivotal row s2 1 1 0 1 9
Z -16 -14 0 0 0
The pivotal column
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
(i) Identify pivotal column
(ii) Find θ-values
(iii) Identify pivotal row
(iv) Identify pivot
(v) Pivot
5. Get a solution
PIVOTING
1. Replace the leaving variable with the entering variable.
2. Divide all entries in the pivotal row by the pivot. The pivot
becomes 1.
3. Add suitable multiples of the pivotal row to all other rows until all
entries, apart from the pivot, in the pivotal column are zero.
Step 1 - Replace the leaving variable with the entering variable.
BASIC VALUE
VARIABLES
X1 X2 s1 s2
s1 2 1 1 0 16
s2 1 1 0 1 9
Z -16 -14 0 0 0
Step 2 - Divide all entries in the pivotal row by the pivot. The pivot
becomes 1.
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1
d 1 1/2 1/2 0 8
s2
Z
PIVOTING
BASIC VALUE
VARIABLES
X1 X2 s1 s2
s1 2 1 1 0 16
s2 1 1 0 1 9
Z -16 -14 0 0 0
Step 3 - Add suitable multiples of the pivotal row to all other rows until all
entries, apart from the pivot, in the pivotal column are zero.
row (ii) – ½ row (i)
gives
s2 0 1/2 -1/2 1 1
PIVOTING
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1 1 1/2 1/2 0 8
s2 0 1/2 -1/2 1 1
Z
PIVOTING
BASIC VALUE
VARIABLES
X1 X2 s1 s2
s1 2 1 1 0 16
s2 1 1 0 1 9
Z -16 -14 0 0 0
Step 3 - Add suitable multiples of the pivotal row to all other rows until all
entries, apart from the pivot, in the pivotal column are zero.
row (iii) + 8 row (i)
gives
Z 0 -6 8 0 128
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1 1 1/2 1/2 0 8
s2 0 1/2 -1/2 1 1
ZZ 0 -6 8 0 128
This is our second tableau
Second iteration
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1 1 1/2 1/2 0 8
s2 0 1/2 -1/2 1 1
ZZ 0 -6 8 0 128
This is the most negative coefficient pivotal column. X2 is
now called the entering variable.
PIVOTAL ROW
For row(i) θ= 8 X 2 =16
For row (ii) θ = ½ /1= ½
• The row with the smallest θ-value is called the
pivotal row.
• Here the pivotal row is row (ii)
THE PIVOT
The pivot!
BASIC VALUE
VARIABLES X1 X2 s1 s2
X1 1 1/2 1/2 0 8
s2 0 1/2 -1/2 1 1
The pivotal row Z 0 -6 8 0 128
The pivotal column
Step 1 - Replace the leaving variable with the entering variable.
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1 1 1/2 1/2 0 8
s2 0 ½ -1/2 1 1
Z -0 -6 8 0 128
Step 2 - Divide all entries in the pivotal row by the pivot. The pivot
becomes 1.
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1
d
X2 0 1 -1 2 2
Z
PIVOTING
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1 1 1/2 1/2 0 8
s2 0 ½ -1/2 1 1
Z -0 -6 8 0 128
Step 3 - Add suitable multiples of the pivotal row to all other rows until all
entries, apart from the pivot, in the pivotal column are zero.
row (i) – 1 x row (ii)
gives
X1 1 0 1 -1 7
PIVOTING
BASIC VALUE
VARIABLES
X1 X2 s1 s2
X1 1 1/2 1/2 0 8
s2 0 ½ -1/2 1 1
Z -0 -6 8 0 128
Step 3 - Add suitable multiples of the pivotal row to all other rows until all
entries, apart from the pivot, in the pivotal column are zero.
row (iii) + 12 row (ii)
gives
Z 0 0 4 12 140
OPTIMAL TABLEAU
BASIC
VARIABLES
X1 X2 s1 s2 VALUE
X1 1 0 1 -1 7
X2 0 1 -1 2 2
Z 0 0 2 12 140
• Note there are no negative entries in the objective
row.
• Can you see the solution?
STEP BY STEP GUIDE
1. Formulate the problem
2. Introduce slack variables
3. Form initial tableau
4. Obtain new tableaux
5. Get the solution
OBTAINING THE SOLUTION
BASIC
VARIABLES
X1 X2 s1 s2 VALUE
X1 1 0 1 -1 7
X2 0 1 -1 2 2
Z 0 0 2 12 140
• Remember that since s and t are now non–basic variables they
are set to zero.
• This corresponds to the solution:
s = 0, t = 0,
d=7
c=2
Z = 140
THE SOLUTION
• Don’t forget to put your solution back into the context of the
problem.
Z = 140
X1 = 7
X2 = 2
• The maximum profit is £140
• To make this profit the factory should produce 7 diggers and 2 cars.