LINEAR PROGRAMMING PROBLEM (LPP)

1. Introduction to Linear Programming

Linear Programming is a mathematical technique used to determine the best possible (optimal)
solution to a problem involving limited resources. The objective may be to maximize profit or
minimize cost, subject to certain constraints.

In Linear Programming:

• All relationships are linear

• Decision variables take non-negative values

• Resources are limited

Linear Programming is widely used in business, industry, economics, and management for
efficient decision-making.

2. Advantages of Linear Programming

1. Ensures optimal utilization of scarce resources

2. Helps in profit maximization or cost minimization

3. Provides a scientific and systematic approach to decision-making

4. Improves planning and control

5. Helps in evaluating alternative courses of action

6. Reduces guesswork in managerial decisions

7. Useful in handling complex business problems

3. Application Areas of Linear Programming

Linear Programming is applied in many fields, such as:

• Production Planning – deciding product mix

• Resource Allocation – optimal use of labor, machines, capital

• Transportation & Distribution – minimizing transport cost

• Inventory Management – controlling stock levels

 • Marketing – media selection, sales planning

• Finance – investment and portfolio selection

• Agriculture – crop planning

• Defence & Military – logistics planning

4. Components of Linear Programming

• The basic components of a linear programming (LP) problem are:

• Decision Variables: Variables you want to determine to achieve the optimal solution.

• Objective Function: Mathematical equation that represents the goal you want to
achieve

• Constraints: Limitations or restrictions that your decision variables must follow.

• Non-Negativity Restrictions: In some real-world scenarios, decision variables

cannot be negative

5. Different kind of Solution of LPP

• Feasible Solution
• A feasible solution is any solution of a Linear Programming Problem that satisfies all
the constraints and non-negativity conditions.
• Infeasible Solution
• A solution that does not satisfy one or more constraints of the LPP is called an
infeasible solution.
• Feasible Region
• The feasible region is the area (or set of points) that contains all feasible solutions of
the LPP.
• Basic Solution
• A basic solution is obtained by setting some variables equal to zero and solving the
remaining equations.
• Basic Feasible Solution (BFS)
• A Basic Feasible Solution is a solution of a Linear Programming Problem which is
both basic and feasible.
 • A solution of an LPP obtained by setting (n − m) variables equal to zero (where n =
number of variables and m = number of constraints) and which satisfies all constraints
and non-negativity conditions is called a basic feasible solution.

5. Formulation of Linear Programming Problem (LPP)

Formulation means expressing a real-life problem into a mathematical model.

Steps in LPP Formulation:

1. Identify decision variables

Example: Let x = units of product A, y = units of product B

2. Formulate objective function

Example: Maximize 𝑍 = 𝑎𝑥 + 𝑏𝑦

3. Identify constraints
Example:
𝑎1 𝑥 +𝑏1 𝑦 ≤𝑐1
𝑎2 𝑥 +𝑏2 𝑦 ≤𝑐2
non-negativity restriction
x ≥ 0, y ≥ 0

General LPP Form:

Maximize / Minimize
𝑍 = 𝑎𝑥 + 𝑏𝑦

Subject to:
𝑎1 𝑥 +𝑏1 𝑦 ≤, ≥, = 𝑐1
𝑎2 𝑥 +𝑏2 𝑦 ≤, ≥, = 𝑐2
x, y ≥ 0

5. Graphical Method of Solving LPP

The graphical method is used when the LPP has only two decision variables.

Steps:

1. Convert inequalities into equations

 2. Plot each constraint on the graph

3. Identify the feasible region

4. Find corner (vertex) points

5. Calculate Z value at each corner point

6. Select the point giving maximum or minimum value of Z

6. Types of Solutions in Graphical Method

1. Unique Solution – one optimal solution

2. Infinite Solutions – more than one optimal solution

3. Unbounded Solution – no maximum or minimum value

4. No Feasible Solution – no common region satisfying all constraints

Formulation:

• A furniture manufacture makes two products: chairs and tables. Processing of these
products is done on two machines A and B. A Chair requires 2 hours on machine A and
6 hours on machine B. A table requires 5 hours on machine A and no time on machine
B. There are 16 hours per day available on machine A and 30 hours on machine B.
Profit gained by the manufacturer from a chair and a table is Rs. 2 and Rs.10,
respectively. Formulate this problem as a linear programming problem to maximize the
total profit of the manufacturer.

• A company manufactures two types of products A and B. Each unit

of A requires 3 grams of nickel and 1 gram of chromium, while each unit
of B requires 1 gram of nickel and 2 grams of chromium. The firm can
produce 9 grams of nickel and 8 grams of chromium. The profit is Rs. 40 on each unit
of product of type A and Rs. 50 on each unit of type B. How many units of each type
should the company manufacture to earn maximum profit? Use linear programming to
find the solution.

• A person wants to include two foods F1 and F2 in his diet. Food F1 contains 2 units of
protein and 1 unit of vitamins, while F2 contains 1 unit of protein and 2 units of
vitamins. The daily requirement is at least 8 units of protein and 6 units of vitamins.
Cost per unit of F1 is ₹3 and F2 is ₹2.
• A firm advertises through TV and newspapers. Each TV advertisement costs ₹1000 and
reaches 40,000 people. Each newspaper advertisement costs ₹500 and reaches 20,000
people. The firm wants to reach at least 4,00,000 people. The budget for advertising is
₹15,000. Formulate the LPP.

• A farmer has 10 hectares of land to grow wheat and rice. Wheat requires 2 units of labor
per hectare and rice requires 3 units. Total labor available is 24 units. Profit per hectare
of wheat is ₹5000 and rice is ₹[Link] the LPP.