krit.club logo

Linear Programming - Constraints, Objective Function, Optimization

Grade 12ICSE

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

🔑Concepts

•

Decision Variables: These are the unknown quantities, usually denoted as xx and yy, which represent the variables to be determined (e.g., number of units to produce). Visually, these are represented on the horizontal and vertical axes of a 2D Cartesian plane, restricting our focus to the first quadrant where x≥0x \geq 0 and y≥0y \geq 0.

•

Objective Function: A linear function Z=ax+byZ = ax + by that represents the quantity to be optimized (either maximized for profit or minimized for cost). Visually, this can be imagined as a series of parallel lines, known as 'iso-profit' or 'iso-cost' lines, that move across the graph as the value of ZZ changes.

•

Linear Constraints: These are systems of linear inequalities like ax+by≤cax + by \leq c or ax+by≥cax + by \geq c that restrict the values of decision variables based on available resources. On a graph, each constraint is represented by a straight line, and the inequality determines which 'half-plane' (the side of the line) satisfies the condition, indicated by shading.

•

Feasible Region: The common region or set of points that satisfies all given constraints simultaneously, including the non-negativity constraints. It is visually represented as the overlapping shaded area of all constraint half-planes. This region is always a convex polygon.

•

Bounded vs. Unbounded Regions: A feasible region is 'Bounded' if it is a closed polygon that can be enclosed within a circle; in this case, the objective function will have both a maximum and a minimum value. If the region extends infinitely in any direction, it is 'Unbounded,' and a maximum or minimum value might not exist.

•

Corner Point Theorem: A fundamental principle stating that the optimal value (maximum or minimum) 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.

•

Optimal Solution: Any point in the feasible region that results in the maximum or minimum value of the objective function. While the optimal value is unique, there may be multiple optimal points if the objective function line is parallel to one of the boundary lines of the feasible region.

📐Formulae

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

Linear Inequality Constraint: aix+biy≤cia_i x + b_i y \leq c_i or aix+biy≥cia_i x + b_i y \geq c_i

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

Slope of the Objective Function Line: m=−abm = -\frac{a}{b}

Intersection Point of two lines a1x+b1y=c1a_1x + b_1y = c_1 and a2x+b2y=c2a_2x + b_2y = c_2 found using simultaneous equations.

💡Examples

Problem 1:

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

Solution:

  1. Identify the Boundary Lines: \n- L1:x+y=6L_1: x + y = 6 (passes through (0,6)(0,6) and (6,0)(6,0)) \n- L2:2x+y=8L_2: 2x + y = 8 (passes through (0,8)(0,8) and (4,0)(4,0)) \n\n2. Find the Intersection Point of L1L_1 and L2L_2: \nSubtract x+y=6x + y = 6 from 2x+y=82x + y = 8: \n(2x−x)+(y−y)=8−6  ⟹  x=2(2x - x) + (y - y) = 8 - 6 \implies x = 2. \nSubstitute x=2x = 2 into x+y=6  ⟹  2+y=6  ⟹  y=4x + y = 6 \implies 2 + y = 6 \implies y = 4. \nIntersection Point: (2,4)(2, 4). \n\n3. Determine the Feasible Region: \nSince both constraints are ≤\leq, the region is toward the origin. The vertices of the bounded feasible region are: \n- O(0,0)O(0, 0) \n- A(4,0)A(4, 0) (from L2L_2) \n- B(2,4)B(2, 4) (Intersection) \n- C(0,6)C(0, 6) (from L1L_1) \n\n4. Evaluate the Objective Function Z=5x+3yZ = 5x + 3y at each vertex: \n- At O(0,0):Z=5(0)+3(0)=0O(0, 0): Z = 5(0) + 3(0) = 0 \n- At A(4,0):Z=5(4)+3(0)=20A(4, 0): Z = 5(4) + 3(0) = 20 \n- At B(2,4):Z=5(2)+3(4)=10+12=22B(2, 4): Z = 5(2) + 3(4) = 10 + 12 = 22 \n- At C(0,6):Z=5(0)+3(6)=18C(0, 6): Z = 5(0) + 3(6) = 18 \n\n5. Conclusion: \nThe maximum value of ZZ is 2222, which occurs at the point (2,4)(2, 4).

Explanation:

We use the Corner Point Method by first sketching the linear equations on a graph to find the feasible region in the first quadrant. By calculating ZZ at every vertex of this region, we identify the highest value as the optimal solution.

Problem 2:

Minimize Z=200x+500yZ = 200x + 500y subject to: x+2y≥10x + 2y \geq 10, 3x+4y≥243x + 4y \geq 24, x≥0,y≥0x \geq 0, y \geq 0.

Solution:

  1. Identify the Boundary Lines: \n- L1:x+2y=10L_1: x + 2y = 10 (Intersects axes at (10,0)(10,0) and (0,5)(0,5)) \n- L2:3x+4y=24L_2: 3x + 4y = 24 (Intersects axes at (8,0)(8,0) and (0,6)(0,6)) \n\n2. Find the Intersection Point: \nMultiply L1L_1 by 22: 2x+4y=202x + 4y = 20. \nSubtract this from L2L_2: (3x−2x)+(4y−4y)=24−20  ⟹  x=4(3x - 2x) + (4y - 4y) = 24 - 20 \implies x = 4. \nSubstitute x=4x = 4 into L1L_1: 4+2y=10  ⟹  2y=6  ⟹  y=34 + 2y = 10 \implies 2y = 6 \implies y = 3. \nIntersection Point: (4,3)(4, 3). \n\n3. Determine the Feasible Region: \nSince both constraints are ≥\geq, the region is 'Unbounded' and away from the origin. Vertices are: \n- A(10,0)A(10, 0) \n- B(4,3)B(4, 3) \n- C(0,6)C(0, 6) \n\n4. Evaluate Z=200x+500yZ = 200x + 500y: \n- At A(10,0):Z=200(10)+0=2000A(10, 0): Z = 200(10) + 0 = 2000 \n- At B(4,3):Z=200(4)+500(3)=800+1500=2300B(4, 3): Z = 200(4) + 500(3) = 800 + 1500 = 2300 \n- At C(0,6):Z=0+500(6)=3000C(0, 6): Z = 0 + 500(6) = 3000 \n\n5. Conclusion: \nThe minimum value of ZZ is 20002000 at the point (10,0)(10, 0).

Explanation:

For minimization with ≥\geq constraints, the feasible region is typically unbounded away from the origin. We identify the 'outer' corner points and evaluate the cost function to find the minimum value.