Linear Programming: Theory and Applications

1 LinearProgramming:TheoryandApplicationsC atherineLewisMay 11, 20081 Contents1 Introductionto a linearprogram?.. LinearProgrammingProblem.. LinearProgramming.. SetsandDirections..82 ..163 nitions..194 AnOutlineof theProof205 ExamplesWithConvex SetsandExtremePoints Precursorsto theSimplexMethod ..237 TheSimplexMethod In Practice258 Whatif thereis noinitialbasisin theSimplextableau? ..319 .. 'sRule.. [2].. Ruleto Use?..3910 Sensitivity .. Analysisfora costcoe cient .. Analysisfora right-hand-sidevalue..4111 CaseStudy:BusingChildrento .. Function.. Together.. Prices..5712 Conclusion5721 Introductionto LinearProgrammingLinearprogrammingwas developedduringWorldWar II, whena systemwithwhich to maximizethee ciencyof resourceswas of \Program-ming"was a militarytermthatreferredto activitiessuch as planningschedulese cientlyor deployingmenoptimally.

2 GeorgeDantzig,a member of ,developedtheSimplexmethod of optimizationin 1947in ordertoprovidean e cient ,expertsfroma variety of elds,especiallymathematicsandeconomics,h ave developedthetheorybehind\linearprogrammi ng"andexploreditsapplications[1].Thispap er willcover themainconceptsin linearprogramming, ,in Section1 we willexploresimpleprop-erties,basicde nitionsandtheoriesof orderto illustratesomeapplicationsof linearprogramming,we willexplainsimpli ed\real-world"examplesin Section2. Section3 presents morede nitions,concludingwiththestatement of theGeneralRepresentationTheorem(GRT).In Section4, we ex-ploreanoutlineof theproof of theGRT andin Section5 we workthroughafewexamplesrelatedto ,we willfocusmethodsof introducesconceptsnecessaryforintroducin gtheSimplexalgorithm,which we explainin , we exploretheSimplexfurtherandlearnhow to dealwithnoinitialbasisin ,Section9 discussescyclingin present anoverviewof sensitivity , we putallof theseconceptstogetherin anextensive casestudyin a linearprogram?

3 We canreducethestructurethatcharacterizesli nearprogrammingproblems(perhapsafterseve ralmanipulations)into thefollowingform:3 Minimizec1x1+c2x2+ +cnxn=zSubjecttoa11x1+a12x2+ +a1nxn=b1a21x1+a22x2+ +a2nxn= +am2x2+ +amnxn=bmx1;x2;: : : ;xn 0:In linearprogrammingz, theexpressionbeingoptimized,is calledtheobjec-tivefunction. Thevariablesx1; x2: : : xnarecalleddecisionvariables, andtheirvaluesaresubjecttom+ 1 constraints (everylineendingwithabi, plusthenonnegativity constraint).A setofx1; x2: : : xnsatisfyingalltheconstraints iscalledafeasiblepointandthesetof allsuch points is calledthefeasiblere-gion. Thesolutionof thelinearprogrammustbe a point (x1; x2; : : : ; xn) in thefeasibleregion,or elsenotalltheconstraints wouldbe satis of Winston[3]illustratesthatge-ometricallyi nterpretingthefeasibleregionis a usefultool forsolvinglinearprogrammingproblemswitht wo :Minimize4x1+x2=zSubjectto3x1+x2 10x1+x2 5x1 3x1; x2 0:We plottedthesystemof inequalitiesas theshadedregionin Figure1.

