Linear Programming Exemplar Sums Class 12 Learncbse - Class 12...

Correct option: (D) q=3p.

Concept used. The value of the objective function Z=px+qy at two corner points is the same precisely when the line px+qy=const is parallel to (or passes through) the segment joining those corner points. If Z attains its maximum simultaneously at two corners (x₁,y₁) and (x₂,y₂), then Z(x₁,y₁)=Z(x₂,y₂), i.e. p x₁+q y₁=p x₂+q y₂.

1. Write Z at the two given corner points: Z(15,15) = 15p+15q, Z(0,20) = 0· p + 20q = 20q.
2. Set them equal (both are required to be the maximum, so they must produce the same value of Z): 15p + 15q = 20q.
3. Solve for the ratio of p and q: 15p = 20q - 15q = 5q ⇒ 3p = q.
4. Therefore q=3p, with both p,q>0 as given.

q=3p; option (D).

Correct option: (C) 47.

Concept used. The corner-point theorem for an LPP with a bounded feasible region states: if the feasible region is bounded and Z=ax+by is the objective function, then both the maximum and the minimum of Z over the feasible region are attained at a corner point of the region.

1. Evaluate Z=11x+7y at each corner point. At (0,3): Z = 11(0)+7(3) = 0+21 = 21.
2. At (3,2): Z = 11(3)+7(2) = 33 + 14 = 47.
3. At (0,5): Z = 11(0) + 7(5) = 0+35 = 35.
4. Compare values: 21, 47, 35. The largest is 47, attained at (3,2).

Maximum Z=47 at (3,2); option (C).

Correct option: (D) any point on the line segment joining the points (0,2) and (3,0).

Concept used. When the objective function Z=ax+by attains the same optimum value at two adjacent corner points, then every point on the edge of the feasible polygon joining those two corners is also optimum. This is the multiple optimal solutions case –- it occurs when the level curve Z=const is parallel to that edge.

1. Compute F=4x+6y at each corner: aligned F(0,2) &= 4(0)+6(2) = 0+12 = 12,
   F(3,0) &= 4(3)+6(0) = 12 + 0 = 12,
   F(6,0) &= 4(6)+6(0) = 24,
   F(6,8) &= 4(6)+6(8) = 24+48 = 72,
   F(0,5) &= 4(0)+6(5) = 30. aligned
2. Minimum value is 12, attained at both (0,2) and (3,0).
3. Since F is linear and equal at the two endpoints, F takes the same value 12 on every point of the segment joining (0,2) and (3,0) as well.
4. Hence the minimum F=12 is attained on the entire edge between (0,2) and (3,0).

Minimum F=12 attained on the whole segment (0,2) to (3,0); option (D).

Correct option: (D) infinite.

Concept used. If a linear function attains the same value at two different points P,Q, then by linearity it attains the same value at every point on the line segment PQ. In an LPP, when two corner points give the same Z, the entire edge connecting them yields the same Z, so there are infinitely many optimal points.

1. Let Z(P)=Z(Q)=M for two adjacent corner points P and Q.
2. For any point R = λ P + (1-λ)Q on the segment (λ∈[0,1]), linearity gives Z(R) = λ Z(P) + (1-λ)Z(Q) = λ M+(1-λ)M = M.
3. So every R∈PQ̄ has Z(R) = M.
4. The segment is uncountable, so infinitely many points attain Z_max.

Infinitely many; option (D).

Correct option: (A) a = 2b.

Concept used. The maximum of Z=ax+by at two corners means both corners satisfy Z=Z_max. Setting Z(2,4)=Z(4,0) gives a single equation relating a and b.

1. Compute Z at the two corners: Z(2,4) = a(2)+b(4) = 2a+4b, Z(4,0) = a(4) + b(0) = 4a.
2. Equate (both are the maximum): 2a + 4b = 4a.
3. Solve: 4b = 4a - 2a = 2a ⇒ 4b = 2a ⇒ 2b = a.
4. Rewrite as a = 2b, which matches option (A).

