Page 83 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes
Example:
Maximise ‘Z’ = 3x + 2y

Sub. to x – y  15
2x – y  40
x, y  0
Where, S and S are slack variables.
1 2
First Iteration
BV CB XB X y S1 S2 Min. Ratio
S1 0 15 1 –1 1 0 15/1 = 15 (KR) ?
S2 0 20 2 –1 0 1 20/2 = 10
Zj 0 0
Cj 3 2
Zj – Cj –3 –2

Second Iteration
BV CB XB X Y S1 S2 Min. Ratio
S1 0 15–10 (1) = 5 1–1 (0) = 0 –1+1/2 (1) –0.5 – – y' s are negative
X 3 10 1 –1/2 – –
Zj 3 –1.5
Cj 3 2
Zj – Cj 0 –3.5

At the end of second iteration y should enter the basis to improve the solution of Z. But there is
no vector leaving the basis since y’s are negative. Hence, the solution is unbounded optimum
solution.
Note that the unbounded feasible region by graph is ABCDE. As the point A and E are extended,
the value of Z increases. Hence, the solution is unbounded optimal solution.
Figure 3.5: Graphical Representation of Unbounded Optimal Solution

78 LOVELY PROFESSIONAL UNIVERSITY