4 Sinceallof theconstraints are\greaterthanorequalto"constraints,the shadedregionabove allthreelinesis a point (x1; x2) such thatthevalueofzis thesmallestit canbe, whilestilllyingin 4x1+x2,plottingthelinex1= (z x2)=4 forvariousvaluesofzresultsinisocostlines ,which have ,thevalueofzis , thedottedlinesrepresent isocostlinesfordi erent valuesofz. Sinceisocostlinesareparallelto each other,thethick dottedisocostlineforwhichz= 14is clearlythelinethatintersectsthefeasibler egionatthesmallestpossiblevalueforz. Therefore,z= 14is theintersectionof thelinesx1= 3 andx1+x2= 5, wherex1= 3 andx2= :Theshadedregionabove allthreesolidlinesis thefeasibleregion(oneof theconstraints does notcontributeto de ningthefeasibleregion). isocostlinethatpassesthroughtheintersect ionof thetwo de ningconstraints represents theminimumpossiblevalueofz= 14 gettoo focusedonsolvinglinearprograms,it is important to reviewsometheory.

5 For instance,severalassumptionsareimplicitin any variableto theobjective func-tionor constraints is proportionalto or economiesto example,thevalueof 8x1is twicethevalueof 4x1, nomoreor any variableto theobjective functionorconstraints is independent of thevaluesof ,by usinga spe-cialtechniquecalledintegerprogrammin g,we , integerprogrammingis beyondthescope of (allcoe cients in theobjective functionandtheconstraints)areknownwithce rtainty. Realistically, however,coe cients andparametersareoftentheresultof ectof changingthesenumberscanbe determinedwithsensitivity analysis,which willbe exploredlaterin Section9 [3]. LinearProgrammingProblemMany linearproblemsdo notinitiallymatch thecanonicalformpresentedin theintroduction,which willbe important whenwe may be in theformof inequalities,variablesmay nothavea nonnegativity constraint, ortheproblemmay want tomaximizezinsteadof minimizez.

