发布时间 : 星期四 文章线性规划问题更新完毕开始阅读e3c3d680b9d528ea81c77989
=35.t.x一+xZ一x3 一xl+xZ x一+2x2 一X4
X一，XZ，X3， +xs=8
x4，xs妻O
通过计算得:
只有零维最优解即一个最优点 (2，3，2，o，o)1’ ‘
臼的法向基为
dl=(l，l，一l，0，0) dZ=(一l，l，0，一l，0)
d3=(l/3，2/3，l，1/3，1)
d’一(一3/s，l/4，一l/8，5/8，一1/8) dZ一(一l/5，一125，一2/5，o，3/5) 例2.Max一x4--xs 5.t.x一+xZ+2x3+x4=2 x一+5x2一3x3+xs=2 x一，xZ，x3，x4，xs)0 通过计算得:
有一维最优解集，其法向基为 d一(l，l，2，l，o)T
dZ一(l，5，一3，o，l)T
d’=(一l/36，一5236，1212，o，35/36)T dZ=(一127，一l/7，一227，627，o)T
中南大学硕士学位论文线性规封逐维选优强多项式解法45 最优解集中的一个最优解为
(41八05，13/21，52/105，0，0) 例3.MaxxZ一2x3 5.t.x一2x2+x3 xZ一3x3+x4 XZ一X3
x一，XZ，x3，X4， 通过计算得: +xs=2
xs)0
只有零维最优解即一个最优点 (13/2，5/2，l/2，o，o)1’ ‘
白的法向基为
d，一(l，一2，l，o，o)T
dZ=(5/6，一2/3，一13.6，l，o)T
d3一(5/48，l/8，7/48，5/16，l/45)T d’=(一/16，一/8，5/16，13216，3/16)T dZ一(一0239，一2/13，一2/39，o，4/39)T 最优解集为0维
例4.Max一x，一xZ 5.t.X一XZ Xl一X3
X4+xs=l
x一，xZ，x3，x4，xs)O 通过计算得:
有一维最优解集，其法向基为 dl=(1，一1，o，o，o)r
dZ=(l/2，l/2，一l，o，o)T
中南大学硕士学位论文线性规划逐维选优强多项式解法46 d3一(o，o，o，1，l)r
d’一(l/3，l/3，l/3，o，o)，’ 最优解集中的一个最优解为 (l，2，0，l/2，l/2)T 例5.Maxx， 5.t.xl+xZ+x3=1 Zx一+xZ+x4=2
x一xZ+xs=一2
x一，xZ，x3，x4，xs)0
通过计算得:由于F不可行，因此问题可行域为空，无最优解。 中南大学硕士学位论文线性规划逐维选优强多项式解法47 致谢
本篇硕士论文是在中南大学岳麓校区应用数学与应用软件系老师 指导下完成的。特此向长期关怀我的中南大学岳麓校区应用数学与应 用软件系诸位老师表示衷心的感谢!
此外，我还要特别感谢刘裔宏、张鸿雁、袁修贵、唐先华、陈小 松、王志忠等教授给予我的帮助与鼓励，也要特别感谢数软系各位领 导、研究生秘书谷群辉博士及办公室各位老师的大力支持与帮助。 吉乡弓子 耳7，皿皿
2002年3月于中南大学
中南大学硕士学位论文线性规划逐维选优强多项式解法48 参考文献
1.徐光辉主编，运筹学基础手册，科学出版社，1999 2
.
茨木俊秀，福岛雅夫，最优化方法，上海世界图书出版公司，1997
:弓.方述诚，5.普森普拉，线性优化及扩展:理论与算法，北京，科学出版社，1994 」.[美l索尔.加斯著，卜建华等译，线性规划方法与应用，高等教育出版社，1990 5
.
Adler，1.，Karmarkar，N.，Resende，M.GC.，andVeiga，G，AnimPlementationof Karnlarkar’5algorithniforlinearProgramming，MatllematiealProgramming，
Vo1 .
44，297一335，1989
6.Adler，1.，Karmarkar，N.，Rese一lde，M.G.C.，andVeiga，G，Datastrueturesand Progra一nmingteclllliquesfortheilnPlementationofKarmarkar’s_al四ritllm，ORSA Journalofeomputingl，84一106，1989 7
.
Adler，1.，a一记Resende，M.G.C.，Lilllitingbehavioroftheaffinescalingeontinuous tr认ieeto，·iesforlinearProgrammingProblems，MathematiealProgramming，Vol.50， 29一51，1991
8 .
Anstreieher，K.M.，Theworst一casestePinLongstePsinKarmarkar’5algorithm，Mathematiesreseareh，Vol.14，294一302，1989
9.Anstreieher，K.M.，OnthePerformaneeofKarmarkar’5algorithmoverasequence ofinterations，SIAMJournalonoPtimization，VOI.l，22一29，1991
一0.人.lstreieher，K.M.，a:记Boseh，R.A.，Lo，19stepsinano(n3L)algorithm化rlinear P一09一’an飞m1119，MatllenlatiealProgranlming，VOI.54，251一265，1992 11 .
Asie，M.D.，Kovaeevic-Vujeie，VV，andRadosavjevie一Nikolie，M.D，，AsymPtotie bellaviorofKarmarkar’5methodforlinearProgra一nming，Matllematieal Progranlming，Vol.46，173一190，1990
12 .
Balinsky，M.L.，andGomory，R.E.，aMutualPrimal一dualsimPlexmethod，Reeent advaneesinmatllematiealProgramming，editedbyR.L.GravesandP.W61fe， MaeGraW，NewYork，1963
13 .
Bar一les，E.l之.，Ava一iationofKar一11arkar’5algorithmforsolvinglinearProgramming， MathenlatiealProg一‘a一11一nillg，Vol.36，174一182，1986 14
.
Bartholo一new，J.W.H.，Chandawa坎ar，A.S.，andPuthenPura，S.C.，SIRCIT:Asystem forAT&ToverseasnetworkPlanning，ProeeedingofINFOCOM’90，SanFraneiseo 1990
15 .
Bayer，D.，andLagarias，J.C.，Karmarkar’5linearProgrammingalgoritlllnand
networkmethod、MathematiealProgramming，Vol.50，291一230，1991 16 .
Beale，E.M.L.，CyelinginthedualsimPlexalgorithm，Navalresearehlogistie quarterly，VOI.2，269一276，1955 17
.
Blandl之.G.，NewfinitePivotingrulesforthesilnPlexmethod，Math.OPerRes.， Vo1
.
2，103一107，1977 18
.
BlandR.G，Goldfarb，D.，andTodd，M.J.，TheelliPsoidmethod:asurvey，OPer. Res.，Vol.29，1030一1091，1981
19.Burrell，B.P.，andTodd，M.J.，TI，eelliPsoidmethodgeneratesdualvariables， MathematiesofOPerationsreseareh，Vol.IO，688一700，1985
20 .
Carolan，W.J.，I一1111，J.E.，Kemiington，J.L.，Niemi，5.，andWiehamnn，S.J.，An 中南大学硕士学位论文线性规划逐维选优强多项式解法49
en1Piriealevaluatio一1oftheKORBXalgoritlllnforminitaryairliftaPPlieations， OPe一Res.，Vol.38240一248，1990 21‘Cavaliel·，1’.M.，a一记Soyster，A，L.，Somecon1PutationalexPerieneeanda 11iodifieationoftlieKarmarkar’5algorithm，Presentedatthe12一thSymPosiu一non mathematiealProgramming，Cambridge，Massachusettes，1985 22.Chen，Y-C，Houek，D.J.，Jr.，Meketon，M.S.，Slutsman，L.，Vanderbei，R.J.，and Wang，P.，TheAT&TKORBXSysterm，AT&TTeehniealjournal，VOI.68， 7一19，1989 23
.
Dantzig，GB.，Maxin飞izationofalinearfunctionofvariablessubjeettolinear inequalities，AetivityanalysisofProduetionandalloeation，editedbyT.C. KooPmans，JolinwildyandSon，NewYork，1951
24 .
Da一ltzig，G.B.，a一ldWolfe，P.，Deeon1PositionPrinciPleforlinearProgramming， OPer-Res.，Vol.8101一111，1960 25
.
Dal:tzig、GB.，LillearProgranl一1、i一lga一ldextellsions，Prilleetol，UlliversityPress， l)ri一leetoll，1963 26 .