Lessons in Linear Programming: Class 2

LESSONS IN LINEAR PROGRAMMING CLASS 2 1. LP Problem: Geometrical Interpretation Theorem 1.1. 1:3:1 in [1] If M Rn; then the following statements are equivalent: (1) 8; 2 R; + = 1; x; y 2 M ) x + y 2 M (2) 8m 2 N0; 0; :::; m 2 R; m X0 i = 1; x0; :::; xm 2 M ) m X0 ixi 2 M (3) If M 6= then M := fy zjy; z 2 Mg Rn is a vector subspace and 8x 2 M;M = x + M = fx + uju 2 Mg (4) If M 6= ; x 2 M then there exists a subspace U of Rn such that M = x + U (5) M is the solution set of a system of linear equations: That is,9m 2 N;A 2 Matm;n(R); b 2 Rm such that M = fx 2 RnjAx = bg 12 CLASS 2 Denition 1.2. A subspace M of Rn satisfying the above conditions is called an ane subspace. Denition 1.3. If M is a hyperplane in Rn, the dimension of M is dened as dimM := dim4M if M 6= ; 1 if M = : Hyperplane A hyperplane in Rn is an ane subspace of dimension n1: It is a subset of Rn of the form Ha;:= fx 2 Rnjax = g; a 2 Rn; a 6= 0; 2 R It is a linear subspace if = 0: Denition 1.4. The function Rn Rn ! R; (x; y) !t xy is called the Euclidean scalar product. The function k k : Rn ! R; x ! kxk := ptxx is called the Euclidean norm. (Rn; kk) is called a normed linear space. Denition 1.5. The vectors x; y 2 Rn are orthogonal if the scalar product (x; y) = 0: If U is a subspace of Rn the orthogonal complement of U is U? := fx 2 Rnj(x; y) = 0; 8y 2 Ug U? is a subspace of Rn: Example 1.6. Hyperplane in R2 M := 1 2 2 R2j1 + 2 = 1LINEAR PROGRAMMING 3 (1)x = 1 2 ; y = 1 2 2 M; ; 2 R; + = 1 x + y = 1 + 1 2 + 2 := u1 u2 u1 + u2 = 1 ) x + y 2 M (2) 4M = fy zjy; z 2 Mg y = 1 2 ; z = &1 &2 2 M; yz = 1 &1 2 &2 := u1 u2 u1 + u2 = 0 M = 1 2 j1 + 2 = 0x = 1 2 2 M; x + M = fx + uju 2 Mg x+u = 1 + u1 2 + u2 := v1 v2 ; 1+2 = 1; u1+u2 = 0 ) v1+v2 = 1 ) x + M = M (3) M := 1 2 2 R2j1 + 2 = 1A := (1; 1); x = 1 2 ; b = (1) M = fx 2 R2jAx = bg and 4M = fx 2 R2jAx = 0g See gure 1 Example 1.7. Hyperplane in R34 CLASS 2 Figure 1. Example 1.6 (1)x = 0@ 1 2 3 1A; y = 0@ 1 2 3 1A2 M; ; 2 R; + = 1 x + y = 1 ) x + y 2 M (2) 4M = fy zjy; z 2 Mg M = 8<: 0@ 1 2 3 1Aj1 + 2 + 3 = 09=;x + M = fx + uju 2 Mg x + M = MLINEAR PROGRAMMING 5 (3) M := 8<: 0@ 1 2 3 1A2 R2j1 + 2 + 3 = 19=;A := (1; 1; 1); x = 0@ 1 2 3 1A; b = (1) M = fx 2 R3jAx = bg and 4M = fx 2 R3jAx = 0g Denition 1.8. 1:3:2 in [1] a 2 Rn; a 6= 0; 2 R;Ha;= fx 2 Rnjax = g is a hyperplane in Rn a = (1; :::; n); x = 0@ 1 :::: n 1Aax = ) 11 + ::: + nn = a linear equation. The hyperplane Ha;is the solution set of this equation. If = 0;Ha;is a linear subspace of Rn: Theorem 1.9. a; a0 2 Rn; a 6= 0 6= a0; ; 0 2 R;Ha;= Ha0;0 Then 92 R such that a0 = a; 0 = In this case the hyper planes are parallel. Denition 1.10. Ha;;Ha0;0 are parallel if a; a0 are lin- early dependent.6 CLASS 2 Theorem 1.11. If a 2 Rn; a 6= 0; 2 R;H = Ha;and y = at ktak2 then y 2 H Proof ay = a katk2at = katk2aat = aataat = Hence the conclusion. Theorem 1.12. If a 2 Rn;t a? = Ha;0 Proof Let a = (1; :::; n);t a? = 8<:x = 0@ 1 :::: n 1A2 Rnjax = 09=;)t a? = Ha;0 Theorem 1.13. Ha;= Ha;0 + at ktak2 See gure 2 Denition 1.14. Half-Spaces If Ha;is a hyperplane, then H+a;= fx 2 Rnjax g and Ha;= fx 2 Rnjax g are called half-spaces of Rn. If > 0; the origin is in Ha;and if < 0; the origin is in H+a;H+a;[Ha;= RnLINEAR PROGRAMMING 7 Figure 2. Theorem 1.13 and H+a;\Ha;= Ha;Theorem 1.15. If > 0; H+a;= H+a;Ha;= Ha;If < 0; H+a;= Ha;Ha;= H+a;Theorem 1.16. 1:3:4 in [1] H0;= Rn if = 0; if 6= 0:8 CLASS 2 H+0;= Rn if 0; if > 0: H0;= Rn if 0; if < 0: 2. Half-Spaces and LP Problems A 2 Matm;n(R); b 2 Rm; c 2 Rn maxfcxjx 2 Rn; Ax bg P = fxjx 2 Rn; Ax bg Let A = 0@ a1 :::: am 1A; ai 2 Rn; b = 0@ 1 :::: m 1A; i 2 R P = m\i=1Hai;i fcxjx 2 Pg = f2 RjHc;\P 6= g maxfcxjx 2 Pg = maxf2 RjHc;\P 6= g Example 2.1. Prob : 1; p:60 in [1] Maximize the objective function z : R2 ! R;1 2 ! 41 + 32 subject to the constraints, (1) 31 + 2 30 (2) 1 8 (3) 2 12, (4) 1 0 (5) 2 0LINEAR PROGRAMMING 9 Graphical Illustration a1 = (3; 1); 1 = 30;Ha1;1 = fx 2 R2j31 + 2 = 30g a2 = (1; 0); 2 = 8;Ha2;2 = fx 2 R2j1 = 8g a3 = (0; 1); 3 = 12;Ha3;3 = fx 2 R2j2 = 12g a4 = (1; 0); 4 = 0;Ha4;4 = fx 2 R2j1 = 0g a5 = (0; 1); 5 = 0;Ha5;5 = fx 2 R2j2 = 0g To nd the feasible region, sketch the above lines(hyper planes) The feasible region is the region bounded by these lines. See gure ?? It is the interior of the polygon OABCD. c = (4; 3); 2 R; cx = Draw the hyper planes(lines) Hc;12 = fx 2 R2j41 + 32 = 12g Hc;24 = fx 2 R2j41 + 32 = 24g Hc;36 = fx 2 R2j41 + 32 = 36g Hc;48 = fx 2 R2j41 + 32 = 48g Hc;60 = fx 2 R2j41 + 32 = 60g cx is maximum at x0 = 6 12 and the maximum value is cx0 = 60 See gure 3 Example 2.2. 1:1:1 in [1] Consider the problem to nd maxfcxjx 2 R2; Ax bg where c = (3; 2) 2 R2; x = 1 2 2 R210 CLASS 2 Figure 3. Example 2.1 A = 0BBBBBB@ 1 1 3 1 1 0 0 1 1 0 0 1 1CCCCCCA 2 Mat6;2(R); b = 0BBBBBB@ 9 18 7600 1CCCCCCA 2 R4LINEAR PROGRAMMING 11 a1 = (1; 1) a2 = (3; 1) a3 = (1; 0) a4 = (0; 1) a5 = (1; 0) a6 = (0;1) 1 = 9 2 = 18 3 = 7 4 = 6 5 = 0 6 = 0 Ha1;1 = fx 2 R2j1 + 2 = 9g Ha2;2 = fx 2 R2j31 + 2 = 18g Ha3;3 = fx 2 R2j1 = 7g Ha4;4 = fx 2 R2j2 = 6g Ha5;5 = fx 2 R2j1 = 0g Ha6;6 = fx 2 R2j2 = 0g hc;= fx 2 R2jcx = ; = 3; 6; 9; 12; 15; 18; 21; 22:5g Let xmax be the vector in the feasible region P such cxmax is the maximum value of cx such that Ax b In this example, xmax is the point of intersection of the lines 1 + 2 = 9 (2.1) 31 + 2 = 18 (2.2) xmax = 9292 max = cxmax = 392 + 292 = 22:5 maxfcxjx 2 R2; Ax bg = 22:5 References [1] H. P. Petersson,Lineare Optimierung [2] J K Sharma, Operations Research Theory and Applications,4th Ed, Macmillan12 CLASS 2 Figure 4. Example 2.2