A study of linear programming technique

This paper focuses on one of the most used techniques of operations research i.e. linear programming. The linear programming is a mathematical method to provide an optimal solution for the problems where objective and the requirements both are linear. The limelight during the Second World War The rapid use of linear programming in various fields started after the Second World War. This study provides insights on the assumptions and properties of the linear programming. It also explains the process of formulating any problem as a linear programming problem if all the assumptions are satisfied. The limitations and mathematical formulation are also problem if all the assumptions are satisfied. The limitations and mathematical formulation are also explained. Some practical applications of linear programming are discussed. This study also provides insight on the latest applications of linear programming problem in various fields like sports, lean manufacturing, financial planning and radiotherapy.

Illustrations explain the paper; charts are replotted from the paper's own table values.

AI-generated illustration

↗ Enlarge

Linear Programming Formulation WorkflowClose ×

AI-generated conceptual illustration (A mathematical optimization workflow represented by geometric symbols). It explains the idea and does not show study data.

Open full-size image ↗

Replotted from source data

↗ Enlarge

Annual expected return: Blue chip stocks vs Speculative stocks vs Short term depositsClose ×

Replotted from Table 2 (page 2) of the original paper. Every bar is the paper's own table value.

Open full-size image ↗

Replotted from source data

↗ Enlarge

Risk factor (0 to 100) Government bonds: Blue chip stocks vs Speculative stocks vs Short term depositsClose ×

Replotted from Table 2 (page 2) of the original paper. Every bar is the paper's own table value.

Open full-size image ↗

Introduction

"No dreams come true until you wake up and go for work" similarly any problem cannot be resolved unless we fix the problem and try to solve it. Most of the business or planning problems involving resources can be converted into a mathematical problem the only vital condition is all information should be available. These problems involved consist of two major components, one is objective function and the other is constraints. If both objective function and constraints are linear, then they can be framed as a linear programming problem. Here linear means that variable involved in constraints and objective function should not have any power. There are some standard types of Linear programming formulations given in this paper, but the list is indicative not exhaustive as after formulating 1000 problems, there would be another problem where the formulation might be entirely different (Jain, 2020) [1] .

Properties and Assumptions in Linear Programming Problem

A Linear programming model is based on the assumption of proportionality, additivity, continuity, certainty, and finite choices. These are given detailed below (Robinson Lawrence W, 1991) [2] .  Proportionality: The rate of change (slope) of the objective function and the constraint equations with respect to decision variable is constant.  Continuity: Decision fractional value and variables can take on any are therefore continuous as opposed to integer in nature.  Certainty: Values of all model parameters are assumed to be known with certainty.

Formulation of Linear Programming problem

Steps of Linear Programming Formulation  Determine the objective of the problem  Identify decision variables and conditions involved  Formulate objective function  Formulate constraints  Express the non-negativity constraints  Weather the all the conditions are satisfied Limitations of linear programming Linear programming linear. But it is not true situations. Considers all relationships as in many real life and business (Kondo Yasushi, 2005) [3] .  As the number of variables and constraints increases the problem becomes very complex and very difficult to solve.  Linear programming gives its solution in fractions which are not suitable in many practical situations. For exampleif it can give a solution as construction of 25/4 apartments and 35/3 shops as optimum solution, which is not possible for any construction company (Brown, 1965) [4] .  Factor pertaining to uncertainty such as, strike, absenteeism of labor, weather conditions, etc. are not taken into deliberation during formulation.  LPP considers only a single objective function; where as in real life and business situations, there may be more than one objective.

Mathematical Formulation

The Linear Programming problem can be put in the following form, which is also known as standard form of LPP (Mohd Baki S, 2021) [5] .

Objective Function Subject to the constraints;

Some Examples of Linear Programming Problem

Some Examples of Linear Programming Problem

Production Mix Problem

Example on use of linear programming to decide the product mix i.e. to use the quantity of products to be manufactured to get the maximum profit (Jain AK, 2019) [6] . Formulate the following as a linear programming problem Publishing house publishes three weekly magazines-Daily life, Agriculture today, and Surf's up. Publication of one issue of each of these magazines requires the following amounts of production time and paper (Haider Z, 2016) [7] . Surf's Up it is 6,000 issues. The production manager wants to know the number of issues of each magazine to produce per week in order to maximize total sales revenue (Soni, 2011) [8] . Let the publishing house publishes x 1 copies of Daily Life, x 2 copies of Agriculture Today and x 3 copies of Surf's up. Here x 1 , x 2 and x 3 are decision variables. The Objective Function-here objective of the publishing house is to maximize the total sales revenue. Thus, the objective function will be.

Max Z = 22.5x 1 +40x 2 +15x 3

The Constraints- Paper (Kg)-0.2x 1 +0.5x 2 +0.3x 3 ≤ 3,000  Circulation (issues)-x 1 +x 2 +x 3 ≥5,000  Production Hours-0.01x 1 +0.03x 2 +0.02x 3 ≤120  Maximum demand for Daily Life-x 1 ≤3,000  Maximum demand for AgricultureToday-x 2 ≤2,000  Maximum demand for Surf'sUp-x 3 ≤ 6000

Non-Negativity condition-As, x 1 , x 2 and x 3 are the Number of unit produced, they cannot be negative. Thus, both of them can assume values only greater-than-or-equal-to zero. This can be stated as (Barnhart C, 2003) [9] .

x 1 ≥0, x 2 ≥ 0 and x 3 ≥ 0 Subject To Hence the mathematical formulation of the problem is 0.01x 1 +0.03x 2 +0.02x 3 ≤120 0.2x 1 +0.5x 2 +0.3x 3 ≤ 3,000x 1 +x 2 +x 3 ≥5,000 x 1 ≤3,000x 2 ≤2,000x 3 ≤6000 x 1 , x 2 and x 3 ≥ 0

