Linear programming (10 Hrs.

)
Linear Programming
Linear programming is a method of solving problem in which
objective function represented by a linear equation, often profit
or cost, is to be optimized (i.e. maximized or minimized) subject
to constraints (conditions) expressed by a system of linear
inequalities. In short, linear programming is an optimization
technique for finding the optimum solution to objective function
of two or more decision variables subject to a set of linear
constraints.
Linear programming is heavily used in economics and company
management such as planning, production, transportation,
technology and other issues. It has also been extensively applied
in solving resource allocation problem such as production,
planning and scheduling, portfolio analysis, sales and advertising
etc. The most of companies would like to maximize profit or
minimize cost with limited resources.
Therefore, Linear programming problem (LPP) deals with finding
optimal allocation of limited resources (e.g. men, materials, machines
and land) to meet given objectives. Note that LPP is very often used by
operating practitioner or decision maker for planning or analysis in
achieving the objective in a best way.

The main objective of any industrial organization is to optimize the use

of their limited resources for maximizing the profit or minimizing cost.
The term 'programming' means planning and the term 'linear' implies
that the equations or inequalities involved in the problem would be
linear. The technique of linear programming first invented by Russian
Mathematician L.V. Kantorovich in 1939 and developed later by George
B. Dantzig in 1947. A linear programming problem (LPP) involves a
linear function of a number of variables in the form of equations or in
equations, subject to certain conditions of the variables and the task is
to maximize or minimize (i.e., optimise) the objective function. Here,
we discuss the LPP on two more than two variables .
Basic Terminologies used in Linear programming
Decision variables: Decision variables are those non-negative
independent variables that are to be determined in the solution of
the linear programming problem. Men, material, machines etc.
are the examples of decision variables. They are generally
denoted by x1, x2, x3, . . . . . . . . ,xn.
Objective function: The linearly expressed function of decision
variables which is to be optimized linear programming problem
subject to given conditions is called the objective function. Thus,
the goal of the linear objective function is to maximize or to
minimize the function. It is usually represented as
Objective function z = c!x! + c"x" + c#x#+ . . . . . . . . . . . +c$x$
Where, c!, c", c# . . . . . . . . . , c$ are constants and x!, x", . . . . . . . . , x$
are decision variables.
Constraints: The conditions or restrictions or limitations imposed on
the available resources in solving linear programming problem are
called constraints. That is, restrictions imposed on the available
resources are called constraints. There should be limitation on
resources which are to be allocated among various competing
activities. These resources may be raw materials, human resources,
time, machinery, budget etc. The constraints are expressed in linear
equations or inequalities in terms of decision variables. For example
a!!x! + a!"x" + a!#x#+ . . . . . . . . +a!$x$ ≥ b!
a"!x! + a""x" + a"#x#+ . . . . . . . . +a"$x$ ≥ b"
.. .. .. ..
.. .. .. ..
a$!x! + a$"x" + a$#x#+ . . . . . . . . +a$$x$ ≥ b$
Where,a!!, a!", . . . . . . . . . , a$$ are constants and x!, x", . . . . . . . . , x$ are
decision variables.
Non-Negativity constraints: The linear inequalities x ≥ 0 and
y ≥ 0 are called non-negativity constraints. The non-negativity
constraints are relating to the restricted decision variables. If the
decision variables or activities of the linear programming are
concerned with physical quantities, the values of the decision
variables are assumed to be non negative. It is always true that
physical quantity never be negative. For instance, time,
production of shirts, toys, materials etc.
Feasible solution: The set of values of decision variables
x!, x", . . . . . . . . , x$ which satisfy all the constraints and non
negativity conditions of a linear programming problem (LPP)
simultaneously is said to be feasible solution. That is, any point in
the feasible region is called feasible solution of the linear
programming. Any feasible solution which optimizes (i.e.
maximize or minimize) the objective function of given LPP is
called an optimal feasible solution. The optimal solution is the
best of the feasible solutions. In solving LPP, the attempts are
made to get optimal feasible solution.
— Basic Variables: The basic variables column contains all the
variables which form an identity matrix. In other words, the
variables whose coefficients form identity matrix or unit
matrix are called basic variables.
Examples of identity matrix:
1 0 0
1 0
, 0 1 0 , etc
0 1
0 0 1
— Slack Variables: Unused capacity or idle capacity. It is
associated with less than or equal to ≤ , less than (<) in the
constraints of given linear programming problem.
— Surplus Variables: Shortage capacity. It is associated with
greater than or equal to ≥ , greater than (>) in the
constraints of given linear programming problem.
Simplex Tableau:
C! Ratio (b" /X" )
C# X# b"

Z!
Z! − C!

Where,
C! = Coefficients of all variables of objective function.
C" = Coefficients of basic variables of objective function.
X " = Basic variable.
b# = Constant of equations or inequalities.
Z! = Objective function
= ∑ C" b# or others
Z! − C! = Optimum net evaluation.
Note I:
To solve the linear programming by simplex method
Introduce slack, surplus and dummy variables in the given
constraints are as follows:
(i) ≤ or < →Add slack variable (S)
(ii) ≥ or > → Subtract surplus variable (S) and Dummy
variables(D)
(iii) = → Add dummy variable (D) or artificial variable (A).

Note II: Since, an identity matrix (Unit matrix) is formed by the

