krit.club logo

Linear Programming - Linear Programming Problem and its Mathematical Formulation

Grade 12CBSE

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

🔑Concepts

•

Linear Programming Problem (LPP) is a mathematical method for determining the best outcome (such as maximum profit or minimum cost) in a model whose requirements are represented by linear relationships.

•

The function to be maximized or minimized is called the Objective Function, usually denoted by Z=ax+byZ = ax + by.

•

The variables xx and yy in the objective function are called Decision Variables.

•

The limitations or restrictions on the decision variables are called Constraints, expressed as linear inequalities such as a1x+b1y≤c1a_1x + b_1y \le c_1.

•

The condition that the decision variables must be non-negative (x≥0,y≥0x \ge 0, y \ge 0) is known as the Non-negative Constraints.

•

A Feasible Region is the set of all points (x,y)(x, y) that satisfy all the given constraints simultaneously.

•

Mathematical formulation involves identifying decision variables, defining the objective function, and listing all constraints based on the problem statement.

📐Formulae

Z=ax+byZ = ax + by

aix+biy≤ci or aix+biy≥cia_ix + b_iy \le c_i \text{ or } a_ix + b_iy \ge c_i

x≥0,y≥0x \ge 0, y \ge 0

💡Examples

Problem 1:

A furniture dealer deals in tables and chairs. He has Rs.50,000Rs. 50,000 to invest and storage space for at most 6060 pieces. A table costs Rs.2,500Rs. 2,500 and a chair costs Rs.500Rs. 500. He estimates that the profit from one table is Rs.250Rs. 250 and from one chair is Rs.75Rs. 75. Formulate this as a Linear Programming Problem to maximize profit.

Solution:

Let xx be the number of tables and yy be the number of chairs.

Objective Function: Maximize Z=250x+75yZ = 250x + 75y

Subject to Constraints:

  1. Investment constraint: 2500x+500y≤500002500x + 500y \le 50000 Simplified: 5x+y≤1005x + y \le 100
  2. Storage constraint: x+y≤60x + y \le 60
  3. Non-negativity constraints: x≥0,y≥0x \ge 0, y \ge 0

Explanation:

The objective is to maximize profit ZZ. The investment constraint is derived from the total money available (Rs.50,000Rs. 50,000). The storage constraint limits the total count of items to 6060. Since the dealer cannot buy a negative number of items, xx and yy must be ≥0\ge 0.

Problem 2:

A diet is to contain at least 8080 units of vitamin A and 100100 units of minerals. Two foods F1F_1 and F2F_2 are available. Food F1F_1 costs Rs.4Rs. 4 per unit and F2F_2 costs Rs.6Rs. 6 per unit. One unit of F1F_1 contains 33 units of vitamin A and 44 units of minerals. One unit of F2F_2 contains 66 units of vitamin A and 33 units of minerals. Formulate this LPP to minimize cost.

Solution:

Let xx units of F1F_1 and yy units of F2F_2 be included in the diet.

Objective Function: Minimize Z=4x+6yZ = 4x + 6y

Subject to Constraints:

  1. Vitamin A constraint: 3x+6y≥803x + 6y \ge 80
  2. Minerals constraint: 4x+3y≥1004x + 3y \ge 100
  3. Non-negativity: x≥0,y≥0x \ge 0, y \ge 0

Explanation:

Here the goal is to minimize the total cost ZZ. The constraints are of the 'at least' type, so we use the ≥\ge symbol. The variables xx and yy represent quantities of food, which must be non-negative.