Assignment5

1PrimeandDual

SupposethatwearegivenalinearprogramLinstandardform,andsupposethatforbothLandthedualofL,thebasicsolutionsassociatedwiththeinitialslackformsarefeasible.ShowthattheoptimalobjectivevalueofLis0.

Answer:TheLandthedualofL’sinitialsolutionsbothare0,andbecauseanysolutionforLisnotsmallerthanthesolutionfordualofL.ThentheoptimalofL(minforL)andtheoptimalofdualofL(maxfordualofL)arethesame,allare0.

2Linear-InequalityFeasibility

Givenasetofmlinearinequalitiesonnvariablesx1,x2,...,xn,thelinear-inequalityfeasibilityproblemasksifthereisasettingofthevariablesthatsimultaneouslysatisfieseachoftheinequalities.

a.Showthatifwehaveanalgorithmforlinearprogramming,wecanuseittosolvethelinear-inequalityfeasibilityproblem.Thenumberofvariablesandconstraintsthatyouuseinthelinear-grogrammingproblemshouldbepolynomialinnandm.

b.Showthatifwehaveanalgorithmforthelinear-inequalityfeasibilityproblem,wecanuseittosolvealinear-programmingproblem.Thenumberofvariablesandlinearinequalitiesthatyouuseinthelinear-inequalityfeasibilityproblemshouldbepolynomialinnandm,thenumberofvariablesandconstraintsinthelinearprogramming.

Answer:

Noneedforoptimalfunctionforthelinear-inequalityfeasibilityproblem.ThenruntheLP-Algorithm.Infact,theLP-Algorithmispolynomialinnandm.

Weshouldrunthealgorithmforthelinear-inequalityfeasibilityproblemfortheLP-ProblemandDLP-Problem.Thenwegettwovalue(oneforLPandanotherforDLP,butneitherisoptimal)Butwecangettheoptimalmustbeintheintervalofthesetwovalues.ThenwegetthemedianofthesetwovaluesandaddmoreinequalityforLP-ProblemandcorrespondingDLP-Problem.Weiterativelyrunthealgorithmuntiltheintervalistoomuchsmall.ThenthissmallintervalistheoptimalvalueforLP-Problem.

3LinearProgrammingModelling

IntegerLinearProgrammingProblemisdifferentfromtheclassicLinearProgrammingProblemthatsomeextraconstraintssuchas

xiisaninteger,foralli=1,2,...,n

areadded.

Arailwaystationhasestimatedthatatleastthefollowingnumberofstaffisneededineachfour-hourintervalthroughoutastandard24-hourperiodandthesalaryperhourforeverypersonduringthedifferentperiod:

TimePeriodStaffNeeded

5:00-9:00S1

9:00-13:00S2

13:00-17:00S3

17:00-21:00S4

21:00-1:00S5

1:00-5:00S6

TimePeriodSalaryPerHourForEveryPerson

0:00-8:00C1

8:00-16:00C2

16:00-24:00C3

Allstaffworksin8-hour-shifts,whichmeanseverypersonwilldocontinuousworkfor8hours.Therearesixpossibleshiftsthatstartonthehourinthebeginningofeach4-hourperiodinthetable.Nowiftherailwaystationwanttominimizethetotalsalarypaidinoneday,pleaseformulatethisproblemasanintegerlinearprogrammingproblem.

Answer:Wecansetthenumberofstaffstartingworkingat5:009:0013:0017:0021:001:00arex1,x2,x3,x4,x5,x6.Sowecangettheintegerlinearprogrammingmodel:

Min:3*C1*x1+5*C2*x1+7*C2*x2+C3*x2+3*C2*x3+5*C3*x3+7*C3*x4+C1*x4+

3*C3*x5+5*C1*x5+7*C1*x6+C2*x6

s.t.x1+x6≥S1

x1+x2≥S2

x2+x3≥S3

x3+x4≥S4

x4+x5≥S5

x5+x6≥S6

foralli=1…6xiispositiveinteger

4LinearProgrammingModelling

0-1IntegerProgrammingProblemisdifferentfromtheclassicLinearProgrammingProblemthatsomeextraconstraintssuchas

xi2{0,1},foralli=1,2,...,n

areadded.

ThereisanundirectedgraphGwithnnodes.WeuseamatrixMtodenotethatwhethertwonodesareconnectedbyanedge.Inotherwords,Mijis1ifiandjareadjacent,and0otherwise.Ifyouwanttopaintthenodeswithsomecolors,suchthatanytwoadjacentnodesdon’tsharethesamecolor,andyoutrytouseaslesscolorsaspossible,pleaseformulatethisproblemasanintegerlinearprogrammingproblem(seethedefinitioninProblem4)ora0-1linearprogrammingproblem.

Answer:wecangetallthetwonodeswhicharenotconnectedbyanedgemeansavariable(thisvariablecanbe0meansthetwonodesarenotinsamecolor,1meansinsamecolor)alsowegetthetwonodeswhichareconnectedbyanedgemeansaconstantfor0(itmeansthesetwonodescanneverbeinsamecolor).Wewillgetthemaxthesumofallthesevariablesintheconstraints:foreverythreenodesweshouldbesurethatthesumofthree“edges”canneverbe2(becauseifitis2,itmeansinthesethreenodes,thenumberoftwonodesisinsamecoloris2andothertwonodes

Answer:

wesetx1isthenumberofproductIandx2isthenumberofproductII,sothelinearprogrammingisasfollowing:

max2x1+3x2ormin-2x1-3x2

s.t.x1+2x2≤8

4x1≤16

4x2≤12

x1≥0

x2≥0

Wegettheoptimalanswerisx1=4,x2=2,andthismaxis14

thedualproblem:wecansety1,y2,y3,isthenumberofdevice,materialAandmaterialB.Sotheduallinearprogrammingisasfollowing:

min8y1+16y2+12y3

s.t.y1+4y2≥2

2y1+4y3≥3

y1≥0

y2≥0

y3≥0

Wecanalsogettheoptimalanswerisy1=1.5,y2=0.125,y3=0,andthisminis14,too.Themeaningofthedualproblem:

Wecanthinkthatinthiscase,wemustbesurethattheprofitofproductIisatleast$2,andtheprofitofproductIIisatleast$3,andletthestuff(itmeansthatwegetminof8y1+16y2+12y3)beasleast