Operations Research
Que. 3 Determine the optimum solutions for the following L.P.s by enumerating all the basic solutions : -
Maximize Z = 2x1 - 4x2 + 5x3 - 6x4
s.t. x1 + 4x2 - 2x3 + 8x4 £ 2
-x1 + 2x2 + 3x3 + 4x4 £ 1
x1, x2, x3, x4 ³ 0
Ans.
Now by using slack variables s1 and s2 the above L.P model can be expressed as :-
Maximize Z = 2x1 - 4x2 + 5x3 - 6x4
s.t. x1 + 4x2 - 2x3 + 8x4 + s1 = 2
- x1 + 2x2 + 3x3 + 4x4 + s2 = 1
x1, x2, x3, x4, s1, s2 ³ 0
now here the number of basic solution = nCm
where n = number of variables = 6
m = number of constraints = 2
\ number of basic solutions = nCm
= 6C2
6!
= (6-2)! * 2!
6*5*4*3*2*1
= (4*3*2*1) * (2*1)
= 15
Now, two variables may be selected as a basic variable, thus the set of basic variables can be expressed as :-
Number of basic variables = {(x1,x2), (x1,x3), (x1,x4), (x1, s1) (x1, s2) (x2, x3) (x2, x4) (x2,s1) (x2,s2) (x3, x4) (x3,s1) (x3,s2) (x4, s1) (x4,s2) (s1, s2)}
Now if we take x1 and x2 as basic variables :
We get the basic solutions as :
Basic variables are x1 and x2.
Non basic variables are x3 = 0, x4 = 0, s1 = 0, and s2=0.
By placing these all values in our L.Ps model we get
x1 + 4x2 - 2x3 + 8x4 + s1 = 2
\ x1 + 4x2 - 2(0) + 8(0) + 0 = 2
\ = x1 + 4x2 = 2 ------------------------------------------------------(I)
and - x1 + 2x2 + 3x3 + 4x4 + s2 = 1
\ - x1 + 2x2 + 3(0) + 4(0) + 0 =1
\ = -x1 + 2x2 = 1 ----------------------------------------------------(II)
Now by adding equation no (I) in equation (II) we get
X2 = ½ ---------------------------------------------------------(1)
By placing the value of x2 in equation(I) we get
x1 + 4x2 = 2
x1 + 4 (1/2) = 2
\ x1 = 0.------------------------------------------------------(2)
Therefore basic solutions:
X1=0, x2 = ½ and Z = -2
In this way we can obtain other remaining basic solutions which are mentioned in the table bellow. |