a=2b; option (A).

Correct option: (A) 60.

Concept used. For a bounded feasible region, both F_max and F_min are attained at corner points (by the corner-point theorem). Compute F at each corner; difference is F_max-F_min.

1. Tabulate F=4x+6y at each given corner:
   tabularc|c Corner & F=4x+6y
   (0,2) & 0+12=12
   (3,0) & 12+0=12
   (6,0) & 24+0=24
   (6,8) & 24+48=72
   (0,5) & 0+30=30 tabular
2. Read off F_max=72 at (6,8) and F_min=12 at both (0,2) and (3,0).
3. Difference: F_max-F_min=72-12=60.

F_max-F_min=60; option (A).

Correct option: (A) linear.

Concept used. By the very name Linear Programming, every defining ingredient must be linear: the objective function Z=ax+by (or ∑ a_i x_i in higher dimensions) and every constraint a_i x + b_i y ≤ c_i (or ≥, or =). Non-linear objectives belong to non-linear optimisation (quadratic, convex, etc.), not LPP.

1. Definition of an LPP (Chapter 12, Section 12.1): a problem in which a linear function (objective) is maximised or minimised subject to linear inequalities/equalities (constraints), and non-negativity restrictions.
2. ``Linear'' means each variable appears to the first power; no products xy, no x², no sin x, no e^x.
3. Hence the objective must be linear, option (A).

Linear; option (A).

Correct option: (D) both (A) and (C).

Concept used. Constraints of an LPP are restrictions that the decision variables must satisfy. They can be of two algebraic shapes: linear inequalities (≤ or ≥) and linear equations (=). Strict inequalities (<, >) are not allowed because optima are then not attained.

1. Resource constraints are usually of the form ``usage ≤ availability'', a linear inequality ≤. Example: 2x + 3y ≤ 12 (hours of labour).
2. Demand/minimum constraints are usually ``output ≥ minimum requirement'', a linear inequality ≥. Example: x + y ≥ 5 (minimum batch).
3. Balance/budget constraints can be exact, hence linear equations. Example: x + y = 100 (sell all 100 units).
4. Hence both (A) inequality and (C) equation are valid constraint forms in LPP.

Both linear inequality and linear equation; option (D).

Correct option: (B) convex polygon.

Concept used. A set S⊆R² is convex if for any two points P,Q∈ S, the entire segment PQ̄ also lies in S. Each linear inequality ax+by≤ c defines a closed half-plane, which is convex. The intersection of any collection of convex sets is convex. Therefore the feasible region (an intersection of half-planes) is convex; in two variables it is a convex polygonal region (bounded or unbounded).

1. Each linear inequality a_ix+b_iy≤ c_i defines a half-plane.
2. Each half-plane is a convex set (take any two points in it, the segment between them is also in the half-plane by linearity).
3. Feasible region = intersection of all half-planes (one per constraint, plus x≥ 0, y≥ 0).
4. Intersection of convex sets is convex.
5. So the feasible region is a convex polygonal region.

Convex polygon; option (B).

Correct option: (B) 120.

Concept used. For a bounded LPP, solve by the corner-point method: (i) plot the constraint lines and identify the feasible region; (ii) find each vertex (corner) by intersecting pairs of binding constraint lines and the axes; (iii) evaluate Z at every corner; (iv) pick the largest value for a maximisation problem.

1. Re-write the constraint lines: ₁x+y=50, ₂3x+y=90.
2. x- and y-intercepts: ₁ cuts the axes at (50,0) and (0,50); ₂ cuts at (30,0) and (0,90).
3. Intersection of ₁ and ₂: x+y=50, 3x+y=90 ⇒ subtract2x=40 ⇒ x=20, y=30.
4. The feasible region is bounded by x≥ 0, y≥ 0, and both lines (with ≤). Corners are: O(0,0), A(30,0), B(20,30), C(0,50). (We use A=(30,0) not (50,0) because the binding constraint on the x-axis is 3x+y≤ 90.)
5. Evaluate Z=4x+y: aligned Z(O) &= 0,
   Z(A) &= 4(30) + 0 = 120,
   Z(B) &= 4(20) + 30 = 80+30 = 110,
   Z(C) &= 0 + 50 = 50. aligned
