QUME507_M4

QUME 507 Module 4: Linear Programming

In Topic 4.1 we will study how linear programming provides methods to identify the amount of optimal resources subject to constraints. Linear programming problems will be formulated and solved with mathematical and graphical tools. Cases where linear programming problems are not feasible, unlimited, redundant and where alternative solutions exist will be analyzed. Also, the student will be taught to solve linear programming problems using programs such as Excel QM and/or QM for Windows. 4.1 Linear Programming Models Many business management decisions involve trying to make the most effective use of limited resources such as: machinery, labor, money, time, warehouse space, raw materials. Linear programming (LP) is a widely used mathematical modeling technique designed to help managers plan and make decisions regarding resource allocation. It belongs to the broader field of mathematical programming. In this sense, programming refers to modeling and mathematically solving a problem (Render et al., 2018). Numerous applications of linear programming can be found in today's competitive business environment (Anderson et al., 2016). Properties of Linear Programs All LP problems have 4 properties in common 1. All problems seek to maximize or minimize some amount (the objective function) 2. The presence of restrictions that limit the degree to which we can pursue our goal. 3. There must be alternative courses of action to choose from 4. The objective and limitations on the problems must be expressed in terms of linear equations or inequalities. Linear Programming Assumptions The following are the assumptions of linear programming: 1. Conditions of certainty exist and the numbers in the objectives and limitations are known with certainty and do not change during the period under study.

2. Proportionality exists in the objective and limitations. 3. Division is assumed in which the total of all activities is equal to the sum of the individual activities 4. Divisibility is assumed in that the solutions do not have to be integers 5. All answers or variables are non-negative. Formulation of CP Programs The formulation of a linear program implies the development of a mathematical model that represents the administrative problem. Therefore, in order to formulate a linear program, it is necessary to fully understand the administrative problem it faces. Once it is understood, it is possible to begin to develop the mathematical formulation of the problem. The steps in formulating a linear program are as follows: 1. Fully understand the administrative problem being faced. 2. Identify the objective and constraints. 3. Define the decision variables. 4. Use decision variables to write mathematical expressions of the objective function and constraints. One of the most common applications of PL is the problem of product mix in companies. To be able to assess the situation, the condition is that two or more products are produced with limited resources, such as personnel, machines and raw materials. It should be noted that the benefit that companies seek to maximize is based on the profit contribution per unit of each product. The profit that the company seeks to maximize is based on the profit contribution per unit of each product. The reality is that companies are interested in determining how many units of each product they should produce to maximize total profit given their limited resources. Let's see an example: Flair Furniture Company Step 1: Fully understand the administrative problem being faced.

Flair Furniture produces low-cost tables and chairs. The manufacturing process for each is similar as both require a certain amount of hours of carpentry work and in the painting and varnishing department. Each table requires 4 hours of carpentry and 2 hours of painting and varnishing. Each chair requires 3 hours of carpentry and 1 hour of painting and varnishing. There are 240 hours of carpentry time available and 100 hours of painting and varnishing. Each table produces a profit of $70 and each chair a profit of $50. The company wants to determine the best combination of tables and chairs to manufacture for maximum profit. The data is shown in Table 1 Table 1. Flair Furniture Company Data Hours required to produce 1 Unit Department (t) (c) Available hours Carpentry Months Chairs this week Painting and 3 varnishing 4 240 Profit per unit 21 100 $70 $50 Step 2: Define the objective and restrictions Summarizing, the goal is: To maximize the benefit The restrictions are: The hours of carpentry time used cannot exceed 240 hours per week. Hours of painting and varnishing cannot exceed 100 hours per week. Third step: Define the variables The decision variables that represent the actual decisions we will make are: T = number of tables to be produced per week C = number of chairs to be produced per week Fourth step: Use decision variables to write mathematical expressions of the target function and constraints. The entire problem is expressed mathematically as:

