Linear Programming Models: Graphical And Computer Methods

Transcription

LinearProgrammingModels: Graphicaland ComputerMethodsLearning ObjectivesStudents will be able to:1. Understand the basic assumptions andproperties of linear programming (LP).2. Graphically solve any LP problem thathas only two variables by both thecorner point and isoprofit line methods.3. Understand special issues in LP such asinfeasibility, unboundedness,redundancy, and alternative optimalsolutions.4. Understand the role of sensitivityanalysis.5. Use Excel spreadsheets to solve LPproblems.1

IntroductionLinear programming (LP) is a widely used mathematical modelingtechnique designed to help managers in planningand decision making related to resource allocation. LP is a technique that helps in resourceallocation decisions.Programming refers to modeling and solving a problemmathematically.Examples of SuccessfulLP Applications1. Development of a production schedulethat will satisfy future demands for a firm’sproduction while minimizing total productionand inventory costs2. Selection of product mix in a factory to make best use of machine-hours andlabor-hours available while maximizing the firm’s products2

Examples of SuccessfulLP Applications (continued)3. Determination of grades of petroleumproducts to yield the maximum profit4. Selection of different blends of rawmaterials to feed mills to producefinished feed combinations at minimumcost5. Determination of a distribution systemthat will minimize total shipping costfrom several warehouses to variousmarket locationsRequirements of a LinearProgramming Problem All LP problems have 4 properties incommon:All problems seek to maximize orminimize some quantity (the objectivefunction).The presence of restrictions orconstraints limits the degree to whichwe can pursue our objective.There must be alternative courses ofaction to choose from.The objective and constraints in linearprogramming problems must beexpressed in terms of linear equationsor inequalities.3

5 Basic Assumptions ofLinear Programming1. Certainty: numbers in the objective and constraintsare known with certainty and do notchange during the period being studied2. Proportionality: exists in the objective and constraintsconstancy between production increasesand resource utilization3. Additivity: the total of all activities equals the sum ofthe individual activities5 Basic Assumptions ofLinear Programming(continued)4. Divisibility: solutions need not be in whole numbers(integers)solutions are divisible, and may take anyfractional value5. Non-negativity: all answers or variables are greater than orequal to ( ) zeronegative values of physical quantities areimpossible4

Formulating LinearProgrammingProblems Formulating a linear program involvesdeveloping a mathematical model torepresent the managerial problem. Once the managerial problem isunderstood, begin to develop themathematical statement of the problem. The steps in formulating a linearprogram follow on the next slide.Formulating LinearProgramming Problems(continued)Steps in LP Formulations1.Completely understand themanagerial problem beingfaced.2.Identify the objective and theconstraints.3.Define the decision variables.4.Use the decision variables towritemathematical expressionsfor the objective function and theconstraints.5

Formulating LinearProgramming Problems(continued)The Product Mix Problem Two or more products are usuallyproduced using limited resources such as- personnel, machines, raw materials,and so on. The profit that the firm seeks tomaximize is based on the profitcontribution per unit of each product. The company would like to determinehow many units of each product itshould produce so as to maximizeoverall profit given its limited resources. A problem of this type is formulated inthe following example on the next slide.Flair Furniture CompanyData - Table 7.1Hours Required to Produce One UnitDepartmentTCTables Chairs Carpentry Painting&VarnishingProfit per unit4231 7 5AvailableHours ThisWeek240100Identify the objective andconstraints:Maximize ProfitSubject to:Hours of carpentry time used 240 hrs.per weekHours of paint. & varnishing used 100 hrs./wk.6

Flair Furniture CompanyData - Table 7.1Identify the objective andconstraints:Maximize ProfitSubject to:Hours of carpentry time used 240 hrs.per weekHours of paint. & varnishing used 100 hrs./wkDefine decision variables:Let T number of tables produced each weekC number of chairs produced each weekFlair Furniture CompanyData - Table 7.1Hours Required to Produce One UnitDepartment Carpentry Painting&VarnishingProfit per unitTCTables Chairs4231 7 5AvailableHours ThisWeek240100Mathematical formulation:Max. profit (z) 7T 5CSubject to: 4T 3C 240 (Carpentry)2T 1C 100 (Paint & Varnishing)T 0 (1st nonnegative cons)C 0 (2nd nonnegative cons)7

