（系统工程专业论文）生产调度混合整数线性规划模型的可行解域分析.pdf

l 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：盈蓥 e l期：型旦：! 旦 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他 复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：拉叁导师签名f 茎堕! 墨日期：趔尘查户 山东大学硕士学位论文 目录 摘要i a b s t r a c t i i i 第一章绪论1 1 1 课题背景和意义。l 1 2 优化模型可行解域分析的研究现状。2 1 2 1 寻找模型的可行解。2 1 2 2 不可行性分析方法7 1 2 3 不可行模型修正方法1 2 1 3 存在的问题1 3 1 4 本文的主要工作1 4 第二章o 1 变量混合整数线性规划形式的生产调度模型1 7 2 1 引言1 7 2 2 生产调度l7 2 2 1 生产调度概述1 7 2 2 2 生产调度分类1 9 2 30 1 m i l p 生产调度优化模型2 0 2 3 1 模型形式2 1 2 3 2 实例模型2 5 2 3 3 模型约束分析和参数分析2 9 2 3 4 模型结构分析31 2 4 连续生产过程的调度规则3 2 2 5 本章小结3 3 第三章模型的可行性分析3 5 3 1 引言3 5 3 2 可行性诊断方法3 5 3 2 1 可行性诊断流程3 5 山东大学硕士学位论文 3 2 2 可行性诊断方法3 6 。3 3 可行性测试算法3 7 3 3 1 分支定界算法3 8 3 3 2 可行性测试的分支定界算法4 2 3 3 3 数值例子4 5 3 3 4 生产调度模型实例实验4 7 3 4 本章小结4 9 第四章不可行模型的不可行性分析。5 1 4 1 引言5 l 4 2 常见错误5l 4 2 1 模型错误5l 4 2 2 数据错误5 3 4 3 不可行模型的i i s 分析方法5 3 4 3 1i i s 方法5 4 4 3 2 基于约束分组的两阶段i i s 方法5 6 4 4 不可行模型的约束修正研究5 7 4 4 1 模型约束修正研究的必要性5 7 4 4 2 一般修正方法5 8 4 4 3 参数限定的模型约束修正方法5 9 4 5 基于i i s 的模型不可行性分析诊断方法6 3 4 5 1 诊断方法思想6 4 4 5 2 诊断方法描述6 4 4 5 3 数值例子6 6 4 5 4 生产调度模型实例实验6 9 4 6 本章小结7 l 第五章结论与展望7 3 5 1 本文主要工作总结7 3 5 2 进一步的工作7 4 山东大学硕士学位论文 参考文献7 5 致谢8 1 攻读硕士学位期间参与的项目8 2 山东大学硕士学位论文 c o n t e n t s a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h i i i c h a p t e r1 p r e f a c e 1 1 1b a e k g r o u da n ds i g n i f i c a n c eo f t h es t u d y 1 1 2f e a s i b l er e g i o na n a l y z i n gr e s e a r c ho v e r v i e w 2 1 2 1m e t h o df o rs e e k i n gm o d e lf e a s i b l es o l u t i o n 2 1 2 2m e t h o df o ra n a l y z i n gi n f e a s i b i l i t y 7 1 2 3m e t h o df o rm o d i f y i n gi n f e a s i b l em o d e l 。1 2 1 3e x i s t i n gp r o b l e m s 1 3 1 4m a i nw o r ko f t h es t u d y 1 4 c h a p t e r 20 1 m i l pp r o d u c t i o ns c h e d u l i n go p t i m i z a t i o nm o d e l 1 7 2 1i n t r o d u c t i o n 1 7 2 2p r o d u c t i o ns c h e d u l i n g 17 2 2 1p r o d u c t i o ns c h e d u l i n go v e r v i e w 1 7 2 2 2p r o d u c t i o ns c h e d u l i n gc l a s s i f i c a t i o n 19 2 3p r o d u c i t o ns c h e d u l i n go p t i m i z a t i o nm o d e l 2 0 2 ：；1m o d e lf o r m 2 1 2 ：；2i n s t a n c em o d e l 2 5 2 3 3c o n s t r a i n t sa n dp a r a m e t e r sa n a l y s i so f m o d e l 2 9 2 3 4s t t u c t u r e a n a l y s i so f m o d e l 3 1 2 4s c h e d u l i n gr u l e so fc o n t i n u o u sp r o d u c t i o np r o c e s s 3 2 2 5b r i e fs u m m a r y 3 3 c h a p t e r3a n a l y s i so fm o d e lf e a s i b i l i t y 3 5 ：；1i n t r o d u c t i o n 3 5 ：；2f e a s i b i l i t yd i a g n o s i n gm e t h o d 3 5 3 2 1f e a s i b i l i t yd i a g n o s i n gf l o w 3 5 山东大学硕士学位论文 3 2 2f e a s i b i l i t yd i a g n o s i n gm e t h o d 3 6 3 3f e a s i b i l i t yt e s t i n ga l g o r i t h m 3 7 3 3 1b r a n c ha n db o u n da l g o r i t h m 3 8 3 3 2ab r a n c ha n db o u n da l g o r i t h mf o rf e a s i b i l i t yt e s t i n g 4 2 3 3 3an u m e r i c a le x a m p l e 4 5 3 3 4e x p e r i m e n to ns c h e d u l i n gm o d e l 4 7 ：；4b r i e fs u m m a r y 4 9 c h a p t e r4i n f e a s i b i l i t ya n a l y s i so fi n f e a s i b l em o d e l 5 1 4 1i n t r o d u c t i o n 51 4 2c o m m o ne r r o r s 5l 4 2 1m o d e le r r o r s 51 4 2 2d a t ae r r o r s 5 3 4 3i i sa n a l y s i sm e t h o df o ri n f e a s i b l em o d e l 5 3 4 3 1i i sm e t h o d 5 z i 4 3 2a t w o - s t a g ei i sm e t h o db a s e do nc o n s t r a i n t sg r o u p i n g 5 6 4 4c o n s t r a i n t sm o d i f y i n gr e s e a r c hi ni n f e a s i b l em o d e l 5 7 4 4 1n e c e s s a r yo fc o n s t r a i n t sm o d i f y i n gr e s e a r c h 5 7 4 4 2c o m m o nm o d i f i c a t i o nm e t h o d s 5 8 4 4 3p a r a m e t e r sl i m i t e dm o d e lm o d i f i c a t i o nm e t h o d 5 9 4 5i n f e a s i b i l i t ya n a l y s i sa n dd i a g n o s i sm e t h o db a s e do ni i s 6 3 4 5 1t h o u g h to f d i a g n o s i sm e t h o d 6 4 4 5 2d e s c r i p t i o no f d i a g n o s i sm e t h o d 6 4 4 5 3an u m e r i c a le x a m p l e 6 6 4 5 4e x p e r i m e n to ns c h e d u l i n gm o d e l 6 9 4 6b r i e fs u m m a r y 7 1 c h a p t e r5 c o n c l u s i o n s 7 3 5 1s u m m a r yf o rt h ew o r k 7 3 5 2f u r t h e rs t e p sf o rt h ew o r k 7 4 v 山东大学硕士学位论文 r e f e r e n c e 7 5 a c k n o w l e d g e m e n t s 8 1 p r o j e c t sp a r t i c i p a t i o n 8 2 山东大学硕士学位论文 摘要 无论是在科学研究还是在工程实际中，最优化问题都有着重要的研究价值。 因此，学者们对于最优化问题非常重视。回顾以往，上世纪中叶起，最优化理论 与方法的研究和应用有了突飞猛进的发展。到如今，凭借先进的硬件与软件保证， 人们可以有效求解最优化问题，数值计算不再是瓶颈。简单地说，最优化问题就 是在问题的可行解域中寻找其最佳解。不同的算法有着不同的可行解域寻优方法。 然而在最优化问题的建模过程中，由于问题的复杂性、信息的不完整性以及不可 避免的人为疏忽错误，我们往往难以全面准确地描述问题。优化模型有可能因为 矛盾约束、违背约束等原因而不存在可行解域。如果不存在可行解域，任何高效 的寻优算法都无能为力。于是，模型的可行解域分析，日益引发众多学者的关注。 虽然当前有关模型可行解域的方法和结论相继出现，但是大多是针对线性规 划的，而且相关的数学方法无法照搬于实际应用。实际上，数学思想与工程实际， 二者相得益彰。运用数学分析，可以科学地解决实际问题；结合工程实际，数学 方法可以得到合理实践。本文正是以0 1 混合整数线性规划( m i l p ) 的炼油厂生产调 度模型为研究背景，在系统工程思想指导下，进行m i l p 的可行解域分析。 模型的可行解域分析包含两方面问题。第一方面问题是可行性分析，即通过 判断模型是否存在可行解域来确定模型的可行性状态，如果存在可行解域则模型 是可行的，如果不存在可行解域则模型是不可行的；第二方面问题是不可行性分 析，找到造成模型不可行的症结所在，并采取措施修正模型使其出现可行解域。 在这两方面问题的基础上，本文主要进行了以下的研究工作： 首先，介绍基于事件逻辑的优化调度模型，并建立一个具体的实例模型，然 后进行模型的参数分析、约束分析以及结构分析，并归纳调度规则，为后续章节 的可行解域分析做准备。 其次，进行模型的可行性分析。首先给出诊断模型可行性的流程与方法。然 后针对0 1 m i l p 模型，结合生产调度特点，给出一种基于规则分支的分支定界算 法，旨在进行模型可行性测试。应用本算法进行测试，可以减少需要搜索的分支， 从而缩小搜索域。在模型存在可行解域时，得到一个可行解作为以后执行模型寻 优算法的初始解。最后通过实例分析，验证本测试算法的有效性。 山东大学硕士学位论文 最后，进行不可行模型的不可行性分析。首先在前人有关最小矛盾约束集合 ( i i s ) 的工作基础上，利用调度模型特点，给出基于约束分组的两阶段i i s 方法，用 于寻找不可行模型的一个i i s 。相比一般寻找i i s 的方法，本方法更适合实际情况 而且更有效。然后，在a m a r a l 等人的一般模型修正方法的基础上，考虑参数限定 因素，给出参数限定的模型修正方法，使得数学方法可以应用于实际模型约束中 有参数限制的情况。最后，针对0 1 m i l p 模型，给出基于i i s 的不可行模型的分 析诊断方法。通过本方法的分析，可以找到造成模型不存在可行解域的问题所在， 再进行参数调整使其出现可行解域，并通过实例分析验证分析方法的效用。 文章最后对研究工作进行了总结，明确了进一步工作的任务，为下一步的研 究提供参考。 关键词：可行解域分析；可行性分析；不可行性分析；分支定界算法；最小矛盾 约束集合：模型修正；参数限定 i i 山东大学硕士学位论文 a b s t r a c t r e s e a r c ho no p t i m i z a t i o np r o b l e m si sv a l u a b l eb o t hi ns c i e n c er e s e a r c ha n di n e n g i n e e r i n gp r a c t i c e ，a n da l w a y sa t t r a c t sp e o p l e sa t t e n t i o n s i n c et h em i d d l eo fl a s t c e n t u r y , t h e r eh a sb e e ng r e a td e v e l o p m e n ti n t h es t u d ya n da p p l i c a t i o no ft h e o p t i m i z a t i o nt h e o r ya n dm e t h o d s n o w a d a y s ，w i t ht h ea d v a n c e dh a r d w a r ea n ds o f t w a r e ， t h eo p t i m a ls o l u t i o no fav e r yl a r g eo p t i m i z a t i o np r o b l e mc a nb ee f f e c t i v e g e n e r a l l y s p e a k i n g ，t h eo p t i m i z a t i o np r o b l e mi sa i m i n g a ts e e k i n gt h eo p t i m a ls o l u t i o nw i t h v a r i o u sa l g o r i t h m si n t h ef e a s i b l er e g i o n ，a n dd i f f e r e n ta l g o r i t h mt a k e sd i f f e r e n t m e a s u r e st or e a c ht h eo p t i m u m h o w e v e r , c o n s i d e r i n gt h ec o m p l e x i t yo ft h ep r a c t i c a l p r o b l e m s ，t h ei m p e r f e c t i o no f t h ei n f o r m a t i o n ，a n dt h eu n a v o i d a b l ea r t i f i c i a ln e g l i g e n c e ， i ti sq u i t ed i f f i c u l tt of o r m u l a t et h ep r a c t i c a lp r o b l e m sc o m p l e t e l y am o d e lm a yd on o t h a v ea n yf e a s i b l er e g i o nb e c a u s eo ft h ec o n t r a d i c t o r yc o n s t r a i n t so rt h ev i o l a t e d c o n s t r a i n t s u n d e rt h i sc i r c u m s t a n c e ，n oe f f i c i e n ta l g o r i t h mw i l lw o r k c o n s e q u e n t l y , t h ea n a l y s i so ft h ef e a s i b l er e g i o no fo p t i m i z a t i o n sp r o b l e m si sb e c o m i n gm o r ea n d m o r ei m p o r t a n t a l t h o u g hs o m em a t h e m a t i c a la p p r o a c h e sh a v eb e e nd e v e l o p e dt oa n a l y z et h e f e a s i b l e s o l u t i o n r e g i o n i nr e c e n ty e a r s ，m o s to ft h e ma r eb a s e do nt h el i n e a r p r o g r a m m i n g ，a l s ot h e yc o u l dn o tb eu t i l i z e dd i r e c t l yi np r a c t i c e i nf a c t ，o n l yw h e n c o m b i n i n gt h em a t h e m a t i c a lt h e o r y w i t ht h ee n g i n e e r i n gp r a c t i c ec a nw es o l v et h e p r a c t i c a lp r o b l e m se f f e c t i v e l y s o ，u n d e rt h eg u i d e l i n eo fs y s t e me n g i n e e r i n gt h o u g h t s ， t h i sp a p e rc a r r i e do u ta n a l y s i si nf e a s i b l er e g i o no fm i x e d i n t e g e rl i n e a rp r o g r a m m i n g ( m i l p ) ，o nt h eb a s i so ft h er e f i n e r yp r o d u c t i o ns c h e d u l i n go p t i m i z a t i o nm o d e l w h i c hi s i nt h ef o r mo f 0 1m i l p t h ef e a s i b l er e g i o na n a l y s i sc o n s i s t so ft w oa s p e c t s t h ef i r s tp r o b l e mi ss e e k i n g f e a s i b i l i t y w en e e dt ok n o ww h e t h e ro rn o tam o d e lh a saf e a s i b l es r e g i o n ，a n dd e c i d e t h ef e a s i b i l i t ys t a t u so ft h em o d e l t h es e c o n d p r o b l e mi sa n a l y z i n gi n f e a s i b i l i t y t of i n d t h ec r u xo ft h ep r o b l e mt h a tr e s u l t si nt h ei n f e a s i b i l i t yo ft h em o d e l ，a n dt a k e i i i 山东大学硕士学位论文 c o r r e s p o n d i n gs t e p st om o d i f yi t b a s e do nt h et w o p r o b l e m sa b o v e ，r e s e a r c hh a sb e e n d o n ea sf o l l o w s ： f i r s t ，i n t r o d u c e dt h es c h e d u l i n go p t i m i z a t i o nm o d e l ，a n db u i l ta ni n s t a n c em o d e l a c c o r d i n g l y m e a n w h i l e ，a n a l y z e dt h ep a r a m e t e r s ，c o n s t r a i n t sa n ds t r u c t u r eo ft h em o d e l ， a n dc o n c l u d e dt h es c h e d u l i n gr u l e s ，t op r e p a r ef o rt h en e x ts t e p s e c o n d ，a n a l y z e dt h ef e a s i b i l i t yo fam o d e l i no r d e rt oe s t i m a t ew h e t h e ram o d e l h a saf e a s i b l er e g i o n ，a na p p r o a c ho f d i a g n o s i n gt h ef e a s i b i l i t yo fa m o d e lw a sd e s c r i b e d a tt h es a m et i m e ，p r o p o s e dar u l e b a s e db r a n c ha n db o u n da l g o r i t h ma i m i n ga tt e s t i n g t h ef e a s i b i l i t yo fa0 1m i l p , w h i c hc o u l dr e d u c et h es e a r c h i n gf i e l d o n ef e a s i b l e s o l u t i o nc o u l db eg m n e di ft h em o d e li sf e a s i b l e ，w h i c hc a l lb ea st h ei n i t i a ls o l u t i o nf o r t h en e x to p t i m i z a t i o na l g o r i t h m s a n dt h er e s u l t so ft h ea n a l y s i sw e r ev e r i f i e db y i n s t a n c e t h i r d ，a n a l y z e dt h ei n f e a s i b i l i t yo fam o d e l b yl e a r n i n gt h ep r e v i o u sw o r kr e l a t e d 诵t hi r r e d u c i b l ei n f e a s i b l es u b s e t ( i i s ) ，a n dm a k i n gu s eo ft h es c h e d u l i n gm o d e l ，g a v ea t w o s t a g ei i sm e t h o db a s e do nc o n s t r a i n t sg r o u p i n g t h e n ，a c c o r d i n gt ol e a r n i n gt h e g e n e r a lm o d i f i c a t i o nm e t h o d ，a n dc o n s i d e r i n gt h ep a r a m e t e rl i m i t a t i o ni nap r a c t i c a l m o d e l ，r e s e a r c h e do nt h ep a r a m e t e rl i m i t e dm o d i f i c a t i o n f i n a l l y , i no r d e rt oa n a l y z et h e 0 - 1m i l pm o d e l ，ad i a g n o s i n gm e t h o db a s e do nt h ei i sm e t h o dw a sg i v e n m a k eu s eo f t h ep r o p o s e dm e t h o d ，t h ec o n f l i c tt h a tc a u s e st h ei n f e a s i b i l i t yc o u l db ef i n da n d c o r r e s p o n d i n ga d j u s t m e n t so ft h ep a r a m e t e r sc o u l db et a k e nt og a i nt h ef e a s i b l es o l u t i o n r e g i o n a n d t h er e s u l t so ft h ea n a l y s i sw e r ev e r i f i e db yi n s t a n c e t h ea r t i c l ee n d e d 谢t has u m m a r yo ft h ef u l lt e x t ，p u tf o r w a r dt h ei s s u e sw h i c h n e e dt ob es o l v e di n t h ef u t u r e k e y w o r d s ：a n a l y s i so ff e a s i b l er e g i o n ，a n a l y s i so ff e a s i b i l i t y , a n a l y s i so fi n f e a s i b i l i t y , b r a n c ha n db o u n da l g o r i t h m ，i r r e d u c i b l ei n f e a s i b l es u b s e t ，m o d e lm o d i f i c a t i o n ， p a r a m e t e rl i m i t e d w 山东大学硕士学位论文 1 1 课题背景和意义 第一章绪论 最优化是人们在工程技术、科学研究和经济管理等诸多领域中经常遇到的问 题。在管理科学、计算机科学、生物学、电子工程等领域都存在着大量优化问题。 因此，人们对于求解最优化问题的研究向来非常重视【1 1 。 从2 0 世纪5 0 年代开始，随着计算机的高速发展，最优化理论和方法的研究 与应用也突飞猛进地发展。如今，在线性规划、整数规划、非线性规划、随机规 划、多目标规划等各种最优化问题方面，理论研究发展迅速，新方法不断出现， 实际应用日益广泛。对于一些规模较小的优化问题，传统的优化算法就能达到较 高的速度和精度，如求解线性规划的单纯形法和k a r m a r k a r 投影尺度算法【2 1 、求解 混合整数线性规划的割平面法和分支定界法、求解非线性规划无约束问题的牛顿 法、共轭梯度法，约束问题的可行方向法、乘子法、序列二次规划法( s q p ) 和罚函 数法等【3 1 。对于生产实际过程中的复杂优化问题，现代优化算法是有力的工具【4 】o 如遗传算法、演化规划【5 1 、模拟退火 6 1 、禁忌搜索【7 8 】、粒子群优化【9 1 、分散搜索1 0 】 等，这些算法称为启发式算法，是通过模拟或揭示某些自然现象或过程而得到发 展的，为解决复杂问题提供了新的思路和手段。 可以说，随着科技的进步和研究的发展，如今人们具备了很强的求解能力， 不论是在硬件配备方面还是软件算法知识方面。但是，任何算法的实施都需要在 模型可行的基础上，对于一个不存在可行解域的优化模型，任何有效的求解算法 都无能为力。而在实际优化问题研究中，建模者所建立的优化数学模型是不可能 保证完全的正确性和合理性的。要建立一个好的优化模型，需要建模者对建模对 象有本质的理解，建模的难点在于如何将实际问题抽象化为有实际价值而又易于 求解的数学模型【1 1 1 。一方面，人们在优化设计建模时，由于缺乏经验或者疏忽， 可能会造成所建立的模型出现某些错误或不合理的情况。另一方面，实际生产过 程中的优化问题，例如生产调度问题，具有复杂随机动态的实际生产环境，而人 们的认知和能力是有限的，从而加大了抽象为优化模型的难度。 所以，模型的正确性成为了最优化问题的瓶颈，关于优化模型可行解域的分 析研究越来越重要。尤其在实际工程优化模型中，可行解域分析成为必不可少的 山东大学硕士学位论文 部分。本文正是以炼油厂优化调度模型为背景，进行相关的分析研究工作。j o l l i lw c h i n n e e k 在文献 1 2 】中提出了这样几个问题：当一个算法无法找到问题的可行解时 会怎么样? 我们如何知道错误是在哪里? 我们如何修正模型? 这几个问题同样指 导了本文优化模型可行解域的分析研究思路。判断模型正确与否，找到模型不存 在可行解域的原因所在，修正不可行模型使其出现可行解域，通过这些可行解域 分析工作，为我们选用优化算法求得问题的最优解奠定良好基础。 1 2 优化模型可行解域分析的研究现状 1 2 1 寻找模型的可行解 对最优化问题，是否存在一个可行解是基础问题。确定哪个解是最优解之前， 必须先确定该问题是否有可能存在一个可行解，当所有的可行域都不存在可行解 则说明问题不可行。大多数算法需要以一个可行点作为算法的初始，开始点的选 择能够影响一个算法的总体效果。一般来说，寻求一个起始点不是一个容易的任 务，它可能会占用算法总计算量的一半 2 1 。还有很多模型不可行分析方法需要约束 子集的解，快速得到可行解可以加速分析。因此，快速得到一个最优化问题的可 行解，有助于下一步的求解或者是下一步的可行解域分析。 1 2 1 1 线性规划问题 线性规划问题的一般模型表示： n l a xz = 懿 s t j 彳x ，= ) 6 ( 1 - 1 ) 【，x u 针对某个确定的具备特殊形式的线性规划( 约束都是约束，b 中没有负数 项) ，很容易可以直接找到一个可行解。而对于一般的不具备特殊形式的线性规划 问题，寻找第一个可行解还是比较困难的。比如，模型中含有等式约束或者约束， 或者b 中含有负数项。线性规划中找可行解是个好理解的问题，现在已有经典优化 与启发式算法寻找可行解。将单纯形算法用于求解一般线性规划问题，最常见的 找可行解的方法是单纯形的两阶段法。另一种常见方法是大m 法，虽然在教科书 中普遍出现，却是很少在求解实现中用到。此外，出现了多种可以加速过程的启 2 山东大学硕士学位论文 发式算法。 l 、第一阶段算法 单纯形算法要求从一个初始基可行解出发，开始单纯形方法的迭代搜索，从 可行域边界上搜索更好的可行解直至寻找到最优。所以在使用算法的时候需要为 算法提供一个可行基，而一个可行基并不容易找到。两阶段单纯形算法的第一阶 段所要完成的任务是：如果所求解的问题可行域非空，为第二阶段的单纯形算法 提供一个初始基可行解；如果所求解的问题可行域为空，判断出问题不可行并终 止算法 2 1 。 对一个标准形式的线性规划问题： m i nc t x s t a x = b 0 ，c r n , b r ”，a r 。”)( 1 - 2 ) x 0 两阶段单纯形算法的第一阶段要解决如下一个辅助问题： m i n 2 - - - - 芹 s t 血+ r = b ( 1 - 3 ) x 0 ，x 口0 其中r = 【矸，】r 是一个m 维的人工变量。由于在线性规划标准型中要 求6 。，所以 耋 = 兰 是辅助问题的一个初始基可行解。于是可以直接利用单纯 形算法求解这个辅助问题。由于限定了r 0 ，所以0 一定是目标函数值的一个下 界。因此辅助问题是可行并且有界的，用单纯形法一定可以求得该辅助问题的一 个最优解 二 。 辅助问题的最优解与原问题的可行解之间的关系，有两种情况： 情况1 若x 矿0 ，那么原问题不可行，算法终止。 情况2 若x 扩= 0 ，说明原问题是可行的。在这一情况下，要进行单纯形算法 的继续执行，需要找到原问题的一个初始可行解。如果现行基中没有任何一个人 工变量，则现行基就形成原问题的一个初始基础可行解。 2 、大m 法 山东大学硕士学位论文 对于标准形式的线性规划原问题( 1 - 2 ) ，引入人工变量r = 【彳，r ，并 对每个人工变量都强加一个大惩罚因子m 0 ，形成如下问题： m i l l z = 罗c + y 胍? j x , z 2 乙+ 乙埘 s t 厶+ 矿= b ( 1 4 ) x 0 ，x 。0 该问题的初始基础可行解可以取为 兰 = 兰 。 已经证明，当m 足够大的时候，该问题与原问题( 1 2 ) 有相同的最优解。虽然 理论上m 取为足够大的正数，但是实际执行的时候不易处理。 3 、内点法 运用不同的思想方法获得通过可行区域内部的迭代点列的算法，统称为解线 性规划问题的内点算法。各种内点算法的共同特点