6 We now considersomeways to manipulateproblemsinto InequalitiesWe rstconsidertheproblemof makingallcon-straints of a linearprogrammingproblemin theformof theproblemthatrepresent thedi erencebetweentheleftandtheright-handside sof theconstraints,we slack variablefroma \greaterthanorequalto"constraint orby addinganexcessvariabletoa \lessthanorequalto"constraint, ,theconstraint 4x1+x2 3becomes4x1+x2+e1= 3 withtheadditionofe1 0. If theconstraint wereoriginally4x1+x2 3, theadditionalsurplusvariables1mustbe subtracted(4x1+x2 s1= 3) so thats1canbe a strictlynonnegative a variablecanbe negative in thecontextof a linearpro-grammingproblemit is calleda urs(or\unrestrictedin sign") x00jwherex0j; x00j 0;theproblem needed,convertinga maximizationprob-lemto a minimizationproblemis anobjectivefunctionfora maximizationproblemmaxz= min( z) LinearProgrammingTheexampleof a canonicallinearprogrammingproblemfromthe introductionlendsitselfto a reminder,theformofa canonicalproblemis:Minimizec1x1+c2x2+ +cnxn=zSubjecttoa11x1+a12x2+ +a1nxn=b1a21x1+a22x2+ +a2nxn= +am2x2+ +amnxn=bmx1;x2;: : : ;xn 0:Byapplyingsomebasiclinearalgebra,thisp roblembecomes:MinimizePnj=1cjxj=zSubject toPnj=1ajxj=bxj 0j= 1;2.

7 : : : ; n:or,morecompactly,Minimizecx=zSubjectto Ax=bx 0;HereAis anmxnmatrixwhosejthcolumnisaj. Thismatrixcorrespondsto thecoe cients onx1; x2; : : : ; xnin theconstraints of a a vectorof solutionsto theproblem,bis theright-hand-sidevector,andcis thecostcoe cient ofthinkingaboutlinearprogrammingproblems is usefulespeciallyin sensitivityanalysis,which willbe discussedin SetsandDirectionsThissectionde nesimportant termsrelatedto thefeasibleregionof a setX2 Ris aconvexsetif givenanytwopointsx1andx2inX, anyconvexcombinationof thesetwopointsis alsoinX. Thatis, x1+ (1 )x22 Xforany 2[0;1][2]. See Figure 4 foranexampleof setXis convex if thelinesegment connectingany two points inXis alsocontainedinX. If any partof thelinesegment notinX, thenXis saidto showsanexampleof a nonconvex setanda convex a linearprogramis always a convex seewhy thismakes sense,considerthe2-dimensionalregionoutl inedontheaxesin Figure3.

8 Thisregionis linearprogramming,thisregioncouldnotoccu rbecause(fromFigure3)y mx+hforc x dbuty bford < x mx+hdoesn'tholdwhend < x eandtheconstrainty bdoesn'tholdwhen0 x d. Thesesortsof conditionalconstraints donotoccurin constraint cannotbe : Set1 is anexampleof a nonconvex setandset2 is anexampleof aconvex of linesegmentABarein set1, yet theentirelineisnotcontainedin set1. Nosuch linesegment is possiblein : A nonconvex (andthereforeinvalid) pointxin a convexsetXis called anextremepointofXifxcannotbe represented as a strictconvexcombinationof twodistinctpointsinX[2]. A strictconvexcombinationis a convexcombinationforwhich 2(0;1):Graphically, anextremepoint is a willnotprove thisfactrigorously. In two dimensions,two constraints de neanextremepoint ,if two pointsx0andx00make upa strictconvexcombinationthatequals x, thenallthreeof thesepoints mustbe de nedby thesameconstraints,or elsetheycouldnotbe ,if two constraintsde ne xat theirintersection,then xis unique,sincetwo linescanonlyintersectonce(ornotat all).

9 Sincethisintersectionis unique,yet allthreepoints mustlieonbothconstraints,x0=x00= x:Therefore,thestrictconvex combinationcan'texistandhencecornerpoint s andextremepoints convexset,a nonzero vectordis adirectionof thesetif foreachx0in theset,therayfx0+ d: 0galsobelongsto a convexsetis a directionof thesetthatcannotbe represented as a positivecombinationof twodistinctdirectionsof : A boundedsetwith4 ,theextremepoint (2;1) is adegenerateextremepointbecauseit is theintersectionof 3 constraints, general,anextremepoint is degenerateif thenumberof intersectingconstraints at thatpoint is greaterthanthedimensionof a directionandanextremedirectioncanbe seenin needallof thesede nitionsto statetheGeneralRepresentationThe-orem,a building-block in in a convexsetcanbe representedas a con-vexcombinationof extremepoints,plusa nonnegative Figure5: Theshadedregionin this gureis anunboundedconvex Ais anexampleof anextremepoint, vectorB is anexampleof a directionof thesetandvectorC is anexampleof anextremedirectionof Considertheproblemof locatinga newmachinetoanexistinglayoutconsistingof thefollowing(x; y) coordinates:(3;0);(0; 3);( 2;1);and(1;4).

10 Letthecoordinatesof thenewmachinebe (x1; x2).Formulatetheproblemof ndinganoptimallocationasa linearprogramif thesumof thedistancesfromthenewmachineto theexistingfourmachinesis ;forexample,thedistancefrom(x1; x2) to the rstmachineat11(3;0) isjx1 3j+jx2j:Thismeansthatthedistanceis notde nedby thelengthof a linebetweentwo points,ratherit is thesumof thelengthsofthehorizontalandverticalcomp onents of such a includedin a linearpro-gram,recallthat:jxj= maxfx; xg:Withthisin mind,thefollowinglinearprogrammodelsthep roblem:Minimizez=(P1+P2) + (P3+P4) + (P5+P6) + (P7+P8)SubjecttoP1 (x1 3)P1 x1 3P2 (x2)P2 x2P3 (x1 1)P3 x1 1P4 (x2 4)P4 x2 4P5 (x1+ 2)P5 x1+ 2P6 (x2 1)P6 x2 1P7 (x1)P7 x1P8 (x2+ 3)P8 x2+ 3allvariables 0:EachP2i 1represents thehorizontaldistancebetweenthenewmachin eandtheitholdmachinefori= 1.