4T + 3C ≤ 240 (woodworking restriction) 2T + 1C ≤ 100 (paint and varnish restriction) T ≥ 0 (first non-negativity restriction) C ≥0 (second non-negativity restriction) Graphic Solution to a PL Problem The easiest way to solve a small LP problem is with the graphical solution approach. The graphical method only works when there are only two decision variables. When there are more than two variables, a more complex approach is needed, as it is not possible to plot the solution on a two-dimensional graph. The first step in solving the problem is to identify a set or region of feasible solutions. To do this, each constraint equation is plotted on a graph. We begin by graphing the equality portion of the constraint equations. 4T + 3C = 240 Then we solve the intersections of the axis and draw the line. When we clear the variables we see that: When Flair doesn't produce boards, the constraint of carpentry is: 4 (0) + 3C = 240 3C = 240 C = 80 Same for no chairs 4T + 3 (0) = 240 4T = 240 T = 60 This line is shown in the graph in Figure 1.

Figure 1. Graph of the woodworking constraint equation: Adapted from Render, B., Stair, R. M., Hanna, M. E. & Hale, T. S. (2018). Quantitative Analysis for Management. (13 ed). Pearson. It should be noted that in the problems of PL we want to satisfy all the restrictions at the same time. The feasible region of a CP problem is the region where all restrictions are satisfied. Any point in the region would be a feasible solution to the Flair Furniture problem and any point outside the shaded area would represent a non-feasible solution. In the example of Fair Furniture, to produce tables and chairs, both departments must be used. A solution needs to be found that satisfies both restrictions simultaneously. In figure 2 a graph is shown that represents the region of feasible solution for the problem of the company Flair Furniture. The feasible region (or feasible solution area) is where all restrictions are met. Any point within this region is a feasible solution. Any point outside the region is an unworkable solution. Figure 2. Feasible solution region Flair Furniture

Adapted from Render, B., Stair, R. M., Hanna, M. E. & Hale, T. S. (2018). Quantitative Analysis for Management. (13 ed). Pearson. Isoprofit Line Solution Method Once the feasible region has been charted, we must find the optimal solution from among the many possible solutions. The fastest way to do this is to use the isoprofit line method. Start by identifying a small gain value and plot the objective function. Once the feasible region has been charted, we must find the optimal solution from among the many possible solutions. The fastest way to do this is to use the isoprofit line method. Start by identifying a small gain value and plot the objective function. For Flair Furniture, a profit of $2,100 is chosen. From this, the objective function is then $ 2,100 = 70T + 50C By solving for the axis intersections, the graph can be drawn. Obviously, this is not the best possible solution. More graphs can be created using larger profits. The further away from the origin, the greater the profit. The highest profit ($4,100) will be generated when the isoprofit line passes through the point (30, 40) Figure 3 shows the graph of the optimal solution of the company Flair Furniture Figure 3. Optimal solution Flair Furniture

Adapted from Render, B., Stair, R. M., Hanna, M. E. & Hale, T. S. (2018). Quantitative Analysis for Management. (13 ed). Pearson. When calculating the profit at this point: Profit = 70T + 50C = 70(30) + 50(40) = $4,100 So by producing 30 tables and 40 chairs you get the maximum profit of $4,100. Summary Steps: Isoprofit Method 1. Chart all restrictions and find the region feasible. 2. Select a specific utility (or cost) line and plot the graph to find the slope. 3. Move the line of the objective function in the direction of increasing utility (or decreasing cost), keeping the slope. The last point touched on in the feasible region is the optimal solution. 4. Determine the values of the decision variables at this last point and calculate the utility (or cost). Corner Point Method The second approach to solving LP problems employs the corner point method. It involves looking at the benefit at each corner point of the feasible region. The mathematical theory behind LP is that the optimal solution must be at one of the corner points, or end points, in the feasible region. For Flair Furniture, the feasible region is a