6. Maximum value is 120 at (30,0).

Z_max=120 at (30,0); option (B).

Concept used. Corner-point method for a bounded LPP. Plot the lines 2x+y=6 and x=2, find the feasible region in the first quadrant, list the corner points, evaluate Z at each, and pick the maximum.

1. Plot constraint lines. ₁2x+y=6 goes through (3,0) and (0,6). ₂x=2 is a vertical line.
2. Find vertices of the feasible region. Intersect ₁ and ₂: substitute x=2 into ₁ 2(2)+y=6 ⇒ y=2. So (2,2) is a corner. Other corners are on the axes: (0,0), (2,0) (where x=2 meets the x-axis), and (0,6) (where ₁ meets the y-axis).
3. Sanity check (0,6) in x≤ 2: 0≤ 2, holds. So (0,6) is a vertex.
4. List corners: O(0,0), A(2,0), B(2,2), C(0,6).
5. Evaluate Z=11x+7y at each: aligned Z(O) &= 11(0)+7(0) = 0,
   Z(A) &= 11(2)+7(0) = 22,
   Z(B) &= 11(2)+7(2) = 22+14 = 36,
   Z(C) &= 11(0)+7(6) = 0+42 = 42. aligned
6. Compare: 0, 22, 36, 42. Maximum is 42 at (0,6).

Z_max=42 at (x,y)=(0,6).

Concept used. Classic two-variable LPP with a single slant constraint plus non-negativity. The feasible region is a triangle with vertices on the axes and at the slant line.

1. Constraint line: x+y=1 goes through (1,0) and (0,1).
2. Feasible region: the triangle O(0,0), A(1,0), B(0,1).
3. Evaluate Z=3x+4y at each corner: aligned Z(O) &= 3(0)+4(0) = 0,
   Z(A) &= 3(1)+4(0) = 3,
   Z(B) &= 3(0)+4(1) = 4. aligned
4. Maximum: compare 0, 3, 4. The largest is 4, attained at (0,1).

Z_max=4 at (x,y)=(0,1).

Concept used. Before applying the corner-point method, always check whether the feasible region is non-empty. Conflicting constraints can yield an empty feasible region, in which case the LPP is infeasible and there is no minimum to report.

1. Plot the lines. ₁x+y=8 through (8,0) and (0,8) –- region x+y≥ 8 is the half-plane above this line. ₂3x+5y=15 through (5,0) and (0,3) –- region 3x+5y≤ 15 is the half-plane below this line.
2. Test a sample point in both regions. Try (0,8): check x+y ≥ 8: 0+8=8 ≥ 8 . check 3x+5y ≤ 15: 0+40 = 40 ≤ 15. Fails.
3. Try (0,3): 0+3=3≥ 8 ×.
4. Try any point with x+y≥ 8 and 3x+5y≤ 15. From the first, y≥ 8-x. Substitute in the second: 3x+5(8-x)≤ 15, i.e. 3x+40-5x≤ 15, -2x≤ -25, x≥ 12.5. But the first constraint x+y≥ 8 with x≥ 12.5 and y≥ 0 is fine. Check the second again at x=12.5, y=0: 3(12.5)+0=37.5≤ 15. So no (x,y) in the first quadrant simultaneously satisfies both.
5. Conclusion: the feasible region is empty; the LPP is infeasible.

The feasible region is empty; the LPP has no feasible solution.

Concept used. Check feasibility first by sketching the two half-planes, then run the corner-point method only if the region is non-empty.