Flair Furniture CompanyConstraintsThe easiest way to solve a small LP problem, suchas that of the Flair Furniture Company, is with thegraphical solution approach.The graphical method works only when there aretwo decision variables, but it provides valuableinsight into how larger problems are structured.When there are more than two variables, it is notpossible to plot the solution on a two-dimensionalgraph; a more complex approach is needed.But the graphical method is invaluable in providingus with insights into how other approaches work.Flair Furniture CompanyConstraints120Number of Chairs1002T 1C 100Painting/Varnishing80604T 3C 24040Carpentry20020406080100Number of Tables8

Number of ChairsFlair Furniture CompanyFeasible asibleRegion020406080100Number of TablesIsoprofit Lines Steps1.2.3.4.Graph all constraints and find thefeasible region.Select a specific profit (or cost) lineand graph it to find the slope.Move the objective function line inthe direction of increasing profit (ordecreasing cost) while maintainingthe slope. The last point it touches inthe feasible region is the optimalsolution.Find the values of the decisionvariables at this last point andcompute the profit (or cost).9

Flair Furniture CompanyIsoprofit LinesIsoprofit Line Solution Method Start by letting profits equal somearbitrary but small dollar amount. Choose a profit of, say, 210.- This is a profit level that can beobtained easily without violatingeither of the two constraints. The objective function can bewritten as 210 7T 5C.Flair Furniture CompanyIsoprofit LinesIsoprofit Line Solution Method The objective function is just theequation of a line called an isoprofit line.- It represents all combinations of (T, C) thatwould yield a total profit of 210. To plot the profit line, proceed exactly asdone to plot a constraint line:- First, let T 0 and solve for the point atwhich the line crosses the C axis.- Then, let C 0 and solve for T.9 210 7(0) 5(C)9 C 42 chairs Then, let C 0 and solve for T.9 210 7(T) 5(0)9 T 30 tables10

Flair Furniture CompanyIsoprofit LinesIsoprofit Line Solution Method Next connect these two points with astraight line. This profit line is illustratedin the next slide. All points on the line represent feasiblesolutions that produce an approximateprofit of 210 Obviously, the isoprofit line for 210does not produce the highest possibleprofit to the firm. Try graphing more lines, each yielding ahigher profit. Another equation, 420 7T 5C, isplotted in the same fashion as the lowerline.Flair Furniture CompanyIsoprofit LinesIsoprofit Line Solution Method When T 0,9 420 7(0) 5(C)9 C 84 chairs When C 0,9 420 7(T) 5(0)9 T 60 tables This line is too high to be considered asit no longer touches the feasible region. The highest possible isoprofit line isillustrated in the second following slide.It touches the tip of the feasible region atthe corner point (T 30, C 40) andyields a profit of 410.11

Flair Furniture CompanyIsoprofit Lines120Number of Chairs100Painting/Varnishing807T 5C 210607T 5C 42040Carpentry20020406080100Number of TablesFlair Furniture CompanyOptimal Solution120Isoprofit LinesNumber of Chairs100Painting/Varnishing8060Solution(T 30, C 40)40Carpentry20020406080100Number of Tables12

Flair Furniture CompanyCorner PointCorner Point Solution Method A second approach to solving LPproblems It involves looking at the profit atevery corner point of the feasibleregion The mathematical theory behind LP isthat the optimal solution must lie atone of the corner points in the feasibleregionCorner PointCorner Point Solution Method, Summary1.Graph all constraints and find thefeasible region.2.Find the corner points of the feasibleregion.3.Compute the profit (or cost) at eachof the feasible corner points.4.Select the corner point with the bestvalue of the objective functionfound in step 3. This is the optimalsolution.13

Flair Furniture CompanyCorner PointCorner Point Solution Method The feasible region for the Flair FurnitureCompany problem is a four-sided polygonwith four corner, or extreme, points. These points are labeled 1 ,2 ,3 , and 4 onthe next graph. To find the (T, C) values producing themaximum profit, find the coordinates ofeach corner point and test their profit levels.Point 1:(T 0,C 0) profit 7(0) 5(0) 0Point 2:(T 0,C 80) profit 7(0) 5(80) 400Point 3:(T 30,C 40) profit 7(30) 5(40) 410Point 4 : (T 50, C 0) profit 7(50) 5(0) 350Flair Furniture CompanyOptimal Solution120Corner PointsNumber of Chairs10080Painting/Varnishing2Solution(T 30, C 40)60403Carpentry2001204 6080Number of Tables4010014

