管理科学线性规划 精选文档.ppt

《管理科学线性规划 精选文档.ppt》由会员分享，可在线阅读，更多相关《管理科学线性规划 精选文档.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理科学线性规划 Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis1本讲稿第一页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 2Chapter TopicsComputer SolutionSensitivity Analysis本讲稿第二页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis

2、 3Early linear programming used lengthy manual mathematical solution procedure called the Simplex Method(See CD-ROM Module A).Steps of the Simplex Method have been programmed in software packages designed for linear programming problems.Many such packages available currently.Used extensively in busi

3、ness and government.Text focuses on Excel Spreadsheets and QM for Windows.Computer Solution本讲稿第三页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 4Beaver Creek Pottery ExampleExcel Spreadsheet Data Screen(1 of 5)Exhibit 3.1本讲稿第四页，共三十八页Chapter 3-Linear Programming:Compute

4、r Solution and Sensitivity Analysis 5Beaver Creek Pottery Example“Solver”Parameter Screen(2 of 5)Exhibit 3.2本讲稿第五页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 6Exhibit 3.3Beaver Creek Pottery ExampleAdding Model Constraints(3 of 5)本讲稿第六页，共三十八页Chapter 3-Linear Program

5、ming:Computer Solution and Sensitivity Analysis 7Exhibit 3.4Beaver Creek Pottery ExampleSolution Screen(4 of 5)本讲稿第七页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 8Beaver Creek Pottery ExampleAnswer Report(5 of 5)Exhibit 3.5本讲稿第八页，共三十八页Chapter 3-Linear Programming:Com

6、puter Solution and Sensitivity Analysis 9Linear Programming Problem Standard FormStandard form requires all variables in the constraint equations to appear on the left of the inequality(or equality)and all numeric values to be on the right-hand side.Examples:x3 x1+x2 must be converted to x3-x1-x2 0

7、x1/(x2+x3)2 becomes x1 2(x2+x3)and then x1-2x2-2x3 0 本讲稿第九页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 10Beaver Creek Pottery ExampleQM for Windows Data Screen(1 of 3)Exhibit 3.6本讲稿第十页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 11Be

8、aver Creek Pottery ExampleModel Solution Screen(2 of 3)Exhibit 3.7本讲稿第十一页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 12Beaver Creek Pottery ExampleGraphical Solution Screen(3 of 3)Exhibit 3.8本讲稿第十二页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity

9、 Analysis 13Beaver Creek Pottery ExampleSensitivity Analysis(1 of 4)Sensitivity analysis determines the effect on optimal solutions of changes in parameter values of the objective function and constraint equations.Changes may be reactions to anticipated uncertainties in the parameters or to new or c

10、hanged information concerning the model.本讲稿第十三页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 14Maximize Z=$40 x1+$50 x2subject to:1x1+2x2 40 4x2+3x2 120 x1,x2 0Figure 3.1Optimal Solution PointBeaver Creek Pottery ExampleSensitivity Analysis(2 of 4)本讲稿第十四页，共三十八页Chapter

11、 3-Linear Programming:Computer Solution and Sensitivity Analysis 15Maximize Z=$100 x1+$50 x2subject to:1x1+2x2 40 4x2+3x2 120 x1,x2 0Figure 3.2Changing the x1 Objective Function CoefficientBeaver Creek Pottery ExampleChange x1 Objective Function Coefficient(3 of 4)本讲稿第十五页，共三十八页Chapter 3-Linear Progr

12、amming:Computer Solution and Sensitivity Analysis 16Maximize Z=$40 x1+$100 x2subject to:1x1+2x2 40 4x2+3x2 120 x1,x2 0Figure 3.3Changing the x2 Objective Function CoefficientBeaver Creek Pottery ExampleChange x2 Objective Function Coefficient(4 of 4)本讲稿第十六页，共三十八页Chapter 3-Linear Programming:Computer

13、 Solution and Sensitivity Analysis 17The sensitivity range for an objective function coefficient is the range of values over which the current optimal solution point will remain optimal.The sensitivity range for the xi coefficient is designated as ci.Objective Function CoefficientSensitivity Range(1

14、 of 3)本讲稿第十七页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 18objective function Z=$40 x1+$50 x2 sensitivity range for:x1:25 c1 66.67 x2:30 c2 80Figure 3.4Determining the Sensitivity Range for c1Objective Function CoefficientSensitivity Range for c1 and c2(2 of 3)本讲稿第十

15、八页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 19Minimize Z=$6x1+$3x2subject to:2x1+4x2 164x1+3x2 24 x1,x2 0sensitivity ranges:4 c1 0 c2 4.5Objective Function CoefficientFertilizer Cost Minimization Example(3 of 3)Figure 3.5Fertilizer Cost Minimization Example本讲稿第十九页

16、，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 20Exhibit 3.9Objective Function Coefficient RangesExcel“Solver”Results Screen(1 of 3)本讲稿第二十页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 21Exhibit 3.10Objective Function Coefficient RangesB

