Computer Oriented
Optimization Methods
(COOM)
(PAPER CODE)
MT-CS-25-13
SIMPLEX METHOD
➢ For the solution of any LPP by simplex algorithm, the existence of initial basic feasible solution is
always assumed. The steps for the computation of an optimum solution are as follows:
➢Step 1: Check whether the objective function of the given LPP is to be maximized or minimized. If it is
to be minimized, then we convert it into a problem of maximizing by using the result:
Min Z= -Max(-Z)
➢ Step 2: Check whether all bi (i=1,2,…,m) are non-negative. If any one of bi is negative, then multiply
the corresponding inequation of constraints by -1 so as to get all bi (i=1,2,..m) non-negative.
➢Step 3: Convert all the inequations of the constraints into equations by introducing the slack and/or
surplus variables in the constraints. Put the costs of these variables equal to zero.
➢Step 4: Obtain Initial Basic Feasible solution to the problem in the form xB= B-1b and put it in the first
column of the simplex table.
SIMPLEX METHOD
➢ Step 5: Compute the net evaluations Zj – Cj (j=1,2,…n) by using the relation Zj – Cj = CByj - Cj, where yj = B-1aj
Examine the sign Zj – Cj
i) If all (Zj – Cj ) >= 0, then the basic initial feasible solution xB is an optimum basic feasible solution.
ii) If at least one (Zj – Cj ) < 0, proceed on to the next step.
➢Step 6: If there are more than one negative Zj – Cj , then choose the most negative of them. Let it be Zr - Cr for some j=r
i) If all yir <= 0 (i=1,2,…m), then there is an unbound solution to the problem.
ii) If at least one yir > 0 (i=1,2,…m) then the corresponding vector y, enter the basis yB.
𝑥𝐵𝑖
➢Step 7: Compute the ratios
𝑦𝑖𝑟
, 𝑦𝑖𝑟 > 0, 𝑖 = 1,2, … , 𝑚 , and choose the minimum of them. Let the minimum of these ratios be
𝑥𝐵𝑘
. Then the vector yk will level the basis yB. The common element ykr, which is in the kth row and rth column, is
𝑦𝐵𝑘
known as the leading element (or pivotal element) of the table.
➢Step 8: Convert the leading element to unity by dividing its row by the leading element itself. And all other elements in its
column to zeros by making use of the relations:
𝑦𝑘𝑗
𝑦ෞ
𝑖𝑗 = 𝑦𝑖𝑗 − 𝑦 , 𝑖 = 1,2, … . 𝑚 + 1; 𝑖 ≠ 𝑘
𝑦𝑘𝑟 𝑖𝑟
𝑦𝑘𝑗
𝑦ෞ
𝑘𝑗 = , 𝑗 = 0,1,2, … 𝑛
𝑦𝑘𝑟
SIMPLEX METHOD
➢ Step 9: Go to step 5 and repeat the computational procedure until either an optimum solution is obtained or there
is an indication of an unbounded solution.
SIMPLEX METHOD
𝑴𝒂𝒙 𝒛 = 𝟑𝒙𝟏 + 𝟐𝒙𝟐
𝑺𝑪 , 𝒙𝟏 + 𝒙𝟐 ≤ 𝟒
𝒙𝟏 − 𝒙𝟐 ≤ 𝟐
➢ Introduce slack variable,
𝑴𝒂𝒙 𝒛 = 𝟑𝒙𝟏 + 𝟐𝒙𝟐 + 𝟎. 𝑺𝟏 + 𝟎. 𝑺𝟐
𝒙𝟏 + 𝒙𝟐 + 𝑺𝟏 = 𝟒
𝒙𝟏 − 𝒙𝟐 + 𝑺𝟐 = 𝟐
➢Initial Basic Feasible Solution
𝑆1 10 4
=
𝑆2 01 2
SIMPLEX METHOD
Cj 3 2 0 0
Basic Variables CB xB x1 x2 S1 S2 Min Ratio
S1 0 4 1 1 1 0 = (4/1) = 4
S2 0 2 1 -1 0 1 = (2/1) = 2
Zj = 0 0 0 0 0
Zj – Cj -3 -2 0 0
SIMPLEX METHOD
Cj 3 2 0 0
Basic Variables CB xB x1 x2 S1 S2 Min Ratio
S1 0 2 0 2 1 1 = (2/2) = 1
x1 3 2 1 -1 0 1 --
Zj = 6 3 -3 0 3
Zj – Cj 0 -5 0 3
SIMPLEX METHOD
Cj 3 2 0 0
Basic Variables CB xB x1 x2 S1 S2 Min Ratio
x2 2 1 0 1 1/2 1/2
x1 3 3 1 0 1/2 3/2
Zj = 11 3 2 5/2 1/2
Zj – Cj 0 0 5/2 11/2
All Zj – Cj’s
are positive.
Sol: x1 = 3, x2 = 1, Z= 11