Linear Programming
Simplex Method
Mathematical Sciences Department
Outline
1. Introduction & Conditions for Simplex method
2. Procedure for Simplex Method
Linear Programming (LP)
3. Maximization Problems
1. Introduction & Conditions
Conditions
The LPP must be maximization in nature,
All constraints (except the non-negative ones) must involve inequalities.
Linear Programming (LP)
All constraints must have +ve constants on the RHS (of
Dfn: STD Form of an LPP
A linear programming problem is said to be in std [maximization] form if it is
of the form:
Subject to constraints of the form:
where , and is any real number
Introduction cont…
Std form is when:
All the variables are non-negatives
All constraints can be written as a linear expression that is
Linear Programming (LP)
less than or equal to a positive constant
Exercise: Std or Not std?
Z Max 5 x1 8 x2 x3
Z Max 3x1 x2
Subject to
Subject to
Linear Programming (LP)
x1 x2 3
x1 2 x2 4 Z Max 4 x1 2 x2 x3 2 x1 3x2 14
x1 3x2 10 Subject to x1 3x2 x3 3
xi 0 3x1 x2 10 xi 0, i 1, 2,3
2 x2 x3 10
x1 0, x2 0
Exercise cont…
Yes, Std Form
Z Max 3x1 x2
Linear Programming (LP)
Subject to
x1 2 x2 4
Positives constants
x1 3x2 10
xi 0
All variables Less than or
non-negatives equal
Exercise cont…
Not in Std Form
Z Max 4 x1 2 x2 x3
Linear Programming (LP)
Subject to
3x1 x2 10
2 x2 x3 10
x1 0, x2 0 x-3 not specified as a non-negative variable
Exercise cont…
Z Max 5 x1 8 x2 x3 Not in Std Form
Linear Programming (LP)
Subject to
x1 x2 3
2 x1 3x2 14
3rd inequality does not have less than or
x1 3x2 x3 3 equal
xi 0, i 1, 2,3 However, can be made std by multiplying the
3rd inequality by -1
Activity
Determine whether the LP model is in std form? If not, cant it be
modified?
Z Max 22 x1 8 x2 5 x3
Linear Programming (LP)
Subject to
Not in Std Form
x1 7 x2 3 x3 3 Can’t be modified
2 x1 3x2 14
x1 3x2 2 x3 5
x1 0, x2 0, x3 0
Introduction cont…
Dfn: Slack Variable
A variable that is added to the LP constraint to make up for the
Linear Programming (LP)
difference between the left- and right-hand sides of an inequality
They represent the unused resources
Denoted corresponding to the constraints
E.g.: Make LHS = RHS
Add a slack variable
2. Procedure for Simplex Method
Step 1: Formulate LP model
Step 2: Transpose all the terms in the OF to the side of Z to end
up with an expression that is equated to 0
Linear Programming (LP)
Step 3: Turn constraint inequalities into equations by adding
slack variables,
Step 4: Present the equations in a augmented matrix form –
coefficients only
Place the OF coefficients at the bottom
The resultant matrix is called the Initial Simplex Tableau/Table
Procedure for SM cont…
BV … … RHS
- - - … 1 0 0 … -
Linear Programming (LP)
- - - … 0 1 0 … -
- - - … 0 0 1 … -
: : : : : : : : : :
: : : : : : : : : :
Z - - - … 0 0 0 … 0
Basic Variable (BV): A variable that has a coefficient of 1 and 0s
elsewhere in its column
Example
The LPP below is in std form. Set up the initial simplex tableau.
Z Max 22 x1 8 x2 5 x3
Linear Programming (LP)
Subject to
x1 7 x2 3 x3 3
2 x1 3x2 x3 14
x1 3x2 2 x3 5
x1 0, x2 0, x3 0
Solution Move all terms
Initial simplex tableau: from RHS to LHS
Z Max 22 x1 8 x2 5 x3 Z Max 22 x1 8 x2 5 x3 0
Linear Programming (LP)
Subject to Add slack variable
to each
x1 7 x2 3 x3 3 x1 7 x2 3 x3 S1 3
2 x1 3x2 x3 14 2 x1 3x2 x3 S 2 14
x1 3x2 2 x3 5 x1 3x2 2 x3 S3 5
x1 0, x2 0, x3 0 The slacks must xi 0, Si 0,
be non-negative
too
Solution cont…
Z Max 22 x1 8 x2 5 x3 0
Decision & Slack Variables s.t.
BV RHS
x1 7 x2 3x3 S1 3
Linear Programming (LP)
Variables
1 7 3 1 0 0 3
2 x1 3x2 x3 S 2 14
Basic
2 -3 1 0 1 0 14
5
x1 3x2 2 x3 S3 5
1 3 2 0 0 1
Z -22 8 -5 0 0 0 0 xi 0, Si 0
Initial simplex tableau
Activity
Set up the initial simplex tableau:
a) b)
Linear Programming (LP)
Z Max 2 x1 3x2 x3 PMax x1 5 x2 3x3 6 x4
s.t.: S.t.:
x1 x2 x3 50 x1 x2 2 x3 2 x4 8
3x1 2 x2 x3 10 x1 x2 x3 x4 10
xi 0, i 1, 2,3 x1 x2 x3 x4 12
x1 0, x2 0, x3 0, x4 0
Solution
a) b)
BV RHS BV RHS
Linear Programming (LP)
1 1 1 1 0 50 -1 1 -2 2 1 0 0 8
3 2 1 0 1 10 1 -1 -1 1 0 1 0 10
Z -2 -2 -1 0 0 0 1 1 1 1 0 0 1 12
P -1 -5 -3 -6 0 0 0 0
Initial simplex tableaus
Procedure for SM cont…
Step 5: Identify key/pivot column, row and element
Key column = Column with the most –ve entry in the OF row
Find the ratios by dividing RHS entries by key column entries
Linear Programming (LP)
Key row = Row with the least +ve ratio
Key element = Entry where key column and row
meet/intersect
Step 6: Turn key element to 1 and other elements in the key
column to zeros (0s) using pivoting (row operation).
Do not swap rows
Repeat the process until the optimal solution is obtained [if it
Procedure for SM cont…
Note
If all entries of the OF row are +ve or 0: The Tableau is final
and a solution is reached.
Linear Programming (LP)
If all entries of the ratios are –ve or 0, The LPP is unbounded
and is infeasible
When you move from one tableau to another, the BVs
change with pivoting – One BV exits while a non BV enters
3. Maximization Example
The LP Model (from Example 1) is given below.
Maximise
Linear Programming (LP)
Subject to
where = number of standard tents
= number of expedition tents
Solve the LPP using the simplex method.
Solution
Step 1-4: Converting the model to initial tableau:
Z Max 50, 000 x1 80, 000 x2
Linear Programming (LP)
s.t. :
x1 2 x2 s1 32
3 x1 4 x2 S 2 84 Initial tableau
xi 0
BV RHS
1 2 1 0 32
3 4 0 1 84
Z -50,000 -80,000 0 0 0
Key column:
Solution cont… Most –ve in OF is -80,000
2nd column is key
Step 5: Key column, key row & pivot element: Key row:
Find ratios: RHS Key column
Entering Variable Least +ve ratio is 16
Linear Programming (LP)
Initial tableau 1st row is key
BV RHS Ratio Pivot element:
Intersection of key column & row
1 2 1 0 32 16 2 is the pivot element
3 4 0 1 84 21
Z -50,000 -80,000 0 0 0
Exiting Variable
To produce 2nd tableau
Solution cont… Turn pivot element into 1:
Step 6: Turn pivot element into 1, rest into 0s
Other key column entries into 0:
Initial tableau
Enter
BV RHS Ratio
Linear Programming (LP)
Check if 2nd tableau has optimal
Exit 1 2 1 0 32 16 solution
3 4 0 1 84 21 OF still has –ve #
Not optimal solution
Z -50,000 -80,000 0 0 0 Repeat Steps 5 - 6
Enter
2nd tableau: BV RHS Ratio
1/2 1 1/2 0 16 32
Exit 1 0 -2 1 20 20
Z -10,000 0 40,000 0 1,280,000
To produce 3rd tableau
Solution cont… Turn pivot element into 1:
Already 1
Step 6: Turn pivot element into 1, rest into 0s Other key column entries
2nd tableau into 0:
Enter
BV RHS Ratio
Linear Programming (LP)
½ 1 ½ 0 16 32 Check if 3rd tableau has
optimal solution
Exit 1 0 -2 1 20 20 OF has +ve #s & 0s
Optimal solution
Z -10,000 0 40,00 0 1,280,000 3rd tableau is FINAL
0
3rd tableau: BV RHS
0 1 11/2 -1/2 6
1 0 -2 1 20
Z 0 0 20,000 10,000 1,480,000
Solution cont…
The optimal OF value is 1,480,000 and occurs when
and .
Linear Programming (LP)
Therefore, the optimal profit is K1,480,000 and will be occur when the
company makes and sells 20 standard tents and 6 expedition mountain
tents. At this level of production, all resources (i.e. time for cutting and
assembly) will be used up completely.
Example: Product Mix
Mbalunji Real Estates intends to construct houses in Blantyre, Lilongwe,
Mzuzu and Zomba. The construction involves three stages – Walls,
Roofing and Finishes. The maximum times (labour-weeks) available for
Linear Programming (LP)
each stage are: Walls – 4,000, Roofing – 1,800 and Finishes – 1,000. The
times required for and profit from each house are given below
Location of House
Stage Lilongwe Blantyre Mzuzu Zomba
Walls 2 2.5 2 2
Roofing 1 1.5 1 2
Finishes 0.5 0.5 1 1
Profit (K million) 5 10 15 20
Example cont…
a) How many houses, in each location, should be constructed to
maximize profit?
b) Analyze/interpret the solution.
Linear Programming (LP)
Activity
Solve the following LPP using simplex method:
a) PMax 3x1 2 x2 5 x3 b) Z Max 10 x1 5 x2 c) Z Max 6 x1 3x2
s.t.: s.t.: s.t.:
Linear Programming (LP)
x1 2 x2 x3 430 4x1 x2 28 -2x1 3x2 9
3x1 2 x3 460 2 x1 3x2 24 x1 3x2 12
x1 4 x2 420 x1 , x2 , 0 xi 0
x1 , x2 , x3 0
No solution
Thank You.