Solved Examples

Important Theorems in Linear Programming

Before solving Linear Programming Problems graphically, recall the core results used repeatedly.

Theorem 1 (Corner Point Theorem): Let $R$ be the feasible region of an LPP and let $Z = ax + by$ be the objective function. If an optimal value (maximum or minimum) exists, then it occurs at a corner point (vertex) of the feasible region.

Theorem 2 (Bounded Region Theorem): If the feasible region $R$ is bounded, then both maximum and minimum values of the objective function exist, and each occurs at a corner point of $R$.

Rule for Unbounded Regions: If the feasible region is unbounded, then an optimum may or may not exist.

• To verify whether a calculated maximum $M$ is the true maximum, check whether the open half-plane $ax + by > M$ has any common point with the feasible region. If it does, then no maximum exists.
• To verify whether a calculated minimum $m$ is the true minimum, check whether the open half-plane $ax + by < m$ has any common point with the feasible region. If it does, then no minimum exists.

Example 1: Bounded Maximization

Maximize $Z = 3x + 4y$ subject to the constraints $x + y \le 4$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Draw the line $x + y = 4$. It cuts the axes at $(4, 0)$ and $(0, 4)$.

Step 2: Since the inequality is $x + y \le 4$, the feasible region lies on or below this line. Together with $x \ge 0$ and $y \ge 0$, the feasible region is the triangle in the first quadrant.

Step 3: The corner points are: $$O(0,0), \quad A(4,0), \quad B(0,4).$$

Step 4: Evaluate the objective function:

• At $O(0,0)$: $$Z = 3(0) + 4(0) = 0$$
• At $A(4,0)$: $$Z = 3(4) + 4(0) = 12$$
• At $B(0,4)$: $$Z = 3(0) + 4(4) = 16$$

Step 5: The greatest value is 16.

Answer: Maximum $Z = 16$ at $(0,4)$.

Example 2: Bounded Minimization

Minimize $Z = -3x + 4y$ subject to $x + 2y \le 8$, $3x + 2y \le 12$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Draw the lines: $$L_1: x + 2y = 8, \quad L_2: 3x + 2y = 12.$$

Step 2: Find the intersection point of $L_1$ and $L_2$: Subtract the first equation from the second: $$(3x+2y) - (x+2y) = 12 - 8$$ $$2x = 4 \Rightarrow x = 2.$$ Substitute in $x + 2y = 8$: $$2 + 2y = 8 \Rightarrow 2y = 6 \Rightarrow y = 3.$$ So the intersection point is $$B(2,3).$$

Step 3: Since both inequalities are of type $\le$, and $x, y \ge 0$, the feasible region is bounded in the first quadrant. Its corner points are: $$O(0,0), \quad A(4,0), \quad B(2,3), \quad C(0,4).$$

Step 4: Evaluate $Z$:

• At $O(0,0)$: $$Z = 0$$
• At $A(4,0)$: $$Z = -3(4) + 4(0) = -12$$
• At $B(2,3)$: $$Z = -3(2) + 4(3) = -6 + 12 = 6$$
• At $C(0,4)$: $$Z = 16$$

Step 5: The smallest value is $-12$.

Answer: Minimum $Z = -12$ at $(4,0)$.

Example 3: Unbounded Minimization

Minimize $Z = 3x + 5y$ subject to $x + 3y \ge 3$, $x + y \ge 2$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Draw the lines: $$x + 3y = 3, \quad x + y = 2.$$ Since both constraints are $\ge$, the feasible region lies above both lines in the first quadrant, so it is unbounded.

Step 2: Find the intersection point of the two lines: Subtract: $$(x+3y) - (x+y) = 3 - 2$$ $$2y = 1 \Rightarrow y = \frac{1}{2}.$$ Then $$x + y = 2 \Rightarrow x = 2 - \frac{1}{2} = \frac{3}{2}.$$ So, $$B\left(\frac{3}{2}, \frac{1}{2}\right).$$

Step 3: The relevant corner points on the boundary are: $$A(3,0), \quad B\left(\frac{3}{2},\frac{1}{2}\right), \quad C(0,2).$$

Step 4: Evaluate $Z$:

• At $A(3,0)$: $$Z = 3(3) + 5(0) = 9$$
• At $B\left(\frac{3}{2},\frac{1}{2}\right)$: $$Z = 3\left(\frac{3}{2}\right) + 5\left(\frac{1}{2}\right) = \frac{9}{2} + \frac{5}{2} = 7$$
• At $C(0,2)$: $$Z = 10$$