four-sided polygon with four corner points identified as 1, 2, 3 and 4 on the graph shown in Figure 4. Figure 4. Four corner points of the feasible region Adapted from Render, B., Stair, R. M., Hanna, M. E. & Hale, T. S. (2018). Quantitative Analysis for Management. (13 ed). Pearson. As you can see, the following is calculated: Point: (T = 0, C = 0) Profit = $70(0) + $50(0) = $0 Point: (T = 0, C = 80) Profit = $70(0) + $50(80) = $4,000 Point: (T = 50, C = 0) Profit = $70(50) + $50(0) = $3,500 Point: (T = 30, C = 40) Profit = $70(30) + $50(40) = $4,100 Since 3 point gives the highest profit, this is the optimal solution. Summary Steps: Corner Point Method 1. Chart all restrictions and find the region feasible. 2. Find the corner points of the feasible region. 3. Calculate the utility (or cost) at each of the feasible corner points. 4. Select the corner point with the best value of the target function determined in step 3.

Let's look at the application in the QM for Windows program: Step 1 When the program is opened, select Linear Programming from the menu on the left. When you open the screen, enter the number of restrictions and variables. Check that the program is to be maximized and press OK. The objective Enter the is to maximize number of restrictions and variables Step 2 Enter the data according to the equations. Remember to check the plus and minus signs. Enter the data

Step 3 Press the Solutions button. Then press links to see the graph. Press solutions button Step 4 The results are displayed in the left menu. Optimal solution Sensitivity Analysis After finding an optimal solution the following question may arise: How sensitive is the optimal solution to changes in utilities, resources or other input parameters? One of the

resources is sensitivity analysis. An important function of sensitivity analysis is to allow managers to experiment with input parameter values. There are two methods for determining how sensitive an optimal solution is to change. The first is simply a method of trial and error, which usually involves solving the entire problem, preferably by computer. The other is post-optimality analysis, which means examining the changes after the optimal solution has been reached. Below, let's look at the example of High Note Sound using the Excel QM program. In the analysis we must know what is slack and surplus. The slack is the amount of a resource that is not used. For a restriction less than or equal to: Slack = amount of available resources - amount of resources used. On the other hand, the surplus is used with a constraint greater than or equal to indicate the amount by which the right side of the constraint is exceeded. Surplus = actual quantity - minimum quantity Let's see the application with the previous example of Flair Furniture with the program Excel QM. Step 1 When the program is opened, select Linear Programming from the menu on the left. When you open the screen, enter the number of restrictions and variables. Check that the program is to be maximized and press OK. The objective is to maximize Enter the number of restrictions and variables Step 2

In the template, as in QM for Windows, enter the data in the boxes. When the results will appear on the first screen you will see the slack or excess, as applicable. Slack/Surplus Step 3 To perform the sensitivity analysis, in the menu look for data and then click on the button. When the screen opens press SOLVE

Step 4 When the screen appears, choose Sensitivity and press OK. Step 5 In another Excel sheet you will obtain 2 reports. One identified as Sensivity Report and one identified as Limits The values on the right side of the restrictions often represent resources available to the company (R H Side). The resources could be working hours or machine time, or perhaps money or available production materials. In this case it is the hours available.

To see video with explanation of the High Note Sound case you can access https://youtu.be/i_15epNIeLw DeBauche, G. (3 de noviembre de 2016). Linear Programming: Sensitivity Analysis. [Video]. Taken from https://youtu.be/i_15epNIeLw -------------------------------------------------------------------------------- Introduction to Topic 4.2 In Topic 4.1 we discussed the models of linear programming. In Topic 4.2 we will be looking at its application in some of the business areas such as marketing, manufacturing and finance. In addition, these techniques will be used in manufacturing and transportation scenarios, among other industries. These linear programming skills will be applied by teaching the student to solve applied linear programming problems using the Excel program, as well as any other that the teacher considers relevant. 4.2 Application of Linear Programming Models Marketing Application Linear programming models have been used in the field of advertising as a decision aid in selecting an effective media mix. Media selection problems in this area can be addressed with LP from two perspectives: 1. Maximize audience exposure 2. Minimize advertising costs Media selection problems can be addressed with CP from two approaches. The objective would be to maximize audience exposure or minimize advertising costs. Let's look at the example of the company Win Big Gambling. Win Big Gambling Example First step: The Win Big Gambling Club promotes gambling on tours from a large city in the Midwest of the United States to casinos in the Bahamas. The club has a budget of up to $8,000 per week for local advertising. The money will be allocated among four media outlets: television spots, newspaper ads and two types of radio commercials. The goal of Win Big is to reach the highest potential audience possible, using different media.

