Linear Programming Problems

Group 1

Ananya Sharma - A016

Muskaan Kothari - A041

Priyangi Jain - A013

Siya Gupta - A001

Tanya Sabharwal - A021

​

Mentor

Prof. Nagapati Hegde

Index

• Linear Programming Problem – An Introduction
• Meaning
• Objectives
• Components
• Common Concepts
• Assumptions
• Investment Portfolio – An Application
• Data Collection
• Methodology
• Numerical Data
• Investment Problem – Formulation and Solution
• Objectives
• Constraints
• Mathematical Model
• Solution using TORA
• Interpretation
• Limitations
• Karmarkar’s Algorithm – A Short Note
• Bibliography

​

​

​

​

​

​

​

​

What is a Linear Programming Problem?

• Linear programming is a mathematical technique for determining the optimum allocation of limited resources subject to limitations or constraints when there are alternative uses of resources

​

• The method of maximizing or minimizing the objective function subject to the conditions:

(i) variables are non – negative

(ii) variables satisfy linear constraints

​

�

OBJECTIVES

Cost Minimisation

Components Of Linear Programming Problem

Constraints

Objective Function

Decision Variables

Common Concepts Involved In LPP Model Formulation

• Decision Variables - Mathematical symbols representing the level of activity of firms

​

• Objective function - A linear mathematical relationship describing an objective of the firm in terms of decision variables- this function is to be maximised or minimised

​

• Constraints - Requirements or restrictions placed on the firm by the operating environment, stated in linear relationship of the decision variables. They include:
1. Non Negativity Constraints
2. Linear Constraints (inequality)

​

​

​

​

Assumptions

Investment Portfolio as an Application

• A portfolio is a collection of financial investments which can be managed by any individual and is designed keeping in mind the investor’s risk tolerance, time frame, and investment objectives.
• Portfolio optimization is a taxing problem in investment and finance and affects portfolio holders and managers who allocate their resources across different categories.
• LPP techniques are used by insurance companies for building asset portfolios.
• We have taken the funds allocated to HDFC Mutual Funds for investment (based on their Annual Report of 2020-21) as a reference and based a problem wherein the firm has to invest in different investment areas in the portfolio in order to maximize their returns keeping in mind, the risk investment constraints of the firm.

HDFC Mutual Funds Annual Report(2020-2021)

Data Collection Methodology

The data we have collected here is Secondary data:

• There are two types of risks in investing - Systematic and Unsystematic.
• In statistics, standard deviation and beta are two well-known tools for risk analysis.
• Standard deviation is used to quantify the total risk and beta is used to get an idea of the market risk.
• We have collected the returns of these 6 investment areas for every month in the past 5 years and formulated a table calculating their risk score and interest rates required for LPP formulation.

​

Data

Objective

• The objective of our problem here is the allocation of the total amount to the various investment areas, keeping in mind their risks and profits.

​

• The objective function is the returns from investing in all these 6 investment areas and the aim is to maximize it.

Constraints:�

1. Invest up to 4753.25 crore in the entire investment options.

​

• Not more than 20% of the total investment in any one investment area.

​

• At least 25% of the total investment in fixed deposits and crude oil.

​

• At least 15% of the total investment in bonds.

​

• At least 35% of the total investment in treasury bills and PPF.

​

• At least 10% of the total investment in gold.

​

• The overall risk should not be more than 10% of the portfolio risk, calculated using the weighted average, which should be equal to or less than 10%. The portfolio risk is calculated using a weighted average.

​

• Non-negativity constraints. 

​

​

​

​

Modelling the problem as LPP

Software Used : TORA

We have chosen to use TORA for this problem since it is easy to operate and has a very user-friendly interface.

Excel’s Solver was also another viable option.

TORA Menu

Input Grid for Problem

TORA Output

Solution

Solution

The surplus and slack basic variables take values :

Surplus variables : S3 = 237.6625, S5 = 312.8628, S6 = 237.6625, S7 = 162.4622

Slack variables : S8 = 550.5253, S11 = 162.4622

The non-basic variables are : S1 = S2 = S4 = S9 = S10 = S12 = 0

(All values are in crores)

​

Interpretation

The maximum possible return is Rs. 2439.6398 crore on the original investment of Rs. 4753.25 crore.

​

This can be achieved if the company invests

Rs. 950.6500 crore in PPF, Rs. 712.9875 crore in Treasury Bills,

Rs. 950.6500 crore in Fixed Deposits, Rs. 637.7872 crore in Gold, Rs. 712.9875 crore in Bonds and Rs. 788.1878 crore in Crude Oil.

​

This shows that we can get a maximum return of 51.33% on our investment if we choose to invest in PPF, Treasury Bills, Fixed Deposits, Gold, Bonds and Crude Oil keeping in mind the constraints we have been given.

​

​

Interpretation

The solution is unique as there is only one investment giving this high a yield. The solution is feasible as all the constraints are satisfied.

​

The solution is optimum because it is the maximum possible value for this investment considering the given constraints.

​

It could be possible to further increase this return by changing the constraints. This is a part of sensitivity analysis.

We could also choose to invest in different securities which give higher returns as compared to the ones listed above.

​

​

​

​

Limitations

1. Unusual Year – The data that we have considered includes data from the Covid Pandemic year.
2. Company Data – Companies do not reveal their whole accounting data for the purpose of privacy and security.
3. Software Used – We have used TORA (not a commonly used software by companies).
4. Obsolete Data – The research process is time-consuming and the data can lose its relevance.

Note : Karmarkar’s Algorithm

Karmarkar’s Algorithm was introduced in 1984 for solving linear programming problems by Dr. Narendra Karmarkar (Pune) from IIT Bombay. Complex optimization problems are solved much faster using Karmarkar’s Algorithm. His algorithm thus enables faster business and policy decisions.

​

​

Bibliography

• HDFC AMC Annual Report FY 2020-21.pdf (hdfcfund.com)
• Gold Returns in Other Currencies | World Gold Prices | Goldhub
• https://www.paisabazaar.com/saving-schemes/ppf-interest-rates/
• https://www.rbi.org.in/Scripts/BS_NSDPDisplay.aspx?param=4
• http://www.worldgovernmentbonds.com/bond-historical-data/india/5years/#:~:text=The%20India%205%20Years%20Government,%3A15%20GMT%2B0
• 210121-Historical Retail Term Deposits Rates for last 10 years.xlsx (live.com)
• https://economictimes.indiatimes.com/wealth/invest/how-to-identify-calculate-risk-in-stocks-using-ms-excel/articleshow/69608883.cms?from=mdr 

​