Case Study About Linear Programming Examples

 Case Report

Profit Optimization Using Linear Programming Model:
A Case Study of Ethiopian Chemical Company

Vishwa Nath Maurya1, Ram Bilas Misra2, Peter K Anderson3, Kamlesh Kumar Shukla4

1Department of Applied Mathematics and Statistics, School of Science & Technology, The University of Fiji, Lautoka, Fiji

2Department of Mathematics & Computing Science, Divine Word University, Madang, Papua New Guinea

3Dept. of Information Systems, and Dept. of Mathematics & Computing Science, Divine Word University, Madang, Papua New Guinea

4Department of Management, Adama Science and Technology University, Adama, Ethiopia

Email address:

(V. N. Maurya)

To cite this article:

Vishwa Nath Maurya, Ram Bilas Misra, Peter K Anderson, Kamlesh Kumar Shukla. Profit Optimization Using Linear Programming Model: A Case Study of Ethiopian Chemical Company. American Journal of Biological and Environmental Statistics. Vol. 1, No. 2, 2015, pp. 51-57.doi: 10.11648/j.ajbes.20150102.12

Received: October 12, 2015; Accepted: April 15, 2016; Published: June 16, 2016

Abstract: This paper aims for profit optimization of an Ethiopian chemical company located in Adama (Ethiopia) using linear programming model. Particularly, our present study brings out clearly the necessity of using quantitative techniques for utilization in Ethiopian company; a factory situated within Adama about 90 kms. from Addis Ababa (Capital of Ethiopia). The first step comprises data generation. A questionnaire is prepared and circulated amongst company staff both executive and technical to determine the production, sales and profit during a few months of 2014. The profits varied considerably owing to subjective approach. It was established that the decisions are undertaken by experienced people without use of quantitative people and quantitative method. Whole approach applied here is seemingly subjective. A theoretical perspective undertaken for the present study is review of various different applications of linear programming. The characteristics of base assumptions of linear programming and its advantages and disadvantages towards establishing its need for optimization are briefly outlined in terms of its application to the factory. Survey data is analyzed to determine the style of decision making and the problem is defined. An objective function is created in terms of decision variables of production, sales and profit over a period of time using the quantitatively available data of these parameters. A linear programming model for company is developed for profit optimization. The model equations with adequate restraints taking into account manufacturing limitations are solved using MS-Excel solver. Finally, some conclusive observations have been drawn and recommendations have been suggested.

Keywords: Profit optimization, linear programming model, simplex method, manufacturing limitation, service industries

1. Introduction

