Lecture_5_Introduction to simplex method

Linear Progamming :
Introduction to simplex method
and computational procedure for simplex method
5.1 Introduction
General Linear Programming Problem (GLPP)
Maximize / Minimize Z = c1x1 + c2x2 + c3x3 +……………..+ cnxn
Subject to constraints
a11x1 + a12x2 + …..........+a1nxn (? or ?) b1
a21x1 + a22x2 + ………..+a2nxn (? or ?) b2
.
.
.
am1x1 + am2x2 + ……….+amnxn (? or ?) bm
and
x1 ? 0, x2 ? 0,…, xn ? 0
Where constraints may be in the form of any inequality (? or ?) or even in the form of an
equation (=) and finally satisfy the non-negativity restrictions.
Step 3 – The right side element of each constraint should be made non-negative
2x1 +x2 – s2 = -15
-2x1 - x2 + s2 = 15 (That is multiplying throughout by -1)
Step 4 – All variables must have non-negative values.
For example: x1 +x2 ? 3
x1 > 0, x2 is unrestricted in sign
Then x2 is written as x2 = x2 ? – x2 ?? where x2 ?, x2 0 ? ??
Therefore the inequality takes the form of equation as x1 + (x2 ? – x2 ?? ) + s1 = 3
Using the above steps, we can write the GLPP in the form of SLPP.
1
Write the Standard LPP (SLPP) of the following
Example 1
Maximize Z = 3x1 + x2
Subject to
2 x1 + x2 ? 2
3 x1 + 4 x2 ? 12
and x1 ? 0, x2 ? 0
SLPP
Maximize Z = 3x1 + x2
Subject to
2 x1 + x2 + s1 = 2
3 x1 + 4 x2 – s2 = 12
x1 ? 0, x2 ? 0, s1 ? 0, s2 ? 0
Example 2
Minimize Z = 4x1 + 2 x2
Subject to
3x1 + x2 ? 2
x1 + x2 ? 21
x1 + 2x2 ? 30
and x1 ? 0, x2 ? 0
SLPP
Maximize Z 4 – = ? x1 – 2 x2
Subject to
3x1 + x2 – s1 = 2
x1 + x2 – s2 = 21
x1 + 2x2 – s3 = 30
x1 ? 0, x2 ? 0, s1 ? 0, s2 ? 0, s3 ? 0
Example 3
Minimize Z = x1 + 2 x2 + 3x3
Subject to
2x1 + 3x2 + 3x3 ? – 4
3x1 + 5x2 + 2x3 ? 7
and x1 ? 0, x2 ? 0, x3 is unrestricted in sign
SLPP
Maximize Z? = – x1 – 2 x2 – 3(x3
? – x3
(??
Subject to
–2x1 – 3x2 – 3(x3
? – x3
?? ) + s1= 4
3x1 + 5x2 + 2(x3
? – x3
?? ) + s2 = 7
x1 ? 0, x2 ? 0, x3
0 ? ? , x3
0 ? ?? , s1 ? 0, s2 ? 0
2