coefficients of Slack and dummy variables. So, only slack and
dummy variables are basic variables for initial simplex tableau.
Example 1
Solve the LP problem by simplex method
Maximize Z = 5X!+8X "
Subject to the constraints
4X!+ 6X " ≤ 24
2X!+ X " ≤ 18
3X!+ 9X " ≤ 36
and X!, X " ≥ 0
Solution:
After Introducing (adding) the slack variables S!, S" and S# to the
constraints, the given LPP becomes
Maximize Z = 5X!+ 8X "+ 0S!+ 0S"+ 0S#
Subject to the constraints
4X!+ 6X "+S!= 24
2X!+ X " +S"= 18
3X!+ 9X "+S#= 36
and X!, X ", S!, S", S# ≥ 0
The above three constraints can be written in matrix form
AX = b as

X!
4 6 1 0 0 X" 24
2 1 0 1 0 S! = 18
3 9 0 0 1 S" 36
S#
A X b
Here, an identity matrix is formed by the coefficients of slack
variables S!, S" & S#. So these slack variables are the basic
variables for initial simplex tableau. The initial simplex tableau
can be constructed as follows:
Initial Simplex Tableau
C! 5 8 0 0 0 Ratio (b" /X" )
C# X# b" 𝑋$ 𝑋% 𝑆$ 𝑆% 𝑆&
0 𝑆$ 24 4 6 1 0 0 %'
(
=4 Key row

0 𝑆% 18 2 1 0 1 0 $)
= 18
$
&(
0 𝑆& 36 3 9 0 0 1 =4
*
Z! 0 0 0 0 0 0
Z! − C! -5 -8 0 0 0

Key column
Here, X " → entering variable
Since, there are two same minimum positive ratio in the ratio
column, degeneracy occurs. To avoid degeneracy, select first row
R! as key row by choosing the ratio to the top and the
corresponding variables S! is a leaving variable. Also, 6 is a key
element.
Main row (or Rep. R!):
./01 ! "7 7 " 8 ! 9 9
= 234 3/353$6 = 8
= 4; 8 = #; 8 = 1; 8; 8 = 0; 8 = 0
For new 𝑹𝟐 :
Old 𝑅" - (Intersectional element of old 𝑅"× Main Row) = New 𝑅"
18 - ( 1 × 4) = 14
" 7
2 - (1 × ) =
# #
1 - (1 × 1) = 0
! ;!
0 - (1 × ) =
8 8
1 - (1 × 0) = 1
0 - (1 × 0) = 0
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Rep. R!) = New R #
36 - (9 × 4) = 0
"
3 - (9 × ) = -3
#
9 - (9 × 1) = 0
! ;#
0 - (9 × ) =
8 "
0 - (9 × 0) = 0
1 - (9 × 0) = 1
 Simplex tableau – 2