Linear Programming (LP) is a problem-solving approach developed to help managers make decisions. Numerous applications of linear programming can be found in today’s competitive business environment Anderson [1]. The term linear programming was first used by G.B. Dantzig [2] in 1947 to refer to specific problems of optimization which assume that both constraints and objective function are linear. As with other branches of Operations Research, the first applications of LP are found in military planning activities, how to distribute men, weapons, and supplies efficiently to the various fronts during World War II. (Here, the word programming means creating a plan that solves a problem; it is not a reference to computer programming.) Soon after that, LP came into wide use in industry, with the most fruitful utilization in the petroleum, petrochemical and food industries (extensive references can be found in Dantzig [2] and [3]. Linear Programming is not a new modeling technique: it has been used routinely for over forty years to describe different productive and economic systems, and also problems in scheduling and distribution. The mathematics of linear programming are well established and presented in number of books ([3],[4], [5], [6]) while computer packages for solving large LP models are well developed and widely available, e.g. (Dash Assoc., 1993). Linear programming is one specialized mathematical decision-making aid. It can be applied to many problems in the real world, not because the world is linear but because it is a powerful problem-solving technique. Here, the researches carried out by Kim [7] and Mehdipoor et al. [8] are also worth mentioning.

Linear programming, or linear optimization, is a mathematical method to achieve the minimum or maximum value of a linear function on a convex polyhedron. This convex polyhedron is, in fact, a graphical representation of some constraints as inequalities on/off functional variables. To put simply, one can achieve the best outcome (e.g. maximum profit or minimum cost) by using linear programming under specific settings and constraints. While linear programming is mainly used in management and economics, it can also be utilized for some engineering problems. Linear programming uses a mathematical model to describe the problem of concern. Thus, linear programming involves the planning of activities to obtain an optimal result, i.e. a result that reaches the specified goal best (according to the mathematical model) among all feasible alternatives. Although allocating resources to activities is the most common type of application, linear programming has numerous other important applications as well. In fact, any problem whose mathematical model fits the very general format for the linear programming model is a linear programming problem. Furthermore, a remarkably efficient solution procedure, called the simplex method, is available for solving linear programming problems of even enormous size [9]. These are some of the reasons for the tremendous impact of linear programming in recent decades [5].

As stated above, linear programming was developed as a mathematical pattern during World War II to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. The method was kept secret until 1947. After the war, many industries began using it. The founders of linear programming are: G.B. Dantzig who published the simplex method in 1947, John von Neumann who developed the theory of duality, and Leonid Kantorovich - the Russian mathematician who applied similar techniques before Dantzig, and won the Noble Prize in 1957. The Babcock and Wilcox applied the linear programming to help plan a major expansion of the company’s Tubular Products Division (TPD) in Pennsylvania. Owen [10] has also used the linear programming method to design antenna array patterns that suppress interference from certain directions.

2. Statement of the Problem

Linear programming is a set of techniques and methods inferred from mathematics and other sciences which can play an efficient role in improving the management decisions. Although it is still regarded as a new science, but it has well proved to be capable of solving problems such as production planning, allocating resources, inventory control, and advertising. Those managers who care about the best outcomes for their decisions cannot be indifferent to this.

Wijeratne and Harris [11] proposed that the linear programming model is used by the managers to determine the most economical arrangement of finance, to arrange the best times to start and finish projects, and to select projects to minimize the total net present cost of capital. Linear programming optimizes (maximizing or minimizing) a dependent variable subject to a set of independent variables in a linear relationship, given a number of linear constraints of independent variables. The value of dependent variables which is the value obtained from solving the problem, is subject to the independent variables set by the decision maker (or determined by solving the problem). The dependent variables are usually set as objective function which may be one of the economic concepts such as profit, cost, income, production, sales, distance and time, etc. The independent variables in linear programming are known as variables of unknown value, and the decision maker has to calculate the value of such variables by solving the problem [13]. In Ethiopia, most decisions were taken by government or non-governmental organizations, whether it is profitable or not for companies, manufacturing or service industries are based on trial and error. Qualitative decisions, like intuition, judgmental approaches are more dominant and the application of model based decision making like optimization techniques, e.g. linear programming models have little or no application. Hence, it is initiated by author to conduct an assessment of the application of linear programming in this particular company as a case study.

3. Objectives and Research Questions

3.1. Objectives of the Study

The main objectives of this paper are:

•To formulate a linear programming model that would suggest a viable product-mix to ensure optimum profit for Company.

•To highlight the peculiarities of using linear programming technique for the Company and prove that despite obstacles, the application of the technique in determining the product-mix of the company would be more profitable than otherwise.

•To know about the constraints of the company regarding cost, resources.

3.2. Research Questions

•How is the company currently making decision on the allocation of resources for the production of its

•products to maximize its sales and profit?

•Whether the company uses qualitative decisions or employs mathematical/statistical models or both?

•Whether the current method adopted in making decision is effective or not?

•Whether the resources available are sufficient for production of the products to satisfy the demands of the customers?

4. Significance of the Study

It helps to understand the best way of making decisions using quantitative models in order to determine its optimal product-mixes that can maximize its profits subject to the scarce resources it has. The study will provide a deep understanding and insight of the applications of linear programming models in industries and how to apply such models in practical and real world experience. To other researchers of similar interest who are willing to undertake further investigation on the topic, this research document can be used as a secondary information source.

This research paper is structured in seven sections.§1 is introduction and it concerns with background of the study and the company. § 2 – 4 deal with the statement of the problem, objectives of the study, research question, and significance of the study. §5 deals with data and methodology. Linear programming and its applications are discussed in §6. Presentation of data, analysis and results are also discussed in §6. Major findings and conclusions are given in§ 7. Finally, some recommendations are illustrated in the end.

This study was conducted for three reasons. Firstly, there was no reliable and comprehensive study to examine the role of linear programming in companies in Ethiopia. Secondly, it might pave the way forward for the company, policy makers, and financial institutions to understand the different roles of institutions in the development process. Finally, this study advances the knowledge of linear programming in decision making.

5. Data and Methodology

5.1. Method of Data Collection

In order to gather the relevant data from the company producing sulfuric acid, oleum and Aluminum sulfate utilizing partially locally available raw materials. This paper was based on primary and secondary sources of data. Especially to get information on the decision making practice of the company under study, an interview was conducted with the manufacturing manager and the sales managers of the company and data collected on the unit costs of production of the products, the unit selling price of the products and also contacted the sales and the purchasing, production and marketing managers of the company. And additionally secondary data sources were used to get accurate information.

5.2. Method of Data Analysis

Collected data were presented in a narrative form and analyzed using linear programming model. Since the purpose of this study was to develop linear programming model for the collected data from the company, the authors tried to transform the data into a linear programming model and solved the model (problem) using simplex algorithm using by applying MS-Excel solver in order to determine the optimal combination of the products of the company that can maximize its profit within the available scarce resources. Simplex algorithm was preferred over graphical approach because of this method can help to solve linear programming problems of any number of decision variables. Excel solver was preferred for accuracy purpose.

6. LPP Model and its Application

Linear Programming is a mathematical technique for generating and selecting the optimal or the best solution for a given objective function. Technically, linear programming may be formally defined as a method of optimizing (i.e. maximizing or minimizing) a linear function for a number of constraints stated in the form of linear inequalities. According to Fagoyinbo [5], Williams [12] and Wood and Dantzig [13] the problem of LP stated as that of the optimization of linear objective function of the following form:

Z = c1x1 + c2x2 (Objective function),

subject to the linear constraints:

a11 x1+ a12 x2(≤ or≥) b1,a21 x1+ a22 x2(≤ or≥) b2,…… ,

am1 x1+ am2x2(≤ or≥)bm,x1, x2(≤ or≥) 0.

6.1. The Proposed Model

The objective function and constraints were used in the following general form:

Maximize Z = P1X1 + P2X2 subject to constraints:

C11X1 + C12X2B1, C21X1 + C22X2B2, C31X1 + C32X2B3,

C41X1 + C42X2B4, C51X1 + C52X2 B5, X1, X2≥ 0,

where:

Z = total profit contribution of Aluminum sulphate and Sulphuric acid,

Pi = profit contribution coefficients expressing per unit contribution to the profit equation,

X1, X2 = the set of unknowns to be determined, i.e. the tons of Aluminum sulphate

And Sulphuric acid produced by company,

C’s = the numerical values that expressed in per unit usage of the right hand side,

B1, B2,….,B5 = the resource values which were fully utilized.

Estimates of the variables are presented in tables. The optimum values of the different brands produced by the firm shows the combination (product mix) obtained through the application of linear programming model.

6.2. Assumptions of the Model

For applying the proposed model to case of profit optimization, following assumptions were taken into consideration:

(i)Proportionality assumption: The contribution of each activity to the value of the objective function Z is proportional to the level of the activity xj, as represented by the terms cjxj in the objective function. Similarly, the contribution of each activity to the left-hand side of each functional constraint is proportional to the level of the activity xj, as represented by the terms aijxj in the constraints.

(ii)Additive assumption: Every function in a linear programming model (whether the objectives function or the function on the left-hand side of a functional constraint) is the sum of the individual contributions of the respective activities.

(iii)Divisibility assumption: Decision variables in a linear programming model are allowed to have any (real) values, including non-integer values that satisfy the functional and non-negativity constraints. Since each decision variable represents the level of some activity, it is being assumed that the activities can be run at fractional levels.

(iv)Certainty assumption: The value assigned to each parameter of a linear programming model is assumed to be a known constant.

6.3. Application and Analysis

This section deals with the presentation and analysis of the data gathered from the company. For collection of the necessary data, the last author prepared a guide questions based on its objectives and research questions. He made an effort to know whether the company applies any model for their decision making especially whether linear programming models are applicable for decision making. If decision is not based on mathematical model, then researchers tried to investigate the style of decision making of this company. Through this research it is identified that the company manufactures two major products namely: aluminum sulphate and sulphuric acid.

6.4. The Decision Approach of the Company

According to collected data of the Company authors investigated that the company has annual based sales records. In order to determine how much to manufacture for the next year the company do not use any sound mathematical or statistical decision making models. Instead it decides the quantity of its products on a simple trial and error or simple individual’s judgment. For this reason their annual sales plan and the actual sales they achieve varies every year. When it comes to the case of the applicability of linear programming model for the optimal decision of the product mixes.

Table1. Production, sales and gross profit trends for the years 2006-2012.

Year2006200720082009201020112012
Net sales8,206,62710,432,6278,341,56719,027,52930,204,05139,549,39750,845,928
Production(tons)2,499.4081,654.4042,245.2262,926.9324,285.7424,856.4987,362.096
Gross profit1,227,2413,688,0723,284,5134,160,4158,198,87213,304,12914,931,836

(Source: Annual bulletin of company, 2012/13)

According to the Annual Bulletin of the company (2012/13), it has been described as below: As compared to the design (production) capacity of the company, the actual production achievement of aluminum sulphate and sulphuric acid is on average 21.51% and 19.56% only. Even though there is an improvement in the actual sales of these items\o some degree over the past four years, compared to the capacity of the company, it did not exceed annual average sales of 20%. Though the reason for such low sales is assumed to be the decline in domestic market the major problems are:

Some users of the products were importing substitute products for their purpose. However, considering the current industry development strategy of the country and the attention given by the government for industry, the company was expecting more demand for its products in the near future. Even though the company states the above factors as causes for low demand and sales of its products, the last author identified that the annual demand for aluminum sulphate was on average 6,000 tons per annum and for sulphuric acid it was 5,000 tons per annum. This indicates that the company was not fully utilizing the currently available demand for its product. One of the cause for underutilizing the demand was the poor decision making approach used by the company. Had it used Quantitative (model based) decision making especially linear programming, it might have achieved more than what it did. According to the information gathered from the company using linear programming model (MS-Excel Solver) it is identified below that the company should produce 20tons of aluminum sulphate per day (20×300=6,000tons per year) and 6.98tons of sulphuric acid per day (6.98×300=2,094 tons per year) in order to get a gross profit of Birr107,353.17 per day (107,353.17×300= 32,205,951 per year).

Figure 1. Year wise grass profit in Birr.

6.5. LPP of the Chemical Company

A linear programming model consists of certain common components and characteristics. The model components include decision variables, an objective function, and model constraints, which consist of decision variables and parameters. Decision variables are mathematical symbols that represent levels of activity by the firm.

Data gathered from the company into a linear programming model as follows:

A chemical industry owned by the Ethiopian Government manufactures two major products, aluminum sulphate and sulphuric acid each of which passes through three different processes: reaction, filtration, and evaporation. Aluminum sulphate is a coagulant used for purification of drinking water, industrial waste water treatment, paper sizing, dyeing, pharmaceuticals, soap modification, tanning cellulose , etc. so it is highly demanded by companies like: water supply and sewerage authorities, pulp and paper factories, leather industries, textiles, food and beverages, metals, chip woods, plywood and others. Sulphuric acid is a chemical used in the production of aluminum sulphate as a raw material or as medium of production for oleum, phosphates, car batteries, pulp & paper, steel picking and textiles (brochures of the company).

According to data collection, the company was manufacturing 51.5 tons of sulphuric acid per day (51.5×300=15,450 tons per year) and only 40 tons of aluminum sulphate per day (40×300 = 12,000 tons per year). The major constraint the company states for this is demand which is at most 6,000tons for aluminum sulphate per annum and utmost 5,000 tons per annum for sulphuric acid. But in addition, availability of machine hours on 3 processes of manufacture was also constraining manufacturing of the products as given below:

Table2. Constraint of machine hours on 3 processes of manufacture.

ProductsMachine hours onDemand in tons/annum
ReactionFiltrationEvaporation
Aluminum sulphate (for 40tons per day)18846,000
Sulphuric acid (produced 51.5 tons daily)2424245,000
Total available time (assuming 300 working days per year)7,2007,2007,200 

According to the production / sales departments of the company, the production of Aluminum sulphate costing Birr 5,237.69 per ton is sold for Birr8,998.35 per ton, whereas the manufacturing of sulphuric acid costing Birr 5,708.87 per ton is sold for Birr 10,313.45 per ton. Thus, the profit earned per ton of these items is Birr 3,760.66 and Birr 4,604.58 respectively. The objective is to determine how many tons of these items should be manufactured per day to maximize the daily profit of the company operating on average of 300 days in a year.

6.6. Mathematical Formulation of LPP for the Company

The profit maximization objective of the company is mathematically expressed as:

Zmax = 3,760.66x1 + 4,604.58x2.

Decision variables are mathematical symbols that represent levels of activity.

Letx1 = the tons of aluminum sulphate manufactured per day, and

x2 = the tons of sulphuric acid manufactured per day.

The model constraints are also linear relationships of the decision variables; they represent the restrictions placed on the firm by the operating environment. Four constraints relate to the number of hours of machine time available on three processes (reaction, filtration, and evaporation); and demand also restricts the number of tons of the items that can be manufactured as presented below:

Table3. Number of hours of machine time on three processes and the demand of items.

ProductsMachine hours per ton per day*Produced/day (in ton)Profit /per ton (in Birr)
ReactionFiltrationEvaporation
Alu. Sulphate0.450.20.1203,760.66
Sulphuric acid2.152.152.1551.54,604.58
Available resource242424  

*The machine hours are roughly converted to per day basis for simplicity of model formulation and calculation while company officials suggested that it is sometimes not logical to make such conversion.

The constraints of the company are expressed as follows:

Maximize Zmax = 3,760.66x1 + 4,604.58x2,

subject to:

0.45x1 + 2.15x2≤24 hrs. (machine hrs. on reaction),

0.2x1 +2.15x2≤24 hrs. (machine hrs. on filtration),

0.1x1 + 2.15x2≤24 hrs. (machine hrs. on evaporation),

x1≤20 tons (demand for aluminum sulphate per day),

x2≤51.5 (sulphuric acid produced per day),

x1, x2≥0 (non-negativity).

6.7. Solution of the LPP Using MS-Excel Solver

To apply the MS-Excel Solver, first we translate the linear programming model into its standard form. Thus, the above model, written in the standard form, becomes.

Zmax = 3,760.66x1+ 4,604.58x2 + 0s1 +0s2 +0s3 +0s4 +0s5,

subject to:

0.45x1 + 2.15x2 +s1 =24 hrs., 0.2x1 +2.15x2 +s2=24hrs.,

0.1x1+ 2.15x2+s3 =24 hrs.,

x1+s4=20 tons, x2+s5= 51.5 tons,

x1, x2,s1, s2,…,s5≥0 (non-negativity).

Eliminating x2 from the first three equations there also result the equations:

0.25 x1 +s1 =s2, 0.35 x1 + s1 =s3, 0.1 x1 + s2= s3.

There are five equations involving seven unknown variables. So, their basic solutions can be obtained by assigning zero values to any (additional) 2unknowns. Setting s1=s2 = 0 a basic and feasible solution is

x1= 0, x2=24/2.15 = 11.16, s3 = 0,s4= 20, s5 = 40.34;

that determines Z = 51,400.08. In the following, we workout all basic solutions and compute the values of Z:

Table 4. Solution of the LPP for the Chemical Company by MS-Excel Solver.

x1x2s1s2s3s4s5Is soln. feasibleZ
011.160002040.34Yes51,400.08
2015/2.15 =6.98"57044.52"107,353.17
— 192.7251.5"< 0<0212.720No 
011.160002040.34Yes51,400.08
2020/2.15 = 9.3— 5"2042.2No 
— 433.251.5<0"< 0453.20" 
2022/2.15 = 10.23— 7— 20041.27" 
— 867.2551.5303.5486.73"887.250" 
20"<0<0<00"" 

Thus, the optimal feasible solution is x1= 20 tons of aluminum sulphate per day, x2 = 6.98 tons of sulphuric acid per day, s1=0, s2=5 hrs., s3=7 hrs., s4=0, s5=44.52 tons, yielding the maximum profit Zmax= Birr 107,353.17 per day.

6.8. Result Analysis

Company produces 20tons of aluminum sulphateperday (20tons/day×300working days = 6,000 tons/annum) and 6.98 tons of sulphurc acid per day (6.98tons/day×300 working days = 2,094tons/annum) in order to get a maximum daily profit of Birr107,353.17 per day (Birr107,353.17 per day ×300working days =Birr32,205,951per annum). In this way, the company is left with an idle filtration and evaporation times of 5 and 7 hours per day and unutilized demand for sulphuric acid of 44.52tons per day but the demand for aluminum sulphate is fully utilized.

7. Conclusive Observations

Based on the data gathered and the major findings of the research, the following conclusions were drawn:

(i)Linear programming model is applied for profit optimization of the Ethiopian chemical company located in Adama (Ethiopia) and the maximum profit Birr 107,353.17 per day for company was found.

(ii)The company was left with an idle filtration and evaporation time of 5 and 7 hours per day respectively and un-utilizing demand for sulphuric acid of 44.52 tons per day but the demand for aluminum sulphate was fully utilized.

(iii)Even though the company has an annual record of its production and sales volume it was not employing any quantitative model to forecast for their production volume and sales; rather the company was employing a simple trial and error and subjective estimation. It led the company to misunderstand the existing demand for their products and to produce less than its capacity and even than the existing local demand.

(iv)The LPP model can be used for other companies for its profit maximization.

Recommendations

Based on the findings and the conclusions of the study, we suggest the following recommendations:

(i)For companies to forecast their production capacity and sales volume different quantitative models like: linear regression, linear trend, nonlinear regression, nonlinear trend, etc. available. Company has annual production and sales records but the company was not employing any mathematical or statistical models for its production or sales forecast rather it depends on a simple trial and error. The company should employ linear regression, linear trend and/or nonlinear regression and trend models to forecast its production capacity and sales.

(ii)On the major constraint that is considered by the company was demand for its products. In the 2012/13 annual bulletin of the company, it was stated that some customers of company were importing substitute products. This indicates that there was a quality and supply problem. Therefore, company should work on improving the qualities of its products to meet customer expectations and to search for other customer groups who can use the products beyond the current target markets.

(iii)It is clear that model based decision is important for its accuracy and objectivity. But such decision making approach was not widely used in practice. Qualitative decisions like subjective estimation, intuition and trial and error were commonly used by company. It is eye opening concern to the policy makers of company to shift the model based decision making styles in general.

References

  1. Anderson, D.R.; Sweeney, D.J.; Williams, T.A.; Camm, J.D.; and Kipp, Martin:An Introduction to Management Science: Quantitative Approaches to Decision Making, Revised 13th ed., South-Western Cengage Learning, 2012.
  2. Dantzig G.B., Programming of interdependent activities: II Mathematical Model, Econometrica, 17 (3), pp. 200–211, 1949. doi:10.2307/1905523.
  3. Dantzig, G.B.: Compact basis triangularization for the simplex method, R.L. Graves and P. Wolfe (eds.), Recent Advances in Mathematical Programming, McGraw-Hill, New York, pp.125–132, 1963.
  4. Drayer, W. and Seabury, S.: Linear programming - A case example, strategy & leadership, 3(5), pp.24-26, 1975.
  5. Fagoyinbo, I.S.: Compendious text on quantitative techniques for professionals, Ilaro, Nigeria, Jombright Productions, 2008.
  6. Frederick, H.S. and Lieberman, J.G.: Introduction to Operations Research, McGraw-Hill, Operations research - 1214 pages, 2001.
  7. Kim, C.: Parametrizing an activity vector in linear programming, Operations Research, 19, pp.1632-1646, 1971.
  8. Mehdipoor, E.; Sadr-ol-ashraafi, S.M. and Karbaasi, A.: A comparison of canonical linear programming techniques, Meaty Chicken’ Feed Farming with Linear Programming Models, Scientific-Research Magazine of Agriculture, 12(3), 2006.
  9. Misra, R.B.: Numerical Analysis for solution of ordinary differential equations, Lambert Academic Publishers, Saarbrücken (Germany), 2010, ISBN 978-3-8433-8489-6.
  10. Owen, P. and Mason, J.C.: The use of linear programming the design of antenna pattern with prescribed nulls and other constraints, compel: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering, 3(4), pp.201-215, 1984.
  11. Wijeratne, N. and Harris, F.C.: Capital budgeting using a linear programming model, International Journal of Operations & Production Management, 4(2), pp.49-64, 1984.
  12. Williams, N.: Linear and non-linear programming in industry, Sir Isaac Pitman & Sons, Ltd., London.Garifinkel (1963). A solution of the Goddard problem, Journal of SIAM Control, 1(3), pp.349–368, 1963.
  13. Wood, M.K. and Dantzig, G.B.: Programming of interdependent activities: I General Discussion. Econometrica, 17 (3/4): 193–91949. JSTOR1905522.

OR-Notes

J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.


Linear programming solution examples

Linear programming example 1997 UG exam

A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.

At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours.

The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximise the combined sum of the units of X and the units of Y in stock at the end of the week.

  • Formulate the problem of deciding how much of each product to make in the current week as a linear program.
  • Solve this linear program graphically.

Solution

Let

  • x be the number of units of X produced in the current week
  • y be the number of units of Y produced in the current week

then the constraints are:

  • 50x + 24y <= 40(60) machine A time
  • 30x + 33y <= 35(60) machine B time
  • x >= 75 - 30
  • i.e. x >= 45 so production of X >= demand (75) - initial stock (30), which ensures we meet demand
  • y >= 95 - 90
  • i.e. y >= 5 so production of Y >= demand (95) - initial stock (90), which ensures we meet demand
  • The objective is: maximise (x+30-75) + (y+90-95) = (x+y-50)
    i.e. to maximise the number of units left in stock at the end of the week

    It is plain from the diagram below that the maximum occurs at the intersection of x=45 and 50x + 24y = 2400

    Solving simultaneously, rather than by reading values off the graph, we have that x=45 and y=6.25 with the value of the objective function being 1.25


    Linear programming example 1995 UG exam

    The demand for two products in each of the last four weeks is shown below.

    Week 1 2 3 4 Demand - product 1 23 27 34 40 Demand - product 2 11 13 15 14

    Apply exponential smoothing with a smoothing constant of 0.7 to generate a forecast for the demand for these products in week 5.

    These products are produced using two machines, X and Y. Each unit of product 1 that is produced requires 15 minutes processing on machine X and 25 minutes processing on machine Y. Each unit of product 2 that is produced requires 7 minutes processing on machine X and 45 minutes processing on machine Y. The available time on machine X in week 5 is forecast to be 20 hours and on machine Y in week 5 is forecast to be 15 hours. Each unit of product 1 sold in week 5 gives a contribution to profit of £10 and each unit of product 2 sold in week 5 gives a contribution to profit of £4.

    It may not be possible to produce enough to meet your forecast demand for these products in week 5 and each unit of unsatisfied demand for product 1 costs £3, each unit of unsatisfied demand for product 2 costs £1.

    • Formulate the problem of deciding how much of each product to make in week 5 as a linear program.
    • Solve this linear program graphically.

    Solution

    Note that the first part of the question is a forecasting question so it is solved below.

    For product 1 applying exponential smoothing with a smoothing constant of 0.7 we get:

    M1 = Y1 = 23
    M2 = 0.7Y2 + 0.3M1 = 0.7(27) + 0.3(23) = 25.80
    M3 = 0.7Y3 + 0.3M2 = 0.7(34) + 0.3(25.80) = 31.54
    M4 = 0.7Y4 + 0.3M3 = 0.7(40) + 0.3(31.54) = 37.46

    The forecast for week five is just the average for week 4 = M4 = 37.46 = 31 (as we cannot have fractional demand).

    For product 2 applying exponential smoothing with a smoothing constant of 0.7 we get:

    M1 = Y1 = 11
    M2 = 0.7Y2 + 0.3M1 = 0.7(13) + 0.3(11) = 12.40
    M3 = 0.7Y3 + 0.3M2 = 0.7(15) + 0.3(12.40) = 14.22
    M4 = 0.7Y4 + 0.3M3 = 0.7(14) + 0.3(14.22) = 14.07

    The forecast for week five is just the average for week 4 = M4 = 14.07 = 14 (as we cannot have fractional demand).

    We can now formulate the LP for week 5 using the two demand figures (37 for product 1 and 14 for product 2) derived above.

    Let

    x1 be the number of units of product 1 produced

    x2 be the number of units of product 2 produced

    where x1, x2>=0

    The constraints are:

    15x1 + 7x2 <= 20(60) machine X

    25x1 + 45x2 <= 15(60) machine Y

    x1 <= 37 demand for product 1

    x2 <= 14 demand for product 2

    The objective is to maximise profit, i.e.

    maximise 10x1 + 4x2 - 3(37- x1) - 1(14-x2)

    i.e. maximise 13x1 + 5x2 - 125

    The graph is shown below, from the graph we have that the solution occurs on the horizontal axis (x2=0) at x1=36 at which point the maximum profit is 13(36) + 5(0) - 125 = £343


    Linear programming example 1994 UG exam

    A company is involved in the production of two items (X and Y). The resources need to produce X and Y are twofold, namely machine time for automatic processing and craftsman time for hand finishing. The table below gives the number of minutes required for each item:

    Machine time Craftsman time Item X 13 20 Y 19 29

    The company has 40 hours of machine time available in the next working week but only 35 hours of craftsman time. Machine time is costed at £10 per hour worked and craftsman time is costed at £2 per hour worked. Both machine and craftsman idle times incur no costs. The revenue received for each item produced (all production is sold) is £20 for X and £30 for Y. The company has a specific contract to produce 10 items of X per week for a particular customer.

    • Formulate the problem of deciding how much to produce per week as a linear program.
    • Solve this linear program graphically.

    Solution

    Let

    • x be the number of items of X
    • y be the number of items of Y

    then the LP is:

    maximise

    • 20x + 30y - 10(machine time worked) - 2(craftsman time worked)

    subject to:

    • 13x + 19y <= 40(60) machine time
    • 20x + 29y <= 35(60) craftsman time
    • x >= 10 contract
    • x,y >= 0

    so that the objective function becomes

    maximise

    • 20x + 30y - 10(13x + 19y)/60 - 2(20x + 29y)/60

    i.e. maximise

    subject to:

    • 13x + 19y <= 2400
    • 20x + 29y <= 2100
    • x >= 10
    • x,y >= 0

    It is plain from the diagram below that the maximum occurs at the intersection of x=10 and 20x + 29y <= 2100

    Solving simultaneously, rather than by reading values off the graph, we have that x=10 and y=65.52 with the value of the objective function being £1866.5


    Linear programming example 1992 UG exam

    A company manufactures two products (A and B) and the profit per unit sold is £3 and £5 respectively. Each product has to be assembled on a particular machine, each unit of product A taking 12 minutes of assembly time and each unit of product B 25 minutes of assembly time. The company estimates that the machine used for assembly has an effective working week of only 30 hours (due to maintenance/breakdown).

    Technological constraints mean that for every five units of product A produced at least two units of product B must be produced.

    • Formulate the problem of how much of each product to produce as a linear program.
    • Solve this linear program graphically.
    • The company has been offered the chance to hire an extra machine, thereby doubling the effective assembly time available. What is the maximum amount you would be prepared to pay (per week) for the hire of this machine and why?

    Solution

    Let

    xA = number of units of A produced

    xB = number of units of B produced

    then the constraints are:

    12xA + 25xB <= 30(60) (assembly time)

    xB >= 2(xA/5)

    i.e. xB - 0.4xA >= 0

    i.e. 5xB >= 2xA (technological)

    where xA, xB >= 0

    and the objective is

    maximise 3xA + 5xB

    It is plain from the diagram below that the maximum occurs at the intersection of 12xA + 25xB = 1800 and xB - 0.4xA = 0

    Solving simultaneously, rather than by reading values off the graph, we have that:

    xA= (1800/22) = 81.8

    xB= 0.4xA = 32.7

    with the value of the objective function being £408.9

    Doubling the assembly time available means that the assembly time constraint (currently 12xA + 25xB <= 1800) becomes 12xA + 25xB <= 2(1800) This new constraint will be parallel to the existing assembly time constraint so that the new optimal solution will lie at the intersection of 12xA + 25xB = 3600 and xB - 0.4xA = 0

    i.e. at xA = (3600/22) = 163.6

    xB= 0.4xA = 65.4

    with the value of the objective function being £817.8

    Hence we have made an additional profit of £(817.8-408.9) = £408.9 and this is the maximum amount we would be prepared to pay for the hire of the machine for doubling the assembly time.

    This is because if we pay more than this amount then we will reduce our maximum profit below the £408.9 we would have made without the new machine.

    Linear programming example 1988 UG exam

    Solve

    minimise

    subject to

      a + b >= 11

      a - b <= 5

      c - a - b = 0

      7a >= 35 - 12b

      a >= 0 b >= 0 c >= 0

    Solution

    To solve this LP we use the equation c-a-b=0 to put c=a+b (>= 0 as a >= 0 and b >= 0) and so the LP is reduced to

    minimise

      4a + 5b + 6(a + b) = 10a + 11b

    subject to

      a + b >= 11

      a - b <= 5

      7a + 12b >= 35

      a >= 0 b >= 0

    From the diagram below the minimum occurs at the intersection of a - b = 5 and a + b = 11

    i.e. a = 8 and b = 3 with c (= a + b) = 11 and the value of the objective function 10a + 11b = 80 + 33 = 113.



    Linear programming example 1987 UG exam

    Solve the following linear program:

    maximise 5x1 + 6x2

    subject to

    x1 + x2 <= 10

    x1 - x2 >= 3

    5x1 + 4x2 <= 35

    x1 >= 0

    x2 >= 0

    Solution

    It is plain from the diagram below that the maximum occurs at the intersection of

    5x1 + 4x2 = 35 and

    x1 - x2 = 3

    Solving simultaneously, rather than by reading values off the graph, we have that

    5(3 + x2) + 4x2 = 35

    i.e. 15 + 9x2 = 35

    i.e. x2 = (20/9) = 2.222 and

    x1 = 3 + x2 = (47/9) = 5.222

    The maximum value is 5(47/9) + 6(20/9) = (355/9) = 39.444



    Linear programming example 1986 UG exam

    A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week.

    Formulate this problem as a linear programming problem and solve it graphically.

    Solution

    Variables

    Let

    xT = number of tables made per week

    xC = number of chairs made per week

    Constraints

    6xT + 3xC <= 40

    xC >= 3xT

    (xC/4) + xT <= 4

    Objective

    maximise 30xT + 10xC

    The graphical representation of the problem is given below and from that we have that the solution lies at the intersection of

    (xC/4) + xT = 4 and 6xT + 3xC = 40

    Solving these two equations simultaneously we get xC = 10.667, xT = 1.333 and the corresponding profit = £146.667



    0 thoughts on “Case Study About Linear Programming Examples

    Leave a Reply

    Your email address will not be published. Required fields are marked *