数据、模型与决策（第12版）课件 第2章线性规划建立模型与图解法求解

Copyright©2016PearsonEducation,Inc.LinearProgramming:ModelFormulationandGraphicalSolutionChapter2Copyright©2016PearsonEducation,Inc.ChapterTopicsModelFormulationAMaximizationModelExampleGraphicalSolutionsofLinearProgrammingModelsAMinimizationModelExampleIrregularTypesofLinearProgrammingModelsCharacteristicsofLinearProgrammingProblemsCopyright©2016PearsonEducation,Inc.Objectivesofbusinessdecisionsfrequentlyinvolvemaximizingprofitorminimizingcosts.Linearprogramminguseslinearalgebraicrelationshipstorepresentafirm’sdecisions,givenabusinessobjective,andresourceconstraints.Stepsinapplication:Identifyproblemassolvablebylinearprogramming.Formulateamathematicalmodeloftheunstructuredproblem.Solvethemodel.ImplementationLinearProgramming:AnOverviewCopyright©2016PearsonEducation,Inc.Decisionvariables-mathematicalsymbolsrepresentinglevelsofactivitybythefirm.Objectivefunction-alinearmathematicalrelationshipdescribinganobjectiveofthefirm,intermsofdecisionvariables-thisfunctionistobemaximizedorminimized.Constraints–requirementsorrestrictionsplacedonthefirmbytheoperatingenvironment,statedinlinearrelationshipsofthedecisionvariables.Parameters-numericalcoefficientsandconstantsusedintheobjectivefunctionandconstraints.ModelComponentsCopyright©2016PearsonEducation,Inc.SummaryofModelFormulationStepsStep1:DefinethedecisionvariablesStep2:Definetheobjectivefunction

Step3:Definetheconstraints

Copyright©2016PearsonEducation,Inc.LPModelFormulationAMaximizationExample(1of3)Productmixproblem-BeaverCreekPotteryCompanyHowmanybowlsandmugsshouldbeproducedtomaximizeprofitsgivenlaborandmaterialsconstraints?Productresourcerequirementsandunitprofit:ResourceRequirementsProductLabor(Hr./Unit)Clay(Lb./Unit)Profit($/Unit)Bowl1440Mug2350Figure2.6BeaverCreekPotteryCompanyCopyright©2016PearsonEducation,Inc.LPModelFormulationAMaximizationExample(2of3)Resource 40hrsoflaborperdayAvailability: 120lbsofclayDecision x1=numberofbowlstoproduceperdayVariables: x2=numberofmugstoproduceperdayObjective MaximizeZ=$40x1+$50x2Function: WhereZ=profitperdayResource 1x1+2x2

40hoursoflaborConstraints: 4x1+3x2

120poundsofclayNon-Negativity x10;x20Constraints: Copyright©2016PearsonEducation,Inc.LPModelFormulationAMaximizationExample(3of3)CompleteLinearProgrammingModel:Maximize Z=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.Afeasiblesolutiondoesnotviolateanyoftheconstraints:

Example: x1=5bowls x2=10mugs Z=$40x1+$50x2=$700

Laborconstraintcheck: 1(5)+2(10)=25≤40hoursClayconstraintcheck: 4(5)+3(10)=70≤120poundsFeasibleSolutionsCopyright©2016PearsonEducation,Inc. Aninfeasiblesolutionviolatesatleastoneoftheconstraints:

Example: x1=10bowls x2=20mugs

Z=$40x1+$50x2=$1400Laborconstraintcheck: 1(10)+2(20)=50>40hoursInfeasibleSolutionsCopyright©2016PearsonEducation,Inc.Graphicalsolutionislimitedtolinearprogrammingmodelscontainingonlytwodecisionvariables(canbeusedwiththreevariablesbutonlywithgreatdifficulty).Graphicalmethodsprovidevisualizationofhowasolutionforalinearprogrammingproblemisobtained.GraphicalSolutionofLPModelsCopyright©2016PearsonEducation,Inc.CoordinateAxesGraphicalSolutionofMaximizationModel(1of12)Figure2.2CoordinatesforgraphicalanalysisMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0X1isbowlsX2ismugsCopyright©2016PearsonEducation,Inc.LaborConstraintGraphicalSolutionofMaximizationModel(2of12)Figure2.3GraphoflaborconstraintMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.LaborConstraintAreaGraphicalSolutionofMaximizationModel(3of12)Figure2.4LaborconstraintareaMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.ClayConstraintAreaGraphicalSolutionofMaximizationModel(4of12)Figure2.5The

constraintareaforclayMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.BothConstraintsGraphicalSolutionofMaximizationModel(5of12)Figure2.6GraphofbothmodelconstraintsMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.FeasibleSolutionAreaGraphicalSolutionofMaximizationModel(6of12)Figure2.7ThefeasiblesolutionareaconstraintsMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.ObjectiveFunctionSolution=$800GraphicalSolutionofMaximizationModel(7of12)Figure2.8ObjectivefunctionlineforZ=$800MaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.AlternativeObjectiveFunctionSolutionLinesGraphicalSolutionofMaximizationModel(8of12)Figure2.9Alternativeobjectivefunctionlinesforprofits,Z,of$800,$1,200,and$1,600MaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.OptimalSolutionGraphicalSolutionofMaximizationModel(9of12)Figure2.10IdentificationofoptimalsolutionpointMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.OptimalSolutionCoordinatesGraphicalSolutionofMaximizationModel(10of12)Figure2.11OptimalsolutioncoordinatesMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.Extreme(Corner)PointSolutionsGraphicalSolutionofMaximizationModel(11of12)Figure2.12SolutionsatallcornerpointsMaximizeZ=$40x1+$50x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Copyright©2016PearsonEducation,Inc.OptimalSolutionforNewObjectiveFunctionGraphicalSolutionofMaximizationModel(12of12)MaximizeZ=$70x1+$20x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Figure2.13OptimalsolutionwithZ=70x1+20x2Copyright©2016PearsonEducation,Inc.Standardformrequiresthatallconstraintsbeintheformofequations(equalities).Aslackvariableisaddedtoa

constraint(weakinequality)toconvertittoanequation(=).Aslackvariabletypicallyrepresentsanunusedresource.Aslackvariablecontributesnothingtotheobjectivefunctionvalue.SlackVariablesCopyright©2016PearsonEducation,Inc.LinearProgrammingModel:StandardFormMaxZ=40x1+50x2+s1+s2subjectto:1x1+2x2+s1=404x2+3x2+s2=120x1,x2,s1,s2

0Where:x1=numberofbowlsx2=numberofmugss1,s2areslackvariablesFigure2.14SolutionsatpointsA,B,andCwithslackCopyright©2016PearsonEducation,Inc.LPModelFormulation–Minimization(1of7)Twobrandsoffertilizeravailable-Super-gro,Crop-quick.Fieldrequiresatleast16poundsofnitrogenand24poundsofphosphate.Super-grocosts$6perbag,Crop-quick$3perbag.Problem:Howmuchofeachbrandtopurchasetominimizetotalcostoffertilizergivenfollowingdata?Figure2.15Fertilizingfarmer’sfieldCopyright©2016PearsonEducation,Inc.DecisionVariables: x1=bagsofSuper-gro x2=bagsofCrop-quickTheObjectiveFunction: MinimizeZ=$6x1+3x2 Where: $6x1=costofbagsofSuper-Gro $3x2=costofbagsofCrop-QuickModelConstraints: 2x1+4x2

16lb(nitrogenconstraint) 4x1+3x2

24lb(phosphateconstraint) x1,x2

0(non-negativityconstraint)LPModelFormulation–Minimization(2of7)Copyright©2016PearsonEducation,Inc.MinimizeZ=$6x1+$3x2subjectto: 2x1+4x2

16 4x2+3x2

24 x1,x2

0Figure2.16ConstraintlinesforfertilizermodelConstraintGraph–Minimization(3of7)Copyright©2016PearsonEducation,Inc.Figure2.17FeasiblesolutionareaFeasibleRegion–Minimization(4of7)MinimizeZ=$6x1+$3x2subjectto: 2x1+4x2

16 4x2+3x2

24 x1,x2

0Copyright©2016PearsonEducation,Inc.Figure2.18TheoptimalsolutionpointOptimalSolutionPoint–Minimization(5of7)MinimizeZ=$6x1+$3x2subjectto: 2x1+4x2

16 4x2+3x2

24 x1,x2