Step 5: The smallest value among corner points is $7$.

Step 6: Since the region is unbounded, we verify whether the half-plane $$3x + 5y < 7$$ has any common point with the feasible region. It does not. Hence the minimum exists.

Answer: Minimum $Z = 7$ at $\left(\frac{3}{2},\frac{1}{2}\right)$.

Example 4: Unbounded Maximization

Maximize $Z = 3x + 4y$ subject to $x \ge 0$, $y \ge 0$, and $x + y \ge 5$.

Solution: Step 1: Draw the line $$x + y = 5.$$ The feasible region lies in the first quadrant and on/above this line. It is unbounded.

Step 2: The boundary corner points are: $$A(5,0), \quad B(0,5).$$

Step 3: Evaluate $Z$:

• At $A(5,0)$: $$Z = 3(5) + 4(0) = 15$$
• At $B(0,5)$: $$Z = 3(0) + 4(5) = 20$$

Step 4: The largest value among these is 20, but since the feasible region is unbounded, we must check whether larger values are possible.

Step 5: Consider the half-plane $$3x + 4y > 20.$$ This clearly has common points with the feasible region; for example, $(10,10)$ is feasible and gives $$Z = 3(10) + 4(10) = 70.$$ So $Z$ can increase without bound.

Answer: No maximum value exists.

Example 5: Infeasible Problem

Maximize $Z = x + y$ subject to $x - y \le -1$, $-x + y \le 0$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Rewrite the inequalities: $$x - y \le -1 \Rightarrow y \ge x + 1$$ $$-x + y \le 0 \Rightarrow y \le x$$

Step 2: So any feasible point must satisfy both $$y \ge x + 1 \quad \text{and} \quad y \le x.$$ That would imply $$x + 1 \le x,$$ which is impossible.

Step 3: Therefore, there is no common region satisfying all the constraints.

Answer: No feasible solution exists.

Example 6: Multiple Optimal Solutions

Maximize $Z = 2x + 4y$ subject to $x + 2y \le 10$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: The feasible region is the triangle bounded by the axes and the line $$x + 2y = 10.$$ Its corner points are: $$O(0,0), \quad A(10,0), \quad B(0,5).$$

Step 2: Evaluate $Z$:

• At $O(0,0)$: $$Z = 0$$
• At $A(10,0)$: $$Z = 2(10) + 4(0) = 20$$
• At $B(0,5)$: $$Z = 2(0) + 4(5) = 20$$

Step 3: Since the maximum value is the same at two adjacent corner points $A$ and $B$, every point on the line segment joining them gives the same maximum value. In fact, $$Z = 2x + 4y = 2(x + 2y),$$ and on the boundary line $x + 2y = 10$, $$Z = 2(10) = 20.$$

Answer: Maximum $Z = 20$. Multiple optimal solutions exist on the line segment joining $(10,0)$ and $(0,5)$.

Example 7: LPP with Two Active Constraints

Maximize $Z = 4x + y$ subject to $x + y \le 50$, $3x + y \le 90$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Draw the lines $$x + y = 50, \quad 3x + y = 90.$$

Step 2: Find their intersection: Subtract the first from the second: $$(3x+y) - (x+y) = 90 - 50$$ $$2x = 40 \Rightarrow x = 20.$$ Then $$x + y = 50 \Rightarrow y = 30.$$ So, $$B(20,30).$$

Step 3: The feasible region in the first quadrant has corner points: $$O(0,0), \quad A(30,0), \quad B(20,30), \quad C(0,50).$$ Here $(30,0)$ is the x-intercept of $3x+y=90$, and $(0,50)$ is the y-intercept of $x+y=50$.

Step 4: Evaluate $Z = 4x + y$:

• At $O(0,0)$: $$Z = 0$$
• At $A(30,0)$: $$Z = 4(30) + 0 = 120$$
• At $B(20,30)$: $$Z = 4(20) + 30 = 110$$
• At $C(0,50)$: $$Z = 50$$

Step 5: The maximum value is 120.

Answer: Maximum $Z = 120$ at $(30,0)$.

Example 8: Simultaneous Maximum and Minimum

