Operations Research

Que. 3        Determine the optimum solutions for the following L.P.s by enumerating all the basic solutions : -

Maximize  Z = 2x₁ - 4x₂ + 5x₃ - 6x₄ 
          s.t.     x₁ + 4x₂ - 2x₃ + 8x₄ £ 2 
                   -x₁ + 2x₂ + 3x₃ + 4x₄ £ 1
                   x₁, x₂, x₃, x₄ ³ 0

Ans.

Now by using slack variables s1 and s2 the above L.P model can be expressed as :- 

Maximize Z = 2x₁ - 4x₂ + 5x₃ - 6x₄ 
          s.t.     x₁ + 4x₂ - 2x₃ + 8x₄ + s₁ = 2
                   - x₁ + 2x₂ + 3x₃ + 4x₄ + s₂ = 1
                   x₁, x₂, x₃, x₄, s₁, s₂ ³ 0

now here the number of basic solution = ⁿC_m

where n = number of variables = 6
         m = number of constraints = 2
\ number of basic solutions = ⁿC_m 
                                      = ⁶C₂
                                                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 = {(x₁,x₂), (x₁,x₃), (x₁,x₄), (x₁, s₁) (x₁, s₂) (x₂, x₃) (x₂, x₄) (x₂,s₁) (x₂,s₂) (x₃, x₄) (x₃,s₁) (x₃,s₂) (x₄, s₁) (x₄,s₂) (s₁, s₂)}
Now if we take x₁ and x₂ as basic variables :

We get the basic solutions as : 

Basic variables are x₁ and x₂.

Non basic variables are x₃ = 0, x₄ = 0, s₁ = 0, and s₂=0.

 By placing these all values in our L.Ps model we get

   x₁ + 4x₂ - 2x₃ + 8x₄ + s₁ = 2
\ x₁ + 4x₂ - 2(0) + 8(0) + 0 = 2
\  = x₁ + 4x₂ = 2 ------------------------------------------------------(I)

and -          x₁ + 2x₂ + 3x₃ + 4x₄ + s₂ = 1
\ - x₁ + 2x₂ + 3(0) + 4(0) + 0 =1
\ = -x₁ + 2x₂ = 1 ----------------------------------------------------(II)

Now by adding equation no (I) in equation (II) we get

X₂ = ½ ---------------------------------------------------------(1)

By placing the value of x2 in equation(I) we get

x₁ + 4x₂ = 2
x₁ + 4 (1/2) = 2
\ x₁ = 0.------------------------------------------------------(2)

Therefore basic solutions:
X₁=0, x₂ = ½ and Z = -2 

In this way we can obtain other remaining basic solutions which are mentioned in the table bellow.

SR. No.	Basic Variables   1st Variable      2nd Variable		Basic Solutions   1st solution       2nd solutions		Value of object function(Z)
1.	x1	x2	0	½	-2
2.	x1	x3	8	3	31
3.	x1	x4	0	1/4	-(3/2)
4.	x1	s1	-1	3	-2
5.	x1	s2	2	3	4
6.	x2	x3	½	0	-2
7.	x2	x4	0	1/4	-(3/2)
8.	x2	s1	½	0	-2
9.	x2	s2	½	0	-2
10.	x3	x4	0	1/4	-(3/2)
11.	x3	s1	1/3	8/3	5/3
12.	x3	s2	-1	4	-5
13.	x4	s1	1/4	0	-(3/2)
14.	x4	s2	1/4	0	-(3/2)
15.	s1	s2	2	1	0

From the above table we can see that the basic solutions and the basic variables in which we get from the serial no 4 and 12 are negative because the value of the variables are negative. 

We can also see from serial no 2 that when the value of x₁ = 8, and the value of x₃ = 3 we get the maximum value of the objective function (i.e. Z = 31). 
Hence the solution for the above mentioned L.P models is as follows :

x₁ = 8, 
x₃ = 3 and 
Z = 31 (Maximum value)