Linear Programming is a problem-solving approach that has been developed to help managers to make decisions. Linear Programming is a mathematical technique for determining the optimum allocation of resources and obtaining a particular objective when there are alternative uses of the resources, money, manpower, material, machines, and other facilities.
THE NATURE OF LINEAR PROGRAMMING PROBLEM
Two of the most common are:
- The product-mix problem
- The blending Problem
In the product-mix problem, there are two or more products also called candidates or activities competing for limited resources. The problem is to find out which products to include in the production plan and in what quantities these should be produced or sold in order to maximize profit, market share, or sales revenue. The blending problem involves the determination of the best blend of available ingredients to form a certain quantity of a product under strict specifications. The best blend means the least cost blend of the required inputs.
FORMULATION OF THE LINEAR PROGRAMMING MODEL
Three components are:
- The decision variable
- The environment (uncontrollable) parameters
- The result (dependent) variable
TERMINOLOGY USED IN LINEAR PROGRAMMING PROBLEM
- Components of LP Problem: Every LPP is composed of a. Decision Variable, b. Objective Function, c. Constraints.
- Optimization: Linear Programming attempts to either maximise or minimize the values of the objective function.
- Profit of Cost Coefficient: The coefficient of the variable in the objective function express the rate at which the value of the objective function increases or decreases by including in the solution one unit of each of the decision variable.
- Constraints: The maximisation (or minimisation) is performed subject to a set of constraints. Therefore LP can be defined as a constrained optimisation problem. They reflect the limitations of the resources.
- Input-Output coefficients: The coefficient of constraint variables are called the InputOutput Coefficients. They indicate the rate at which a given resource is unitized or depleted. They appear on the left side of the constraints.
- Capacities: The capacities or availability of the various resources are given on the right hand side of the constraints.
THE MATHEMATICAL EXPRESSION OF THE LP MODEL
FORMULATION OF LPP
STEPS
- Identify decision variables
- Write objective function
- Formulate constraints
It is required to determine the daily number of units to be manufactured for each product. The profit per unit for product 1, 2 and 3 is Rs. 4, Rs.3 and Rs.6 respectively. It is assumed that all the amounts produced are consumed in the market. Formulate the mathematical (L.P.) model that will maximize the daily profit.
Formulation of Linear Programming Model
Step 1
From the study of the situation find the key-decision to be made. In the given situation key decision is to decide the extent of products 1, 2 and 3, as the extents are permitted to vary.
Step 2
Assume symbols for variable quantities noticed in step 1. Let the extents (amounts) of products 1, 2 and 3 manufactured daily be x1, x2 and x3 units respectively.
Step 3
Express the feasible alternatives mathematically in terms of variable. Feasible alternatives are those which are physically, economically and financially possible. In the given situation feasible alternatives are sets of values of x1, x2 and x3 units respectively. where x1, x2 and x3 ≥ 0. since negative production has no meaning and is not feasible.
Step 4
Mention the objective function quantitatively and express it as a linear function of variables. In the present situation, objective is to maximize the profit.
i.e., Z = 4×1+ 3×2 + 6×3
Step 5
Put into words the influencing factors or constraints. These occur generally because of constraints on availability (resources) or requirements (demands). Express these constraints also as linear equations/inequalities in terms of variables. Here, constraints are on the machine capacities and can be mathematically expressed as
2×1+ 3×2 + 2×3 ≤ 440
4×1+ 0x2 + 3×3 ≤ 470
2×1+ 5×2 + 0x3 ≤ 430
EXAMPLE 2: PRODUCT MIX PROBLEM
A factory manufactures two products A and B. To manufacture one unit of A, 1.5 machine hours and 2.5 labour hours are required. To manufacture product B, 2.5 machine hours and 1.5 labour hours are required. In a month, 300 machine hours and 240 labour hours are
available.Profit per unit for A is Rs. 50 and for B is Rs. 40. Formulate as LPP.
X1 = Number of units of A manufactured per month.
X2 = Number of units of B manufactured per month.
The objective function:
Max Z = 50×1+ 40×2
Subjective Constraints
For machine hours
1.5×1+ 2.5×2 ≤ 300
For labour hours
2.5×1+ 1.5×2 ≤ 240
Non negativity
x1, x2 ≥0
EXAMPLE: 3
A company produces three products A, B, C. For manufacturing three raw materials P, Q and R are used. Profit per unit A – Rs. 5, B – Rs. 3, C – Rs. 4. Resource requirements/unit
Solution:
Decision variables:
x1 = Number of units of A
x2 = Number of units of B
x3 = Number of units of C
Objective Function
Since Profit per unit is given, the objective function is the maximisation
Max Z = 5×1+ 3×2 + 4×3
Constraints:
For P: 0x1+ 20×2 + 30×3 ≤ 80
For Q: 20×1+ 30×2 + 20×3 ≤ 100
For R: 50×1+ 0x2 + 40×3 ≤ 150
(for B, R is not required)
X1, X2, X3 ≥ 0
EXAMPLE 4: PORTFOLIO SELECTION (INVESTMENT DECISIONS)
An investor is considering investing in two securities ‘A’ and ‘B’. The risk and return associated with these securities is different.Security ‘A’ gives a return of 9% and has a risk factor of 5 on a scale of zero to 10. Security ‘B’ gives return of 15% but has risk factor of 8. Total amount to be invested is Rs. 5, 00, 000/- Total minimum returns on the investment should be 12%. Maximum combined risk should not be more than 6. Formulate as LPP.
Solution:
Decision Variables:
X1 = Amount invested in Security A
X2 = Amount invested in Security B
Objective Function:
The objective is to maximise the return on total investment.
⸫ Max Z = 0.09 X1 + 0.015 X2 ((% = 0.09, 15% = 0.15)
Constraints:
- Related to Total Investment:
X1 + X2 = 5, 00, 000 - Related to Risk:
5X1 + 8X2 = (6 X 5, 00, 000)
5X1 + 8X2 = 30, 00, 000 - Related to Returns:
0.09X1 + 0.15X2 = (0.12 X 5, 00, 000)
⸫0.09X1 + 0.15X2 = 60, 000 - Non-negativity
X1, X2 ≥ 0
EXAMPLE 5: INSPECTION PROBLEM
A company has two grades of inspectors, I and II to undertake quality control inspection. At least 1, 500 pieces must be inspected in an 8-hour day. Grade I inspector can check 20 pieces in an hour with an accuracy of 96%. Grade II inspector checks 14 pieces an hour with an
accuracy of 92%. Wages of grade I inspector are Rs. 5 per hour while those of grade II inspector are Rs. 4 per hour. Any error made by an inspector costs Rs. 3 to the company. If there are, in all, 10 grade I inspectors and 15 grade II inspectors in the company, find the optimal assignment of inspectors that minimise the daily inspection cost.
Solution:
Let x1 and x2 denote the number of grade I and grade II inspectors that may be assigned the job of quality control inspection.
The objective is to minimise the daily cost of inspection. Now the company has to incur two types of costs; wages paid to the inspectors and the cost of their inspection errors.
The cost of grade I inspector/hour is
Rs. (5 + 3 X 0.04 X 20) = Rs. 7.40.
Similarly, cost of grade II inspector/hour is
Rs. (4 + 3 X 0.08 X 14) = Rs. 7.36.
⸫ The objective function is minimise Z = 8(7.40×1 + 7.36×2) = 59.20 x1 + 58.88×2.
Constraints are on the number of grade I inspectors: x1 ≤ 10,
on the number of grade II inspectors: x2 ≤ 15
on the number of pieces to be inspected daily: 20 x 8×1 + 14 x 8×2 ≥ 1500
or 160×1 + 112×2 ≥ 1500
where, x1, x2 ≥ 0.
EXAMPLE 6: TRIM LOSS PROBLEM
A manufacturer of cylindrical containers receives tin sheets in widths of 30 cm and 60 cm respectively. For these containers the sheets are to be cut to three different widths of 15 cm, 21 cm and 27 cm respectively. The number of containers to be manufactured from these three widths are 400, 200 and 300 respectively. The bottom plates and top covers of the containers are purchased directly from the market. There is no limit on the lengths of standard tin sheets. Formulate the LPP for the production schedule that minimises the trim losses.
Solution:
Key decision is to determine how each of the two standard widths of tin sheets be cut to the require widths so that trim losses are minimum. From the available widths of 30 cm and 60 cm, several combinations of the three required widths of 15 cm, 21 cm and 27 cm are possible. Let xij represent these combinations. Each combination results in certain trim loss. Constraints can be formulated as follows:
The possible cutting combinations (plans) for both types of sheets are shown in the table below:
EXAMPLE 7: MEDIA SELECTION
An advertising agency is planning to launch an ad campaign. Media under consideration are T.V., Radio & Newspaper. Each medium has different reach potential and different cost. Minimum 10, 000, 000 households are to be reached through T.V. Expenditure on
newspapers should not be more than Rs. 10, 00, 000. Total advertising budget is Rs. 20 million. Following data is available:
Solution:
Decision Variables:
x1 = Number of units of T.V. ads,
x2 = Number of units of Radio ads,
x3 = Number of units of Newspaper ads.
Objective function: (Maximise reach)
Max. Z = 20, 00, 000 x1 + 10, 00, 000 x2 + 2, 00, 000×3
Subject to constraints:
20, 00, 000 x1 ≥ 10, 000, 000 …….. (for T.V.)
40, 000 x3 ≤ 10, 00, 000 ……….. (for Newspaper)
2, 00, 000×1 + 80, 000×2 + 40, 000×3 ≤ 20, 000, 000 ………. (Ad. budget)
x1, x2, x3 ≥ 0
⸫ Simplifying constraints:
for T.V. 2 x1 ≥ 10 ⸫ x1 ≥ 5
for Newspaper 4 x3 ≤ 100 ⸫ x3 ≤ 25
Ad. Budget
20 x1 + 8 x2 + 4 x3 ≤ 2000
5 x1 + 2×2 + x3 ≤ 500
x1, x2, x3 ≥ 0
EXAMPLE 8: DIET PROBLEM
Vitamins B1 and B2 are found in two foods F1 and F2. 1 unit of F1 contains 3 units of B1 and 4 units of B2. 1 unit of F2 contains 5 units of B1 and 3 units of B2 respectively. Minimum daily prescribed consumption of B1 & B2 is 50 and 60 units respectively. Cost per unit of F1 & F2 is Rs. 6 & Rs. 3 respectively. Formulate as LPP.
EXAMPLE 9: BLENDING PROBLEM
A manager at an oil company wants to find optimal mix of two blending processes. Formulate LPP
EXAMPLE 10: FARM PLANNING
A farmer has 200 acres of land. He produces three products X, Y & Z. Average yield per acre for X, Y & Z is 4000, 6000 and 2000 kg.
Selling price of X, Y & Z is Rs. 2, 1.5 & 4 per kg respectively. Each product needs fertilizers. Cost of fertilizer is Rs. 1 per kg. Per acre need for fertilizer for X, Y & Z is 200, 200 & 100 kg respectively. Labour requirements for X, Y & Z is 10, 12 & 10 man hours per acre. Cost
of labour is Rs. 40 per man hour. Maximum availability of labour is 20, 000 man hours. Formulate as LPP to maximise profit.
Solution:
Decision variables:
The production/yield of three products X, Y & Z is given as per acre.
Hence,
x1 = No. of acres allocated to X
x2 = No. of acres allocated to Y
x3 = No. of acres allocated to Z
Objective Function:
Profit = Revenue – Cost
Profit = Revenue – (Fertiliser Cost + Labour Cost)
MERITS OF LPP
- Helps management to make efficient use of resources.
- Provides quality in decision making.
- Excellent tools for adjusting to meet changing demands.
- Fast determination of the solution if a computer is used.
- Provides a natural sensitivity analysis.
- Finds solution to problems with a very large or infinite number of possible solutions.
DEMERITS OF LPP - Existence of non-linear equation: The primary requirements of Linear Programming is
the objective function and constraint function should be linear. Practically linear relationship
do not exist in all cases. - Interaction between variables: LP fails in a situation where non-linearity in the equation
emerge due to joint interaction between some of the activities like total effectiveness. - Fractional Value: In LPP fractional values are permitted for the decision variable.
- Knowledge of Coefficients of the equation: It may not be possible to state all coefficients
in the objective function and constraints with certainty