Determine the maximum and minimum values of $Z = x + 2y$ subject to $x + 2y \ge 100$, $2x - y \le 0$, $2x + y \le 200$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Rewrite the second inequality: $$2x - y \le 0 \Rightarrow y \ge 2x.$$ So the feasible region is given by: $$x + 2y \ge 100, \quad y \ge 2x, \quad 2x + y \le 200, \quad x,y \ge 0.$$

Step 2: Find the intersection points of the boundary lines.

(i) Intersection of $x + 2y = 100$ and $y = 2x$: Substitute $y = 2x$: $$x + 2(2x) = 100 \Rightarrow 5x = 100 \Rightarrow x = 20, \ y = 40.$$ So, $$A(20,40).$$

(ii) Intersection of $y = 2x$ and $2x + y = 200$: $$2x + 2x = 200 \Rightarrow 4x = 200 \Rightarrow x = 50, \ y = 100.$$ So, $$B(50,100).$$

(iii) Intersection with y-axis: Since $x=0$ is allowed,

• From $x + 2y \ge 100$, we get $y \ge 50$.
• From $2x + y \le 200$, we get $y \le 200$. So the y-axis portion of the feasible region runs from $$C(0,50) \text{ to } D(0,200).$$

Thus the corner points are: $$C(0,50), \quad A(20,40), \quad B(50,100), \quad D(0,200).$$

Step 3: Evaluate $Z = x + 2y$:

• At $C(0,50)$: $$Z = 0 + 2(50) = 100$$
• At $A(20,40)$: $$Z = 20 + 2(40) = 100$$
• At $B(50,100)$: $$Z = 50 + 200 = 250$$
• At $D(0,200)$: $$Z = 400$$

Step 4: Hence,

• Minimum value is 100, attained at both $(0,50)$ and $(20,40)$, so in fact it is attained at every point on the segment joining these two points.
• Maximum value is 400 at $(0,200)$.

Answer: Minimum $Z = 100$ on the line segment joining $(0,50)$ and $(20,40)$. Maximum $Z = 400$ at $(0,200)$.

Example 9: Complex Bounded Region

Maximize $Z = 3x + 2y$ subject to $x + y \le 5$, $x \le 4$, $y \le 6$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: In the first quadrant, the condition $x + y \le 5$ already forces $$y \le 5.$$ Therefore the extra condition $$y \le 6$$ is automatically satisfied and is redundant.

Step 2: So we only need to consider: $$x + y \le 5, \quad x \le 4, \quad x \ge 0, \quad y \ge 0.$$ The corner points are: $$O(0,0), \quad A(4,0), \quad B(4,1), \quad C(0,5).$$

Step 3: Evaluate $Z = 3x + 2y$:

• At $O(0,0)$: $$Z = 0$$
• At $A(4,0)$: $$Z = 12$$
• At $B(4,1)$: $$Z = 3(4) + 2(1) = 14$$
• At $C(0,5)$: $$Z = 10$$

Step 4: The maximum value is 14.

Answer: Maximum $Z = 14$ at $(4,1)$.

Example 10: Diet Problem Formulation and Solution

Minimize $Z = 4x + 6y$ subject to $3x + 6y \ge 80$, $4x + 3y \ge 100$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Draw the lines $$3x + 6y = 80 \quad \text{and} \quad 4x + 3y = 100.$$ Since both inequalities are of type $\ge$, the feasible region is unbounded in the first quadrant.

Step 2: Find the intersection of the two lines: Multiply the second equation by 2: $$8x + 6y = 200.$$ Subtract the first equation: $$5x = 120 \Rightarrow x = 24.$$ Then $$3(24) + 6y = 80 \Rightarrow 72 + 6y = 80 \Rightarrow 6y = 8 \Rightarrow y = \frac{4}{3}.$$ So, $$B\left(24,\frac{4}{3}\right).$$

Step 3: Find the axis corner points of the feasible region:

• On x-axis ($y=0$): $$3x \ge 80 \Rightarrow x \ge \frac{80}{3}, \qquad 4x \ge 100 \Rightarrow x \ge 25.$$ Hence the effective x-axis corner is $$A(25,0).$$
• On y-axis ($x=0$): $$6y \ge 80 \Rightarrow y \ge \frac{40}{3}, \qquad 3y \ge 100 \Rightarrow y \ge \frac{100}{3}.$$ Hence the effective y-axis corner is $$C\left(0,\frac{100}{3}\right).$$

