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.

2 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. GeorgeDantzig,a member of ,developedtheSimplexmethod of optimizationin 1947in ordertoprovidean e cient ,expertsfroma variety of elds,especiallymathematicsandeconomics,h ave developedthetheorybehind\linearprogrammi ng"andexploreditsapplications[1].

3 Thispaper 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?

4 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.

5 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. 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.

6 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.

7 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].

8 LinearProgrammingProblemMany linearproblemsdo notinitiallymatch thecanonicalformpresentedin theintroduction,which willbe important whenwe may be in theformof inequalities,variablesmay nothavea nonnegativity constraint, ortheproblemmay want tomaximizezinsteadof minimizez. 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.

9 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.

10 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.