Portfolio Management

Example on use of linear programming in financial planning, a mutual fund has $ 20 million available for investment in Government bonds, blue chips stocks, and speculative tock sand short term bank deposits. The annual expected return and risk factor are given as follows (Shivlani N, 2019) [10] : Mutual Fund is required to keep at least $ 2 million in short term deposits and not to exceed an average risk factor of 42.Speculative stocks must be at most 20percent of the total invested. How should Mutual Fund invest the funds so as to maximize its total expected annual return?? Formulate this as a linear programming problem. Solution-let mutual fund makes the following investments, $ x 1 in government bonds, $ x 2 in blue chip stocks, $ x 3 in speculative stocks and $. x 4 in short term deposits (Kiok LT, 2009) [11] .

Objective function-Max Z =.14x

Research on applications of linear programming

There has been lot of research on linear programming in last few decades. Some of the latest works on the applications of linear programming in the various fields are given below (Mohamed AM, 2015) [12] .  Mehrzad Hamidi et al., 2011 [13] have evaluated the performance of Iranian football teams utilizing linear programming.  Oleg Viacheslavovich Yeriomin (2011) [14] had used linear programming for calculation of standard thermodynamic potentials for Na-Zeolites.  Konstantine Georgakakos (2012) [15] worked on water supply and demand sensitivities of linear programming solutions to a water all ocation problem.  Bruno Rüttimann. Discoursed about Linear Programming and Lean Manufacturing: Two Different Approaches with a Similar, Converging Rational  Chongyu Jiang et al., (2016) [16] worked on Application of Linear Programming Model to Refugee Migrating Problem  Thais R. Salvador et al., (2016) [17] worked on the application of simplex method one of the method use to solve linear programming in the radio the reply treatment.

Conclusion

This study provides complete details about the linear programming technique, one of the most applied techniques of Operations Research. This note can help students and researchers to understand the assumptions and properties of linear programming. This paper also provides the limitations of linear programming. Also, some of the latest research on applications of linear programming in various fields have been discussed in this study. Thus, this study will act as a catalyst for encouraging more research on applications of linear programming.

Figures and tables from the paper

↗ Enlarge

Table 2Close ×

Provides annual expected return and risk factor for each

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

Magazine	Production (hour)	Paper (kg) Daily Life
Agriculture Today	0.03	0.05
Surf’s Up	0.02	0.03

Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.

View original table image

↗ Enlarge

Table 1Close ×

Gives requirements of each product

Open full-size image ↗

Original paper tableSource PDF · page 2 ↗

1. Jain, Amit Kumar, et al. Application of Linear Programming for Profit Maximization of a Pharma Company. Journal of Critical Reviews. 2020;7(12):11181123.
2. Robinson Lawrence W. Baseball playoff eliminations: An application of linear programming. Operations Research Letters. 1991;10(2):67-74.
3. Kondo Yasushi, Shinichiro Nakamura. Waste inputoutput linear programming model with its application to eco-efficiency analysis. Economic Systems Research. 2005;17(4):393-408.
4. Brown, Douglas B, Martin R. Warshaw Media selection by linear programming. Journal of Marketing Research. 1965;2(1):83-88.
5. Mohd Baki S, Cheng JK. A Linear Programming Model for Product Mix Profit Maximization in a Small Medium Enterprise Company. International Journal of Industrial Management. 2021;9:64-73.
6. Jain AK, Bhardwaj R, Saxena H, Choubey A. Application of linear programming for profit maximization of the bank and the investor. International Journal of Engineering and Advanced Technology. 2019;8(6):4166-4168. https://doi.org/10.35940/ijeat.F9337.088619
7. Haider Z, Fareed R, Tariq MB, Usman S, Ud din N, Khan S. Application of Linear Programming for Profit Maximization: A Case of Paints. International Journal of Management Sciences and Business Research. 2016;5(12):144-151.
8. Soni, Kiran, Saxena K. A study of applicability of waiting line model in health care: a systematic review. Operation Research. 2011;19(1):75-91.
9. Barnhart C, Belobaba P, Odoni AR. Applications of operations research in the air transport1 industry. Transportation Science. 2003;37(4):368-391. https://doi.org/10.1287/trsc.37.4.368.23276
10. Shivlani N. Applications of Operations Research in the food delivery industry. International Journal of Advance Research. 2019;5(5):396-400. Retrieved from www.IJARIIT.com
11. Kiok LT. Practical operations research applications for healthcare managers. Annals of the Academy of Medicine Singapore. 2009;38(6):564-73.
12. Mohamed AM. Operations Research Applications in Audit Planning and Scheduling. International Journal of Social. 2015;9(6):2026-2034.
13. Hamidi M, Sajadi H, Soleimani-Damaneh J. Evaluating the performance of Iranian football teams utilizing linear programming. American Journal of Operations Research. 2011;1(02):65.
14. Yeriomin OV. Calculation of standard thermodynamic potentials for Na-zeolites with the use of linear programming problems. International Journal of Geosciences. 2011;2(3):227-30.
15. Georgakakos KP. Water supply and demand sensitivities of linear programming solutions to a water allocation problem. Applied Mathematics. 2012;3(10):1285-1297.
16. Jiang C, Li X, Li Y. Application of Linear Programming Model to Refugee Migrating Problem. Journal of Applied Mathematics and Physics. 2016;4(5):967-77.
17. Salvador TR, Carvalho SM, Coelho MV. Application of simplex method in the radiotherapy treatment. Applied Mathematics. 2016;7(17):2229.