1. Re-write the constraints: ₁x-y=-1 i.e. y=x+1. Constraint x-y≤ -1 means y≥ x+1 (above the line). ₂-x+y=0 i.e. y=x. Constraint -x+y≤ 0 means y≤ x (below the line).
2. Combine: we need both y≥ x+1 and y≤ x, i.e. x+1≤ y≤ x, which forces x+1≤ x, i.e. 1≤ 0. Impossible.
3. Therefore the feasible region is empty.

Infeasible LPP: no feasible solution exists.

Concept used. Identify all binding pairs of constraints (lines) to find the corners of the feasible region, then evaluate Z.

1. Constraint lines: ₁x+3y=60 through (60,0), (0,20). ₂x+y=10 through (10,0), (0,10). ₃x=y through (0,0) at 45^∘.
2. Half-plane directions (test origin where applicable): x+3y≤ 60: origin gives 0≤ 60 , so origin side. x+y≥ 10: origin gives 0≥ 10, so opposite side. x≤ y: origin gives 0≤ 0 , so origin side / above the line y=x.
3. Find vertices. Solve binding pairs:
   • ₂∩₃: x+y=10, x=y ⇒ 2x=10, x=y=5. (5,5).
   • ₁∩₃: x+3y=60, x=y ⇒ y+3y=60, y=x=15. (15,15).
   • ₁∩x=0: (0,20). Check x≤ y: 0≤ 20 . Check x+y≥ 10: 20≥ 10 . Feasible.
   • ₂∩x=0: (0,10). Check x+3y≤ 60: 30≤ 60 . Check x≤ y: 0≤ 10 . Feasible.
4. Corner list: A(0,10), B(5,5), C(15,15), D(0,20).
5. Evaluate Z=3x+9y: aligned Z(A) &= 0+90 = 90,
   Z(B) &= 15+45 = 60,
   Z(C) &= 45+135 = 180,
   Z(D) &= 0+180 = 180. aligned
6. Maximum: Z_max=180, attained at both C(15,15) and D(0,20). Since Z equal at two corners, every point on the edge CD also gives Z=180 –- infinitely many optima.

Z_max=180 on the entire segment from (15,15) to (0,20).

Concept used. Formulate a real-world LPP in four steps: (i) identify decision variables; (ii) write the objective function; (iii) write all resource and demand constraints, including non-negativity; (iv) solve graphically by the corner-point method.

1. Decision variables. Let x= number of tables bought, y= number of chairs bought. Both must be non-negative integers, though for the LP-relaxation we treat them as reals in [0,∞).
2. Objective function. Profit per table = Rs. 250; profit per chair = Rs. 75. So Z = 250 x + 75 y (to be maximised).
3. Constraints.
   1. [label=()]
   2. Capital constraint: a table costs 2500, a chair 500, total spend ≤ 50000: 2500 x + 500 y ≤ 50000. Divide by 500: 5x + y ≤ 100.
   3. Storage constraint: total pieces ≤ 60: x + y ≤ 60.
   4. Non-negativity: x≥ 0, y≥ 0.
4. Plot the constraint lines.
   • ₁5x+y=100. x-intercept (20,0), y-intercept (0,100).
   • ₂x+y=60. x-intercept (60,0), y-intercept (0,60).
5. Find vertices of the feasible region.
   • ₁∩₂: 5x+y=100, x+y=60. Subtract: 4x=40 ⇒ x=10, then y=50. So (10,50). Check non-negativity: .
   • ₁∩y=0: 5x=100 ⇒ x=20. So (20,0). Check x+y≤ 60: 20≤ 60 .
   • ₂∩x=0: y=60. So (0,60). Check 5x+y≤ 100: 60≤ 100 .
   • Origin O(0,0).
6. Corner list: O(0,0), A(20,0), B(10,50), C(0,60).
7. Evaluate Z=250 x + 75 y: aligned Z(O) &= 0,
   Z(A) &= 250(20)+75(0) = 5000,
   Z(B) &= 250(10)+75(50) = 2500+3750 = 6250,
   Z(C) &= 250(0)+75(60) = 4500. aligned
