krit.club logo

Linear Programming - Introduction, related terminology (constraints, objective function, optimization)

Grade 12CBSE

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

🔑Concepts

•

Linear Programming Problem (LPP): A mathematical method to find the optimal value (maximum or minimum) of a linear function, known as the objective function, subject to a set of linear constraints. Visually, it involves finding a specific point within a geometric region on a Cartesian plane that produces the best result.

•

Objective Function: The linear function Z=ax+byZ = ax + by that is intended to be maximized (e.g., profit) or minimized (e.g., cost). Visually, this can be imagined as a 'moving line' whose position is adjusted across the graph to find the extreme feasible point.

•

Constraints: These are linear inequalities or equations like a1x+b1y≤c1a_1x + b_1y \le c_1 that represent the restrictions on the decision variables. Geometrically, each constraint represents a half-plane, and the boundaries are straight lines.

•

Feasible Region: The common region determined by all the given constraints, including the non-negativity constraints x≥0,y≥0x \ge 0, y \ge 0. Visually, this is the overlapping shaded area on a graph where all inequalities are satisfied simultaneously. If the area is enclosed like a polygon, it is 'bounded'; if it extends infinitely in any direction, it is 'unbounded'.

•

Corner Point Method: A fundamental theorem stating that the optimal value of the objective function must occur at one of the vertices (corner points) of the feasible region. Visually, these points are the intersections of the boundary lines of the feasible region.

•

Feasible and Infeasible Solutions: Points within or on the boundary of the feasible region are called feasible solutions. Any point outside this shaded area is an infeasible solution and cannot be considered for optimization.

•

Non-negativity Constraints: The conditions x≥0x \ge 0 and y≥0y \ge 0 which restrict the solution to the first quadrant of the graph. Visually, this means the feasible region will always be located to the right of the y-axis and above the x-axis.

•

Optimal Solution: Any point in the feasible region that provides the maximum or minimum value of the objective function. Geometrically, if the objective function line is moved as far as possible while still touching the feasible region, the last point(s) it touches are the optimal solutions.

📐Formulae

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

General Linear Constraint: aix+biy≤ci or aix+biy≥cia_i x + b_i y \le c_i \text{ or } a_i x + b_i y \ge c_i

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

Condition for Bounded Region: ZmaxZ_{max} and ZminZ_{min} exist at corner points.

Condition for Unbounded Region: If the region is unbounded, a maximum or minimum may or may not exist.

💡Examples

Problem 1:

Maximize Z=3x+4yZ = 3x + 4y subject to the constraints: x+y≤4x + y \le 4, x≥0x \ge 0, y≥0y \ge 0.

Solution:

  1. Convert the inequality to an equation: x+y=4x + y = 4. The line passes through (4,0)(4, 0) and (0,4)(0, 4).
  2. Since the constraint is x+y≤4x + y \le 4, the feasible region is the area below the line x+y=4x + y = 4 in the first quadrant (due to x,y≥0x, y \ge 0).
  3. The corner points of the feasible region are O(0,0)O(0, 0), A(4,0)A(4, 0), and B(0,4)B(0, 4).
  4. Evaluate ZZ at each corner point:
  • At O(0,0):Z=3(0)+4(0)=0O(0, 0): Z = 3(0) + 4(0) = 0
  • At A(4,0):Z=3(4)+4(0)=12A(4, 0): Z = 3(4) + 4(0) = 12
  • At B(0,4):Z=3(0)+4(4)=16B(0, 4): Z = 3(0) + 4(4) = 16
  1. Comparing the values, the maximum value of ZZ is 1616 at the point (0,4)(0, 4).

Explanation:

The problem asks for the maximum value of a linear function. By plotting the boundary and identifying the vertices of the resulting triangle (feasible region), we test each vertex in the objective function to find the highest value.

Problem 2:

Minimize Z=5x+10yZ = 5x + 10y subject to: x+2y≥120x + 2y \ge 120, x+y≥60x + y \ge 60, x,y≥0x, y \ge 0.

Solution:

  1. Plot the boundary lines: L1:x+2y=120L_1: x + 2y = 120 (intercepts (120,0),(0,60)(120, 0), (0, 60)) and L2:x+y=60L_2: x + y = 60 (intercepts (60,0),(0,60)(60, 0), (0, 60)).
  2. The constraints are 'greater than or equal to', so the feasible region is the area above both lines in the first quadrant (unbounded region).
  3. Find the corner points of the feasible region: A(120,0)A(120, 0) and B(0,60)B(0, 60). Note that the intersection of the two lines is at (0,60)(0, 60).
  4. Evaluate ZZ at the corner points:
  • At A(120,0):Z=5(120)+10(0)=600A(120, 0): Z = 5(120) + 10(0) = 600
  • At B(0,60):Z=5(0)+10(60)=600B(0, 60): Z = 5(0) + 10(60) = 600
  1. Since the value is the same at both points, any point on the line segment joining (120,0)(120, 0) and (0,60)(0, 60) that satisfies the constraints will give the minimum value of 600600.

Explanation:

This example demonstrates a minimization problem with an unbounded feasible region. It also shows a special case where multiple points (an entire line segment) provide the same optimal value.