krit.club logo

Linear Programming - Graphical method of solution for problems in two variables

Grade 12CBSE

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

🔑Concepts

•

Linear Objective Function: This is the linear function Z=ax+byZ = ax + by, where aa and bb are constants, which needs to be maximized or minimized according to the problem requirements. Visually, this represents a family of parallel lines on the coordinate plane.

•

Linear Constraints: These are linear inequalities or equations such as a1x+b1y≤c1a_1x + b_1y \leq c_1 or a2x+b2y≥c2a_2x + b_2y \geq c_2 that limit the values of the decision variables. Each inequality defines a half-plane on the graph, and the boundary is the line ax+by=cax + by = c.

•

Non-negativity Restrictions: In most practical linear programming problems, variables xx and yy represent physical quantities, hence x≥0x \geq 0 and y≥0y \geq 0. Visually, these constraints restrict the solution space to the first quadrant of the Cartesian plane.

•

Feasible Region: This is the common region determined by all the constraints including non-negativity restrictions. It is visually represented as a shaded convex polygonal region. Every point within or on the boundary of this region represents a 'feasible solution' that satisfies all constraints.

•

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

•

Bounded and Unbounded Regions: A feasible region is 'bounded' if it can be enclosed within a circle; otherwise, it is 'unbounded'. For a bounded region, both maximum and minimum values of ZZ always exist. If the region is unbounded, a maximum or minimum value may or may not exist.

•

Optimal Solution: This is any point (x,y)(x, y) in the feasible region that provides the maximum (or minimum) value for the objective function ZZ. There can be a unique optimal solution at one vertex, or infinitely many solutions if the objective function line is parallel to one of the boundary segments of the feasible region.

📐Formulae

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

Standard Linear Constraint: aix+biy≤ci or aix+biy≥cia_i x + b_i y \leq c_i \text{ or } a_i x + b_i y \geq c_i

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

Condition for Multiple Optimal Solutions: If two corner points (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) give the same maximum/minimum value, then every point on the line segment joining them is also an optimal solution.

💡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 the intercepts for L1L_1: (50,0)(50, 0) and (0,50)(0, 50). Find the intercepts for L2L_2: (30,0)(30, 0) and (0,90)(0, 90). Step 3: Solve L1L_1 and L2L_2 simultaneously to find the intersection point: Subtracting x+y=50x + y = 50 from 3x+y=903x + y = 90 gives 2x=40  ⟹  x=202x = 40 \implies x = 20. Substituting into L1L_1 gives 20+y=50  ⟹  y=3020 + y = 50 \implies y = 30. The intersection is B(20,30)B(20, 30). Step 4: Identify the feasible region (bounded by the axes and these lines in the first quadrant). The corner points are O(0,0)O(0, 0), A(30,0)A(30, 0), B(20,30)B(20, 30), and C(0,50)C(0, 50). Step 5: Evaluate Z=4x+yZ = 4x + y 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=110B(20, 30): Z = 4(20) + 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 the point (30,0)(30, 0).

Explanation:

We use the graphical method to find the intersection of the constraints. Since the region is bounded, we evaluate the objective function at all vertices of the shaded polygon to find the highest value.

Problem 2:

Minimize Z=20x+10yZ = 20x + 10y subject to: x+2y≥40x + 2y \geq 40, 3x+y≥303x + y \geq 30, x,y≥0x, y \geq 0.

Solution:

Step 1: Boundary lines are L1:x+2y=40L_1: x + 2y = 40 (intercepts (40,0),(0,20)(40, 0), (0, 20)) and L2:3x+y=30L_2: 3x + y = 30 (intercepts (10,0),(0,30)(10, 0), (0, 30)). Step 2: Find intersection of L1L_1 and L2L_2: Multiply L1L_1 by 3  ⟹  3x+6y=1203 \implies 3x + 6y = 120. Subtract L2L_2 from this: (3x+6y)−(3x+y)=120−30  ⟹  5y=90  ⟹  y=18(3x + 6y) - (3x + y) = 120 - 30 \implies 5y = 90 \implies y = 18. Then x+2(18)=40  ⟹  x=4x + 2(18) = 40 \implies x = 4. Intersection is (4,18)(4, 18). Step 3: The feasible region is unbounded and lies above the lines L1L_1 and L2L_2. The corner points are A(40,0)A(40, 0), B(4,18)B(4, 18), and C(0,30)C(0, 30). Step 4: Evaluate Z=20x+10yZ = 20x + 10y:

  • At A(40,0):Z=20(40)+0=800A(40, 0): Z = 20(40) + 0 = 800
  • At B(4,18):Z=20(4)+10(18)=80+180=260B(4, 18): Z = 20(4) + 10(18) = 80 + 180 = 260
  • At C(0,30):Z=20(0)+10(30)=300C(0, 30): Z = 20(0) + 10(30) = 300 Step 5: The minimum value is 260260 at (4,18)(4, 18). (Since the region is unbounded, we verify if 20x+10y<26020x + 10y < 260 has points in common with the feasible region; it does not, so 260 is the actual minimum).

Explanation:

This is a minimization problem with an unbounded feasible region extending away from the origin. The corner point with the smallest ZZ value is the candidate for the minimum.