chapter02線性基本概念

運(yùn)籌學(xué)

OperationsResearch楊雯博士深圳大學(xué)管理學(xué)院

OperationsResearchChapter2.LinearProgramming:BasicConceptsChapter2.

LinearProgramming:

BasicConcepts第二章.線性規(guī)劃:基本概念OperationsResearchChapter2.LinearProgramming:BasicConceptsThreeClassicApplicationsofLP(Section2.1)(線性規(guī)劃的三個(gè)經(jīng)典應(yīng)用[第2.1節(jié)])TheWyndorGlassCompanyProductMixProblem(Section2.2)(偉恩德玻璃制品公司產(chǎn)品組合問(wèn)題[第2.2節(jié)])FormulatingtheWyndorProblemonaSpreadsheet(Section2.3)(在電子表格上建立韋恩德公司問(wèn)題的模型[第2.3節(jié)])TheAlgebraicModelforWyndor(Section2.4)(韋恩德公司問(wèn)題的數(shù)學(xué)模型[第2.4節(jié)])TableofContentsChapter2.LinearProgramming:BasicConceptsTheGraphicalMethodAppliedtotheWyndorProblem(Section2.5)(韋恩德公司問(wèn)題的圖形方法[第2.5節(jié)])UsingtheExcelSolverwiththeWyndorProblem(Section2.6)(使用ExcelSolver解決韋恩德公司問(wèn)題[第2.6節(jié)])AMinimizationExample—TheProfit&GambitCo.(Section2.7)(一個(gè)最小化的例子——利博公司廣告組合問(wèn)題[第2.7節(jié)])TableofContentsChapter2.LinearProgramming:BasicConceptsProductMixatPonderosaIndustrial(潘得羅索工業(yè)公司的產(chǎn)品組合問(wèn)題)市場(chǎng)的變動(dòng)導(dǎo)致不同時(shí)期生產(chǎn)不同類型的膠合板所帶來(lái)的利潤(rùn)也不同生產(chǎn)資源的有限性Consideredlimitedresources,anddeterminedoptimalmixofplywoodproducts.(考慮了有限資源，并確定了膠合板產(chǎn)品的最優(yōu)組合)Increasedoverallprofitabilityofcompanyby20%.(公司的總利潤(rùn)增加了20%)ThreeClassicApplicationsofLPChapter2.LinearProgramming:BasicConceptsPersonnelSchedulingatUnitedAirlines(聯(lián)合航空公司的員工排程)Designedworkschedulesforallemployeesatalocationtomeetservicerequirementsmostefficiently.(在每個(gè)地點(diǎn)為所有員工設(shè)計(jì)工作排程以最有效地滿足服務(wù)需求)Saved$6millionannually.(每年可節(jié)約600萬(wàn)美元)線性規(guī)劃太有用了！ThreeClassicApplicationsofLPChapter2.LinearProgramming:BasicConceptsPlanningSupply,Distribution,andMarketingatCitgoPetroleumCorporation(Citgo石油公司的供應(yīng)、配送和營(yíng)銷計(jì)劃)TheSDMsystemusesLPtocoordinatethesupply,distribution,andmarketingofeachofCitgo’smajorproductsthroughouttheUnitedStates.(SDM系統(tǒng)使用LP來(lái)協(xié)調(diào)全美Citgo石油公司主要產(chǎn)品的供應(yīng)、配送和營(yíng)銷)Theresultingreductionininventoryadded$14millionannuallytoCitgo’sprofits.(庫(kù)存成本的下降每年為公司增加1400萬(wàn)美元的收入)ThreeClassicApplicationsofLPChapter2.LinearProgramming:BasicConceptsWyndorhasdevelopedthefollowingnewproducts(韋恩德公司開(kāi)發(fā)了下列新產(chǎn)品):An8-footglassdoorwithaluminumframing.(8英尺的鋁框玻璃門)A4-footby6-footdouble-hung,wood-framedwindow.(4英尺*6英尺的雙把木框門)Thecompanyhasthreeplants(公司有三個(gè)工廠)Plant1producesaluminumframesandhardware.(工廠1生產(chǎn)鋁框和五金件)Plant2produceswoodframes.(工廠2生產(chǎn)木框)Plant3producesglassandassemblesthewindowsanddoors.(工廠3生產(chǎn)玻璃并組裝窗和門)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDataofWyndorGlassCo.ProductMixProblem(韋恩德玻璃制品公司產(chǎn)品組合問(wèn)題的有關(guān)數(shù)據(jù))WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsShouldtheygoaheadwithlaunchingthesetwonewproducts?Ifso,whatshouldbetheproductmix?公司是否應(yīng)該生產(chǎn)這兩個(gè)新產(chǎn)品？如果生產(chǎn)，兩個(gè)新產(chǎn)品的生產(chǎn)組合如何？WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsAlgebraicModelforWyndorGlassCo.(韋恩德公司問(wèn)題的數(shù)學(xué)模型)Let D=thenumberofdoorstoproduce