C! 5 8 0 0 0 Ratio
C# X# b" X$ X% S$ S% S&
8 X% 4 % $ -
&
1 (
0 0

0 S% 14 ' +$ -
0 1 0
& (
0 S& 0 -
+&
-3 0 0 1
%
$( '
Z! 32 8 0 0
& &
Z! − C! $ '
0 0 0
& &

Since, all (Z= -C= ) ≥ 0, an optimum feasible solution has been

obtained.
Thus, the optimal solution is, X " = 4, X! = 0 and max Z = 32.
Big-M method
Example 2: Solve the following problems by the simplex method:
Minimize Z = 3X! + 2X "
Subject to the Constraints
2X!+ 4X " ≥ 10
4X! + 2X " ≥ 10
X" ≥ 4
and X!, X " ≥ 0
Solution:
After introducing the surplus and dummy variables to the
constraints, the standard form of the LP problem becomes
Minimize Z = 3X! + 2X " + 0S! + 0S" + 0S# + MD! + MD" + MD#,
where M is the high positive value.
Subject to the constraints
2X!+ 4X " - S! + D! = 10
4X! + 2X " - S" + D" = 10
X " - S# + D# = 4
and X!, X ", S!, S", S#, D!, D", D# ≥ 0
i.e. 2X! + 4X " - 1S! + 0S" + 0S# + 1D! + 0D" + 0D# = 10
4X! + 2X " + 0S! - 1S" + 0S# + 0D! + 1D" + 0D# = 10
0X! + 1X " + 0S! + 0S" - 1S# + 0D! + 0D" + 1D# = 4
These three constraints can be written in matrix from AX = b as

X!
X"
S!
2 4 −1 0 0 1 0 0 S 10
4 2 0 −1 0 0 1 0 S" = 10
#
0 1 0 0 −1 0 0 1 4
D!
D"
D#
Here, an identity matrix is formed by the coefficient of variables
D! , D" , D# . So these variables are basic variables for initial
simplex tableau. The above information is entered into the
simplex tableau as follows:
Initial Simplex Tableau
C! 3 2 0 0 0 M M M Ratio
C# X# b" 𝑋$ 𝑋% 𝑆$ 𝑆% 𝑆& 𝐷$ 𝐷% 𝐷& (b" /X" )

M 𝐷$ 10 2 4 -1 0 0 1 0 0 $,
'
= 2.5 Ke

M 𝐷% 10 4 2 0 -1 0 0 1 0 $,
=5
%
'
M 𝐷& 4 0 1 0 0 -1 0 0 1 =4
$
Z! 24M 6M 7M -M -M -M M M M
Z! − C! 6M-3 7M-2 -M -M -M 0 0 0

Key column
 ./0 1!
=
@34 3/353$6
!9 A " ! 7 ;! 9 9 ! 9 9
Main row (or Rep.𝑅!): = ; = ; = 1; ; = 0; = 0; ; = 0; = 0.
7 " 7 " 7 7 7 7 7 7 7
For new 𝐑 𝟐 :
Old 𝑅" - (Intersectional element of old 𝑅"× Main Row) = New 𝑅"
A
10 – ( 2 × "
) =5
!
4 – (2 × ") = 3
2 – (2 × 1) = 0
;! !
0 – (2 × 7
) = "
-1 – (2 × 0) = -1
0 – (2 × 0) = 0
! ;!
0 – (2 × 7) = "
1 – (2 × 0) = 1
0 – (2 × 0) = 0
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Rep. R!) = New R #
A #
4 – (1 × "
) = "
! ;!
0 – (1 × "
) = "
1 – (1 × 1) = 0
;! !
0 – (1 × 7
) = 7
0 – (1 × 0) = 0
-1 – (1 × 0) = -1
! ;!
0 – (1 × ) =
7 7
0 – (1 × 0) = 0
1 – (1 × 0) = 1
 Simplex tableau – 2
C! 3 2 0 0 0 M M M Ratio
C# X# b" X$ X% S$ S% S& D$ D% D&
2 X% - $ +$ $ 5
%
1 '
0 0 '
0 0
%

M D% -
5 $ +$
3 0 -1 0 1 0 &
% %
+$ $ +$
M D& & 0 0 -1 0 1
% ' ' -3
%
Z! $&. -. &. $ +&/ $
%
+5 %
+1 2 '
-% -M -M '
+% M M
Z! − C! -. &. $ +0/ $
%
-2 0 '
-% -M -M '
+% 0 0

Key column
A # 9 ! ;! 9 ;! ! 9
Main row (or Rep. 𝑅") : #; # = 1; # = 0; 8; , =
# #
0, , , =
8 # #
0
For new 𝑹𝟏 :
Old 𝑅! - (Intersectional element of old 𝑅!× Main Row) = New 𝑅!
A ! A A
- ( × )=
" " # #
! !
"
- (" × 1) = 0
!
1 - (" × 0) = 1
;! ! ! ;!
7
- (" × 8) = #
! ;! !
0 - (" × # ) = 8
!
0 - (" × 0) = 0
! ! ;! !
-( × 8) =#
7 "
! ! ;!
0 – (" × #) = 8
!
0 – (" × 0) = 0
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Rep. R ") = New R #
# ;! A E
"
– ( "
× #
) = #
;! ;!
– ( × 1) = 0
" "
;!
0 – ( " × 0) = 0
! ;! ! !
7
– ( " × 8) = #
;! ;! ;!
0–(" × #)= 8
;!
-1 – ( " × 0) = -1
;! ;! ;! ;!
7
– ( "
× 8
) = #
;! ! !
0 – ( " × #) = 8
;!
1 – ( " × 0) = 1
Simplex Tableau-3

C! 3 2 0 0 0 M M M Ratio
C# X# b" X$ X % S$ S% S& D$ D% D&
2 X% - +$ $ $ +$ -5
0 1 & (
0 & (
0
&

3 X$ - $ +$ +$ $ 10
1 0 0 0
& ( & ( &
M D& 7
0 $ +$ +$ $
0 0 -1 1
& & ( & (
Z! 0. $- . $ +. % +. $ . %
+ 3 2 - - -M + + M
& & & ( ( & & ( ( &
Z! − C! . $ +. % +'. $ +-. %
0 0 &
- ( (
- &
-M &
+( (
+& 0

Key column
Main row (Rep. 𝐑 𝟑 ):
% ' (' (' (' ' '
×3 = 7; 0×3 = 0; ×3 = 1; ×3= ; -3; ×3 = -1; ×3 = ; 1×3 =
& & ) * & ) *
3
For new 𝐑 𝟏 :
Old R' - (Intersectional element of old R' × Main Row) = New R'
, ('
-( × 7) = 4
& &
('
0-( × 0) = 0
&
('
1 - ( × 0) = 1
&
(' ('
- ( × 1) = 0
& &
' (' ('
-( × )=0
) & *
('
0-( × -3) = -1
&
' ('
-( × -1) = 0
& &
(' (' '
-( × )=0
) & *
('
0–( × 3) = 1
&
For new 𝑹𝟐 :
Old R " - (Intersectional element of old R "× Main Row) = New R "
A ! !
– ( × 7) =
# 8 "
!
1 – (8 × 0) = 1
!
0 – ( × 0) = 0
8
! !
8
– (8 × 1) = 0
;! ! ;! ;!
–( × )=
# 8 " 7
! !
0 – (8 × -3) = "
;! !
8
– ( 8
× -1) = 0
! ! ! !
#
– (8
× "
) = 7
! ;!
0 – (8 × 3) = "
Simplex tableau- 4
C! 3 2 0 0 0 M M M Ratio
C# X# b" 𝑋$ 𝑋% 𝑆$ 𝑆% 𝑆& 𝐷$ 𝐷% 𝐷& (b" /X" )

2 𝑋% $ +$ $ $ +$ −
%
1 0 0 ' %
0 ' %

3 𝑋$ −
4 0 1 0 0 -1 0 0 1
0 𝑆$ +$ $ −
7 0 0 1 -3 -1 2
% %
Z! 13 +$ $
2 3 0 %
-2 0 %
2
Z! − C! +$ $
0 0 0 -2 -M -M 2-M
% %

Since, all (Z= -C= ) ≤ 0, an optimum feasible solution has been

obtained.
!
Thus, the optimal solution is, X! = 4, X " = and Min Z = 13.
"
TU 2079 (ORS 255)(BIT)
Solve the given Linear Programming Problem (LP) by using
simplex method and interpret the results.
Minimize Z= 25A + 10B
Subject to constraints
A + B = 50
A ≥ 20
B ≤ 40
Where, A, B ≥ 0
Solution:
After introducing the surplus, dummy and slack variables to the
constraints, the standard form of the LP problem becomes
Minimize Z = 25A + 10B + 0S!+ 0S" + MD! + MD"
where M is the high positive value.
Subject to the constraints
A + B + D!= 50
A - S!+ D" = 20
B + S" = 40
& A, B, S!, S",D!, D" ≥ 0
The above constraints can be written in matrix form AX = b as
𝐴
𝐵
1 1 0 1 0 0 S 50
!
1 0 −1 0 1 0 D = 20
!
0 1 0 0 0 1 D 40
"
S"
Here, an identity matrix is formed by the coefficient of variables
D! , D" , S" . So these variables are basic variables for initial
simplex tableau. The above information is entered into the
simplex tableau as follows:
 Initial Simplex Tableau -I
C! 25 10 0 M M 0 Ratio (b" /X" )
C# X# b" A B. 𝑆$ 𝐷$ 𝐷% 𝑆%
M 𝐷$ 50 1 1 0 1 0 0 -,
$
= 50
%,
M 𝐷% 20 1 0 -1 0 1 0 ,
= ∞

0 𝑆% 40 0 1 0 0 0 1 ',
= 40 Ke
$
Z! 70M 2M M -M M M 0
Z! − C! 2M-25 2M-10 -M 0 0 0

Key column
 ./0 1"
Main row (or Rep.𝑅#): = @34 3/353$6
79 9 ! 9 9 9 !
= = 40, = 0, =1; = 0; = 0 ; = 0; = 1
! ! ! ! ! ! !
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main Row) = New R!
50 - (1 ×40) = 10
1 - (1 ×0) = 1
1 - (1 × 1) = 0
0 - (1 × 0) = 0
1 - (1 × 0) = 1
0 - (1 ×0) = 0
0 - (1 ×1) = -1
For new 𝐑 𝟐 :
Old R " - (Intersectional element of old R "× Main Row) = New R "
20 - (0×40) = 20
1 - (0 ×0) = 1
0 - (0 × 1) = 0
-1- (0 × 0) = -1
0 - (0 × 0)= 0
1 - (0 ×0) = 1
0 - (0×1) = 0
 Simplex Tableau -II
C! 25 10 0 M M 0 Ratio (b" /X" )
C# X# b" A B. 𝑆$ 𝐷$ 𝐷% 𝑆%
M 𝐷$ 10 1 0 0 1 0 -1 $,
$
= 10 Ke
M 𝐷% 20 1 0 -1 0 1 0 %,
= 20
$
',
10 B 40 0 1 0 0 0 1 =∞
,
Z! 30M 2M 10 -M M M -M+10
+400
Z! − C! 2M-25 0 -M 0 0 -M+10

Key column
 ./0 1!
Main row (or Rep.𝑹𝟏 ): = @34 3/353$6
!9 ! 9 9 ! 9 ;!
= = 10, = 1, = 0; = 0; = 1 ; = 0; = -1
! ! ! ! ! ! !
For new 𝐑 𝟐 :
Old R " - (Intersectional element of old R "× Main Row) = New R "
20 -(1 ×10) = 10
1 - (1 ×1) = 0
0 - (1 × 0) = 0
-1- (1 × 0) = -1
0 - (1 ×1 )= -1
1 - (1 ×0) = 1
0 -(1 ×−1)=1
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Main Row) = New R #
40 - (0×10) = 40
0 - (0 ×1) = 0
1 - (0 × 0) = 1
0- (0 × 0) = 0
0 -(0 × 1) = 0
0 - (0 ×0) = 0
1- (0×−1) = 1
 Simplex Tableau -III
C! 25 10 0 M M 0 Ratio (b" /X" )
C# X# b" A B. 𝑆$ 𝐷$ 𝐷% 𝑆%
25 A 10 1 0 0 1 0 -1 $,
+$
= -10

M 𝐷% 10 0 0 -1 -1 1 1 $, Ke
= 10
$
',
10 B 40 0 1 0 0 0 1 = 40
$
Z! 10M 25 10 -M -M+25 0 M -15
+650
Z! − C! 0 0 -M -2M+25 -M M+10

Key column
 ./0 1#
Main row (or Rep.𝑹𝟐 ): = @34 3/353$6
!9 9 9 ;! ;! ! !
= = 10, = 0, = 0; = -1; = -1 ; = 1; = 1
! ! ! ! ! ! !
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main Row) = New R!
10 - (-1 ×10) = 20
1 - (-1 ×0) = 1
0 - (-1 × 0)= 0
0 - (-1 × -1) =-1
1 - (-1 ×-1 )= 0
0 - (-1 ×1) = 1
-1 -(-1 ×1) = 0
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Main Row) = New R #
40 - (1×10) = 30
0 - (1 ×0) = 0
1 - (1 × 0) = 1
0- (1 × -1) = 1
0 -(1 × -1) = 1
0 - (1 ×1) = -1
1- (1×1) = 0
 Simplex Tableau –IV
C! 25 10 0 M M 0 Ratio (b" /X" )
C# X# b" A B. 𝑆$ 𝐷$ 𝐷% 𝑆%
25 A 20 1 0 -1 0 1 0 $,
+$
= -10

0 𝑆% 10 0 0 -1 -1 1 1 $,
= 10
$
',
10 B 30 0 1 1 1 -1 0 = 40
$
Z! 800 25 10 -15 10 15 0
Z! − C! 0 0 -15 -M+10 -M+15 0

Since, all (Z= -C= ) ≤ 0, an optimum feasible solution has been

obtained.
Thus, the optimal solution is, A = 20, B = 30 and Min Z = 800.
Example 3:
Use the penalty (Big-M) method to solve the following LP
problem.
Minimize Z = 5X! + 3X "
Subject to the constraints
2X! + 4X " ≤ 12
2X! + 2X " = 10
5X! + 2X " ≥10
and X!, X " ≥ 0
Solution:
After introducing slack variables S! , surplus variable S" and
artificial variables (Dummy variables) D! and D" in the
constraints of the given LP problem, the standard from of the LP
problem is stated as follows.
Minimize Z = 5X! + 3X " + 0S"+ 0S! + MD! + MD"
Subject to the constraints
2X! + 4X " + S! = 12
2X! + 2X " + D! = 10
5X! + 2X " - S" + D" = 10
and X!, X ", S!, S", D!, D" ≥ 0
The above constraints can be written in matrix form AX = b as

X!
X"
2 4 0 1 0 0 S" 12
2 2 0 0 1 0 = 10
S!
5 2 −1 0 0 1 10
D!
D"
Here, an identity matrix is formed by the coefficients of variables
S!, D! & D". So, S!, D! & D" are basic variables for initial simplex
tableau.
Initial Simplex Tableau – 1
C! 5 3 0 0 M M Ratio (b" /X" )
C# X# b" 𝑋$ 𝑋% 𝑆% 𝑆$ 𝐷$ 𝐷%
0 𝑆$ 12 2 4 0 1 0 0 $%
%
=6

M 𝐷$ 10 2 2 0 0 1 0 $,
=5
%
$,
M 𝐷% 10 5 2 -1 0 0 1 =2 Key row
-
Z! 20M 7M 4M -M 0 M M
Z! − C! 7M-5 4M-3 -M 0 0 0

Key column
!9 A " ;! 9 9 !
Main row (Rep 𝑅#): A
= 2; A = 1; A; ; =
A A
0; A = 0; A
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main Row) = New R!
12 - (2 × 2) = 8
2 - (2 × 1) = 0
" !8
4 - (2 × A) =A
;! "
0- (2 × ) =
A A
1 - (2 × 0) = 1
0 - (2 × 0) = 0
! ;"
0 - (2 × A) = A
For new 𝐑 𝟐 :
Old R " - (Intersectional element of old R "× Rep. R #) = New R "
10 - (2 × 2) = 6
2 - (2 × 1) = 0
" 8
2 - (2 × A) = A
;! "
0 - (2 × )=
A A
0 - (2 × 0) = 0
1 - (2 × 0) = 1
! ;"
0 - (2 × A) = A
Simplex tableau – 2
C! 5 3 0 0 M M Ratio
C# X# b" 𝑋$ 𝑋% 𝑆% 𝑆$ 𝐷$ 𝐷% (b" /X" )
$( % +% !
0 𝑆$ 8 0 1 0 "# - Key row
- - - =
- %
M 𝐷$ 6 ( % +%
0 0 1 5
- - -
5 𝑋$ 2
% +$ $ 5
1 0 0
- - -
Z! 6M + 10 (/ %/ +%/
5 +2 -1 0 M +1
- - -
Z! − C! (/ %/ +0/
0 -1 -1 0 0 +1
- - -

Key column
 A A A !8 A " A ! A A
Main row: 8 × = ; 0 × = 0; × = 1; × = , 1× = ; 0
!8 " !8 A !8 A !8 I !8 !8
A ;" A ;!
× = 0; × =
!8 A !8 I
For new 𝐑 𝟐 :
Old R " - (Intersectional element of old R "× Main row) = New R "
8 A
6 - (A × ") = 3
8
0 - (A × 0) = 0
8 8
- ( × 1) = 0
A A
" 8 ! !
-
A A
( × I
) = 7
8 A ;#
0 - (A × !8) = I
8
1 - (A × 0) = 1
;" 8 ;! ;!
A
- (A × I ) = 7
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Main row) = New R "
" A
2 - (A × ") = 1
"
1 - (A × 0) = 1
" "
- ( × 1) = 0
A A
;! " ! ;!
-( × )=
A A I 7
" A ;!
0-( × )=
A !8 I
"
0 - (A × 0) = 0
! " ;! !
-
A A
( × I
) = 7
Simplex Tableau – 3
C! 5 3 0 0 M M Ratio
C# X# b" X$ X% S% S$ D$ D% (b" /X" )

3 X$ - $ - +$ 20
0 1 0
% ) $( )

M D$ 3 $ +& +$ 12 Key
0 0 1
' ) '

1 +$ +$ $
5 X$ 1 0 0 -
' ) '
Z! %- . 0 +&. - +. 0
3M + 5 3 - + M +
% ' ) ) $( ' )
Z! − C! . 0 +&. - +-. 0
0 0 '
- ) )
+ $(
0 '
+)

Key column
7 7 7 ! 7 ;# 7 ;#
Main row: 3 × = 12; 0 × = 0, 0 × = 0; × = 1; × = ;
! ! ! 7 ! I ! "
7 ;! 7
1 × = 4; × = -1
! 7 !
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main row) = New R!
A !
- ( × 12) = 1
" I
!
0 - (I × 0) = 0
!
1 - (I × 0) = 1
! !
- ( × 1) = 0
I I
A ! ;# !
-( × )=
!8 I " "
! ;!
0 - (I × 4) = "
;! !
I
- (I × -1) = 0
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Main row) = New R #
;!
1 − ( 7 × 12) = 1
;!
1 −( 7 × 0) = 1
;!
0 −( 7 × 0) = 0
;! ;!
7
− ( 7
× 1) = 0
;! ;! ;# ;!
I
−( 7
× "
) = "
;!
0 − ( × 4) = 1
7
! ;!
− ( × -1) = 0
7 7
Simplex tableau – 4
C! 5 3 0 0 M M Ratio (b" /X" )
C# X# b" 𝑋$ 𝑋% 𝑆% 𝑆$ 𝐷$ 𝐷%
3 𝑋% 1 $ +$ -
0 1 0 % %
0

0 𝑆% 12 +& -
0 0 1 4 -1
%
5 𝑋$ 4
+$
1 0 0 1 0 -
%
Z! 23 0
5 3 0 -1 0
%
Z! − C! 0
0 0 0 -1 %
- M -M

Since, all (Z= − C= ) ≤0, an optimum feasible solution has been

obtained.
Thus, the optimum solution is 𝑋! = 4, 𝑋" = 1, 𝑆! = 12 and Min Z = 23.
Example 4
Solve the following LP problem by simplex method
Maximize Z = 6X! + 5X "
Subject to the constraints
3X! + 4X " ≤ 120
2X! + X " ≤ 40
X! ≥ 10
X! + X " = 30
and X!, X " ≥ 0
Solution:
After introducing the slack, surplus and artificial variables
(dummy variables) to the constraints, the LP problem becomes
Maximize Z = 6X! + 5X " + 0S# + 0S! + 0S" - MD! - MD"
Subject to the constraints
3X! + 4X " + S! = 120
2X! + X " + S" = 40
X! - S# + D! = 10
X! + X " + D" = 30
and X!, X ", S!, S", S#, D!, D" ≥ 0
The above 4 constraints can be written in matrix form AX = b as:

𝑋!
𝑋"
3 4 0 1 0 0 0 𝑆# 120
2 1 0 0 1 0 0 𝑆! = 40
1 0 −1 0 0 1 0 10
1 1 0 0 0 0 1 𝑆"
30
𝐷!
𝐷"
 Here, an identity matrix is formed by the coefficients of variables
S!, S", D! and D". So, S!, S", D!and D" are basic variables for
initial simplex tableau.
Initial simplex tableau
C! 6 5 0 0 0 -M -M Ratio (b" /X" )
C# X# b" 𝑋$ 𝑋% 𝑆& 𝑆$ 𝑆% 𝐷$ 𝐷%
0 𝑆$ 120 3 4 0 1 0 0 0 $%,
&
= 40
',
0 𝑆% 40 2 1 0 0 1 0 0 %
= 20

$,
-M 𝐷$ 10 1 0 -1 0 0 1 0 = 10 Key
$

-M 𝐷% 30 1 1 0 0 0 0 1 &,
= 30
$
Z! -40M -2M -M M 0 0 -M -M
Z! − C! -2M-6 -M-5 M 0 0 0 0

Key column
 ./0 1"
Main row (Rep.𝑅#) =
234 3/353$6
= 10, 1, 0, -1, 0, 0, 1, 0
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main row) = New R!
120 – (3 × 10) = 90
3 – (3 × 1) = 0
4 – (3 × 0) = 4
0 – (3 × -1) = 3
1 – (3 × 0) = 1
0 – (3 × 0) = 0
0 – (3 × 1) = -3
0 – (3 × 0) = 0
For new 𝐑 𝟐 :
Old R " - (Intersectional element of old R "× Main row) = New R "
40 – (2 × 10) = 20
2 – (2 × 1) = 0
1 – (2 × 0) = 1
0 – (2 × -1) = 2
0 – (2 × 0) = 0
1 – (2 × 0) = 1
0 – (2 × 1) = -2
0 – (2 × 0) = 0
For new 𝐑 𝟒 :
Old R 7 - (Intersectional element of old R 7× Main row) = New R 7
30 – (1 × 10) = 20
1 – (1 × 1) = 0
1 – (1 × 0) = 1
0 – (1 × 0) = 0
0 – (1 × 0) = 0
0 – (1 × -1) = 1
0 – (1 × 1) = -1
1 – (1 × 0) = 1
Simplex Tableau - 2
C! 6 5 0 0 0 -M -M Ratio (b" /X" )
C# X# b" 𝑋$ 𝑋% 𝑆& 𝑆$ 𝑆% 𝐷$ 𝐷%
0 𝑆$ 90 0 4 3 1 0 -3 0 *,
&
= 30
%,
0 𝑆% 20 0 1 2 0 1 -2 0 = 10
% K

-M 𝐷$ 10 1 0 -1 0 0 1 0 -10

%,
-M 𝐷% 20 0 1 1 0 0 -1 1 = 20
$
Z! -30M -M -M -2M-6 0 0 -M+6 -M
Z! − C! 0 -M-5 -2M-6 0 0 6 0

Key column
 "9 9 ! " 9 ! ;" 9
Main row: = 10, = 0, , = 1, = 0, , = -1, = 0
" " " " " " " "
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main row) = New R!
90 – (3 × 10) = 60
0 – (3 × 0) = 0
! A
4– (3 × ") = "
3 – (3 × 1) = 0
1 – (3 × 0) = 1
! ;#
0 – (3 × ") = "
-3 – (3 × -1) = 0
0 – (3 × 0) = 0
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Main row) = New R #
10 – (-1 × 10) = 20
1 – (-1 × 0) = 1
! !
0 – (-1 × ") = "
-1 – (-1 × 1) = 0
0 – (-1 × 0) = 0
! !
0– (-1 × ") = "
1 – (-1 × -1) = 0
0 – (-1 × 0) = 0
For new 𝐑 𝟒 :
Old R 7 - (Intersectional element of old R 7× Main row) = New R 7
20 – (1 × 10) = 10
0 – (1 × 0) = 0
! !
1 – (1 × ") = "
1 – (1 × 1) = 0
0 – (1 × 0) = 0
! ;!
0– (1 × ") = "
-1 – (1 × -1) = 0
1 – (1 × 0) = 1
Simplex tableau – 3
C! 6 5 0 0 0 -M -M Ratio (b" /X" )
C# X# b" X$ X% S& S$ S% D$ D%
0 S$ 60 - +& 24
0 %
0 1 %
0 0
$ $
0 S& 10 0 %
1 0 %
-1 0 20
$ $
6 X$ 20 1 0 0 0 0 40
% %
$ +$
0 0 0 0 1 K
-M D% 10 % % 20
Z! -10M +/ +/
6 %
+3 0 0 %
+3 0 -M
+120
Z! − C! +/ +/
0 %
-2 0 0 %
+3 M 0

Key column
 !
Main row: 10 × 2 = 20, 0 × 2 = 0, "
× 2 = 1, 0 × 2 = 0, 0 × 2 = 0,
;!
× 2 = -1, 0 × 2 = 0, 1 × 2 = 2
"
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main row) = New R!
A
60 – ( × 20) = 10
"
A
0 – ( × 0) = 0
"
A A
"
– ("
× 1) = 0
A
0 – (" × 0) = 0
A
1 – (" × 0) = 1
;# A
– ( × -1) = 1
" "
A
0 – (" × 0) = 0
A
0 – ( × 2) = -5
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main row) = New R!
!
10 – (" × 20) = 0
!
0 – (" × 0) = 0
! !
"
– ("
× 1) = 0
!
1 – (" × 0) = 1
!
0 – (" × 0) = 0
! !
– ( × -1) = 1
" "
!
0 – ( × 0) = -1
"
!
0 – (" × 2) = -1
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Main row) = New R #
!
20 – (" × 20) = 10
!
1 – (" × 0) = 1
! !
"
– ("
× 1) = 0
!
0 – (" × 0) = 0
!
0 – (" × 0) = 0
! !
– ( × -1) = 1
" "
A
0 – (" × 0) = 0
A
0 – (" × 2) = -1
Simplex tableau – 4

C! 6 5 0 0 0 -M -M Ratio (b" /X" )

C# X# b" X$ X% S& S$ S% D$ D%
0 S$ 10 0 0 0 1 1 0 -5 -
0 S& 0 0 0 1 0 1 -1 -1 -
6 X$ 10 1 0 0 0 1 0 -1 -
5 X% 20 0 1 0 0 -1 0 2 -
Z! 160 6 5 0 0 1 0 4
Z! − C! 0 0 0 0 1 M 4+M

Since, all (Z= - C= ) ≥ 0, an optimum feasible solution has been

obtained. Thus, the optimum feasible solution is
X! = 10, X " = 20 and max Z = 160
Example 5
Solve the following LP problem by simplex method
Maximize Z = 5X! + 8X "
Subject to constraints
4X! + 6X " ≤ 24
2X! + X " ≤ 18
3X! + 9X " ≤ 36
and X! , X " ≥ 0
Solution:
After adding the slack variables S! , S" and S# to the
constraints, the given LP problem becomes
Maximize Z = 5X!+ 8X "+ 0S! + 0S" + 0S#
Subject to constraints
4X!+ 6X "+ S! = 24
2X!+ X "+ S" = 18
3X!+ 9X "+ S# = 36
and X!, X ", S!, S", S# ≥ 0
The above three constraints can be written in matrix form AX = b
as
X!
4 6 1 0 0 X" 24
2 1 0 1 0 S! = 18
3 9 0 0 1 S" 36
S#
Here, an identity matrix forms by the coefficients of slack
variables S!, S", S#. So these variables are slack variables. The
initial simplex tableau can be constructed as follows:
Initial simplex Tableau

C! 5 8 0 0 0 Ratio (b" /X" )

C# X# b" X$ X% S$ S% S&
0 X$ 24 4 6 1 0 0 %'
=4 Key row
(
$)
0 S% 18 2 1 0 1 0 $
= 18
&(
=4
*
0 S& 36 3 9 0 0 1
Z! 0 0 0 0 0 0
Z! − C! -5 -8 0 0 0

Key column
Here, X * →entering variable.
Since there are two same minimum positive ration in the ratio column,
degeneracy occurs. To avoid degeneracy, select first row R' as key row
by choosing the ratio to the top and the corresponding variable S' is a
leaving variable. Also, 6 is a key element.
*- - * ) ' . .
Main row: = 4; = ; = 1; ; = 0; = 0
) ) & ) ) ) )
For new 𝐑 𝟐 :
Old R * - (Intersectional element of old R * × Main row) = New R *
18 – (1 × 4) = 14
* -
2 – (1× ) =
& &
1 – (1× 1) = 0
' ('
0 – (1× ) =
) )
1 – (1× 0) = 1
0 – (1× 0) = 0
For new 𝐑 𝟑 :
Old R # - (Intersectional element of old R #× Main row) = New R #
36 – (9 × 4) = 0
"
3 – (9× ) = -3
#
9 – (9× 1) = 0
! ;#
0– (9× ) =
8 "
0 – (9× 0) = 0
1 – (9× 0) = 1
Simplex Tableau – 2
C! 5 8 0 0 0 Ratio
C# X# b" X$ X% S$ S% S& (b" /X" )

8 X$ 4 % $ -
&
1 (
0 0
0 S% 14 ' +$ -
0 S& 0 &
0 (
1 0 -
+&
-3 0 0 1
%
$( '
Z! 32 8 0 1
& &
Z! − C! $
0 0 0 1
&

Since, all (Z= - C= ) ≥ 0, an optimum feasible solution has been

obtained. Thus, the optimum feasible solution is X! = 4, X " = 0
and max Z = 32. Notice that 𝑆# has the value 0 in the constant
column, even through it is one of the variables in the solution.
Whenever a variable in the solution has the value 0, that variable
and the solution are said to be degenerate.
Example 6
Solve the following LP problem by simplex method
Maximize Z = 3X!+ 9X "
Subject to constraints
X!+ 4X " ≤ 8
X!+ 2X " ≤ 4
and X!, X " ≥ 0
Solution:
After introducing (adding) the slack variables S!and S" to the given
constraints, the LP problem becomes
Maximize Z = 3X!+ 9X "+ 0S! + 0S"
Subject to constraints
X!+ 4X "+ S! = 8
X!+ 2X "+ S" = 4
and X!, X ", S!, S" ≥ 0
The above constraints can be written in matrix form AX = b as

X!
1 4 1 0 X" 8
=
1 2 0 1 S! 4
S"
Here, an identity matrix is formed by the coefficients of variables
S! and S". So, S! and S" are basic variables for initial simplex
tableau.
Initial Simplex Tableau – 1
C! 3 9 0 0 Ratio (b" /X" )
C# X# b" X$ X% S$ S%
0 S$ 8 1 4 1 0 )
=2 Key row
'

0 S% 4 1 2 0 1 '
=2
%

Z! 0 0 0 0 0
Z! − C! -3 -9 0 0
Key column
Here, X " → entering variable
S! → leaving variable.
./0 1!
Main row (Rep R!) =
234 3/353$6
I ! 7 ! 9
7
= 2; 7; 7 = 1; 7; 7 = 0
For new 𝐑 𝟐 :
Old R " - (Intersectional element of old R "× Main row) = New R "
4 – (2 × 2) = 0
! !
1– (2× 7) = "
2 – (2× 1) = 0
! ;!
0– (2× 7) = "
1 – (2× 0) = 1
 Simplex tableau – 2

C! 3 9 0 0 Ratio (b" /X" )

C# X# b" X$ X% S$ S%
9 X$ 2 $ $ %
'
1 '
0 $/'
=8

0 S% 0 $ +$ ,
0 1 =0 Key row
% % $/%

Z! 18 * *
9 0
' '
+& *
Z! − C! 0 0
' '

Key column
" ! " " ;! " "
Main row (Rep 𝑅"): 0× ! = 0; " × ! = 1; 0× ! = 0; " × ! = -1; 1 × ! = 2
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main row) = New R!
!
2 – (7 × 0) = 2
! !
7
– (7 × 1) = 0
!
1 – (7 × 0) = 1
! ! !
7
– (7
× -1) = "
! ;!
0 – (7 × 2) = "
Simplex tableau – 3

C! 3 9 0 0 Ratio (b" /X" )

C# X# b" X$ X% S$ S%
9 X% 2 $ +$ -
0 1 % %
3 X$ 0 -
1 0 -1 2
Z! 18 & &
3 9
% %
Z! − C! & &
0 0 % %

Since all Z= - C= ≥ 0, an optimum feasible solution has been obtained.

Thus, the optimal solution is X! = 0, X " = 2 and max Z = 18
Alternative method:
In simplex tableau 1, the minimum ratio is same, i.e. 2, so there
is a tie between two rows S! and S" for selecting key row. This is
an indication for the existence of degeneracy. To obtain the
unique key row, the following methods are used to avoid the
degeneracy.
(i) Write down the coefficients of slack variables as follows:
𝑆$ 𝑆%
𝑆$ 1 0
𝑆% 0 1
(ii) Divide the coefficients by the corresponding element of the
key column as follows:
S! S"
S! ! ! $
= =0
# # #
S" $ ! !
=0 =
" " "

(iii) Comparing the ratios of step (ii) from left to right column-
wise, the minimum ratio occurs for second row. So, second row
is key row and corresponding variable S! is a leaving variable.
Thus,
Simplex tableau – 1
C! 3 9 0 0 Ratio (b" /X" )
C# X# b" X$ X% S$ S%
0 S$ 8 1 4 1 0 )
'
=2

0 S% 4 1 2 0 1 '
=2 Key row
%

Z! 0 0 0 0 0
Z! − C! -3 -9 0 0

Key column
Here, 𝑋" → entering variable
and 𝑆" → leaving variable.
7 ! " 9 !
Main row: = 2; ; = 1; = 0;
" " " " "
For new 𝐑 𝟏 :
Old R! - (Intersectional element of old R!× Main row) = New R!
8 – (4 × 2) = 0
! !
1 – (4 × ) =
" "
4 – (4 × 1) = 0
1 – (4 × 0) = 1
!
0– (4 × ") = -2
Simplex Tableau – 2

C! 3 9 0 0 Ratio (b" /X" )

C# X# b" X$ X% S$ S%
0 S$ 0 $ -
%
0 1 -2
9 X% 2 $ $ -
%
1 0 %
Z! 18 * *
%
9 0 %
Z! − C! & *
0 0
% %

Since all Z= - C= ≥ 0, an optimum feasible solution has been

obtained. Thus, the optimal solution is X! = 0, X " = 2 and max Z =
18.