Table 1 shows the number of potential players exposed through an advertisement in each of the four media. It also provides the cost per ad placed and the maximum number that can be purchased per week. Table 1. Advertising Options Medium Audience Cost per ad $ Maximum reached per 800 number of ads per week minute 12 TV spot [ (1 5,000 minute) Daily newspaper 8,500 925 5 (full page ad) Radio spot (30 2,400 290 25 seconds, prime 2,800 380 20 time) Radio spot (1 minute, afternoon) Adapted from Render, B., Stair, R. M., Hanna, M. E. & Hale, T. S. (2018). Quantitative Analysis for Management. (13 ed). Pearson. Second step: Objective: Maximize the number of people (audience) exposed Restrictions: 1. No more than 12 commercials can be placed on TV. 2. No more than 5 newspaper ads can be used. 3. No more than 25 30-second radio commercials can be used. 4. No more than 20 1-minute commercials can be used on radio. 5. Total amount spent must not exceed $8,000.

6. The total number of radio commercials must be at least 5. 7. The total amount spent on radio commercials must not exceed $1,800 Third step: The decision variables are defined. The decisions that are made are the number of commercials of each type that will be hired. Once they are known, they can be used to calculate the amount spent and the number of people exposed. X1 = number of 1-minute TV spots in each week X2 = number of 1-page ads in the newspaper in each week X3 = number of 30-second radio spots in each week X4 = number of 1-minute radio spots in the afternoon each week Fourth step: Write the mathematical expressions for the objective and the constraints that were identified. The non-negativity restrictions are also explicitly stated. Objective: Maximize audience coverage = 5,000X1 + 8,500X2 + 2,400X3 + 2,800X4 Subject to: X1 ≤ 12 (maximum of TV spots / week) X2 ≤ 5 (maximum of newspaper ads / week) X3 ≤ 25 (maximum 30s radio spots per week) X4 ≤ 20 (1 min max spots in radius>week) 800X1 + 925X2 + 290X3 + 380X4 ≤ $ 8,000 (weekly advertising budget) X3 + X4 ≥ 5 (minimum of contracted radio spots) 290X3 + 380X4 ≤ $ 1,800 (maximum dollars spent on radio) X1, X2, X3, X4 ≥ 0 Fifth Step: Let's see your application in the QM for Windows program. This problem can also be solved with the Excel QM program.

Step 1 Enter the number of constraints and variables and identify the objective. In this case it is to maximize the audience. The objective is to maximize Enter the number of restrictions and variables Step 2 A blank template will appear. Enter the data and press the Solve key. The results will appear as shown: We see that the solution is: 1.97 TV spots, 5 newspaper ads, 6.2 30-second radio spots and 0 1-minute radio spots. This produces an exposed audience of 67,240 contacts. As X1 and X3 are fractions, they are rounded to 2 and 6, respectively.

Manufacturing Application To see the application of the programming model in the manufacturing area we will see the example of the company Fifth Avenue Industries. Fifth Avenue Industries Examples: First step Fifth Avenue Industries, a well-known local manufacturer of men's clothing, produces four varieties of ties. One is an expensive pure silk tie, another is made of polyester, yet another is a polyester/cotton blend, and the fourth is a silk/cotton blend. Table 2 illustrates the cost and availability (by monthly production planning period) of the three materials used in the production process. Table 2. Cost & Availability: Fifth Avenue Industries MATERIAL Cost per Yard ($) Material available per month (Yards) Silk 24 1,200 Polyester 6 3,000 Cotton 9 1,600 The variables are defined as: X1 number of silk ties produced per month X2 number of polyester ties X3 number of ties of the mixture 1, polyester and cotton X4 number of ties of the mixture 2, cotton and silk Table 3 summarizes the contract demand for each of the four styles of tie, the sales price per tie and the fabric requirements for each variety. Fifth Avenue's goal is to maximize its monthly profit. You must decide on the policy for product mix. Table 3. Fifth Avenue Data

Variety Selling Monthly Monthly Material Material of ties price contract demand required requirements per tie $ minimum per tie All silk (Yards) 19.24 5,000 7,000 0.125 100% silk All 8.70 10,000 14,000 0.08 100% polyester 13,000 16,000 0.10 polyester 50% polyester Half 9.52 5,000 8,500 0.11 + 50% cotton polyester half 60% silk + cotton 40% cotton Poly- 10.64 cotton blend 2 First the company must establish the profit per tie: 1. Each silk tie (X1) requires 0.125 yards of silk, at a cost of $24.00 per yard. Therefore, the cost of material per tie is $3.00. The selling price is $19.24 per silk tie, which gives a net profit of $16.24. 2. Each polyester tie (X2) requires 0.08 yards of polyester, at a cost of $6 per yard. Therefore, the material cost per tie is $0.48. The selling price is $8.70, which leaves a net profit of $8.22 per polyester tie. 3. Each polyester and cotton (X3) tie (blend 1) requires 0.05 yards of polyester, at a cost of $6 per yard, and 0.05 yards of cotton, at $9 per yard, at a cost of $0.30 $0.45 $0.75 per tie. The selling price is $9.52, leaving a net profit of $8.77 per polyester and cotton tie.

4. Performing similar calculations we will show that each silk and cotton (X4) tie (mix 2) has a material cost of $1.98 and a profit of $8.66. Let's see the calculations in Table 4. Table 4. Calculations: Fifth Avenue Variety of Selling Material Cost of Cost per Profit per ties price required per material per tie $ Tie$ per tie tie (Yards) yard $ $ All silk $19.24 0.125 $24 $3.00 $16.24 All polyester $8.70 0.08 $6 $0.48 $8.22 Half $9.52 0.05 $6 $0.30 polyester- 0.05 half cotton $9 $0.45 $8.77 Poly-cotton 10.64 0.06 $24 $1.44 blend 2 0.06 $9 $0.54 $8.66 Objective function Maximize profit = $ 16.24X1 + $ 8.22X2 + $ 8.77X3 + $ 8.66X4 Subject to 0.125X1 + 0.066X4 ≤ 1200 (silk yards) 0.08X2 + 0.05X3 ≤ 3,000 (polyester yards) 0.05X3 + 0.44X4 ≤ 1,600 (cotton yards) X1 ≥ 5,000 (minimum contract for silk) X1 ≤ 7,000 (minimum contract)

X2 ≥ 10,000 (minimum contract for all polyester) X2 ≤ 14,000 (maximum contract) X3 ≥ 13,000 (minimum contract for mix 1) X3 ≤ 16,000 (maximum contract) X4 ≥ 5,000 (minimum contract for mix 2) X4 ≤ 8,500 (maximum contract) Solve by QM for Windows As in the previous exercise, when you open the program, choose Linear Programming. Enter the number of constraints and variables and identify that it is a maximizing exercise. Then enter the data according to the equations formulated for each constraint and press SOLVE.

You will obtain the results as shown below. As shown in the results, the company is well placed to produce 5,112 pure silk ties each month; 14,000 polyester ties; 16,000 of the polyester/cotton blend 1; and 8,500 of the silk/cotton blend 2. This generates a profit of $412,028 per production period. Finance Application To see the application of the programming model in the area of finance we will see the example of the company International City Trust (ICT) International City Trust (ICT) Example: First step A problem often encountered by managers of banks, mutual funds, investment services and insurance companies is selecting specific investments from a wide variety of alternatives. The overall objective of the manager is usually to maximize the expected return on the investment, given a set of legal, political, or risk restrictions. International City Trust (ICT) invests in short-term trade credits, corporate bonds, gold reserves and construction loans. To encourage a diversified portfolio, the board of directors has placed limits on the amount that can be committed to any one type of

investment. ICT has $5 million available for immediate investment and wants to do two things: 1). maximize the return on the investment made for the next six months and 2) meet the diversification requirements as stipulated by the board of directors. Details of the investment possibilities are given in Table 5 Investment Interest Maximum investment Trade credit 7 ($ Millons) Corporate bonds 11 1.0 2.5 Gold stocks 19 1.5 Construction loans 15 1.8 In addition, the council specifies that at least 55% of the funds must be invested in gold reserves and construction loans, and at least 15% must be invested in trade credits. By formulating this as a linear program, the goal is to maximize return. There are four separate restrictions that limit the maximum amount in each investment option to the amount. The total amount in gold reserves and construction loans should be at least 55% of the total invested The total amount invested in commercial loans must be at least 15% of the total invested. The total amount invested must not exceed $5 million (may be less). Variables X1 dollars invested in trade credit X2 dollars invested in corporate bonds X3 dollars invested in gold reserves X4 dollars invested in construction loans The total amount invested is X1 X2 X3 X4, which must be less than $5 million. This is important when calculating 55% of the total amount invested and 15% of the total amount invested in two of the restrictions. Objective function