(門的生產(chǎn)量)

W=thenumberofwindowstoproduce

(窗的生產(chǎn)量)MaximizeP=$300D+$500Wsubjectto(約束)

D≤4

2W≤12

3D+2W≤

18and D≥

0,W≥

0.運(yùn)籌學(xué)線性規(guī)劃WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts產(chǎn)品組合圖形WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts非負(fù)約束WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts非負(fù)約束D≤4WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts非負(fù)約束2W≤12WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsBoundaryLineforConstraint3D+2W≤

18(約束條件邊界線)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts只改變約束條件右側(cè)得到平行的約束邊界線WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConcepts3D+2W≤

18的非負(fù)可行域WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsGraphofFeasibleRegion(可行域圖像)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsObjectiveFunction(P=1,500)(目標(biāo)函數(shù))WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsFindingtheOptimalSolution(尋找最優(yōu)解)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDrawtheconstraintboundarylineforeachconstraint.Usetheorigin(oranypointnotontheline)todeterminewhichsideofthelineispermittedbytheconstraint.(畫出每個(gè)函數(shù)約束的約束邊界線，用原點(diǎn)或其它不在約束邊界線上的點(diǎn)來(lái)確定直線的哪一邊是約束條件所允許的)Findthefeasibleregionbydeterminingwhereallconstraintsaresatisfiedsimultaneously.(找出由所有約束條件都同時(shí)滿足所決定的可行域)Determinetheslopeofoneobjectivefunctionline.Allotherobjectivefunctionlineswillhavethesameslope.(確定一條目標(biāo)函數(shù)線的斜率，所有其它目標(biāo)函數(shù)線具有與之相同的斜率)SummaryoftheGraphicalMethodWyndorGlassCo.ProductMixProblemMoveastraightedgewiththisslopethroughthefeasibleregioninthedirectionofimprovingvaluesoftheobjectivefunction.Stopatthelastinstantthatthestraightedgestillpassesthroughapointinthefeasibleregion.Thislinegivenbythestraightedgeistheoptimalobjectivefunctionline.(在可行域范圍內(nèi)朝著目標(biāo)函數(shù)改進(jìn)的方向移動(dòng)目標(biāo)函數(shù)線，在它還穿過(guò)可行域的一個(gè)點(diǎn)時(shí)停止移動(dòng)，這時(shí)得到的就是最優(yōu)目標(biāo)函數(shù)線)Afeasiblepointontheoptimalobjectivefunctionlineisanoptimalsolution.(最優(yōu)目標(biāo)函數(shù)線上的可行點(diǎn)是一個(gè)最優(yōu)解)SummaryoftheGraphicalMethodWyndorGlassCo.ProductMixProblemDevelopingaSpreadsheetModel(建立電子表格模型)Step#1:DataCells(第一步:數(shù)據(jù)單元格)Enterallofthedatafortheproblemonthespreadsheet.(在電子表格中輸入問(wèn)題的所有數(shù)據(jù))Makeconsistentuseofrowsandcolumns.(有效利用行和列)Itisagoodideatocolorcodethese“datacells”(e.g.,lightblue).(為這些數(shù)據(jù)單元格標(biāo)上顏色便于區(qū)分和建模)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel(建立電子表格模型)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsStep#2:ChangingCells(第二步:可變單元格)Addacellinthespreadsheetforeverydecisionthatneedstobemade.(在電子表格中為每一決策添加一個(gè)單元格)Ifyoudon’thaveanyparticularinitialvalues,justenter0ineach.(如果沒(méi)有任何初始值，輸入0即可)Itisagoodideatocolorcodethese“changingcells”(e.g.,yellowwithborder).(為這些可變單元格標(biāo)上顏色便于區(qū)分和建模)DevelopingaSpreadsheetModel(建立電子表格模型)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel(建立電子表格模型)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立電子表格模型)Step#3:TargetCell(第三步:目標(biāo)單元格)Developanequationthatdefinestheobjectiveofthemodel.(建立定義模型目標(biāo)的方程式)Typicallythisequationinvolvesthedatacellsandthechangingcellsinordertodetermineaquantityofinterest(e.g.,totalprofitortotalcost).(典型地，這個(gè)方程式包含了數(shù)據(jù)單元格和可變單元格的數(shù)據(jù)，以確定有關(guān)的數(shù)量值，如總利潤(rùn)和總成本)Itisagoodideatocolorcodethiscell(e.g.,orangewithheavyborder).(給目標(biāo)單元格標(biāo)記顏色)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立電子表格模型)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立電子表格模型)Step#4:Constraints(約束)Foranyresourcethatisrestricted,calculatetheamountofthatresourceusedinacellonthespreadsheet(anoutputcell).(對(duì)所有有限資源，在電子表格的輸出單元格中計(jì)算出資源的使用量)Definetheconstraintinthreeconsecutivecells.Forexample,ifQuantityA≤QuantityB,putthesethreeitems(QuantityA,≤,QuantityB)inconsecutivecells.(在三個(gè)連續(xù)的單元格中定義約束)WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsDevelopingaSpreadsheetModel

(建立電子表格模型)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsATrialSolution(試驗(yàn)解)ThespreadsheetfortheWyndorproblemwithatrialsolution(4doorsand3windows)enteredintothechangingcells.(含試驗(yàn)解的韋恩德公司問(wèn)題的電子表格模型，在可變單元格中輸入了4扇門和3扇窗)41218WyndorGlassCo.ProductMixProblemChapter2.LinearProgramming:BasicConceptsChoosethe“Solver”fromtheToolsmenu.(從工具菜單中選擇“Solver”)Selectthecellyouwishtooptimizeinthe“SetTargetCell”window.(在“SetTargetCell”中選擇要優(yōu)化的單元格)Choose“Max”or“Min”dependingonwhetheryouwanttomaximizeorminimizethetargetcell.(根據(jù)需要選擇“Max”或者“Min”選項(xiàng))Enterallthechangingcellsinthe“ByChangingCells”window.(在“ByChangingCells”窗體中輸入所有可變單元格)IdentifyingtheTargetCellandChangingCells

(確定目標(biāo)單元格和可變單元格)Solver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConcepts41218Solver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConceptsAddingConstraints(添加約束)Tobeginenteringconstraints,clickthe“Add”buttontotherightoftheconstraintswindow.(在約束窗體的右側(cè)點(diǎn)擊“Add”按鈕添加約束)FillintheentriesintheresultingAddConstraintdialoguebox.(在添加約束對(duì)話框中填入相應(yīng)內(nèi)容)Solver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConcepts41218Solver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConceptsTheCompleteSolverDialogueBox(設(shè)置完成的Solver對(duì)話框)Solver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConceptsSomeImportantOptions(一些重要選項(xiàng))Clickonthe“Options”button,andclickinboththe“AssumeLinearModel”andthe“AssumeNon-Negative”box.(單擊“Options”按鈕，并且選中“AssumeLinearModel”和“AssumeNon-Negative”選項(xiàng))“AssumeLinearModel”tellstheSolverthatthisisalinearprogrammingmodel.(“AssumeLinearModel”選項(xiàng)使Solver確定該模型為線性規(guī)劃模型)“AssumeNon-Negative”addsnonnegativityconstraintstoallthechangingcells.(“AssumeNon-Negative”選項(xiàng)給所有可變單元格添加非負(fù)約束條件)Solver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConceptsSolver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConceptsTheOptimalSolution(最優(yōu)解)41218Solver求解韋恩德公司的產(chǎn)品組合問(wèn)題Chapter2.LinearProgramming:BasicConceptsManagementhasdecidedtoundertakeamajoradvertisingcampaignthatwillfocusonthefollowingthreekeyproducts:(管理層決定集中在下列三個(gè)主要產(chǎn)品上實(shí)行大規(guī)模廣告活動(dòng))Asprayprewashstainremover.(一種噴霧去污劑)Aliquidlaundrydetergent.(一種液體洗滌劑)Apowderlaundrydetergent.(一種洗衣粉)Thecampaignwillusebothtelevisionandprintmedia(這一廣告活動(dòng)將采用電視和印刷媒體)Thegeneralgoalistoincreasesalesoftheseproducts.(總目標(biāo)是要增加所有這些產(chǎn)品的銷售量)TheProfit&GambitCo.Chapter2.LinearProgramming:BasicConceptsManagementhassetthefollowinggoalsforthecampaign:(管理層設(shè)定了如下廣告目標(biāo))Salesofthestainremovershouldincreasebyatleast3%.(噴霧去污劑至少增加3%的市場(chǎng)份額)Salesoftheliquiddetergentshouldincreasebyatleast18%.(液體洗滌劑至少增加18%的市場(chǎng)份額)Salesofthepowderdetergentshouldincreasebyatleast4%.(洗衣粉至少增加4%的市場(chǎng)份額)TheProfit&GambitCo.Chapter2.LinearProgramming:BasicConceptsDataofProfit&GambitCo.Problem(利博公司問(wèn)題的有關(guān)數(shù)據(jù))TheProfit&GambitCo.Chapter2.LinearProgramming:BasicConcepts