Step 4: Evaluate $Z$:

• At $A(25,0)$: $$Z = 4(25) + 6(0) = 100$$
• At $B\left(24,\frac{4}{3}\right)$: $$Z = 4(24) + 6\left(\frac{4}{3}\right) = 96 + 8 = 104$$
• At $C\left(0,\frac{100}{3}\right)$: $$Z = 6\left(\frac{100}{3}\right) = 200$$

Step 5: The least value is 100.

Step 6: Since the feasible region is unbounded, check whether the half-plane $$4x + 6y < 100$$ intersects the feasible region. It does not. So the minimum exists.

Answer: Minimum $Z = 100$ at $(25,0)$.

Example 11: Manufacturing Problem

Maximize $Z = 50x + 60y$ subject to $5x + 8y \le 200$, $5x + 4y \le 120$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Find the intersection of the two boundary lines: $$5x + 8y = 200, \quad 5x + 4y = 120.$$ Subtract: $$4y = 80 \Rightarrow y = 20.$$ Then $$5x + 4(20) = 120 \Rightarrow 5x = 40 \Rightarrow x = 8.$$ So, $$B(8,20).$$

Step 2: Axis intercepts:

• For $5x + 8y \le 200$, x-intercept is 40 and y-intercept is 25.
• For $5x + 4y \le 120$, x-intercept is 24 and y-intercept is 30. Thus the effective corner points are: $$O(0,0), \quad A(24,0), \quad B(8,20), \quad C(0,25).$$

Step 3: Evaluate $Z$:

• At $O(0,0)$: $$Z = 0$$
• At $A(24,0)$: $$Z = 50(24) = 1200$$
• At $B(8,20)$: $$Z = 50(8) + 60(20) = 400 + 1200 = 1600$$
• At $C(0,25)$: $$Z = 60(25) = 1500$$

Step 4: Maximum value is 1600.

Answer: Maximum $Z = 1600$ at $(8,20)$.

Example 12: Allocation Problem

Minimize $Z = 6x + 5y$ subject to $2x + y \ge 280$, $3x + 5y \ge 700$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Find the intersection point of the lines: $$2x + y = 280, \quad 3x + 5y = 700.$$ Multiply the first by 5: $$10x + 5y = 1400.$$ Subtract the second: $$7x = 700 \Rightarrow x = 100.$$ Then $$y = 280 - 2(100) = 80.$$ So, $$B(100,80).$$

Step 2: Axis corner points:

• On x-axis: $$2x \ge 280 \Rightarrow x \ge 140,$$ $$3x \ge 700 \Rightarrow x \ge \frac{700}{3}.$$ Hence the effective x-axis corner is $$A\left(\frac{700}{3},0\right).$$
• On y-axis: $$y \ge 280, \quad 5y \ge 700 \Rightarrow y \ge 140.$$ Hence the effective y-axis corner is $$C(0,280).$$

Step 3: Evaluate $Z$:

• At $A\left(\frac{700}{3},0\right)$: $$Z = 6\left(\frac{700}{3}\right) = 1400$$
• At $B(100,80)$: $$Z = 6(100) + 5(80) = 1000$$
• At $C(0,280)$: $$Z = 1400$$

Step 4: The minimum value is 1000.

Step 5: Since the region is unbounded, check whether $$6x + 5y < 1000$$ intersects the feasible region. It does not.

Answer: Minimum $Z = 1000$ at $(100,80)$.

Example 13: Furniture Dealer

Maximize $Z = 250x + 75y$ subject to $5x + y \le 100$, $x + y \le 60$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Find the intersection of the lines: $$5x + y = 100, \quad x + y = 60.$$ Subtract: $$4x = 40 \Rightarrow x = 10.$$ Then $$y = 60 - 10 = 50.$$ So, $$B(10,50).$$

Step 2: Axis intercepts give the other corner points:

• x-axis corner: $A(20,0)$
• y-axis corner: $C(0,60)$ Hence the feasible region has corner points: $$O(0,0), \quad A(20,0), \quad B(10,50), \quad C(0,60).$$

Step 3: Evaluate $Z$:

• At $A(20,0)$: $$Z = 250(20) = 5000$$
• At $B(10,50)$: $$Z = 250(10) + 75(50) = 2500 + 3750 = 6250$$
• At $C(0,60)$: $$Z = 75(60) = 4500$$

