krit.club logo

Linear Programming - Mathematical formulation of L.P. problems

Grade 12CBSE

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

🔑Concepts

•

Decision Variables: These are the unknown quantities to be determined, usually denoted as xx and yy. They represent the choices we make, such as the number of units to produce or the amount of resources to use, and they must always be measurable quantities.

•

Objective Function: This is a linear function of the form Z=ax+byZ = ax + by, where aa and bb are constants. It represents the quantity we aim to either maximize (like profit) or minimize (like cost). Visually, the objective function can be imagined as a series of parallel lines moving across the coordinate plane to find the highest or lowest point within the allowed area.

•

Constraints: These are linear inequalities or equations that limit the values of the decision variables, such as ax+by≤cax + by \le c or ax+by≥cax + by \ge c. They represent restrictions like limited labor hours, machine time, or raw materials. On a graph, each constraint is represented by a straight line that divides the plane into two half-planes, one of which contains the points that satisfy the inequality.

•

Non-negativity Restrictions: These are the conditions x≥0x \ge 0 and y≥0y \ge 0. Since variables like production counts or food weights cannot be negative, these constraints ensure that our mathematical model remains physically realistic. Visually, these restrictions limit our entire problem to the first quadrant of the Cartesian coordinate system.

•

Feasible Region: This is the common region determined by all the constraints, including the non-negativity restrictions. It is the area where all inequalities overlap. If you were to shade the regions for each individual constraint, the Feasible Region would be the darkest area where every single shade intersects, typically forming a convex polygon.

•

Feasible Solutions: Every point (x,y)(x, y) that lies within or on the boundary of the feasible region is called a feasible solution. These points satisfy all given constraints simultaneously and are potential candidates for the optimal value.

•

Optimal Solution: This is any point (x,y)(x, y) in the feasible region that gives the maximum or minimum value for the objective function ZZ. According to the Corner Point Theorem, if an optimal solution exists, it will always occur at one of the vertices (corner points) of the feasible region polygon.

•

Mathematical Formulation: This is the process of translating a real-world word problem into a system of linear inequalities and an objective function. It involves identifying the variables, listing the goal (Maximize/Minimize), and cataloging all the limitations imposed by the environment.

📐Formulae

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

General Linear Constraint: aix+biy≤cia_i x + b_i y \le c_i or aix+biy≥cia_i x + b_i y \ge c_i

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

Standard L.P. Problem Form: Maximize/Minimize Z=c1x1+c2x2+...+cnxnZ = c_1x_1 + c_2x_2 + ... + c_nx_n subject to ∑j=1naijxj≤bi\sum_{j=1}^{n} a_{ij}x_j \le b_i and xj≥0x_j \ge 0

💡Examples

Problem 1:

A manufacturer produces two items, AA and BB. Each unit of AA requires 33 hours of machining and 11 hour of painting. Each unit of BB requires 22 hours of machining and 22 hours of painting. There are 1212 hours of machining time and 88 hours of painting time available. The profit on AA is Rs50Rs 50 and on BB is Rs40Rs 40. Formulate this as an LPP to maximize profit.

Solution:

Step 1: Define Decision Variables. Let xx be the number of units of item AA produced and yy be the number of units of item BB produced. Step 2: Formulate the Objective Function. The total profit Z=50x+40yZ = 50x + 40y. We want to maximize ZZ. Step 3: List the Constraints. Machining time: 3x+2y≤123x + 2y \le 12. Painting time: 1x+2y≤81x + 2y \le 8. Step 4: Non-negativity Constraints. Since we cannot produce negative items, x≥0,y≥0x \ge 0, y \ge 0. Final Formulation: Maximize Z=50x+40yZ = 50x + 40y subject to: 3x+2y≤123x + 2y \le 12 x+2y≤8x + 2y \le 8 x,y≥0x, y \ge 0

Explanation:

We identify the two variables based on the items being manufactured. The profit per item determines the objective function coefficients. Each resource (machining and painting) creates a separate linear inequality based on its total capacity.

Problem 2:

A dietician wishes to mix two types of foods F1F_1 and F2F_2 such that the mixture contains at least 88 units of vitamin A and 1010 units of vitamin C. Food F1F_1 contains 22 units/kg of vitamin A and 11 unit/kg of vitamin C. Food F2F_2 contains 11 unit/kg of vitamin A and 22 units/kg of vitamin C. The cost of F1F_1 is Rs50/kgRs 50/kg and F2F_2 is Rs70/kgRs 70/kg. Formulate the LPP to minimize the cost.

Solution:

Step 1: Define Decision Variables. Let xx be the quantity of F1F_1 in kg and yy be the quantity of F2F_2 in kg. Step 2: Formulate the Objective Function. Total cost Z=50x+70yZ = 50x + 70y. We want to minimize ZZ. Step 3: Vitamin Constraints. Vitamin A: 2x+1y≥82x + 1y \ge 8 (at least means ≥\ge). Vitamin C: 1x+2y≥101x + 2y \ge 10. Step 4: Non-negativity. x≥0,y≥0x \ge 0, y \ge 0. Final Formulation: Minimize Z=50x+70yZ = 50x + 70y subject to: 2x+y≥82x + y \ge 8 x+2y≥10x + 2y \ge 10 x,y≥0x, y \ge 0

Explanation:

This is a minimization problem where the constraints are of the 'at least' type, meaning the variables must satisfy a minimum requirement, resulting in ≥\ge inequalities. The feasible region for this problem will be unbounded in the first quadrant.