一個新的最鈍角單純形算法.pdf

1、東南大學碩士學位論文一個新的最鈍角單純形算法姓名：金婷申請學位級別：碩士專業(yè)：運籌與控制指導教師：潘平奇20071201A b s t r a c tP r o f e s s o rP i n g o Q i P a n p r o p o s e dah e u r i s t i c c h a r a c t e r i z a t i o no f a r to p t i m a lb a s i sr t h em o s

2、 t -o b t u s e - a n g l ep r i n c i p l e ) ，a n d d e r i v e da v a r i a n to f B l a n d ' sr u l e ．黜p a p e r o 伍e r sa n e w p i v o t r u l e ．A s e t o fn o n - b a s i cv a r i a b l e si sg i V e n p r

3、i o r i t y u n d e r t h em o s t - o b t n s e - a n g l ep r i n c i p l e ，E n t e r i n gv a r i a b l e s a r e s e l e c t e dw i t h i n t h i ss e t ，u n t i la l lr e d u c e dc o s t sa s s o c i a t e dw i t

4、ht h e s e th a v e c o r r e c ts i g n s ．A tt h i sm o m e n t ，r e d u c e dc o s t sa s s o c i a t e dw i t ht h er e m a i n i n g n o n - b a s i sv a r i a b l e sa r ee x A i m n e d 。I ft h e ya l l h a v ec o

5、 r r e c ts i g n s ，t h e n o p t i m a l i t y i sa c h i e v e d ．O t h e r w i s e ，an e w s e to fn o n - b a s i sv a r i a b l e si sd e t e r m i n e dt oh a v eh i g h e rp r i o r i t y , a n d t h ep r e c e d

6、 i n g p r o c e s s i sr e p e a t e d ．I nv i e wo ft h ed u a lp r o b l e m ，t h ep r o p o s e da l g o r i t h mm a y b er e g a r d e da sa k i n do fr e l a x a t i o na p p r o a c hb a s e d O nt h e m o s t -

7、o b t r u d e - a n g l ep r i n c i p l e 。T h ea l g o r i t h mi sp r o m i s i n gi nr e d u c t i o n o ft h en u m b e ro f i t e r a t i o n s ．K e y w o r d s ：L P p i v o t i n gi n d e x m o s t - o b t u s e -