Maximize dollars of interest earned = 0.07X1 + 0.11X2 + 0.19X3 + 0.15X4 Subject to: X1 ≤ 1,000,000 X2 ≤ 2,500,000 X3 ≤ 1,500,000 X4 ≤ 1,800,000 X3 + X4 ≥ 0,55 (X1 + X2 + X3 + X4) X1 ≥ 0.15 (X1 + X2 + X3 + X4) X1 + X2 + X3 + X4 ≤ 5,000,000 X1, X2, X3, X4 ≥ 0 Solve QM for Windows As in previous exercises, when you open the program choose Linear Programming. Enter the number of constraints and variables and identify that it is a maximizing exercise. Then enter the data according to the equations formulated for each constraint and press SOLVE. The results will appear as shown below.

ICT maximizes your interest earned, if you make the following investment: X1 = $750,000, X2 = $950,000, X3 = $1,500,000 and X4 = $1,800,000; total interest earned is $712,000. To see investigations where the applied the linear programming models, you can access the following articles found in the Folder with Complementary Material. Castillo, B. & Aguirre, Z. (2018). Modelación del raleo mediante el uso de la programación lineal en plantaciones de Pinus caribaea Morelet de la Empresa Agroforestal Pinar del Río, Cuba. Arnaldoa 25(2): 597-614. González, V. H. Sanando-Vera, D., Barcia-Villacreses, K., Oñate-Guerrero, K., Murillo García, D. & Zambrano Carrillo, G. (19-21 de julio de 2018). Modelo de Programación Lineal aplicado a una Empresa PYME de Calzado. 6th LACCEI International Multiconference for Engineering, Education, and Technology: Innovation in Education and Inclusion, Lima-Perú. Recuperado de http://www.laccei.org/LACCEI2018- Lima/full_papers/FP291.pdf Pincay Orellana, J. R., Romero Ortiz, J. F., Soto Chávez, L. E. (2018). Propuesta de Modelo de Mejora Simulado aplicado a un Proceso de Fabricación. III Congreso Virtual Internacional Desarrollo Económico, Social y Empresarial en Iberoamérica. Recuperado de https://www.eumed.net/actas/18/desarrollo-empresarial/13-propuesta-de- modelo-de-mejora.pdf Kanu, S. I., Ozurumba B. A & Emerole I. C. (2014). Application of Linear Programming Techniques to Practical Decision Making. Mathematical Theory and Modeling, 4(9), 100-111. Uko, L. U., Lutz, R. J., Weisel, J. A. (2017). An Application of Linear Programming in Performance Evaluation. Academy of Educational Leadership Journal, 21(1), 1-7.