8. Maximum: Z_max=6250 at (x,y)=(10,50), i.e. buy 10 tables and 50 chairs.
9. Sanity check. Capital used: 2500(10)+500(50)=25000+25000 =50000 . Storage used: 10+50=60 . Both constraints active –- the optimum sits at the intersection of both binding lines, as expected.

Buy 10 tables and 50 chairs for maximum profit of Rs. 6250.

Concept used. Resource-allocation LPP. Decision variables are production quantities; objective is total profit; constraints are resource limits and non-negativity.

1. Decision variables. Let x= units of P produced, y= units of Q produced.
2. Objective function. Z = 40 x + 30 y (maximise).
3. Constraints.
   1. [label=()]
   2. Labour: 4x+3y≤ 200.
   3. Raw material: 2x+5y≤ 150.
   4. Non-negativity: x,y≥ 0.
4. Plot constraint lines. ₁4x+3y=200 through (50,0), (0,200/3)≈ (0,66.67). ₂2x+5y=150 through (75,0), (0,30).
5. Vertices of feasible region.
   • ₁∩₂: solve 4x+3y=200, 2x+5y=150. Multiply 2nd by 2: 4x+10y=300. Subtract 1st: 7y=100 ⇒ y=100/7. Then 4x=200-3(100/7) = 200-300/7 = (1400-300)/7=1100/7, so x=275/7. Vertex (2757,1007) ≈ (39.29, 14.29).
   • ₁∩y=0: (50,0). Check ₂: 2(50)+0=100≤ 150 .
   • ₂∩x=0: (0,30). Check ₁: 0+3(30)=90≤ 200 .
   • Origin O(0,0).
6. Corner list: O(0,0), A(50,0), B(2757,1007), C(0,30).
7. Evaluate Z=40x+30y: aligned Z(O) &= 0,
   Z(A) &= 40(50)+30(0) = 2000,
   Z(B) &= 40·2757+30·1007 = 11000+30007 = 140007 = 2000,
   Z(C) &= 40(0)+30(30) = 900. aligned
8. Comparison: Z_max=2000, attained at both A(50,0) and B(275/7,100/7) –- and hence on the entire segment AB (multiple optima).

Z_max= Rs. 2000, on the edge from (50,0) to (275/7,100/7).

Concept used. Mixed-direction LPP –- one constraint is ≥ (a ``floor''), another is ≤ (a ``ceiling''). The feasible region is bounded between them; check both for binding.

1. Plot lines. ₁x+2y=10 through (10,0), (0,5). Region x+2y≥ 10 is above this line. ₂3x+4y=24 through (8,0), (0,6). Region 3x+4y≤ 24 is below this line.
2. Vertices of feasible region.
   • ₁∩₂: solve x+2y=10, 3x+4y=24. Multiply 1st by 2: 2x+4y=20. Subtract from 2nd: x=4. Back-sub: 4+2y=10 ⇒ y=3. Vertex (4,3).
   • ₁∩x=0: (0,5). Check ₂: 0+20=20 ≤ 24 .
   • ₂∩x=0: (0,6). Check ₁: 0+12=12 ≥ 10 .
   • ₁∩y=0: (10,0). Check ₂: 30+0=30≤ 24. ×
   • ₂∩y=0: (8,0). Check ₁: 8+0=8≥ 10. ×
   So vertices are A(0,5), B(4,3), C(0,6).
3. Evaluate Z=200x+500y: aligned Z(A) &= 200(0)+500(5) = 2500,
   Z(B) &= 200(4)+500(3) = 800+1500 = 2300,
   Z(C) &= 200(0)+500(6) = 3000. aligned
4. Minimum: Z_min=2300 at (4,3).
5. Verify both constraints are binding at (4,3): x+2y=4+6=10 (eq.); 3x+4y=12+12=24 (eq.).

Z_min=2300 at (x,y)=(4,3).