Step 4: Maximum value is 6250.

Answer: Maximum $Z = 6250$ at $(10,50)$.

Example 14: Investment Mix

Maximize $Z = 4500x + 5000y$ subject to $x + y \le 250$, $5x + 8y \le 1400$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Find the intersection of the two lines: $$x + y = 250, \quad 5x + 8y = 1400.$$ From the first, $$x = 250 - y.$$ Substitute: $$5(250-y) + 8y = 1400$$ $$1250 - 5y + 8y = 1400$$ $$3y = 150 \Rightarrow y = 50.$$ Hence $$x = 200.$$ So the intersection point is $$B(200,50).$$

Step 2: The other boundary corner points are: $$A(250,0), \quad C(0,175).$$ Together with the origin, the corner points are $$O(0,0), A(250,0), B(200,50), C(0,175).$$

Step 3: Evaluate $Z$:

• At $A(250,0)$: $$Z = 4500(250) = 1125000$$
• At $B(200,50)$: $$Z = 4500(200) + 5000(50) = 900000 + 250000 = 1150000$$
• At $C(0,175)$: $$Z = 5000(175) = 875000$$

Step 4: Maximum value is 11,50,000.

Answer: Maximum $Z = 11,50,000$ at $(200,50)$.

Example 15: Transportation Problem Simplified

Minimize $Z = 3x + 3y + 280$ subject to $x + y \le 50$, $x + y \ge 10$, $x \le 20$, $y \le 30$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Since $$Z = 3x + 3y + 280 = 3(x+y) + 280,$$ we only need to minimize $x+y$.

Step 2: The feasible region is bounded by: $$x+y \le 50, \quad x+y \ge 10, \quad x \le 20, \quad y \le 30, \quad x,y \ge 0.$$ The lower boundary is the line $$x+y = 10.$$ Within the rectangle $0 \le x \le 20$, $0 \le y \le 30$, the feasible segment on this line runs from $$(10,0) \text{ to } (0,10).$$

Step 3: Since $Z = 3(x+y)+280$, every point on $x+y=10$ gives $$Z = 3(10) + 280 = 310.$$

Step 4: Therefore the minimum value is attained at every feasible point on the segment joining $(10,0)$ and $(0,10)$.

Answer: Minimum $Z = 310$ on the line segment joining $(10,0)$ and $(0,10)$.

Example 16: Advertising Problem

Maximize $Z = 1000x + 4000y$ subject to $3x + 10y \le 60$, $x \ge 5$, $y \ge 2$.

Solution: Step 1: The feasible region is bounded by the lines $$x = 5, \quad y = 2, \quad 3x + 10y = 60.$$

Step 2: Find the corner points.

(i) Intersection of $x=5$ and $y=2$: $$A(5,2).$$ Check feasibility: $$3(5) + 10(2) = 35 \le 60,$$ so it is feasible.

(ii) Intersection of $x=5$ and $3x+10y=60$: $$15 + 10y = 60 \Rightarrow 10y = 45 \Rightarrow y = 4.5.$$ So, $$B(5,4.5).$$

(iii) Intersection of $y=2$ and $3x+10y=60$: $$3x + 20 = 60 \Rightarrow 3x = 40 \Rightarrow x = \frac{40}{3}.$$ So, $$C\left(\frac{40}{3},2\right).$$

Step 3: Evaluate $Z$:

• At $A(5,2)$: $$Z = 1000(5) + 4000(2) = 13000$$
• At $B(5,4.5)$: $$Z = 1000(5) + 4000(4.5) = 5000 + 18000 = 23000$$
• At $C\left(\frac{40}{3},2\right)$: $$Z = 1000\left(\frac{40}{3}\right) + 8000 = \frac{40000}{3} + 8000 = \frac{64000}{3} \approx 21333.33$$

Step 4: Maximum value is 23000.

Answer: Maximum $Z = 23000$ at $(5,4.5)$.

Example 17: Airline Optimization

Maximize $Z = 1000x + 600y$ subject to $x + y \le 200$, $x \ge 20$, $y \ge 4x$, $y \ge 0$.

Solution: Step 1: The feasible region is bounded by the lines $$x = 20, \quad y = 4x, \quad x + y = 200.$$

Step 2: Find the corner points.