17、eaver Creek Example Sensitivity Report(2 of 3)本讲稿第二十一页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 22Exhibit 3.11Objective Function Coefficient RangesQM for Windows Sensitivity Range Screen(3 of 3)本讲稿第二十二页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensi

18、tivity Analysis 23Changes in Constraint Quantity ValuesSensitivity Range(1 of 4)The sensitivity range for a right-hand-side value is the range of values over which the quantity values can change without changing the solution variable mix,including slack variables.本讲稿第二十三页，共三十八页Chapter 3-Linear Progr

19、amming:Computer Solution and Sensitivity Analysis 24Changes in Constraint Quantity ValuesIncreasing the Labor Constraint(2 of 4)Maximize Z=$40 x1+$50 x2subject to:1x1+2x2 40 4x2+3x2 120 x1,x2 0Figure 3.6Increasing the Labor Constraint Quantity本讲稿第二十四页，共三十八页Chapter 3-Linear Programming:Computer Solut

20、ion and Sensitivity Analysis 25Changes in Constraint Quantity ValuesSensitivity Range for Labor Constraint(3 of 4)Sensitivity range for:30 q1 80 hrFigure 3.7Determining the Sensitivity Range for Labor Quantity本讲稿第二十五页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 26Cha

21、nges in Constraint Quantity ValuesSensitivity Range for Clay Constraint(4 of 4)Sensitivity range for:60 q2 160 lbFigure 3.8Determining the Sensitivity Range for Clay Quantity本讲稿第二十六页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 27Exhibit 3.12Constraint Quantity Value

22、Ranges by ComputerExcel Sensitivity Range for Constraints(1 of 2)本讲稿第二十七页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 28Exhibit 3.13Constraint Quantity Value Ranges by ComputerQM for Windows Sensitivity Range(2 of 2)本讲稿第二十八页，共三十八页Chapter 3-Linear Programming:Computer

23、 Solution and Sensitivity Analysis 29Changing individual constraint parametersAdding new constraintsAdding new variablesOther Forms of Sensitivity AnalysisTopics(1 of 4)本讲稿第二十九页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 30Other Forms of Sensitivity AnalysisChanging

24、 a Constraint Parameter(2 of 4)Maximize Z=$40 x1+$50 x2subject to:1x1+2x2 40 4x2+3x2 120 x1,x2 0Figure 3.9Changing the x1 Coefficient in the Labor Constraint本讲稿第三十页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 31Adding a new constraint to Beaver Creek Model:0.20 x1+0.

25、10 x2 5 hours for packaging Original solution:24 bowls,8 mugs,$1,360 profitExhibit 3.13Other Forms of Sensitivity AnalysisAdding a New Constraint(3 of 4)本讲稿第三十一页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 32Adding a new variable to the Beaver Creek model,x3,a third

26、product,cupsMaximize Z=$40 x1+50 x2+30 x3subject to:x1+2x2+1.2x3 40 hr of labor 4x1+3x2+2x3 120 lb of clay x1,x2,x3 0Solving model shows that change has no effect on the original solution(i.e.,the model is not sensitive to this change).Other Forms of Sensitivity AnalysisAdding a New Variable(4 of 4)

27、本讲稿第三十二页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 33Defined as the marginal value of one additional unit of resource.The sensitivity range for a constraint quantity value is also the range over which the shadow price is valid.Shadow Prices(Dual Values)本讲稿第三十三页，共三十

28、八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 34Maximize Z=$40 x1+$50 x2 subject to:x1+2x2 40 hr of labor4x1+3x2 120 lb of clay x1,x2 0Exhibit 3.14Excel Sensitivity Report for Beaver Creek PotteryShadow Prices Example(1 of 2)本讲稿第三十四页，共三十八页Chapter 3-Linear Programming:Comp

29、uter Solution and Sensitivity Analysis 35Excel Sensitivity Report for Beaver Creek PotterySolution Screen(2 of 2)Exhibit 3.15本讲稿第三十五页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 36Two airplane parts:no.1 and no.2.Three manufacturing stages:stamping,drilling,milling.D

30、ecision variables:x1(number of part no.1 to produce)x2(number of part no.2 to produce)Model:Maximize Z=$650 x1+910 x2 subject to:4x1+7.5x2 105(stamping,hr)6.2x1+4.9x2 90(drilling,hr)9.1x1+4.1x2 110(finishing,hr)x1,x2 0 Example ProblemProblem Statement(1 of 3)本讲稿第三十六页，共三十八页Chapter 3-Linear Programmin

31、g:Computer Solution and Sensitivity Analysis 37Maximize Z=$650 x1+$910 x2subject to:4x1+7.5x2 105 6.2x1+4.9x2 90 9.1x1+4.1x2 110 x1,x2 0s1=0,s2=0,s3=11.35 hr485.33 c1 1,151.43137.76 q1 89.10Figure 3.10Graphical SolutionExample ProblemGraphical Solution(2 of 3)本讲稿第三十七页，共三十八页Chapter 3-Linear Programming:Computer Solution and Sensitivity Analysis 38Example ProblemExcel Solution(3 of 3)Exhibit 3.16本讲稿第三十八页，共三十八页