Bài giảng Operations Management - Chapter 19 Linear Programming

Linear ProgrammingChapter 19Copyright © 2015 McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.You should be able to:LO 19.1 Describe the type of problem that would lend itself to solution using linear programmingLO 19.2 Formulate a linear programming model from a description of a problemLO 19.3 Solve simple linear programming problems using the graphical methodLO 19.4 Interpret computer solutions of linear programming problemsLO 19.5 Do sensitivity analysis on the solution of a linear programming problemChapter 19: Learning ObjectivesIn order for LP models to be used effectively, certain assumptions must be satisfied:LinearityThe impact of decision variables is linear in constraints and in the objective functionDivisibilityNoninteger values of decision variables are acceptableCertaintyValues of parameters are known and constantNonnegativityNegative values of decision variables are unacceptableLP AssumptionsLO 19.1List and define the decision variables (D.V.)These typically represent quantitiesState the objective function (O.F.)It includes every D.V. in the model and its contribution to profit (or cost)List the constraintsRight hand side valueRelationship symbol (≤, ≥, or =)Left Hand SideThe variables subject to the constraint, and their coefficients that indicate how much of the RHS quantity one unit of the D.V. representsNon-negativity constraintsModel FormulationLO 19.2Graphical LPGraphical LPA method for finding optimal solutions to two-variable problemsProcedureSet up the objective function and the constraints in mathematical formatPlot the constraintsIdentify the feasible solution spaceThe set of all feasible combinations of decision variables as defined by the constraintsPlot the objective functionDetermine the optimal solutionLO 19.3Computer SolutionsLO 19.4In Excel 2010, click on Tools on the top of the worksheet, and in that menu, click on SolverBegin by setting the Target CellThis is where you want the optimal objective function value to be recordedHighlight Max (if the objective is to maximize)The changing cells are the cells where the optimal values of the decision variables will appearComputer SolutionsLO 19.4Add a constraint, by clicking addFor each constraint, enter the cell that contains the left-hand side for the constraintSelect the appropriate relationship sign (≤, ≥, or =)Enter the RHS value or click on the cell containing the valueRepeat the process for each system constraintComputer SolutionsLO 19.4For the non-negativity constraints, check the checkbox to Make Unconstrained Variables Non-NegativeSelect Simplex LP as the Solving MethodClick SolveComputer SolutionsLO 19.4Computer SolutionsLO 19.4Solver ResultsSolver will incorporate the optimal values of the decision variables and the objective function into your original layout on your worksheetsLO 19.4Answer ReportLO 19.4Sensitivity ReportLO 19.5A change in the value of an O.F. coefficient can cause a change in the optimal solution of a problemNot every change will result in a changed solutionRange of OptimalityThe range of O.F. coefficient values for which the optimal values of the decision variables will not changeO.F. Coefficient ChangesLO 19.5Shadow priceAmount by which the value of the objective function would change with a one-unit change in the RHS value of a constraintRange of feasibilityRange of values for the RHS of a constraint over which the shadow price remains the sameRHS Value ChangesLO 19.5