Bài giảng Operations Management - Module B: Linear Programming

Operations ManagementLinear ProgrammingModule B1OutlineREQUIREMENTS OF A LINEAR PROGRAMMING PROBLEMFORMULATING LINEAR PROGRAMMING PROBLEMSShader Electronics exampleGRAPHICAL SOLUTION TO A LINEAR PROGRAMMING PROBLEMGraphical representation of ConstraintsIso-Profit Line Solution Method Corner-Point Solution Method2Outline - ContinuedSENSITIVITY ANALYSISSensitivity ReportChange in the Resources of the Right-Hand-Side ValuesChanges in the Objective Function CoefficientSOLVING MINIMIZATION PROBLEMSLINEAR PROGRAMMING APPLICATIONSProduction Mix ExampleDiet Problem ExampleProduction Scheduling ExampleLabor Scheduling ExampleTHE SIMPLEX METHOD OF LP3When you complete this chapter, you should be able to :Identify or Define:Objective functionConstraintsFeasible regionIso-profit/iso-cost methodsCorner-point solutionShadow priceLearning Objectives4When you complete this chapter, you should be able to :Describe or Explain:How to formulate linear modelsGraphical method of linear programmingHow to interpret sensitivity analysisLearning Objectives - Continued5Mathematical technique Not computer programmingAllocates scarce resources to achieve an objectivePioneered by George Dantzig in World War IIDeveloped workable solution called Simplex Method in 1947What is Linear Programming?6Scheduling school busses to minimize total distance traveled when carrying studentsAllocating police patrol units to high crime areas in order to minimize response time to 911 callsScheduling tellers at banks to that needs are met during each hour of the day while minimizing the total cost of laborExamples of Successful LP Applications7Examples of Successful LP Applications - ContinuedPicking blends of raw materials in feed mills to produce finished feed combinations at minimum costsSelecting the product mix in a factory to make best use of machine- and labor-hours available while maximizing the firm’s profitAllocating space for a tenant mix in a new shopping mall so as to maximize revenues to the leasing company8Requirements of a Linear Programming ProblemMust seek to maximize or minimize some quantity (the objective function)Presence of restrictions or constraints - limits ability to achieve objectiveMust be alternative courses of action from which to chooseObjectives and constraints must be expressible as linear equations or inequalities9Formulating Linear Programming ProblemsAssume:You wish to produce two products (1) Walkman AM/FM/Cassette and (2) Watch-TVWalkman takes 4 hours of electronic work and 2 hours assemblyWatch-TV takes 3 hours electronic work and 1 hour assemblyThere are 240 hours of electronic work time and 100 hours of assembly time availableProfit on a Walkman is $7; profit on a Watch-TV $510Formulating Linear Programming Problems - continuedLet:X1 = number of WalkmansX2 = number of Watch-TVsThen:4X1 + 3X2  240 electronics constraint2 X1 + 1X2  100 assembly constraint7X1 + 5X2 = profit maximize profit11Draw graph with vertical & horizontal axes (1st quadrant only)Plot constraints as lines, then as planesUse (X1,0), (0,X2) for lineFind feasible regionFind optimal solutionCorner point methodIso-profit line methodGraphical Solution Method12Shader Electronic Company ProblemHours Required toProduce 1 UnitDepartmentX1WalkmansX2Watch-TV’sAvailable HoursThis WeekElectronic43240Assembly21100Profit/unit$7$5Constraints:4x1 + 3x2  240 (Hours of Electronic Time)2x1 + 1x2  100 (Hours of Assembly Time)Objective:Maximize: 7x1 + 5x213Shader Electronic Company Constraints02040608010012001020304050607080Number of Walkmans (X1)Number of Watch-TVs (X2)Electronics(Constraint A)Assembly(Constraint B)14Shader Electronic Company Feasible Region02040608010012001020304050607080Number of Walkmans (X1)Number of Watch-TVs (X2)FeasibleRegionElectronics(Constraint A)Assembly(Constraint B)15Shader Electronic CompanyIso-Profit Lines02040608010012001020304050607080Number of Walkmans (X1)Number of Watch-TVs (X2)7*X1 + 5*X2 = 2107*X1 + 5*X2 = 420Electronics(Constraint A)Assembly(Constraint B)Iso-profit line16Shader Electronic Company Corner Point Solutions02040608010012001020304050607080Number of Walkmans (X1)Number of Watch-TVs (X2)Iso-profit lineElectronics(Constraint A)Assembly(Constraint B)Possible Corner Point Solution17Shader Electronic Company Optimal Solution02040608010012001020304050607080Number of Walkmans (X1)Number of Watch-TVs (X2)Optimal solutionIso-profit lineElectronics(Constraint A)Assembly(Constraint B)Possible Corner Point Solution18Shader Electronic Company Optimal Solution020406080100120010203040507080Number of Walkmans (X1)Number of Watch-TVs (X2)Optimal solutionIso-profit lineElectronics(Constraint A)Assembly(Constraint B)Possible Corner Point SolutionX1 = 30X2 = 406019Decision variables X1 = tons of BW chemical producedX2 = tons of color chemical producedObjectiveMinimize Z = 2500X1 + 3000X2ConstraintsX1 30 (BW); X2 20 (Color)X1 + X2 60 (Total tonnage)X1  0; X2  0 (Non-negativity)Formulation of Solution20Simplex Steps for MaximizationChoose the variable with the greatest positive Cj- Zj to enter the solutionDetermine the row to be replaced by selecting that one with the smallest (non-negative) quantity-to-pivot column ratioCalculate the new values for the pivot rowCalculate the new values for the other row(s)Calculate the Cj and Cj-Zj values for this tableau. If there are any Cj-Zj numbers greater than zero, return to step 1.21Simplex Steps for MinimizationChoose the variable with the greatest negative Cj- Zj to enter the solutionDetermine the row to be replaced by selecting that one with the smallest (non-negative) quantity-to-pivot column ratioCalculate the new values for the pivot rowCalculate the new values for the other row(s)Calculate the Cj and Cj-Zj values for this tableau. If there are any Cj-Zj numbers less than zero, return to step 1.22Sensitivity AnalysisProjects how much a solution might change if there were changes in variables or input data.Shadow price (dual) - value of one additional unit of a resource23You’re an analyst for a division of Kodak, which makes BW & color chemicals. At least 30 tons of BW and at least 20 tons of color must be made each month. The total chemicals made must be at least 60 tons. How many tons of each chemical should be made to minimize costs?BW: $2,500 manufacturing cost per monthColor: $ 3,000 manufacturing cost per month© 1995 Corel Corp.Minimization Example24Graphical SolutionX1Feasible Region0204060800Tons, Color Chemical (X2)20406080Tons, BW Chemical (X1)BWColorTotalFind values for X1 + X2  60.X1  30, X2  20.X1X225Optimal Solution: Corner Point MethodFeasible Region0204060800Tons, Color Chemical20406080Tons, BW ChemicalBWColorTotalABFind corner points26Assembly Constraint RHS Increased by 10X10204060801000204060Original assembly constraintAssembly constraint increased by 10Sol’nSol’nX2Original SolutionElectronics ConstraintNew SolutionFeasible Region27Assembly Constraint RHS Decreased by 10X10204060801000204060Original assembly constraintSol’nSol’nX2Assembly constraint decreased by 10Original SolutionNew Solution28A Minimization ProblemFeasible regionX1 = 30X2 = 20x1 + x2 = 60ab29