DOC

A_1

By Larry Payne,2014-07-23 03:46
6 views 0
A_1

    A

未驭’NORTHEAST.MATH.J

    ;24(1)(2oo8),31-34

    ;ANewMethodforAchievinganInitial

    ;RegularSolutionofaLinearProgramming

    ;LIANGPing(梁平),SUNYan.hua(孙艳华)andWEIDe-bin(魏德宾)

    ;(CollegeofInformation,DalianUniversity,Dalian,116622)

    ;ZHANGXiang-bin(张相斌)

    ;(CollegeofEcnomicsandManagement,DalianUniversity,Dalian,116622) ;Abstract:Amethodisprovidedforfindinganinitialregularsolutionofalinear ;programminginthispaper.Thekeytothismethodistosolveanauxiliarylinear ;programminginsteadoftointroduceanyartificialvariableorconstraint.Compared ;withthetraditionalmethodofachievingtheregularsolutionbyintroducinganar- ;tificialconstraint,ithasadvantagesofsavingthememoriesandlittlecomputational ;efforts.

    ;Keywords:initialregularsolution,auxiliarylinearprogramming,artificialvariable, ;artificialconstrain

    ;2000MRsubjectclassification:90C05

    ;CLCnumber:0221.1

    ;DocumentCOde:A

    ;ArticleID:1000-1778(2008)01.0031.04

    ;1Introduction

    ;Thelinearprogrammingisanimportantbranchoftheoperationresearchandisusedwidely ;inthemilitarytransportation,structuraloptimaldesignandmanagementdecision,etc. ;SincethesimplexmethodispresentedbyG.B.Dantzigin1947,ithasalreadybeenwidely ;usedinmanyfields.Boththesimplexmethodandthedualsimplexmethodarethecorn- ;monlyusedmethods.Althoughitisnotapolynomialalgorithm,itisacceptedbymany ;users.Inordertosolvealinearprogrammingbythedualsimplexmethodonemustmake ;iterationsfromaregularsolution.Foraproblemwhichhasnoevidentregularsolutionthe ;commonmethodiSintroducinganartificialconstrainandanartificialvariablefsee11).So

    ;itiSveryimportanttofindamethodthatcaneliminateintroducingtheartificialconstrains ;orartificialvariables.Muchworkonithasbeenmadeandmanyefficientmethodshave ;beenobtained.AnewmethodiSprovidedwhicheliminateintroducingtheartificialcon- ;strainsorartificialvariablesinthispaper.ThebasicideaiSintroducinganauxiliarylinear ;programmingbyusingabasisoftheprimalone.Aregularsolutioncanbeobtainedorthe ;Receiveddate:Nov.27,2006

    ;Foundationitem:TheNSF(70572069)ofChina.

    ;

    ;NoRTHEAST.MATH.JV0L.24

    ;unboundnessofLPisverifiedbythediscussionoftheauxiliaryprogramming.Thefollowin

