krit.club logo

Linear Programming - Feasible and Infeasible Regions and Solutions

Grade 12ICSE

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

🔑Concepts

•

Decision Variables: These are the unknown quantities to be determined, usually denoted as xx and yy. In Grade 12 problems, these must be non-negative (x≥0,y≥0x \geq 0, y \geq 0), which visually restricts the feasible region to the first quadrant of the Cartesian coordinate system.

•

Objective Function: A linear mathematical expression of the form Z=ax+byZ = ax + by that needs to be either maximized (e.g., profit) or minimized (e.g., cost). Visually, this function can be represented as a series of parallel lines called 'iso-profit' or 'iso-cost' lines that move across the feasible region.

•

Linear Constraints: These are a set of linear inequalities such as a1x+b1y≤c1a_1x + b_1y \leq c_1 or a2x+b2y≥c2a_2x + b_2y \geq c_2 that represent restrictions on resources. Visually, each inequality defines a 'half-plane' on one side of a boundary line. For ≤\leq, the region usually includes the origin if the constant is positive; for ≥\geq, it usually excludes the origin.

•

Feasible Region: This is the common area or set of points that satisfies all the given linear constraints and non-negativity conditions simultaneously. Visually, it is the overlapping shaded area of all half-planes. If the area is enclosed on all sides by constraint lines, it is called a 'Bounded' region; if it extends infinitely in any direction, it is 'Unbounded'.

•

Feasible and Infeasible Solutions: A 'Feasible Solution' is any point (x,y)(x, y) that lies within or on the boundary of the feasible region. Conversely, an 'Infeasible Solution' is any point outside this region that violates at least one constraint. Visually, any point in the unshaded part of the graph is an infeasible solution.

•

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

•

Optimal Solution: The specific feasible solution (x,y)(x, y) that results in the highest (for maximization) or lowest (for minimization) value of the objective function ZZ. If two corner points yield the same optimal value, then every point on the line segment joining these two points is also an optimal solution.

📐Formulae

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

General Linear Constraint: aix+biy≤cia_ix + b_iy \leq c_i or aix+biy≥cia_ix + b_iy \geq c_i

Non-negativity Constraints: x≥0,y≥0x \geq 0, y \geq 0

Slope of the Boundary Line ax+by=cax + by = c: m=−abm = -\frac{a}{b}

Intercept Form of a Line: xxint+yyint=1\frac{x}{x_{int}} + \frac{y}{y_{int}} = 1

💡Examples

Problem 1:

Maximize Z=4x+6yZ = 4x + 6y subject to the constraints: x+2y≤8x + 2y \leq 8, x+y≤5x + y \leq 5, and x,y≥0x, y \geq 0.

Solution:

Step 1: Convert inequalities to equations to find boundary lines: L1:x+2y=8L_1: x + 2y = 8 and L2:x+y=5L_2: x + y = 5. Step 2: Find intercepts for L1L_1: If x=0,y=4x=0, y=4; if y=0,x=8y=0, x=8. Points: (0,4),(8,0)(0, 4), (8, 0). Step 3: Find intercepts for L2L_2: If x=0,y=5x=0, y=5; if y=0,x=5y=0, x=5. Points: (0,5),(5,0)(0, 5), (5, 0). Step 4: Find the intersection point of L1L_1 and L2L_2: Subtracting x+y=5x + y = 5 from x+2y=8x + 2y = 8 gives y=3y = 3. Substituting y=3y=3 into x+y=5x + y = 5 gives x=2x = 2. Intersection point: (2,3)(2, 3). Step 5: Identify the corner points of the feasible region (shaded toward the origin as both are ≤\leq): O(0,0)O(0, 0), A(5,0)A(5, 0), B(2,3)B(2, 3), and C(0,4)C(0, 4). Step 6: Evaluate ZZ at each corner point:

  • At (0,0):Z=4(0)+6(0)=0(0, 0): Z = 4(0) + 6(0) = 0
  • At (5,0):Z=4(5)+6(0)=20(5, 0): Z = 4(5) + 6(0) = 20
  • At (2,3):Z=4(2)+6(3)=8+18=26(2, 3): Z = 4(2) + 6(3) = 8 + 18 = 26
  • At (0,4):Z=4(0)+6(4)=24(0, 4): Z = 4(0) + 6(4) = 24

Max value is 2626 at point (2,3)(2, 3).

Explanation:

We first identify the feasible region by plotting the lines and checking the origin (0,0)(0,0) against the inequalities. Since both constraints are ≤\leq, the region is bounded and close to the origin. We then use the Corner Point Method, calculating the objective value at every vertex of the polygon to find the maximum.

Problem 2:

Determine the feasible region for 2x+y≥62x + y \geq 6, x+2y≥8x + 2y \geq 8, x,y≥0x, y \geq 0 and find the minimum value of Z=5x+7yZ = 5x + 7y.

Solution:

Step 1: Boundary lines: L1:2x+y=6L_1: 2x + y = 6 (Intercepts: (3,0),(0,6)(3,0), (0,6)) and L2:x+2y=8L_2: x + 2y = 8 (Intercepts: (8,0),(0,4)(8,0), (0,4)). Step 2: Since constraints are ≥\geq, the feasible region is 'Unbounded' and away from the origin. Step 3: Intersection of L1L_1 and L2L_2: Multiply L1L_1 by 2⇒4x+2y=122 \Rightarrow 4x + 2y = 12. Subtract L2⇒3x=4⇒x=43L_2 \Rightarrow 3x = 4 \Rightarrow x = \frac{4}{3}. Solve for yy: 43+2y=8⇒2y=203⇒y=103\frac{4}{3} + 2y = 8 \Rightarrow 2y = \frac{20}{3} \Rightarrow y = \frac{10}{3}. Intersection point: (43,103)(\frac{4}{3}, \frac{10}{3}). Step 4: Corner points of the unbounded region: A(8,0)A(8, 0), B(43,103)B(\frac{4}{3}, \frac{10}{3}), and C(0,6)C(0, 6). Step 5: Evaluate ZZ:

  • At (8,0):Z=5(8)+7(0)=40(8, 0): Z = 5(8) + 7(0) = 40
  • At (43,103):Z=5(43)+7(103)=20+703=903=30(\frac{4}{3}, \frac{10}{3}): Z = 5(\frac{4}{3}) + 7(\frac{10}{3}) = \frac{20+70}{3} = \frac{90}{3} = 30
  • At (0,6):Z=5(0)+7(6)=42(0, 6): Z = 5(0) + 7(6) = 42

Minimum value is 3030 at point (43,103)(\frac{4}{3}, \frac{10}{3}).

Explanation:

This problem involves an 'Unbounded' feasible region because the constraints are 'greater than or equal to'. The region extends infinitely away from the origin in the first quadrant. However, the minimum value still occurs at one of the corner points of the boundary.