Linear Programming: Computer Solution and Sensitivity Analysis PDF

CHAPTER 3: LINEAR PROGRAMMING: COMPUTER SOLUTION AND SENSITIVITY ANALYSIS Overview The application of linear proramming methods in business operation is a tough activity, because of its approach which is too mathematical. Since this is so essential, more so that there is too much compe...

CHAPTER 3: LINEAR PROGRAMMING: COMPUTER SOLUTION AND SENSITIVITY ANALYSIS Overview The application of linear proramming methods in business operation is a tough activity, because of its approach which is too mathematical. Since this is so essential, more so that there is too much competition now in every corner of the business everyone need to devise measures by which to make their decision highly efficient to generate greater profitability. Each and every manager must learn quantititive methods in decision making to make them effective in crafting business decisions especially in regards to profitability. Linear programming technique is one of the best mathematical methods that can aid the manager come up with good decisions. However, the rigor involved in using this method requires adoption of a much easier and reliable way of generating solutions for problems involving maximization and minimization conditions. Thus computer solutions for this method is highly sought to make computations much easier and reliable. In this chapter, we will show how linear programming problems can be solved using several personal computer software packages. We will also describe how to use a computer solution result to experiment with a linear programming model to see what effect parameter changes have on the optimal solution, referred to as sensitivity analysis. Learning Outcomes At the end of this lesson. Students must be able to: 1. Apply computer solutions such as Excel Spreadsheet and QM for windows 2. Apply analysis of parameter changes and their effects on model solution COURSE MATERIALS Computer Solution When linear programming was first developed in the 1940s, virtually the only way to solve a problem was by using a lengthy manual mathematical solution procedure called the simplex method. As computer technology evolved, the computer was used more and more to solve linear programming models. The mathematical steps of the simplex method were simply programmed in prewritten software packages designed for the solution of linear programming problems. The ability to solve linear programming problems quickly and cheaply on the computer, regardless of the size of the problem, popularized linear programming and expanded its use by businesses. As a result of the easy and low-cost availability of personal computers and linear programming software, the simplex method has become less of a focus in the teaching of linear programming. In the next few sections, we demonstrate how to solve linear programming problems by using Excel spreadsheets and QM for Windows, a typical general-purpose quantitative methods software package. 23 Excel Spreadsheets Excel can be used to solve linear programming problems, although the data input requirements can be more time-consuming and tedious than with a software package like QM for Windows that is specifically designed for the purpose. A spreadsheet requires that column and row headings for the specific model be set up and that constraint and objective function formulas be input in their entirety, as opposed to just the model parameters, as with QM for Windows. However, this is also an advantage of spreadsheets, in that it enables the problem to be set up in an attractive format for reporting and presentation purposes. In addition, once a spreadsheet is set up for one problem, it can often be used as a template for others. The values for bowls and mugs and for profit are contained in cells B10, B11, and B12, respectively. These cells are currently empty or zero because the model has not yet been solved. The objective function for profit, =C4*B10+D4*B11, is embedded in cell B12 shown in bar. This formula is essentially the same as Z = 40x1 + 50x2, where B10 and B11 represent x1 and Exhibit 3.1 x2, and B12 equals Z. The objective function coefficients, 40 and 50, are in cells C4 and D4. Similar formulas for the constraints for labor and clay are embedded in cells E6 and E7. For example, in cell E6 we input the formula =C6*B10+D6*B11. The < = signs in cells F6 and F7 are for cosmetic purposes only; they have no real effect. To solve this problem, first click on the ―Data‖ tab on the toolbar at the top of the screen and then click on ―Solver‖ on the far right side of the Data toolbar. The window Solver Parameters will appear, as shown in Exhibit 3.2. Initially all the windows on this screen are blank, and we must input the objective function cell, the cells representing the decision variables, and the cells that make up the model constraints. When inputting the Solver parameters as shown in Exhibit 3.2, we first ―Set Objective:‖ which is B12 for our example. (Excel automatically inserts the $ sign next to cell addresses; you should not type it in.) Next we indicate that we want to maximize the objective by clicking on ―Max.‖ We achieve our objective by changing cells B10 and B11, which represent our model decision variables. The designation ―B10:B11‖ means all the cells between B10 and B11, inclusive. We next input our model constraints by clicking on ―Add,‖ which will access the screen shown in Exhibit 3.3. 24 Exhibit 3.3 shows our labor constraint. Cell E6 contains the constraint formula for labor whereas cell G6 contains the labor hours available (i.e., 40). We continue to add constraints until the model is complete. Note that we could have input our constraints by adding a single constraint formula, E6:E7 < = G6:G7, which means that the constraints in cells E6 and E7 are less than or equal to the values in cells G6 and G7, respectively. It is also not necessary to input the nonnegativity constraints for our decision variables, B10:B11 > = 0. This can be done in the Solver Parameters screen (Exhibit 3.2). Click on ―OK‖ on the Add Constraint window after all constraints have been added. This will return us to the Solver Parameters screen. There are two more necessary steps before proceeding to solve the problem. On the Solver Parameters screen, check where it says, ―Make Unconstrained Variables Non-Negative,‖ and where it says ―Select a Solving Method,‖ select ―Simplex LP.‖ This will ensure that Solver uses the simplex procedure to solve the model and not some other numeric method (which Excel has available). Exhibit 3.2 Exhibit 3.3 Once the complete model is input, click on ―Solve‖ at the bottom of the Solver Parameters screen (Exhibit 3.2). First, a screen will appear, titled Solver Results, which will provide you with the opportunity to select the reports you want and then when you click on ―OK,‖ the solution screen shown in Exhibit 3.4 will appear. 25 If there had been any extra, or slack, left over for labor or clay, it would have appeared in column H on our spreadsheet, under the heading ―Left Over.‖ In this case, there are no slack resources left over. When you click on ―OK‖ from the Solver screen, the intermediate Solver Results screen provides an opportunity for you to select several reports, including the answer report, shown in Exhibit 3.5. This report provides a summary of the solution results. QM for Windows Before demonstrating how to use QM for Windows, we must first make a few comments about the proper form that constraints must be in before a linear programming model can be solved with QM for Windows. The constraints formulated in the linear programming models presented in Chapter 2 and in this chapter have followed a consistent form. All the variables in the constraint have appeared to the left of the inequality, and all numerical values have been on the right-hand side of the inequality. For example, in the pottery company model, the constraint for labor is x1 + 2x2