g

    ;sectionwilldiscussitindetail.

    ;2TheMethodforAchievingaRegularSolution

    ;Considerthefollowinglinearprogramming:

    ;LPmincTx

    ;S.t.Ax=b,

    ;(2.1)

    ;?0.

    ;HereA:(0t)m×nwithR(A)=m<n.Somecomponentsofbmaybenegative?LetBbe ;abasicmatr,and?anonbasicmatrix.LetzB,?becolumnvectorsofbasicvariables

    ;andnonbasicv{iab1esrespectively,andcBthevectorwhoseelementsaretheobjective ;functioncoefficientsfor

    ;canbetransfcIrmedinto

    ;thecorrespondingelementsofXB.

    ;thefollowing

    ;ALPmin

    ;Thelinearprogramming(2.1)

    ;(2.2)

    ;s.t.B+BNxN=,

    ;xj?0,J=1,2,’,n?

    IN:{jlxjarenonbasicvariables})arecriterionnuInbers.6=B6 ;Here,aj(J?

    ;-abasicsolution,butperhsisnotaregularsolution.Constructanauxiliarylinear ;programming

    ;mnc

    ;(?)jEN

    ;(2.3)

    ;?0,=1,2,.,n?

    ;HereMisasufficient1ylargenumberande=(1,1,…,1){×m-

    ;ItlseasvtoseethatforanenoughlargenumberM>0,theauxiliaryprogrammlng ;(2.3)h…n(

    ;Thereforewecanso1veitbysimplexmethodtoobtainanoptimalsolutionortoprovethat ;ithasnoniteoptima1solution.Thefollowingtheoremscanbeobtained? ;Theorem2.1TheDptimalsolutiono/(2.3)isregularsolutionof(2?2)?

    ;ProDTheobjectivefunctionsandconstraintmatrixofthelinearprogramrmng1)are ;thes?asth0seoftheauxiliarylinearprogramming(2.2),SOthecriterionvectoco

    ;spondingthesamebasicmatricesisthesametoo.Thecriterionnumberscorresponding ;theoptimalsolutionoftheauxiliarylinearprogrammingareallnonpositive,sothisoPt1. ;ma1solutionoftheauxiliarylinearprogramming(2.3)isaregularsolutionofthelnear ;programining(2.2)or(2.1).Theproofiscompleted.

    ;m

    ;

    ;NO.1LIANGP.et.REGULARSOLUTIONOFALINEARPROGRAMMING33

    ;Theorem2.2theau.viliaryprogramming(2.3)hasnofiniteoptimalsolution,thenthe ;linearprogramming(2.2)hasnofiniteoptimalsolution07”thefeasiblere9ionisempty.

    ;Iftheauxiliaryprogramming(2.1)hasnofiniteoptimalsolution,thenitsdual ;linearprogramminghasanemptyfeasibleregion.Itiseasytoseethattheduallinear ;programmingsofthelinearprogramming(2.1)and(2.3)havethesamefeasibleregions,SO

    ;thedualprogrammingofthelinearprogramming(2.2)hasalsoanemptyfeasibleregion,

    ;andthelinearprogramming(2.2)hasnofiniteoptimalsolutionorhasanemptyfeasible

    ;region.Theproofiscompleted.

    ;3TheAlgorithmoftheNewMethod

    ;LetUSshowthealgorithmofthenewmethod:

    ;,,,

    ;Step1?Findabasicsolutionllofthelinearprogramming(2.1); ;Step2?Ifb?0,thenitisabasicfeasiblesolutionof(2.2),andgotoStep4;otherwise,

    ;gotoStep3;

    ;Step3.Solvetheauxiliaryprogramming(2.3)bythesimplexmeth0d:ifithasnonjte

    ;optimalsolution,thenstop;otherwise,anoptimalsolutionof(2.3),i.e.,abasicfeasible

    ;solutionof(2.2),hasbeenobtained,andgotoStep4;

    ;Step4.Solvethelinearprogramming(2.2)bythedualsimplexmethodtoobtainan ;optimalsolutionof(2.1)or(2.2),orprovethatithasanemptyregion. ;4AnExplanationExample

    ;Weusethefollowingexampletodemonstrateourmethod.

    ;Considerthefollowingexample

    ;(LP):

    ;LPmin3xa+X2+3

    ;S.t.Xl2x2+X3+X4=11.

    ;

    ;4Xl+X2+2X3X5=3,

    ;

    ;2xl+X3=1.

    ;1,2,…,5?0.

    ;Solution?TakeX3,X4,X5tobebasicvariables.

    ;Theaugmentedform(ARC)andthe

    ;assistantprogramming(ALP)are

    ;.

    ;ARGmin11+2

    ;S?t?3xl2x2+274=10,

    ;——

    ;272

    ;

    ;2271+273

    ;1,2,…,5?0;

    ;+275=1,

    ;=1,

    ;

    ;NoRTHEAST.MATH.JVoL.24

    ;and

;ALPminXl+2

    ;S.t.3xl2x2+X4=10+M.

    ;——

    ;X2

    ;

    ;2xl+X3

    ;+X5=-1+M.

    ;=1+M,

    ;l,2,…,?0,

    ;respectively.Itiseasilyseenthat=(0,0,1,10,i)riseitherafeasiblesolutionora

    ;regularsolution.SolvingtheALPbythesimplexmethod,weseethatitsiterationprocess ;is:

    ;/0+M\f0+}

    ;I1+MII

    ;10+MI\

    ;l+M/\/

    ;AnoptimalsolutionofALPisobtained.So(10/3,0,23/3,0,1)isaregularsolutionof

    ;LP.NowmakethedualsimplexiterationfromitandanoptimalsolutionofLPisobtained, ;whichis(4,1,9).

    ;5ConcludingRemarks

    ;Amethodisprovidedforfindinganinitialregularsolutionofalinearprogramminginthis ;paper.Thekeytothismethodistosolveanauxiliarylinearprogramminginsteadofto ;introduceanyartificialvariableorconstraint.

    ;1)TheALPhasanobviousfeasiblesolutionwhichcanbeobtainedbythesimplex ;method,SOanoptimalsolutionoftheALPcanbeattainedornonexistenceoffiniteoptimal ;solutionsofALPisproved;

    ;2)IftheALPhasnofiniteoptimalsolution,thentheLPhasnoafiniteoptimalone ;neither,or,ithasanemptyfeasibleregion;

    ;3)IftheALPhasafiniteoptimalsolution,thenitisaregularsolutionoftheLP.Thus ;wecansolvetheLPbythedualsimplexmethod.

    ;References

    ;f1

    ;[2

    ;Zhang,J.Z.andXu,S.J.,LinearProgramming,SciencePress,Beijing,1997. ;Xia,S.G.,Thepolynomialalgorithmfindingabasicfeasiblesolutioninthesenseofprobability,

    ;ORTransactions,2(4)(1998),39-47.

    ;[3

    Li,W.,Anewmethodtoachieveprimalfeasibilityforlinearprogramming,Oper.Res.Manag. ;Sci.,13(1)(2004),7-10.

    ;[4

    Jian,J.B.andLi,J.L.,Monotonicbuild.uppivotalmethodsforfindinginitialbasicfeasible ;solutiontolinearprogramming,J,GuangxiUniv,,19(1)(1994),27-33. ;//

;:;}.M++J+

;

;

Report this document

For any questions or suggestions please email
cust-service@docsford.com