krit.club logo

Linear Programming - Feasible and infeasible regions (bounded and unbounded)

Grade 12CBSE

Review the key concepts, formulae, and examples before starting your quiz.

πŸ”‘Concepts

β€’

Objective Function: This is a linear function of the form Z=ax+byZ = ax + by, where aa and bb are constants. The goal in Linear Programming is to either maximize or minimize this value based on specific requirements. Visually, this is represented as a family of parallel lines on a coordinate plane.

β€’

Constraints and Non-negative Restrictions: These are linear inequalities like a1x+b1y≀c1a_1x + b_1y \leq c_1 or a2x+b2yβ‰₯c2a_2x + b_2y \geq c_2 that restrict the values of xx and yy. In most real-world problems, we also include non-negative constraints xβ‰₯0x \geq 0 and yβ‰₯0y \geq 0, which visually restrict the solution to the first quadrant of the Cartesian plane.

β€’

Feasible Region: This is the common region determined by all the constraints, including the non-negative constraints. Graphically, it is the overlapping shaded area where the solution to every individual inequality exists simultaneously. If no such common area exists, the problem is said to have an infeasible solution.

β€’

Bounded Feasible Region: A feasible region is called bounded if it can be enclosed within a circle. Visually, it looks like a closed polygon. For a bounded region, the objective function ZZ will always have both a maximum and a minimum value occurring at one of the corner points.

β€’

Unbounded Feasible Region: A feasible region is unbounded if it extends infinitely in at least one direction and cannot be enclosed by any circle. Visually, the shaded area remains open on one or more sides. In this case, a maximum or minimum value may or may not exist. To confirm an optimal value, additional tests using the inequality ax+by<Max + by < M (for minimum) or ax+by>Max + by > M (for maximum) are required.

β€’

Corner Point Theorem: This fundamental theorem states that the optimal (maximum or minimum) value of the objective function, if it exists, must occur at one of the vertices (corner points) of the feasible region. Visually, these are the points where the boundary lines of the constraints intersect.

β€’

Multiple Optimal Solutions: If two corner points of the feasible region produce the same maximum (or minimum) value, then every point on the line segment joining these two points also provides the same optimal value. Graphically, the objective function line becomes parallel to one of the boundary edges of the feasible region.

πŸ“Formulae

Objective Function: Z=ax+byZ = ax + by

Linear Constraints: aix+biy≀cia_ix + b_iy \leq c_i or aix+biyβ‰₯cia_ix + b_iy \geq c_i

Non-negative constraints: xβ‰₯0,yβ‰₯0x \geq 0, y \geq 0

General form of a line: ax+by=cax + by = c

Intercept form for graphing: xΞ±+yΞ²=1\frac{x}{\alpha} + \frac{y}{\beta} = 1, where Ξ±\alpha is the xx-intercept and Ξ²\beta is the yy-intercept.

πŸ’‘Examples

Problem 1:

Maximize Z=4x+yZ = 4x + y subject to the constraints: x+y≀50x + y \leq 50, 3x+y≀903x + y \leq 90, xβ‰₯0,yβ‰₯0x \geq 0, y \geq 0.

Solution:

Step 1: Convert inequalities to equations to find boundary lines: L1:x+y=50L_1: x + y = 50 and L2:3x+y=90L_2: 3x + y = 90. Step 2: Find intercepts. For L1L_1: (50,0),(0,50)(50,0), (0,50). For L2L_2: (30,0),(0,90)(30,0), (0,90). Step 3: Plot the lines. The region is bounded by the axes and these lines in the first quadrant. The intersection point of x+y=50x + y = 50 and 3x+y=903x + y = 90 is solved by subtraction: (3x+y)βˆ’(x+y)=90βˆ’50β€…β€ŠβŸΉβ€…β€Š2x=40β€…β€ŠβŸΉβ€…β€Šx=20(3x+y) - (x+y) = 90 - 50 \implies 2x = 40 \implies x = 20. Then y=30y = 30. Intersection point is (20,30)(20, 30). Step 4: Identify corner points of the feasible region: O(0,0),A(30,0),B(20,30),C(0,50)O(0,0), A(30,0), B(20,30), C(0,50). Step 5: Evaluate ZZ at each corner point:

  • At O(0,0):Z=4(0)+0=0O(0,0): Z = 4(0) + 0 = 0
  • At A(30,0):Z=4(30)+0=120A(30,0): Z = 4(30) + 0 = 120
  • At B(20,30):Z=4(20)+30=80+30=110B(20,30): Z = 4(20) + 30 = 80 + 30 = 110
  • At C(0,50):Z=4(0)+50=50C(0,50): Z = 4(0) + 50 = 50 Step 6: The maximum value of ZZ is 120120 at point (30,0)(30,0).

Explanation:

This is a bounded feasible region problem. We first identify the vertices formed by the intersection of the constraint lines and then test the objective function at each vertex to find the maximum.

Problem 2:

Minimize Z=3x+5yZ = 3x + 5y subject to x+3yβ‰₯3x + 3y \geq 3, x+yβ‰₯2x + y \geq 2, x,yβ‰₯0x, y \geq 0.

Solution:

Step 1: Boundary lines are x+3y=3x + 3y = 3 and x+y=2x + y = 2. Step 2: Find intercepts. For L1L_1: (3,0),(0,1)(3,0), (0,1). For L2L_2: (2,0),(0,2)(2,0), (0,2). Step 3: The intersection point: Subtracting (x+y=2)(x+y=2) from (x+3y=3)(x+3y=3) gives 2y=1β€…β€ŠβŸΉβ€…β€Šy=0.52y = 1 \implies y = 0.5. Then x=1.5x = 1.5. Intersection point is (1.5,0.5)(1.5, 0.5). Step 4: The feasible region is unbounded and lies above the lines. Corner points are A(3,0),B(1.5,0.5),C(0,2)A(3,0), B(1.5, 0.5), C(0,2). Step 5: Evaluate ZZ:

  • At A(3,0):Z=3(3)+5(0)=9A(3,0): Z = 3(3) + 5(0) = 9
  • At B(1.5,0.5):Z=3(1.5)+5(0.5)=4.5+2.5=7B(1.5, 0.5): Z = 3(1.5) + 5(0.5) = 4.5 + 2.5 = 7
  • At C(0,2):Z=3(0)+5(2)=10C(0,2): Z = 3(0) + 5(2) = 10 Step 6: Smallest value is 77. Since the region is unbounded, we check if 3x+5y<73x + 5y < 7 has any common points with the feasible region. Plotting 3x+5y=73x + 5y = 7, we see the open half-plane 3x+5y<73x + 5y < 7 has no points in common with the feasible region. Therefore, the minimum value is 77.

Explanation:

In an unbounded region, we find the candidate minimum at the corner points. To confirm it is truly the minimum, we must ensure that the region defined by Z<minΒ valueZ < \text{min value} does not overlap with the feasible region.