krit.club logo

Linear Programming - Mathematical Formulation of L.P. Problems

Grade 12ICSE

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

🔑Concepts

•

Linear Programming Problem (LPP) is a mathematical technique used to find the optimal value (maximum or minimum) of a linear function, known as the objective function, subject to various linear constraints. It is widely used in resource allocation, production planning, and transport logistics.

•

Decision Variables are the unknown quantities that we need to determine to solve the problem, usually denoted as xx and yy. These variables represent the quantities of products to be produced or resources to be used, and they are the coordinates plotted on the xx-axis and yy-axis of a 2D graph.

•

The Objective Function is a linear mathematical expression, typically denoted as Z=ax+byZ = ax + by, which represents the quantity we want to maximize (like profit) or minimize (like cost). Visually, this function can be imagined as a series of parallel 'iso-profit' or 'iso-cost' lines moving across the feasible region.

•

Constraints are a set of linear inequalities or equations that limit the values of the decision variables, such as a1x+b1y≤c1a_1x + b_1y \le c_1. On a graph, each constraint is represented by a straight line, and the inequality determines which side of the line (a half-plane) contains the valid points. For example, x≤kx \le k is a vertical line where the valid region is to the left.

•

Non-negativity Restrictions are constraints that ensure the decision variables are always zero or positive (x≥0,y≥0x \ge 0, y \ge 0). Geometrically, these restrictions confine the problem to the first quadrant of the Cartesian plane, meaning we only look at the upper-right section of the graph.

•

The Feasible Region is the common area on a graph where all the given constraints, including non-negativity restrictions, are satisfied simultaneously. It usually appears as a shaded convex polygon. If the region is enclosed on all sides, it is called a 'Bounded Feasible Region'; if it extends infinitely in one direction, it is 'Unbounded'.

•

Feasible Solutions are any points (x,y)(x, y) that lie within or on the boundary of the feasible region. An Optimal Solution is the specific feasible solution (a point in the shaded region) that gives the maximum or minimum value for the objective function ZZ.

•

The Corner Point Method states that if an optimal solution exists, it must occur at one of the vertices (corners) of the feasible region. Visually, you identify the 'corners' where constraint lines intersect and test each of these coordinates in the objective function to find the best result.

📐Formulae

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

General Linear Constraints: aix+bjy≤cka_i x + b_j y \le c_k or aix+bjy≥cka_i x + b_j y \ge c_k

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

General Form of LPP: Maximize/Minimize Z=c1x+c2yZ = c_1x + c_2y, subject to a11x+a12y≤b1,a21x+a22y≤b2,…,x,y≥0a_{11}x + a_{12}y \le b_1, a_{21}x + a_{22}y \le b_2, \dots, x, y \ge 0

💡Examples

Problem 1:

A furniture manufacturer makes two types of products: chairs and tables. Processing a chair requires 2 hours on Machine A and 6 hours on Machine B. Processing a table requires 4 hours on Machine A and 2 hours on Machine B. Machine A is available for at most 16 hours, and Machine B for at most 30 hours. The profit on a chair is 250andonatableis250 and on a table is 150. Formulate this as a Linear Programming Problem to maximize profit.

Solution:

  1. Define Decision Variables: Let xx be the number of chairs and yy be the number of tables produced.
  2. Objective Function: We want to maximize the total profit ZZ. Since profit per chair is 250andpertableis250 and per table is 150, the function is: Maximize Z=250x+150yZ = 250x + 150y
  3. Constraints:
  • Machine A constraint: 2x+4y≤162x + 4y \le 16 (hours used cannot exceed 16)
  • Machine B constraint: 6x+2y≤306x + 2y \le 30 (hours used cannot exceed 30)
  • Non-negativity constraints: x≥0,y≥0x \ge 0, y \ge 0 (cannot produce negative furniture)
  1. Final Formulation: Maximize Z=250x+150yZ = 250x + 150y subject to: 2x+4y≤162x + 4y \le 16 6x+2y≤306x + 2y \le 30 x,y≥0x, y \ge 0

Explanation:

The problem is a maximization type. We first identified the variables representing the items to be produced. Then, we created the objective function based on unit profit. Finally, we translated the resource limits (machine hours) into linear inequalities.

Problem 2:

A diet is to contain at least 20 units of Vitamin A and at least 15 units of Vitamin B. Two foods, F1F_1 and F2F_2, are available. F1F_1 contains 5 units of Vitamin A and 1 unit of Vitamin B per gram. F2F_2 contains 2 units of Vitamin A and 3 units of Vitamin B per gram. The cost of F1F_1 is 5pergramand5 per gram and F_2isis8 per gram. Formulate the LPP to minimize the cost of the diet.

Solution:

  1. Define Decision Variables: Let xx be the quantity of food F1F_1 in grams and yy be the quantity of food F2F_2 in grams.
  2. Objective Function: We want to minimize the total cost ZZ. Minimize Z=5x+8yZ = 5x + 8y
  3. Constraints:
  • Vitamin A requirement: 5x+2y≥205x + 2y \ge 20 (must have at least 20 units)
  • Vitamin B requirement: 1x+3y≥151x + 3y \ge 15 (must have at least 15 units)
  • Non-negativity: x≥0,y≥0x \ge 0, y \ge 0
  1. Final Formulation: Minimize Z=5x+8yZ = 5x + 8y subject to: 5x+2y≥205x + 2y \ge 20 x+3y≥15x + 3y \ge 15 x,y≥0x, y \ge 0

Explanation:

This is a minimization problem concerning cost and nutritional requirements. Because the problem states 'at least', the inequality signs are ≥\ge. The variables represent the weights of food items.