Զѧ
ACTA AUTOMATICA SINICA
1999ꡡ255ڡVol.25 No.5 1999



һµԹ滮ⷨ
֡ѡ
ؼʡԹ滮磬ϰż.
NEW ALGORITHM FOR LINEAR PROGRAMMING WITH NEURAL NETWORKS
TIAN DagangFEI Qi
(Institute of System Engineering, Huazhong University of Science and Technology, Wuhan430074)
Key wordsLinear programming, neural network, entropic perturbation.
1
ηǽԹ滮÷һֶʽ㷨1.Բ㷨2ݵʹʶԹ滮ڶʽⷨ.Բ㷨ʵеӦȴɹ.ڵ㷨3-5µһʽ㷨ģԹ滮ⷽʾ൱Ǳ㷨ľȺĿдƺͷչ.
緽չʾһµļ˼.ڹеĲԺѧϰӦúͷչǰδɹ.Թ滮ԣHopfieldTankTH㷨6ַĴȻTH㷨ṩԼֲֻ֤ͬСȫС㣬ʱ߽ⲻУ7.ЩȱݵĲӰ쵱ȻTH.
ϸϰż8ݵĿ꺯.ָô˺ΪõʣһԹ滮˷ĵ㷨.
2Թ滮ϰż
Ǳ׼ʽԹ滮Pmin CTXXԼAX=bX0ԼPĶżQmax bTWWATWCAmnԼ.ֱӽP,Q⣬PŶʽ

ҪPԼż8ݣ

>0.D̵ȫԼԼĿ꺯ʹÿøԼ⣬Ŷ봫ͳϰҪ.
ĳЩ׼£ڵPΨһŽX*()lim̡0 X*()=x*x*PŽ.ͬDΨһŽW*()W*()=w*,w*DŽ.LPתΪԼD̵Ž.
D̵.>0>0

ȻʱֻҪw(,)н磬f(w,,)ļСw(,)D̵Ľw().
ݶϵͳ
(1)
ݶϵͳʣ9֪ʽ(1)ƽ㣬ضǽȶ.µĶ.
1.κΦ>0>0ʽ(1)Ψһƽw(,)ȫָͽȶ.Aʱڦ=0ʽ(1)ƽw()ڣΨһָͽȶ.
֤.ȡf(w,,)Ϊʽ(1)LiapunovӦף10ж8.7ף9ж3.֤.
ԶĽǶȿǣۦʱt仯.
(2)
2.w()Ǧ=0ʱ(1)ƽ.(t)(t)=0ҡ1()d=ޣʽ(2)ⶼw().
֤.Ӧף10ж10.1.֤.
3ϰż
ʽ(1)дɱʽ
(3)
ͼ1Ϊʽ3ͼӷͺ.
ri(w)=akiwk-ci,i=1,2,,n.һϰʵֵȽ,ʽ3̬.


ͼ1ϵͳ(1)ʵ
4ͽ
1min z=3x1+2x2+x3+4x4,
s.t2x1+4x2+5x3+x4-x5=230
3x1-x2+7x3-2x4-x6=46
5x2+2x2+x3+6x4-x7=345,
x1, x2, x3, x4, x5, x6, x70.
2̬
min z=x1+x2,
s.t 2x1-2x2+x3+x4+0.5x5=2
x1+x2+x3+0.5x5=13x1-x2+2x3+x4+x5=3,x1,x2,x3,x4,x50,
ͼ2.,Ŵ0.000 1䵽1.0e-10.1ֵΪ251.0002У
w1=0.086 957 51,w2=-0.000 000 67, w3=0.565 217 50.
2ֵͽΪ.-ҽ˲.expĴڣ㾫ҪϸߣײĽȶ1.0e-15.Ϊ0.000 1,ʱ䳤ȷֱΪ0.008 33,0.002 37.


ͼ212ķ
κΦ>0>0ʽ(1)ȫʹŽļ㲻شڵУʽ(1)ʣҲʹǿԲȡŻţٷԹ滮⣬Եõ.ͨ>0ʱʽ(1)ļжD̽ĴԣHopfieldļУҲؿǳ̬ѡȡͿ֤ԭͶżĽͬʱõ8.22̬Ӱ.һоŶȡexp⽫߼Чʣһ㽫ķ.
߼飺֡40꣬ʿ.оۼӦáߺ;֧ϵͳӦɢ̡ھеӦõ.
ѡ桡59꣬ʿʦ.о򣺾֧ϵͳۡģ֧֪֡ʶȷԷֲʽµȺߡھеӦõ.
ߵλѧϵͳо人430074
ο
1Klee V, Minty G J. How good is the simplex algorithm? In Inequalities III(Edited by Shisha O), New YorkAcademic Press, 1972, 159175
2Bland R G, Goldfarb D, Todd M J. The ellipsoid method: a survey. Oper.Res, 1981, 29:10391091
3Karmarkar N K. A new polynomial-time algorithm for linear programming. Combinatorica, 1984, 4(4):375395
4Hooker J N. Karmarkar's linear programming algorithm. Interfaces, 1986,14(1):7590
5Ghellinck G de, Vial J P. A polynomial Newton method for linear programming. Algorithmica, 1986,1(3): 425453
6Tank D W, Hopfield J J. Simple neural optimization networks: an A/D converter, signal decision circuit, and a linear programming circuit. IEEE Trans. Circuits Syst., 1986, 33(4):533541
7Jun W, Vira C. Recurrent neural networks for linear programming: analysis and design principles. Computers Ops.Res., 1992, 19(3-4): 297311
8Fang S-C, Tsao H-S T. Linear programming with entropic perturbation. ZOR.,1993, 37(2)171186
9Ž. ΢ַ̼֧. ѧ磬1981179183
10Yoshizawa T, ֣ӵ. ȶڽ͸ڽĴ. 磬1985, 36136
ոڣ1998-02-17
޸ڣ1998-10-25