• Intersection of $x=20$ and $y=4x$: $$A(20,80)$$
• Intersection of $x=20$ and $x+y=200$: $$B(20,180)$$
• Intersection of $y=4x$ and $x+y=200$: $$x + 4x = 200 \Rightarrow 5x = 200 \Rightarrow x = 40, y = 160$$ So, $$C(40,160).$$

Step 3: Evaluate $Z$:

• At $A(20,80)$: $$Z = 1000(20) + 600(80) = 68000$$
• At $B(20,180)$: $$Z = 1000(20) + 600(180) = 128000$$
• At $C(40,160)$: $$Z = 1000(40) + 600(160) = 136000$$

Step 4: Maximum value is 136000.

Answer: Maximum $Z = 136000$ at $(40,160)$.

Example 18: Tailor Shop Problem

Maximize $Z = 500x + 400y$ subject to $x + 2y \le 80$, $3x + y \le 120$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Find the intersection of the two lines: $$x + 2y = 80, \quad 3x + y = 120.$$ From the first, $$x = 80 - 2y.$$ Substitute into the second: $$3(80 - 2y) + y = 120$$ $$240 - 6y + y = 120$$ $$-5y = -120 \Rightarrow y = 24.$$ Then $$x = 80 - 48 = 32.$$ So, $$B(32,24).$$

Step 2: Axis corner points are: $$A(40,0), \quad C(0,40).$$ Hence the feasible region has corner points: $$O(0,0), A(40,0), B(32,24), C(0,40).$$

Step 3: Evaluate $Z$:

• At $A(40,0)$: $$Z = 500(40) = 20000$$
• At $B(32,24)$: $$Z = 500(32) + 400(24) = 16000 + 9600 = 25600$$
• At $C(0,40)$: $$Z = 400(40) = 16000$$

Step 4: Maximum value is 25600.

Answer: Maximum $Z = 25600$ at $(32,24)$.

Example 19: Finding Parameter Relation for Multiple Optima

Let $Z = px + qy$, where $p, q > 0$. Find the condition on $p$ and $q$ such that the maximum of $Z$ occurs at both $(15, 15)$ and $(0, 20)$.

Solution: Step 1: If the same optimal value occurs at both points, then the objective function must have equal value at the two points.

Step 2: At $(15,15)$: $$Z_1 = 15p + 15q.$$ At $(0,20)$: $$Z_2 = 20q.$$

Step 3: Equate them: $$15p + 15q = 20q$$ $$15p = 5q$$ $$3p = q.$$

Answer: The required condition is $$q = 3p.$$

Example 20: Minimum of Objective Function

Minimize $Z = 200x + 500y$ subject to $x + 2y \ge 10$, $3x + 4y \le 24$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Draw the lines $$x + 2y = 10, \quad 3x + 4y = 24.$$ The feasible region lies above the first line, below the second line, and in the first quadrant.

Step 2: Find the intersection point: From $$x + 2y = 10 \Rightarrow 3x + 6y = 30.$$ Subtract $3x + 4y = 24$: $$2y = 6 \Rightarrow y = 3.$$ Then $$x + 2(3) = 10 \Rightarrow x = 4.$$ So, $$B(4,3).$$

Step 3: Find the other boundary corner points on the y-axis:

• On $x + 2y = 10$, y-intercept is $(0,5)$
• On $3x + 4y = 24$, y-intercept is $(0,6)$ Both satisfy $x \ge 0$ and define the vertical side of the feasible region. Thus the corner points are: $$A(0,5), \quad B(4,3), \quad C(0,6).$$

Step 4: Evaluate $Z$:

• At $A(0,5)$: $$Z = 200(0) + 500(5) = 2500$$
• At $B(4,3)$: $$Z = 200(4) + 500(3) = 800 + 1500 = 2300$$
• At $C(0,6)$: $$Z = 3000$$

Step 5: Minimum value is 2300.

Answer: Minimum $Z = 2300$ at $(4,3)$.

JEE Main Standard

Example 21: Maximize over a Bounded Region

Maximize $Z = 3x + 5y$ subject to $x + 4y \le 24$, $3x + y \le 21$, $x + y \le 9$, $x \ge 0$, $y \ge 0$.

Solution: Step 1: Find the intersections of the boundary lines.

(i) Intersection of $x + 4y = 24$ and $x + y = 9$: Subtract: $$3y = 15 \Rightarrow y = 5, \quad x = 4.$$ So, $$P(4,5).$$ Check in $3x + y \le 21$: $$3(4) + 5 = 17 \le 21,$$ so it is feasible.

