Page 53 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes 3.1 Simplex Method of Linear Programming

Under 'Graphical solutions' to LP, the objective function obviously should have not more than
two decision variables. If the decision variables are more than two, the 'Cartesian Plane' cannot
accommodate them. And hence, a most popular and widely used analysis called 'SIMPLEX
METHOD', is used. This method of analysis was developed by one American Mathematician by
name George B. Dantzig, during 1947.
This method provides an algorithm (a procedure which is iterative) which is based on fundamental
theorems of Linear Programming. It helps in moving from one basic feasible solution to another
in a prescribed manner such that the value of the objective function is improved. This procedure
of jumping from one vertex to another vertex is repeated.
Steps:
1. Convert the inequalities into equalities by adding slack variables, surplus variables or
artificial variables, as the case may be.
2. Identify the coefficient of equalities and put them into a matrix form AX = B
Where "A" represents a matrix of coefficient, "X" represents a vector of unknown quantities
and B represents a vector of constants, leads to AX = B [This is according to system of
equations].

3. Tabulate the data into the first iteration of Simplex Method.
Table 3.1: Specimen

Basic (BV) C B X B Y 1 Y 2 S1 S2 Minimum Ratio
Variable X Bi/Yij; Y ij > 0
S1
S2
Z j
C j
Z j - C j

(a) Cj is the coefficient of unknown quantities in the objective function.
Zj = C (Multiples and additions of coefficients in the table, i.e., C × Y + C ×
BiYij B1 11 B2
Y )
12
(b) Identify the Key or Pivotal column with the minimum element of Zj - Cj denoted as
'KC' throughout to the problems in the chapter.
(c) Find the 'Minimum Ratio' i.e., X /Y .
Bi ij
(d) Identify the key row with the minimum element in a minimum ratio column. Key
row is denoted as 'KP'.
(e) Identify the key element at the intersecting point of key column and key row, which
is put into a box throughout to the problems in the chapter.
4. Reinstate the entries to the next iteration of the simplex method.
(a) The pivotal or key row is to be adjusted by making the key element as '1' and
dividing the other elements in the row by the same number.
(b) The key column must be adjusted such that the other elements other than key
elements should be made zero.

48 LOVELY PROFESSIONAL UNIVERSITY