0Theoptimalsolutionofaminimizationproblemisattheextremepointclosesttotheorigin.Copyright©2016PearsonEducation,Inc.Asurplusvariableissubtractedfroma

constrainttoconvertittoanequation(=).Asurplusvariablerepresentsanexcessaboveaconstraintrequirementlevel.Asurplusvariablecontributesnothingtothecalculatedvalueoftheobjectivefunction.Subtractingsurplusvariablesinthefarmerproblemconstraints:2x1+4x2-s1=16(nitrogen) 4x1+3x2-s2=24(phosphate)SurplusVariables–Minimization(6of7)Copyright©2016PearsonEducation,Inc.Figure2.19GraphofthefertilizerexampleGraphicalSolutions–Minimization(7of7)MinimizeZ=$6x1+$3x2+0s1+0s2subjectto: 2x1+4x2–s1

=16 4x2+3x2–s2=24 x1,x2,s1,s2

0Copyright©2016PearsonEducation,Inc. Forsomelinearprogrammingmodels,thegeneralrulesdonotapply.Specialtypesofproblemsincludethosewith:MultipleoptimalsolutionsInfeasiblesolutionsUnboundedsolutionsIrregularTypesofLinearProgrammingProblemsCopyright©2016PearsonEducation,Inc.Figure2.20GraphofBeaverCreekPotteryexamplewithmultipleoptimalsolutionsMultipleOptimalSolutionsBeaverCreekPotteryTheobjectivefunctionisparalleltoaconstraintline.MaximizeZ=$40x1+30x2subjectto: 1x1+2x2

40 4x2+3x2

120 x1,x2

0Where:x1=numberofbowlsx2=numberofmugsCopyright©2016PearsonEducation,Inc.AnInfeasibleProblemFigure2.21GraphofaninfeasibleproblemEverypossiblesolutionviolatesatleastoneconstraint:MaximizeZ=5x1+3x2subjectto: 4x1+2x2

8 x1

4 x2

6 x1,x2

0Copyright©2016PearsonEducation,Inc.AnUnboundedProblemFigure2.22GraphofanunboundedproblemValueoftheobjectivefunctionincreasesindefinitely:MaximizeZ=4x1+2x2subjectto:x1

4x2

2x1,x2

0Copyright©2016PearsonEducation,Inc.CharacteristicsofLinearProgrammingProblemsAdecisionamongalternativecoursesofactionisrequired.Thedecisionisrepresentedinthemodelbydecisionvariables.Theproblemencompassesagoal,expressedasanobjectivefunction,thatthedecisionmakerwantstoachieve.Restrictions(representedbyconstraints)existthatlimittheextentofachievementoftheobjective.Theobjectiveandconstraintsmustbedefinablebylinearmathematicalfunctionalrelationships.Copyright©2016PearsonEducation,Inc.Proportionality

-Therateofchange(slope)oftheobjectivefunctionandconstraintequationsisconstant.Additivity

-Termsintheobjectivefunctionandconstraintequationsmustbeadditive.Divisibility

-Decisionvariablescantakeonanyfractionalvalueandarethereforecontinuousasopposedtointegerinnature.Certainty-Valuesofallthemodelparametersareassumedtobeknownwithcertainty(non-probabilistic).PropertiesofLinearProgrammingModelsCopyright©2016PearsonEducation,Inc.ProblemStatementExampleProblemNo.1(1of3)Hotdogmixturein1000-poundbatches.Twoingredients,chicken($3/lb)andbeef($5/lb).Reciperequirements:atleast500poundsof“chicken”atleast200poundsof“beef”Ratioofchickentobeefmustbeatleast2to1.Determineoptimalmixtureofingredientsthatwillminimizecosts.Copyright©2016PearsonEducation,Inc.Step1:Identifydecisionvariables.x1=lbofchickeninmixturex2=lbofbeefinmixtureStep2:Formulatetheobjectivefunction. MinimizeZ=$3x1+$5x2 whereZ=costper1,000-lbbatch$3x1=costofchicken$5x2=costofbeefSolutionExampleProblemNo.1(2of3)Copyright©2016PearsonEducation,Inc.Step3:EstablishModelConstraintsx1+x2=1,000lbx1

500lbofchickenx2

200lbofbeefx1/x2

2/1orx1-2x2

0x1,x2

0TheModel:MinimizeZ=$3x1+5x2subjectto:x1+x2=1,000lbx1