(ii) Intersection of $3x + y = 21$ and $x + y = 9$: Subtract: $$2x = 12 \Rightarrow x = 6, \quad y = 3.$$ So, $$Q(6,3).$$ Check in $x + 4y \le 24$: $$6 + 12 = 18 \le 24,$$ so it is feasible.

Step 2: Axis intercepts give the remaining corner points:

• x-axis corner: $(7,0)$ from $3x+y\le21$
• y-axis corner: $(0,6)$ from $x+4y\le24$ Hence the corner points are: $$O(0,0), \quad A(7,0), \quad Q(6,3), \quad P(4,5), \quad C(0,6).$$

Step 3: Evaluate $Z$:

• At $A(7,0)$: $$Z = 21$$
• At $Q(6,3)$: $$Z = 3(6) + 5(3) = 33$$
• At $P(4,5)$: $$Z = 3(4) + 5(5) = 12 + 25 = 37$$
• At $C(0,6)$: $$Z = 30$$

Step 4: Maximum value is 37.

Answer: Maximum $Z = 37$ at $(4,5)$.

Example 22: Triangular Region

Find the maximum value of $Z = 2x + 3y$ in the region bounded by $y \ge 0$, $y \le x$, and $x + y \le 2$.

Solution: Step 1: The bounding lines are: $$y = 0, \quad y = x, \quad x + y = 2.$$

Step 2: Find the corner points:

• Intersection of $y=0$ and $y=x$: $$(0,0)$$
• Intersection of $y=0$ and $x+y=2$: $$(2,0)$$
• Intersection of $y=x$ and $x+y=2$: $$x+x=2 \Rightarrow x=1, y=1.$$ So, $$(1,1).$$

Step 3: Evaluate $Z$:

• At $(0,0)$: $$Z = 0$$
• At $(2,0)$: $$Z = 4$$
• At $(1,1)$: $$Z = 2 + 3 = 5$$

Step 4: Maximum value is 5.

Answer: Maximum $Z = 5$ at $(1,1)$.

Example 23: Modulus Constraint

Find the maximum value of $Z = 2x + y$ subject to the feasible region $|x| + |y| \le 1$.

Solution: Step 1: The inequality $$|x| + |y| \le 1$$ defines a diamond-shaped region (a square rotated by $45^\circ$) with corner points: $$(1,0), \quad (0,1), \quad (-1,0), \quad (0,-1).$$

Step 2: Evaluate $Z = 2x + y$ at these points:

• At $(1,0)$: $$Z = 2$$
• At $(0,1)$: $$Z = 1$$
• At $(-1,0)$: $$Z = -2$$
• At $(0,-1)$: $$Z = -1$$

Step 3: Maximum value is 2.

Answer: Maximum $Z = 2$ at $(1,0)$.

Example 24: Minimum Point in an Unbounded Region

Find the minimum point for $Z = 2x + 3y$ over the region $x \ge 0, y \ge 0, x + y \ge 4, 2x + y \ge 5$.

Solution: Step 1: Draw the lines $$x + y = 4, \quad 2x + y = 5.$$ The feasible region is in the first quadrant and above both lines, so it is unbounded.

Step 2: Find the intersection of the two lines: Subtract: $$(2x+y) - (x+y) = 5 - 4 \Rightarrow x = 1.$$ Then $$y = 3.$$ So one corner point is $$B(1,3).$$

Step 3: The other boundary corner points are found on the axes:

• On x-axis ($y=0$): $$x \ge 4, \quad 2x \ge 5.$$ Effective point is $$A(4,0).$$
• On y-axis ($x=0$): $$y \ge 4, \quad y \ge 5.$$ Effective point is $$C(0,5).$$

So the relevant corner points are: $$A(4,0), \quad B(1,3), \quad C(0,5).$$

Step 4: Evaluate $Z$:

• At $A(4,0)$: $$Z = 2(4) + 3(0) = 8$$
• At $B(1,3)$: $$Z = 2 + 9 = 11$$
• At $C(0,5)$: $$Z = 15$$

Step 5: The smallest value is 8.

Step 6: Since the region is unbounded, check whether the half-plane $$2x + 3y < 8$$ intersects the feasible region. It does not.

Answer: Minimum $Z = 8$ at $(4,0)$.