krit.club logo

Linear Programming - Optimal feasible solutions

Grade 12CBSE

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

🔑Concepts

•

The Objective Function is a linear function of the form Z=ax+byZ = ax + by, where aa and bb are constants, which needs to be maximized or minimized. Visually, this function can be represented as a series of parallel lines (isoprofit or isocost lines) that move across the coordinate plane as the value of ZZ changes.

•

Constraints are linear inequalities or equations like a1x+b1y≤c1a_1x + b_1y \le c_1 that restrict the values of the variables. Geometrically, each inequality represents a half-plane, and the boundaries of these half-planes are straight lines.

•

The Feasible Region is the common region determined by all constraints including non-negative constraints x,y≥0x, y \ge 0. It is visually represented as a shaded convex polygonal area on a graph where all conditions are simultaneously satisfied.

•

Feasible Solutions are the points within or on the boundary of the feasible region. Any point (x,y)(x, y) in this shaded region represents a possible solution that satisfies all the given restrictions.

•

The Corner Point Method (Optimal Test) states that the optimal (maximum or minimum) value of the objective function ZZ must occur at one of the vertices (corner points) of the feasible region. Visually, these are the 'sharp turns' or intersections of the boundary lines of the shaded polygon.

•

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. In an unbounded region, a maximum or minimum may not exist; if it does, additional tests are required by plotting the inequality ax+by>Max + by > M or ax+by<max + by < m.

•

Multiple Optimal Solutions occur if two corner points produce the same maximum or minimum value. In this case, every point on the line segment joining these two vertices is also an optimal solution, meaning there are infinitely many solutions.

📐Formulae

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

General Linear Constraint: aix+biy≤cia_ix + b_iy \le c_i or aix+biy≥cia_ix + b_iy \ge c_i

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

Optimal Value Condition: Zmax=max⁡{Z(P1),Z(P2),...,Z(Pn)}Z_{max} = \max\{Z(P_1), Z(P_2), ..., Z(P_n)\} where PiP_i are corner points.

Unbounded Region Condition for Minimum: ax+by<max + by < m has no common point with the feasible region, where mm is the smallest value at corner points.

💡Examples

Problem 1:

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

Solution:

Step 1: Convert inequalities to equations to find boundary lines: L1:x+y=50L_1: x + y = 50, L2:3x+y=90L_2: 3x + y = 90.\nStep 2: Find intercepts for L1L_1: (0,50)(0, 50) and (50,0)(50, 0). For L2L_2: (0,90)(0, 90) and (30,0)(30, 0).\nStep 3: Identify the feasible region by testing (0,0)(0,0). Since 0+0≤500+0 \le 50 and 0+0≤900+0 \le 90 are true, the region is towards the origin.\nStep 4: Find the corner points of the shaded region: O(0,0)O(0, 0), A(30,0)A(30, 0), B(20,30)B(20, 30) (intersection of L1L_1 and L2L_2), and C(0,50)C(0, 50).\nStep 5: Evaluate ZZ at each corner point:\n- At O(0,0):Z=4(0)+0=0O(0, 0): Z = 4(0) + 0 = 0\n- At A(30,0):Z=4(30)+0=120A(30, 0): Z = 4(30) + 0 = 120\n- At B(20,30):Z=4(20)+30=110B(20, 30): Z = 4(20) + 30 = 110\n- At C(0,50):Z=4(0)+50=50C(0, 50): Z = 4(0) + 50 = 50\nStep 6: The maximum value is 120120 at point (30,0)(30, 0).

Explanation:

This is a standard maximization problem on a bounded feasible region. We use the Corner Point Method to evaluate the objective function at all vertices of the polygon formed by the constraints.

Problem 2:

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

Solution:

Step 1: Boundary lines are x+2y=10x + 2y = 10 (intercepts (10,0),(0,5)(10, 0), (0, 5)) and 3x+4y=243x + 4y = 24 (intercepts (8,0),(0,6)(8, 0), (0, 6)).\nStep 2: Plot the lines. For x+2y≥10x + 2y \ge 10, the region is away from the origin. For 3x+4y≤243x + 4y \le 24, the region is towards the origin.\nStep 3: Identify corner points of the feasible region: A(4,3)A(4, 3), B(0,5)B(0, 5), C(0,6)C(0, 6). Note: (4,3)(4,3) is the intersection of x+2y=10x+2y=10 and 3x+4y=243x+4y=24.\nStep 4: Evaluate ZZ:\n- At A(4,3):Z=200(4)+500(3)=800+1500=2300A(4, 3): Z = 200(4) + 500(3) = 800 + 1500 = 2300\n- At B(0,5):Z=200(0)+500(5)=2500B(0, 5): Z = 200(0) + 500(5) = 2500\n- At C(0,6):Z=200(0)+500(6)=3000C(0, 6): Z = 200(0) + 500(6) = 3000\nStep 5: The minimum value is 23002300 at x=4,y=3x = 4, y = 3.

Explanation:

In this minimization problem, we identify the corner points of the feasible region (a triangle in this case) and select the vertex that yields the lowest ZZ value.