[Ebook]_Linear_Programming_-_Foundations_and_Extensions

《[Ebook]_Linear_Programming_-_Foundations_and_Extensions》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、LinearProgramming:FoundationsandExtensionsRobertJ.VanderbeiDEPARTMENTOFOPERATIONSRESEARCHANDFINANCIALENGINEERING,PRINCETONUNIVERSITY,PRINCETON,NJ08544E-mailaddress:rvdb@princeton.eduLINEARPROGRAMMING:FOUNDATIONSANDEXTENSIONSSecondEditionCopyrightc2001byRobertJ.Vanderbei.Allrightsreserved.Printedin

2、theUnitedStatesofAmerica.ExceptaspermittedundertheUnitedStatesCopyrightActof1976,nopartofthispublicationmaybereproducedordistributedinanyformorbyanymeans,orstoredinadatabaseorretrievalsystem,withoutthepriorwrittenpermissionofthepublisher.ISBN0-0000-0000-0ThetextforthisbookwasformatedinTimes-Romana

3、ndthemathematicswasformatedinMichaelSpivak’sMathtimesusingAMS-LATEX(whichisamacropackageforLeslieLamport’sLATEX,whichitselfisamacropackageforDonaldKnuth’sTEXtextformattingsystem)andconvertedfromdevice-independenttopostscriptformatusingDVIPS.Thefig-ureswereproducedusingSHOWCASEonaSiliconGraphics,Inc

4、.workstationandwereincorporatedintothetextasencapsulatedpostscriptfileswiththemacropackagecalledPSFIG.TEX.Tomyparents,HowardandMarilyn,mydearwife,Krisadee,andthebabes,MarisaandDianaContentsPrefacexiiiPrefaceto2ndEditionxviiPart1.BasicTheory—TheSimplexMethodandDuality1Chapter1.Introduction31.Managin

5、gaProductionFacility32.TheLinearProgrammingProblem6Exercises8Notes10Chapter2.TheSimplexMethod131.AnExample132.TheSimplexMethod163.Initialization194.Unboundedness225.Geometry22Exercises24Notes27Chapter3.Degeneracy291.DefinitionofDegeneracy292.TwoExamplesofDegenerateProblems293.ThePerturbation/Lexico

6、graphicMethod324.Bland’sRule365.FundamentalTheoremofLinearProgramming386.Geometry39Exercises42Notes43Chapter4.EfficiencyoftheSimplexMethod451.PerformanceMeasures452.MeasuringtheSizeofaProblem45viiviiiCONTENTS3.MeasuringtheEfforttoSolveaProblem464.Worst-CaseAnalysisoftheSimplexMethod47Exercises52Not

7、es53Chapter5.DualityTheory551.Motivation—FindingUpperBounds552.TheDualProblem573.TheWeakDualityTheorem584.TheStrongDualityTheorem605.ComplementarySlackness666.TheDualSimplexMethod687.ADual-BasedPhaseIAlgorithm718