krit.club logo

Linear Programming - Graphical Method of Solution

Grade 12ICSE

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

🔑Concepts

•

The Objective Function is a linear expression Z=ax+byZ = ax + by that represents the quantity to be maximized (such as profit) or minimized (such as cost). Visually, this can be imagined as a series of parallel lines called 'isoprofit' or 'isocost' lines that move across the coordinate plane as the value of ZZ changes.

•

Decision Variables are the unknown quantities xx and yy that we need to determine. In the graphical method, these are plotted on the horizontal (x-axis) and vertical (y-axis) of a Cartesian plane.

•

Constraints are linear inequalities like a1x+b1y≤c1a_1x + b_1y \leq c_1 or a2x+b2y≥c2a_2x + b_2y \geq c_2 that represent the restrictions on resources. Geometrically, each constraint defines a half-plane on the graph, divided by the boundary line ax+by=cax + by = c.

•

Non-negativity Restrictions, expressed as x≥0x \geq 0 and y≥0y \geq 0, ensure that the solution remains in the first quadrant of the coordinate system. This represents the physical reality that production quantities cannot be negative.

•

The Feasible Region is the common region determined by all constraints including non-negativity restrictions. Visually, it is the shaded area where all inequality half-planes intersect. If the region is enclosed by boundary lines on all sides, it is called a 'Bounded' region; if it extends infinitely in any direction, it is 'Unbounded'.

•

A Feasible Solution is any point (x,y)(x, y) that lies within or on the boundary of the feasible region. Any point outside this shaded intersection is called an Infeasible Solution as it violates at least one constraint.

•

The Corner Point Theorem states that the optimal value (maximum or minimum) of the objective function, if it exists, must occur at one of the vertices (corners) of the feasible region. Visually, these are the intersection points of the boundary lines forming the polygon.

•

Multiple Optimal Solutions occur when the objective function line is parallel to one of the boundary lines of the feasible region. In this case, every point on that boundary line segment (between two corner points) provides the same maximum or minimum value.

📐Formulae

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

General form of Linear Constraints: 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

Equation of a boundary line: ax+by=cax + by = c

Slope-intercept form for plotting lines: y=−abx+cby = -\frac{a}{b}x + \frac{c}{b}

💡Examples

Problem 1:

Maximize Z=5x+3yZ = 5x + 3y subject to the constraints: 3x+5y≤153x + 5y \leq 15, 5x+2y≤105x + 2y \leq 10, and x,y≥0x, y \geq 0.

Solution:

Step 1: Convert inequalities to equations to find intercepts. For 3x+5y=153x + 5y = 15: When x=0,y=3  ⟹  (0,3)x=0, y=3 \implies (0,3); When y=0,x=5  ⟹  (5,0)y=0, x=5 \implies (5,0). For 5x+2y=105x + 2y = 10: When x=0,y=5  ⟹  (0,5)x=0, y=5 \implies (0,5); When y=0,x=2  ⟹  (2,0)y=0, x=2 \implies (2,0).

Step 2: Plot the lines and find the feasible region. Since both constraints are ≤\leq, the region is towards the origin. The non-negativity constraints x,y≥0x, y \geq 0 limit the region to the first quadrant.

Step 3: Find the intersection point of 3x+5y=153x + 5y = 15 and 5x+2y=105x + 2y = 10. Multiplying the first by 2 and the second by 5: 6x+10y=306x + 10y = 30 25x+10y=5025x + 10y = 50 Subtracting: 19x=20  ⟹  x=2019≈1.0519x = 20 \implies x = \frac{20}{19} \approx 1.05 Substitute xx: 3(2019)+5y=15  ⟹  5y=15−6019=22519  ⟹  y=4519≈2.373(\frac{20}{19}) + 5y = 15 \implies 5y = 15 - \frac{60}{19} = \frac{225}{19} \implies y = \frac{45}{19} \approx 2.37.

Step 4: Evaluate ZZ at corner points:

  • At O(0,0):Z=5(0)+3(0)=0O(0,0): Z = 5(0) + 3(0) = 0
  • At A(2,0):Z=5(2)+3(0)=10A(2,0): Z = 5(2) + 3(0) = 10
  • At B(2019,4519):Z=5(2019)+3(4519)=100+13519=23519≈12.37B(\frac{20}{19}, \frac{45}{19}): Z = 5(\frac{20}{19}) + 3(\frac{45}{19}) = \frac{100+135}{19} = \frac{235}{19} \approx 12.37
  • At C(0,3):Z=5(0)+3(3)=9C(0,3): Z = 5(0) + 3(3) = 9

Maximum value of ZZ is 23519\frac{235}{19} at x=2019,y=4519x = \frac{20}{19}, y = \frac{45}{19}.

Explanation:

We first identify the boundary lines and shade the region satisfied by all inequalities. The feasible region is a quadrilateral with vertices (0,0),(2,0),(2019,4519),(0,0), (2,0), (\frac{20}{19}, \frac{45}{19}), and (0,3)(0,3). We then test the objective function at each vertex to find the maximum value.

Problem 2:

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

Solution:

Step 1: Find intercepts for boundary lines. Line 1: x+2y=10  ⟹  (10,0)x + 2y = 10 \implies (10,0) and (0,5)(0,5). Line 2: 3x+4y=24  ⟹  (8,0)3x + 4y = 24 \implies (8,0) and (0,6)(0,6).

Step 2: Identify the Feasible Region. Since constraints are ≥\geq, the region is 'unbounded' and away from the origin (above the lines).

Step 3: Find the corner points of the unbounded region.

  • Intersection of x+2y=10x + 2y = 10 and the y-axis: (0,6)(0,6) (since (0,6)(0,6) is higher than (0,5)(0,5)).
  • Intersection of the two lines: 3x+4y=243x + 4y = 24 2x+4y=202x + 4y = 20 (Line 1 multiplied by 2) Subtracting: x=4x = 4. Substituting xx: 4+2y=10  ⟹  2y=6  ⟹  y=34 + 2y = 10 \implies 2y = 6 \implies y = 3. Corner point: (4,3)(4,3).
  • Intersection of 3x+4y=243x + 4y = 24 and the x-axis: (10,0)(10,0) (since (10,0)(10,0) is further right than (8,0)(8,0)).

Step 4: Evaluate ZZ at corner points:

  • At (0,6):Z=2(0)+10(6)=60(0,6): Z = 2(0) + 10(6) = 60
  • At (4,3):Z=2(4)+10(3)=38(4,3): Z = 2(4) + 10(3) = 38
  • At (10,0):Z=2(10)+10(0)=20(10,0): Z = 2(10) + 10(0) = 20

Minimum value of ZZ is 2020 at (10,0)(10,0).

Explanation:

In this minimization problem with ≥\geq constraints, the feasible region is unbounded in the first quadrant. The corner points are (0,6),(4,3),(0,6), (4,3), and (10,0)(10,0). After testing these points, we find the minimum value at (10,0)(10,0).