Page 1 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Linear Programming 2 Linear Programming Significance. ¦ Quintessential tool for optimal allocation of scarce resources, among a number of competing activities. ¦ Powerful model generalizes many classic problems: – shortest path, max flow, multicommodity flow, MST, matching, 2-person zero sum games ¦ Ranked among most important scientific advances of 20 th century. – accounts for a major proportion of all scientific computation ¦ Helps find "good" solutions to NP-hard optimization problems. – optimal solutions (branch-and-cut) – provably good solutions (randomized rounding) 3 Brewery Problem Small brewery produces ale and beer. ¦ Production limited by scarce resources: corn, hops, barley malt. ¦ Recipes for ale and beer require different proportions of resources. How can brewer maximize profits? ¦ Devote all resources to beer: 32 barrels of beer $736. ¦ Devote all resources to ale: 34 barrels of ale $442. ¦ 7½ barrels of ale, 29½ barrels of beer $776. ¦ 12 barrels of ale, 28 barrels of beer $800. Beverage Corn (pounds) Malt (pounds) Hops (ounces) Beer 15 20 4 Ale 5 35 4 Profit ($) 23 13 Quantity 480 1190 160 4 Brewery Problem 0 , 1190 20 35 160 4 4 480 15 5 t. s. 23 13 max ‡ £ + £ + £ + + B A B A B A B A B A Page 2 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Linear Programming 2 Linear Programming Significance. ¦ Quintessential tool for optimal allocation of scarce resources, among a number of competing activities. ¦ Powerful model generalizes many classic problems: – shortest path, max flow, multicommodity flow, MST, matching, 2-person zero sum games ¦ Ranked among most important scientific advances of 20 th century. – accounts for a major proportion of all scientific computation ¦ Helps find "good" solutions to NP-hard optimization problems. – optimal solutions (branch-and-cut) – provably good solutions (randomized rounding) 3 Brewery Problem Small brewery produces ale and beer. ¦ Production limited by scarce resources: corn, hops, barley malt. ¦ Recipes for ale and beer require different proportions of resources. How can brewer maximize profits? ¦ Devote all resources to beer: 32 barrels of beer $736. ¦ Devote all resources to ale: 34 barrels of ale $442. ¦ 7½ barrels of ale, 29½ barrels of beer $776. ¦ 12 barrels of ale, 28 barrels of beer $800. Beverage Corn (pounds) Malt (pounds) Hops (ounces) Beer 15 20 4 Ale 5 35 4 Profit ($) 23 13 Quantity 480 1190 160 4 Brewery Problem 0 , 1190 20 35 160 4 4 480 15 5 t. s. 23 13 max ‡ £ + £ + £ + + B A B A B A B A B A 5 Brewery Problem: Feasible Region Ale Beer (34, 0) (0, 32) Corn 5A + 15B £ 480 (12, 28) (26, 14) (0, 0) Hops 4A + 4B £ 160 Malt 35A + 20B £ 1190 6 Brewery Problem: Objective Function Ale Beer (34, 0) (0, 32) (12, 28) 13A + 23B = 800 13A + 23B = 1600 13A + 23B = 442 (26, 14) Profit (0, 0) 7 Ale Beer (34, 0) (0, 32) (12, 28) (26, 14) (0, 0) Extreme points Brewery Problem: Geometry Brewery problem observation. Regardless of coefficients of linear objective function, there exists an optimal solution that is an extreme point. 8 Linear Programming LP "standard" form. ¦ Input data: rational numbers c j , b i , a ij . ¦ Maximize linear objective function. ¦ Subject to linear inequalities. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 0 t. s. max (P) ‡ £ • x b Ax x c Page 3 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Linear Programming 2 Linear Programming Significance. ¦ Quintessential tool for optimal allocation of scarce resources, among a number of competing activities. ¦ Powerful model generalizes many classic problems: – shortest path, max flow, multicommodity flow, MST, matching, 2-person zero sum games ¦ Ranked among most important scientific advances of 20 th century. – accounts for a major proportion of all scientific computation ¦ Helps find "good" solutions to NP-hard optimization problems. – optimal solutions (branch-and-cut) – provably good solutions (randomized rounding) 3 Brewery Problem Small brewery produces ale and beer. ¦ Production limited by scarce resources: corn, hops, barley malt. ¦ Recipes for ale and beer require different proportions of resources. How can brewer maximize profits? ¦ Devote all resources to beer: 32 barrels of beer $736. ¦ Devote all resources to ale: 34 barrels of ale $442. ¦ 7½ barrels of ale, 29½ barrels of beer $776. ¦ 12 barrels of ale, 28 barrels of beer $800. Beverage Corn (pounds) Malt (pounds) Hops (ounces) Beer 15 20 4 Ale 5 35 4 Profit ($) 23 13 Quantity 480 1190 160 4 Brewery Problem 0 , 1190 20 35 160 4 4 480 15 5 t. s. 23 13 max ‡ £ + £ + £ + + B A B A B A B A B A 5 Brewery Problem: Feasible Region Ale Beer (34, 0) (0, 32) Corn 5A + 15B £ 480 (12, 28) (26, 14) (0, 0) Hops 4A + 4B £ 160 Malt 35A + 20B £ 1190 6 Brewery Problem: Objective Function Ale Beer (34, 0) (0, 32) (12, 28) 13A + 23B = 800 13A + 23B = 1600 13A + 23B = 442 (26, 14) Profit (0, 0) 7 Ale Beer (34, 0) (0, 32) (12, 28) (26, 14) (0, 0) Extreme points Brewery Problem: Geometry Brewery problem observation. Regardless of coefficients of linear objective function, there exists an optimal solution that is an extreme point. 8 Linear Programming LP "standard" form. ¦ Input data: rational numbers c j , b i , a ij . ¦ Maximize linear objective function. ¦ Subject to linear inequalities. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 0 t. s. max (P) ‡ £ • x b Ax x c 9 LP: Geometry Geometry. ¦ Forms an n-dimensional polyhedron. ¦ Convex: if y and z are feasible solutions, then so is ½y + ½z. ¦ Extreme point: feasible solution x that can't be written as ½y + ½z for any two distinct feasible solutions y and z. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 z y z y Convex Not convex Extreme points 10 LP: Geometry Extreme Point Theorem. If there exists an optimal solution to standard form LP (P), then there exists one that is an extreme point. ¦ Only need to consider finitely many possible solutions. Greed. Local optima are global optima. 11 LP: Algorithms Simplex. (Dantzig 1947) ¦ Developed shortly after WWII in response to logistical problems: used for 1948 Berlin airlift. ¦ Practical solution method that moves from one extreme point to a neighboring extreme point. ¦ Finite (exponential) complexity, but no polynomial implementation known. 12 LP: Polynomial Algorithms Ellipsoid. (Khachian 1979, 1980) ¦ Solvable in polynomial time: O(n 4 L) bit operations. – n = # variables – L = # bits in input ¦ Theoretical tour de force. ¦ Not remotely practical. Karmarkar’s algorithm. (Karmarkar 1984) ¦ O(n 3.5 L). ¦ Polynomial and reasonably efficient implementations possible. Interior point algorithms. ¦ O(n 3 L). ¦ Competitive with simplex! – will likely dominate on large problems soon ¦ Extends to even more general problems. Page 4 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Linear Programming 2 Linear Programming Significance. ¦ Quintessential tool for optimal allocation of scarce resources, among a number of competing activities. ¦ Powerful model generalizes many classic problems: – shortest path, max flow, multicommodity flow, MST, matching, 2-person zero sum games ¦ Ranked among most important scientific advances of 20 th century. – accounts for a major proportion of all scientific computation ¦ Helps find "good" solutions to NP-hard optimization problems. – optimal solutions (branch-and-cut) – provably good solutions (randomized rounding) 3 Brewery Problem Small brewery produces ale and beer. ¦ Production limited by scarce resources: corn, hops, barley malt. ¦ Recipes for ale and beer require different proportions of resources. How can brewer maximize profits? ¦ Devote all resources to beer: 32 barrels of beer $736. ¦ Devote all resources to ale: 34 barrels of ale $442. ¦ 7½ barrels of ale, 29½ barrels of beer $776. ¦ 12 barrels of ale, 28 barrels of beer $800. Beverage Corn (pounds) Malt (pounds) Hops (ounces) Beer 15 20 4 Ale 5 35 4 Profit ($) 23 13 Quantity 480 1190 160 4 Brewery Problem 0 , 1190 20 35 160 4 4 480 15 5 t. s. 23 13 max ‡ £ + £ + £ + + B A B A B A B A B A 5 Brewery Problem: Feasible Region Ale Beer (34, 0) (0, 32) Corn 5A + 15B £ 480 (12, 28) (26, 14) (0, 0) Hops 4A + 4B £ 160 Malt 35A + 20B £ 1190 6 Brewery Problem: Objective Function Ale Beer (34, 0) (0, 32) (12, 28) 13A + 23B = 800 13A + 23B = 1600 13A + 23B = 442 (26, 14) Profit (0, 0) 7 Ale Beer (34, 0) (0, 32) (12, 28) (26, 14) (0, 0) Extreme points Brewery Problem: Geometry Brewery problem observation. Regardless of coefficients of linear objective function, there exists an optimal solution that is an extreme point. 8 Linear Programming LP "standard" form. ¦ Input data: rational numbers c j , b i , a ij . ¦ Maximize linear objective function. ¦ Subject to linear inequalities. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 0 t. s. max (P) ‡ £ • x b Ax x c 9 LP: Geometry Geometry. ¦ Forms an n-dimensional polyhedron. ¦ Convex: if y and z are feasible solutions, then so is ½y + ½z. ¦ Extreme point: feasible solution x that can't be written as ½y + ½z for any two distinct feasible solutions y and z. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 z y z y Convex Not convex Extreme points 10 LP: Geometry Extreme Point Theorem. If there exists an optimal solution to standard form LP (P), then there exists one that is an extreme point. ¦ Only need to consider finitely many possible solutions. Greed. Local optima are global optima. 11 LP: Algorithms Simplex. (Dantzig 1947) ¦ Developed shortly after WWII in response to logistical problems: used for 1948 Berlin airlift. ¦ Practical solution method that moves from one extreme point to a neighboring extreme point. ¦ Finite (exponential) complexity, but no polynomial implementation known. 12 LP: Polynomial Algorithms Ellipsoid. (Khachian 1979, 1980) ¦ Solvable in polynomial time: O(n 4 L) bit operations. – n = # variables – L = # bits in input ¦ Theoretical tour de force. ¦ Not remotely practical. Karmarkar’s algorithm. (Karmarkar 1984) ¦ O(n 3.5 L). ¦ Polynomial and reasonably efficient implementations possible. Interior point algorithms. ¦ O(n 3 L). ¦ Competitive with simplex! – will likely dominate on large problems soon ¦ Extends to even more general problems. 13 LP Duality Primal problem. Find a lower bound on optimal value. ¦ (x 1 , x 2 , x 3 , x 4 ) = (0, 0, 1, 0) z* ‡ 5. ¦ (x 1 , x 2 , x 3 , x 4 ) = (2, 1, 1, 1/3) z* ‡ 15. ¦ (x 1 , x 2 , x 3 , x 4 ) = (3, 0, 2, 0) z* ‡ 22. ¦ (x 1 , x 2 , x 3 , x 4 ) = (0, 14, 0, 5) z* ‡ 29. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 14 LP Duality Primal problem. Find an upper bound on optimal value. ¦ Multiply 2 nd inequality by 2: 10x 1 + 2x 2 + 6x 3 + 16x 4 £ 110. z* = 4x 1 + x 2 + 5x 3 + 3x 4 £ 10x 1 + 2x 2 + 6x 3 + 16x 4 £ 110. ¦ Adding 2 nd and 3 rd inequalities: 4x 1 + 3x 2 + 6x 3 + 3x 4 £ 58. z* = 4x 1 + x 2 + 5x 3 + 3x 4 £ 4x 1 + 3x 2 + 6x 3 + 3x 4 £ 58. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 15 LP Duality Primal problem. Find an upper bound on optimal value. ¦ Adding 11 times 1 st inequality to 6 times 3 rd inequality: z* = 4x 1 + x 2 + 5x 3 + 3x 4 £ 5x 1 + x 2 + 7x 3 + 3x 4 £ 29. Recall. ¦ (x 1 , x 2 , x 3 , x 4 ) = (0, 14, 0, 5) z* ‡ 29. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 16 LP Duality Primal problem. General idea: add linear combination (y 1 , y 2 , y 3 ) of the constraints. Dual problem. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 3 2 1 4 3 2 1 3 3 2 1 2 3 2 1 1 3 2 1 3 55 ) 5 8 3 ( ) 3 3 ( ) 2 ( ) 5 ( y y y x y y y x y y y x y y y x y y y + + £ - + + + + - + + + - + - + 0 , , 3 5 8 3 5 3 3 1 2 4 5 t. s. 3 55 min 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 ‡ ‡ - + ‡ + + - ‡ + + - ‡ - + + + y y y y y y y y y y y y y y y y y y Page 5 Princeton University • COS 423 • Theory of Algorithms • Spring 2001 • Kevin Wayne Linear Programming 2 Linear Programming Significance. ¦ Quintessential tool for optimal allocation of scarce resources, among a number of competing activities. ¦ Powerful model generalizes many classic problems: – shortest path, max flow, multicommodity flow, MST, matching, 2-person zero sum games ¦ Ranked among most important scientific advances of 20 th century. – accounts for a major proportion of all scientific computation ¦ Helps find "good" solutions to NP-hard optimization problems. – optimal solutions (branch-and-cut) – provably good solutions (randomized rounding) 3 Brewery Problem Small brewery produces ale and beer. ¦ Production limited by scarce resources: corn, hops, barley malt. ¦ Recipes for ale and beer require different proportions of resources. How can brewer maximize profits? ¦ Devote all resources to beer: 32 barrels of beer $736. ¦ Devote all resources to ale: 34 barrels of ale $442. ¦ 7½ barrels of ale, 29½ barrels of beer $776. ¦ 12 barrels of ale, 28 barrels of beer $800. Beverage Corn (pounds) Malt (pounds) Hops (ounces) Beer 15 20 4 Ale 5 35 4 Profit ($) 23 13 Quantity 480 1190 160 4 Brewery Problem 0 , 1190 20 35 160 4 4 480 15 5 t. s. 23 13 max ‡ £ + £ + £ + + B A B A B A B A B A 5 Brewery Problem: Feasible Region Ale Beer (34, 0) (0, 32) Corn 5A + 15B £ 480 (12, 28) (26, 14) (0, 0) Hops 4A + 4B £ 160 Malt 35A + 20B £ 1190 6 Brewery Problem: Objective Function Ale Beer (34, 0) (0, 32) (12, 28) 13A + 23B = 800 13A + 23B = 1600 13A + 23B = 442 (26, 14) Profit (0, 0) 7 Ale Beer (34, 0) (0, 32) (12, 28) (26, 14) (0, 0) Extreme points Brewery Problem: Geometry Brewery problem observation. Regardless of coefficients of linear objective function, there exists an optimal solution that is an extreme point. 8 Linear Programming LP "standard" form. ¦ Input data: rational numbers c j , b i , a ij . ¦ Maximize linear objective function. ¦ Subject to linear inequalities. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 0 t. s. max (P) ‡ £ • x b Ax x c 9 LP: Geometry Geometry. ¦ Forms an n-dimensional polyhedron. ¦ Convex: if y and z are feasible solutions, then so is ½y + ½z. ¦ Extreme point: feasible solution x that can't be written as ½y + ½z for any two distinct feasible solutions y and z. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 z y z y Convex Not convex Extreme points 10 LP: Geometry Extreme Point Theorem. If there exists an optimal solution to standard form LP (P), then there exists one that is an extreme point. ¦ Only need to consider finitely many possible solutions. Greed. Local optima are global optima. 11 LP: Algorithms Simplex. (Dantzig 1947) ¦ Developed shortly after WWII in response to logistical problems: used for 1948 Berlin airlift. ¦ Practical solution method that moves from one extreme point to a neighboring extreme point. ¦ Finite (exponential) complexity, but no polynomial implementation known. 12 LP: Polynomial Algorithms Ellipsoid. (Khachian 1979, 1980) ¦ Solvable in polynomial time: O(n 4 L) bit operations. – n = # variables – L = # bits in input ¦ Theoretical tour de force. ¦ Not remotely practical. Karmarkar’s algorithm. (Karmarkar 1984) ¦ O(n 3.5 L). ¦ Polynomial and reasonably efficient implementations possible. Interior point algorithms. ¦ O(n 3 L). ¦ Competitive with simplex! – will likely dominate on large problems soon ¦ Extends to even more general problems. 13 LP Duality Primal problem. Find a lower bound on optimal value. ¦ (x 1 , x 2 , x 3 , x 4 ) = (0, 0, 1, 0) z* ‡ 5. ¦ (x 1 , x 2 , x 3 , x 4 ) = (2, 1, 1, 1/3) z* ‡ 15. ¦ (x 1 , x 2 , x 3 , x 4 ) = (3, 0, 2, 0) z* ‡ 22. ¦ (x 1 , x 2 , x 3 , x 4 ) = (0, 14, 0, 5) z* ‡ 29. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 14 LP Duality Primal problem. Find an upper bound on optimal value. ¦ Multiply 2 nd inequality by 2: 10x 1 + 2x 2 + 6x 3 + 16x 4 £ 110. z* = 4x 1 + x 2 + 5x 3 + 3x 4 £ 10x 1 + 2x 2 + 6x 3 + 16x 4 £ 110. ¦ Adding 2 nd and 3 rd inequalities: 4x 1 + 3x 2 + 6x 3 + 3x 4 £ 58. z* = 4x 1 + x 2 + 5x 3 + 3x 4 £ 4x 1 + 3x 2 + 6x 3 + 3x 4 £ 58. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 15 LP Duality Primal problem. Find an upper bound on optimal value. ¦ Adding 11 times 1 st inequality to 6 times 3 rd inequality: z* = 4x 1 + x 2 + 5x 3 + 3x 4 £ 5x 1 + x 2 + 7x 3 + 3x 4 £ 29. Recall. ¦ (x 1 , x 2 , x 3 , x 4 ) = (0, 14, 0, 5) z* ‡ 29. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 16 LP Duality Primal problem. General idea: add linear combination (y 1 , y 2 , y 3 ) of the constraints. Dual problem. 0 , , , 3 5 3 2 55 8 3 5 1 3 t. s. 3 5 4 max 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 4 3 2 1 ‡ £ - + + - £ + + + £ + - - + + + x x x x x x x x x x x x x x x x x x x x 3 2 1 4 3 2 1 3 3 2 1 2 3 2 1 1 3 2 1 3 55 ) 5 8 3 ( ) 3 3 ( ) 2 ( ) 5 ( y y y x y y y x y y y x y y y x y y y + + £ - + + + + - + + + - + - + 0 , , 3 5 8 3 5 3 3 1 2 4 5 t. s. 3 55 min 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 3 2 1 ‡ ‡ - + ‡ + + - ‡ + + - ‡ - + + + y y y y y y y y y y y y y y y y y y 17 n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1 m i y n j c y a y b i j m i i ij m i i i £ £ ‡ £ £ ‡ = = 1 0 1 t. s. min (D) 1 1 LP Duality Primal and dual linear programs: given rational numbers a ij , b i ,c j , find values x i , y j that optimize (P) and (D). Duality Theorem (Gale-Kuhn-Tucker 1951, Dantzig-von Neumann 1947). If (P) and (D) are nonempty then max = min. ¦ Dual solution provides certificate of optimality decision version ? NP ? co-NP. ¦ Special case: max-flow min-cut theorem. ¦ Sensitivity analysis. 18 LP Duality: Economic Interpretation Brewer’s problem: find optimal mix of beer and ale to maximize profits. Entrepreneur’s problem: Buy individual resources from brewer at minimum cost. ¦ C, H, M = unit price for corn, hops, malt. ¦ Brewer won’t agree to sell resources if 5C + 4H + 35M < 13. 0 , 1190 20 35 160 4 4 480 15 5 t. s. 23 13 max (P) ‡ £ + £ + £ + + B A B A B A B A B A 0 , , 23 20 4 15 13 35 4 5 t. s. 1190 160 480 min (D) ‡ ‡ + + ‡ + + + + M H C M H C M H C M H C A* = 12 B* = 28 OPT = 800 C* = 1 H* = 2 M* = 0 OPT = 800 19 LP Duality: Economic Interpretation Sensitivity analysis. ¦ How much should brewer be willing to pay (marginal price) for additional supplies of scarce resources? ! corn $1, hops $2, malt $0. ¦ Suppose a new product "light beer" is proposed. It requires 2 corn, 5 hops, 24 malt. How much profit must be obtained from light beer to justify diverting resources from production of beer and ale? ! At least 2 ($1) + 5 ($2) + 24 (0$) = $12 / barrel. 20 Standard Form Standard form. Easy to handle variants. ¦ x + 2y - 3z ‡ 17 -x - 2y + 3z £ -17. ¦ x + 2y - 3z = 17 x + 2y - 3z £ 17, -x - 2y + 3z £ -17. ¦ min x + 2y - 3z max -x - 2y + 3z. ¦ x unrestricted x = y - z, y ‡ 0, z ‡ 0. n j x m i b x a x c j i n j j ij n j j j £ £ ‡ £ £ £ = = 1 0 1 t. s. max (P) 1 1Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!