Linear Programming
involves a series of linear equations used to construct a mathematical model.
The objective is to obtain an optimal solution to a complex operational
problem, which may involve the production of a number of products in an
environment in which there are many constraints.
It is a mathematical
technique for determining the optimal allocation of resources and achieving the
specified objective when there are alternative uses of resources like money,
manpower, materials, machines and other facilities. The objective of resource
allocation may be either cost minimization or profit maximization.
A problem in linear
programming has three key elements:
- Objective – The metric that needs to be optimized. For example, an objective could be to maximize profit for the current fiscal year.
- Decision – The decisions that need to be made to achieve the objective. For example, a decision could be made on the amount of financial investment.
- Constraints – They are restrictions or limit that can influence a decision. For example, the size of the budget can limit the scope of a decision.
A Linear Programming
Problem should always follow the below mentioned steps:
- Understand the problem.
- Identify variables and name them
- Allocate cells for optimum results into equations.
- Convert business constraints into equations.
- Transfer them to excel understandable language- objective function
Example:
A company manufactures two products A and B, involving three departments –
Machining, Fabrication and Assembly. The process time, profit/loss and total
capacity of each department is given in the following table:
Machining
(hours)
|
Fabrication
(hours)
|
Assembly (hours)
|
Profit (Rs.)
|
|
HA
|
1
|
5
|
3
|
80
|
B
|
2
|
4
|
1
|
100
|
Capacity
|
720
|
1800
|
900
|
In the above problem the company wants to maximize its profit by producing optimum units of products A and B. But it is subjected to some constraints like availability of limited numbers of hours in each of its departments. Thus in such case Linear Programming helps us to find the number of units that should be produced to maximize firms profits keeping in consideration the constraints available.
Let x1 and x2 denote the
number of units produced for the product A and B respectively.
Maximize (Profit)
Z = 80x1 + 100x2
Subject to constraints:
x1 + 2x2 <= 720 (Machining Time)
5x1 + 4x2 <= 1800 (Fabrication Time)
3x1 + x2 <= 900 (Assembly Time)
After formulating the
problem in terms of linear equations, we need to input the data into excel in
the following manner:
A Linear Programming problem can be easily solved with the help of Solver which is present in Microsoft Excel.
HOW TO INSTALL SOLVER IN EXCEL:
HOW TO INSTALL SOLVER IN EXCEL:
1. Go
to File and select the Option to enter Back stage window.
2. Click
Add-Ins, and then in the Mange Box, select Excel Add-Ins and click Go.
3. In
the Add-Ins available box, select the Solver Add-in check box and then click
OK.
4. After
you load Solver, the Solver command is available in the Analysis group on the
Data tab.
Now use the excel formula
‘=SUMPRODUCT’ in cells E14 and copy paste the formula in cells E15 & E16 to
take into consideration our constraints with the no. of units required to
optimize our solution as shown in the below figure. We select Cells C9:D9 as array1 and Cells C14:D14 as array2 while constructing the formula. We also use $ (Dollar Sign) in between 'C' and '9' and 'D' and '9' so as to freeze row 9 and easily copy the formula in E15 and E16.
We again use the same
formula ‘=SUMPRODUCT’ in the cell C19 to take into consideration the profit per
product and no. of units required to optimize our solution.
Then go to Data Tab and
click on 'Solver' to open Solver Parameters dialog box. In the Set Objective field select Cell C19 to set it as the cell where the maximum profit generated
by the LPP problem will be shown. In the ‘By Changing Variable Cells’ we select
the Cells that will give us the quantity of Product A and B that needs to be
produced. We select Cells C9 & D9.
Then we fill the ‘Subject
to the Constraints’ box to fill the constraints in our LPP problem. Click Add
button to open ‘Add Constraint’ dialog box. In the cell reference cell we
select Cells E14, E15 and E16 individually and in the Constraint box we select
cells F14, F15, F16 respectively. Add all the constraints individually and in
the end click ok.
After clicking ok we will
see all the constraint cells displayed in the ‘Subject to Constraints’ box.
Then select Simplex LP as our method of solving the problem in ‘Select a
solving Method’. Finally click Solve button.
A Solver Results dialog
box will open. We need to select ‘Keep Solver Solution’. In the Reports section
select Answer and tick ‘Outline Reports’ and give ok to get our solution.
FINAL OUTPUT -
This shows us that the
optimum number of units of A and B that should be produced are 120 units of A
and 300 units of B to get a maximum profit of Rs. 39,600.
The solver creates another worksheet containing an Answer Report, like the one below that shows the original and final value of the objective function and the decision variables, as well as the status of each constraint at the optimal solution.
The solver creates another worksheet containing an Answer Report, like the one below that shows the original and final value of the objective function and the decision variables, as well as the status of each constraint at the optimal solution.
Thus a simple optimization problem (Linear Programming) can be easily solved using Microsoft Excel Solver.
Did you find this article useful? Share your opinions / views in the comments section below. The tutorial can be downloaded by clicking on this link. Download
Auhor - Kunal Patel
Visit me at Kunal Patel
Comments
Post a Comment