Flair Furniture - QMfor WindowsTo use QM for Windows,1. Select the Linear Programming module.2. Then specify- the number of constraints (other than thenon-negativity constraints, as it is assumedthat the variables must be nonnegative),- the number of variables, and- whether the objective is to be maximized orminimized.For the Flair Furniture Company problem, there aretwo constraints and two variables.3. Once these numbers are specified, the inputwindow opens as shown on the next slide.Flair Furniture - QM forWindows (continued)4. Next, the coefficients for the objectivefunction and the constraints can be entered.- Placing the cursor over the X1 or X2 andtyping a new name such as Tables andChairs will change the variable names.- The constraint names can be similarlymodified.- When you select the Solve button, you getthe output shown in the next slide.15

Flair Furniture - QMfor Windows (continued)Flair Furniture - QMfor Windows (continued)5. Modify the problem by selecting theEdit button and returning to the inputscreen to make any desired changes.6. Once these numbers are specified, theinput window opens as shown on thenext slide.7. Once the problem has been solved, agraph may be displayed by selectingWindow—Graph from the menu bar inQM for Windows.8. The next slide shows the output for thegraphical solution.Notice that in addition to the graph, thecorner points and the original problemare also shown.16

Flair Furniture - QMfor Windows (continued)Flair Furniture –Solver in ExcelTo use Solver, open an Excel sheet and:1. Enter the variable names and the coefficientsfor the objective function and constraints.2. Specify cells where the values of the variableswill be located. The solution will be put here.3. Write a formula to compute the value of theobjective function. The SUMPRODUCTfunction is helpful with this.4. Write formulas to compute the left-hand sidesof the constraints. Formulas may be copied andpasted to these cells.5. Indicate constraint signs ( , , and ) fordisplay purposes only. The actual signs must beentered into Solver later, but having thesedisplayed in the spreadsheet is helpful.6. Input the right-hand side values for eachconstraint.17

Flair Furniture – Solverin Excel (continued)Once the problem is entered in an Excel sheet,follow these steps to use Solver:1. In Excel, select Tools—Solver. If Solver does not appear on the menuunder Tools, select Tools—Add-ins andthen check the box next to Solver Add-in.Solver then will display in the Tools dropdown menu.2. Once Solver has been selected, a window willopen for the input of the Solver Parameters.Move the cursor to the Set Target Cell box andfill in the cell that is used to calculate the valueof the objective function.3. Move the cursor to the By Changing Cells boxand input the cells that will contain the valuesfor the variables.4. Move the cursor to the Subject to theConstraints box, and then select Add.Flair Furniture – Solverin Excel (continued)Solver steps, continued:5. The Cell Reference box is for the range of cellsthat contain the left-hand sides of theconstraints.6. Select the to change the type of constraint ifnecessary. Since this setting is the default, nochange is necessary. If there had been some or constraints inaddition to the constraints, it would bebest to input all of one type [e.g., ] first,and then select Add to input the other typeof constraint.7. Move the cursor to the Constraint box to inputthe right-hand sides of the constraints. SelectAdd to finish this set of constraints and begininputting another set, or select OK if there areno other constraints to add.18

Flair Furniture – Solverin Excel (continued)Solver steps, continued:8. From the Solver Parameters window, selectOptions and check Assume Linear Model andcheck Assume Non-negative; then click OK.9. Review the information in the Solver windowto make sure it is correct, and click Solve.10. The Solver Solutions window is displayed andindicates that a solution was found. The valuesfor the variables, the objective function, and theslacks are shown also.11. Select Keep Solver Solution and the values inthe spreadsheet will be kept at the optimalsolution.12. You may select what sort of additionalinformation (e.g., Sensitivity) is to be presentedfrom the reports Window (discussed later).You may select any of these and select OK tohave these au

Flair Furniture - QM for Windows (continued) Flair Furniture – Solver in Excel To use Solver, open an Excel sheet and: 1. Enter the variable names and the coefficients for the objective function and constraints. 2. Specify cells where the values of the variables