Introduction to linear optimization

INTRODUCTIONTOLINEAROPTIMIZATIONDimitrisBertsimasandJohnTsitsiklis

ErratasheetLastupdatedon5/23/04

Theerratadependontheprinting.Booksfromthe2ndor3dprintingcanbeidentifiedbytheentry“Secondprinting”or“Thirdprinting”belowtheISBNnumberinthecopyrightpageinthefront.

Erratainthesecondprinting,correctedinthethirdprinting.

p.27,l.−11,replace“Schwartz”by“Schwarz”

p.69,l.−13:“a󰀁i∗x=bi”shouldbe“a󰀁i∗x=bi∗”

p.126,l.16,replace“inequalityconstraints”by“linearinequalityconstraints”

p.153,l.−8,replacea󰀁ix=bibya󰀁ixI=bip.163,Example4.9,firstline:replace“from”with“form”

p.165,l.11,replacep󰀁Ax≥0byp󰀁Ax≥0

p.175,l.1,replace“Tothissee”by“Toseethis”

p.203,l.12:replacex≥0byx≥0,xn+1≥0

p.216,l.−6:replace“≤c}”by“≤c󰀁}”

p.216,l.−3:replacec󰀁by(c1)󰀁

p.216,l.−2:replacec󰀁by(c2)󰀁

p.216,l.−1:right-handsideshouldbeλ(c1)󰀁+(1−λ)(c2)󰀁

p.220,l.−12:replace“addedtothepivotrow”by“addedtothezerothrow”

p.238,Fig.6.1,caption,6thline:replace“thatched”by“hatched”

p.239,l.1:replace“thatched”by“hatched”

p.249,firstdisplayedequationshouldread

3󰀄

j=1λj1D1xj1+2󰀄

k=1θk1D1wk1+x3=8

p.259,inthedisplayedequationinitem4,zωshouldbez∗ωp.264,lastline:“Wosley”shouldbe“Wolsey”

1p.281,caption:replace“thatched”by“hatched”

p.304,caption:replace“thatched”by“hatched”

p.305,2ndand4thlineofExample7.5:replace“thatched”by“hatched”

p.349,replacepart(d)by:“Doesthereexistanondegenerateoptimalbasicfeasiblesolution?”

p.373,Lemma8.2,2ndline,replace󰀆nby󰀆m

p.447,l.5,replacezt=󰀃tj=1byzt=󰀃nj=1p.480,l.5,deletethesecond“that”

p.483,l.−9:theequationshouldread

x2+110x3+410x4=2510.

p.506,replaceTable11.1bythefollowing:tptstZ(pt)

15.00−3−9.00

22.60−2−2.20

31.321−0.68

41.83−2−0.66

51.011−0.99

61.341−0.66

71.601−0.40

81.81−2−0.62

91.481−0.52

101.611−0.39

p.516,l.−4:replace“equivalenttoI3”by“equivalenttoI2”

p.567,l.−16,“Schultz”shouldbe“Schulz”

p.574,l.5,“Schultz”shouldbe“Schulz”

p.577,l.20,“Schultz”shouldbe“Schulz”

p.585,“Schwartz”shouldbe“Schwarz”

2Erratainthefirstprinting,correctedinthesecondandthirdprint-ings.

p.35,Exercise1.9,line3:“gradei”shouldbe“gradeg”

p.38,Exercise1.20(a):Rewriteasfollows:“LetS={Ax|x∈󰀆n},whereAisagivenm×nmatrix.ShowthatSisasubspaceof󰀆m.”

p.43,rewritelastsentenceoffirstparagraphasfollows:“Inparticular,asetoftheform{x∈󰀆n|Ax=b,x≥0}isalsoapolyhedron,inastandardformrepresentation.”

p.76,Exercise2.3:Assumethatui>0foralli.

p.129,Exercise3.4:“Replace“Ex∗

p.130,Exercise3.8:Replacebythefollowing.

“Thisexercisedealswiththeproblemofdecidingwhetheragivendegeneratebasicfeasiblesolutionisoptimalandshowsthatthisisessentiallyashardassolvingagenerallinearprogrammingproblem.

Considerthelinearprogrammingproblemofminimizingc󰀁xoverallx∈P,whereP={x∈󰀆n|Ax≤b}isagivenboundedandnonemptypolyhedron.LetQ=󰀅(x,t)∈󰀆n+1󰀂󰀂Ax≤tb,t∈[0,1]󰀁.

(a)GiveanexampleofPandQ,withn=2,forwhichthezerovector(in󰀆n+1)isadegeneratebasicfeasiblesolutioninQ;showtheexampleinafigure.

(b)Showthatthezerovector(in󰀆n+1)minimizes(c,0)󰀁yoverally∈Qifandonlyiftheoptimalcostintheoriginallinearprogrammingproblemisgreaterthanorequaltozero.”

p.133,Exercise3.18(e):Replaceby“Ifxisanoptimalsolutionfoundbythesimplexmethod,nomorethanmofitscomponentscanbepositive,wheremisthenumberofequalityconstraints.”

p.134,Exercise3.20(b):Replaceby“Thefirstrowinthepresenttableau(belowtherowwiththereducedcosts)indicatesthattheproblemisinfeasible.”

p.135,Exercise3.25.Replacelastsentenceofpart(a)by“Also,showthatitisnondegenerateifandonlyifxi=0andxi=uiforeverybasicvariablexi.”

p.142,firstdisplayedequation:replace0byb.

p.188.Exercise4.6(a):Replace󰀃mi=1pi=1by󰀃mi=1pi≤1

p.191,Exercise4.13(b):Replace“oneofthebasic”by“oneofthenonbasic”

p.197,Exercise4.39:delete“andsomeλ∈(0,1)”

p.223,Exercise5.5(c):“γ≥0”shouldbereplacedby“γ>0”

3p.316,firstline:replace“networkflowproblem”by“uncapacitatednetworkflowproblem.”

p.347,Exercise7.2,thirdline:replace“period”by“year”

p.349,Exercise7.11,beforepart(a):Insert“Assumethatdi>0foralli.”

p.354,Exercise7.31(b):rewriteasfollows:“Givenadualfeasiblebasisasso-ciatedwithacertaintree,showthatitisanoptimalbasisifandonlyifthecorrespondingtreesolutiontotheprimalisfeasible.”

p.355,Exercise7.35(c):replace“andthereforeconverges”by“andthereforeconvergesafterafinitenumberofsteps”

p.445,Exercise9.12(b):“Showthatthedirection”shouldbereplacedby“Sup-posethatthedirection”

p.445,lastline:replacedksbydkx.

p.455,replacenexttolastsentenceby:“Tothiseffect,weconsiderabinaryvariableyi,i=1,...,k−1,whichcanbeequalto1onlyifai≤x≤ai+1,andmustbe0otherwise.”

p.525,Exercise11.9:inthehint,replace“f(x)≤t”by“f(x)≥t”.

p.538,nexttolastdisplayedequation:replacexfdoτbyxfodτ

4