Operations Research Class 3

OPERATIONS RESEARCH CLASS 3 1. LP Standard Form Example 1.1. Rewrite in the standard form: Optimize(Maximize or Minimize) z = 2x1 + x2 + 4x3 subject to (1) 􀀀2x1 + 4x2 4 (2) x1 + 2x2 + x3 5 (3) 2x1 + 3x3 2 and x1; x2; x3 0 Solution The constraints of the problem become (1) 􀀀2x1 + 4x2 + s1 = 4 (2) x1 + 2x2 + x3 􀀀 s2 = 5 (3) 2x1 + 3x3 + s3 = 2 The new variables s1; s2; s3 are called slack variables. Now the decision variables are x1; x2; x3; s1; s2; s3 all of which are non-negative, and the constraints become (1) 􀀀2x1 + 4x2 + 0x3 + s1 + 0s2 + 0s3 = 4 (2) x1 + 2x2 + x3 + 0s1 􀀀 s2 + 0s3 = 5 (3) 2x1 + 0x2 + 3x3 + 0s1 + 0s2 + s3 = 2 Under these conditions we have to optimize z = 2x1 + x2 + 4x3 + 0s1 + 0s2 + 0s3 This can be written in the matrix form as: Optimize Z = CX + OS subject to the constraints AX + S = b and X; S 0; where C = (2; 1; 4);X = (x1; x2; x3)T ;O = (0; 0; 0) 12 OR 3 , b = (4; 5; 2)T ; S = (s1; s2; s3)T and A = 0@ 􀀀2 4 0 1 2 1 2 0 3 1A Example 1.2. Rewrite in the standard form: Optimize z = x1 􀀀 3x2 subject to (1) 􀀀x1 + 2x2 15 (2) x1 + 3x2 = 10 and x1; x2 0 Solution The constraints are (1) 􀀀x1 + 2x2 + s1 = 15 (2) x1 + 3x2 + 0s1 = 10 where s1 is a slack variable. Under these conditions we have to optimize z = x1 􀀀 3x2 + 0s1 Let C = (1;􀀀3);X = (x1; x2)T ; 0 = (0); S = (s1); b = (15; 10) and A = 􀀀1 2 1 3 Then the LP becomes Optimize Z = CX + OS subject to the constraints AX + S = b and X; S 0;OR 3 3 2. Basic Feasible Solution, BFS Example 2.1. Obtain all the basic feasible solutions of the following system of linear equations: (1) x1 + 2x2 + x3 = 4 (2) 2x1 + x2 + 5x3 = 5 This is of the form AX = b where A = 1 2 1 2 1 5 ;X = 0@ x1 x2 x3 1A; b = 45 Since det1 2 2 1 6= 0 rank of A is 2. Denition 2.2. If AX = b is a system of linear equations, and rankA = m, then any non-singular m m submatrix of A is called a basis matrix. The basis matrices of A are A1 = 1 2 2 1 ;A2 = 1 1 2 5 ;A3 = 1 1 1 5 ; A1 is not associated with x3,A2 is not associated with x2, and A3 is not associated with x1 Now solve (1) A1 x1 x2 = 45 (2) A2 x1 x3 = 45 (3) A3 x2 x3 = 45 On solving them we get the basic solutions as (1) x1 = 2; x2 = 1; x3 = 0 (2) x1 = 5; x2 = 0; x3 = 􀀀1 (3) x1 = 0; x2 = 5=3; x3 = 2=3 In (1) x1; x2 are the basic variables and x3 is a non-basic variable.4 OR 3 Similarly for the other solutions. Note A basic solution is (1) degenerate if any value of a basic variable is zero,and (2) non-feasible if any value of a basic variable is negative. In the given example, the basic feasible solutions are [0; 5=3; 2=3]; [2; 1; 0] Example 2.3. Obtain all the basic feasible solutions of the following system of linear equations: (1) 2x1 + 6x2 + 2x3 + x4 = 3 (2) 6x1 + 4x2 + 4x3 + 6x4 = 2 This is of the form AX = b where A = 2 6 2 1 6 4 4 6 ;X = 0BB@ x1 x2 x3 x4 1CCA; b = 32 The rank of A is 2. The basis matrices of A are A1 = 2 6 6 4 ;A2 = 2 2 6 4 ;A3 = 2 1 6 6 ;A4 = 6 2 4 4 ;A5 = 6 1 4 6 and A6 = 2 1 4 6 A1 is not associated with x3; x4, A2 is not associated with x2; x4,etc. Now solve A1 x1 x2 = 32 and so on. On solving them we get the basic solutions as (1) basic; x1 = 0; x2 = 1=2; nonbasic; x3 = x4 = 0 (2) basic; x1 = 􀀀2; x3 = 7=2; nonbasic; x2 = x4 = 0 (3) basic; x1 = 8=3; x4 = 􀀀7=3; nonbasic; x2 = x3 = 0 (4)OR 3 5 (5) basic; x2 = 1=2; x3 = 0; nonbasic; x1 = x4 = 0 (6) (7) basic; x3 = 1=2; x4 = 0; nonbasic; x1 = x3 = 0 (8) basic; x3 = 2; x4 = 􀀀1; nonbasic; x1 = x2 = 0 There is no feasible, non-degenerate basic solution.