（电机与电器专业论文）一种特殊永磁型磁体的匀场技术研究.pdf

沈阳工业大学硕士学位论文 t h ep a s s i v es h i m m i n gt e c h n i q u er e s e a r c hf o ras p e c i a la p p l i c a t i o no f t h ep e r m a n e n t m a g n e t a b s t r a c t i no r d e rt om a t c hi m a g i n gs t a n d a r d , i t sr e q u i r e dt h a tt ob r i n gm a i nm a g n e t i cf i e l d h o m o g e n e i t yo fm a g n e t i cr e s o n a n c ci m a g i n g ( m r i ) a p p a r a t u st oa na c c e p t a b l el e v e l h o w e v e r , e v e l lf o ra ni d e a ld e s i g n , m a g n e t i cf i e l dh o m o g e n e i t yd o e s n tr e a c he x p e c t e dl e v e l a f t e rm a g n e ta s s e m b l i e s h e n c e ，s p e c i a lm e t h o d sa r en e e d e dt oi m p r o v et h eh o m o g e n e i t y , t h a t ss h i m m i n g a tp r e s e n t , t w oc o m m o nm e t h o d sh a v eb e e nu s e dt os h i m ：a c t i v es h i m m i n g a n dp a s s i v es h i m m i n g t h eb a s i ct h e o r yf o rs h i m m i n gi sb a s e do ns p h e r i c a lc o o r d i n a t e a n a l y t i cm e t h o d i tb r i n g sh o m o g e n e i t yo ff i e l dt om a t c hi m a g i n gs t a n d a r db yc o u n t e r a c t i n g u n w a n t e ds p h e r i c a lh a r m o n i cc o m p o n e n t a tb e g i 皿i n g t h et h e s i si n t r o d u c e sd o m e s t i ca n df o r e i g ns h i m m i n gd e v e l o p m e n t , a n a l y z et h ee x i s t i n gs h i m m i n gm e t h o d ，a n dp r o b ei n t ot h ep o s s i b l em e t h o d t h e nk e y q u e s t i o n s ，d i f f i c u i t i e sa n dm a i nc o n t e n to f t h i sr e s e a r c ha r ep r e s e n t e d s e c o n d l y ，i nt h ep r o c e s so f s t u d ys h i m m i n gm e t h o d so f p e r m a n e n tm a g n e tf o ro p e nm l u s y s t e m ，a c t i v es h m m 她i su n s u i t a b l ed u et oi t ss p e c i a l t i e s i fc o m m o nm e t h o d sb a s e do n s p h e r i c a lh a r m o n i cf u n c t i o nw e r ea d o p t e d n o n l i n e a re q u a t i o n sw i l lb es o l v e da tl a s t h e n c ea h i g he f f i c i e n tm e t h o di sn e e d e d i nt h i sp a p e r , ap a s s i v es h i m m i n gm e t h o db a s e do ni n t e g e r p r o g r a m m i n ga n db a s i ct h e o r i e so fs h i m m i n gi sd e v e l o p e d , a n db u i l du pas h i m m i n g m a t h e m a t i cm o d e lt h a ti ss o l v e db yu s i n gl i n g 0 8 0a n dm a t l a b 6 5 t h er e s u l t sa r e d i s p l a y e di nt h ef o r mo f g r a p h i c s 珏翻1 y ，t h ee x p e r i m e n t a lv e r i f i c a t i o ni sp e r f o r m e di no r d e rt ot e s tc o r r e g q l l e s so ft h e m o d e la n dr e s u l t s s h i m m i n ge x p e r i m e n t sa r cp e r f o r m e di nq u e e n - p o l em a g n e ta n dt r a d i t i o n a l c - s h a p em a g n e t , a n di tt u r n e do u tt h a tt h et r e n do f t h em o d e li sr e a s o n a b l e i nt h ep r o c e s so f m e a s h r e , am e t h o db a s e do nh a r m o n i cf u n c t i o nw a sa d o p t e dt oo b t a i nm a s se x p e r i m e n td a t a w h i c h 矾f o u n d a t i o nf o rt h er e s e a r c h d e t a i l e de x p e r i m e n t a le l t 0 1 $ a n ds o m ed e f e c t sa 托 a n a l y z e di nt h i st h e s i s 一种特殊永磁型磁体的匀场技术研究 l a s t ，t h es u m m a r yw h i c hi n c l u d i n gs o m ew e a k n e s sa n dq u e s t i o n sn e e dt ob es o l v e di s g i v e na b o u tt h ew h o l ep a p e ra n ds u g g e s t i o n sf o rt h ef u r t h e rr e s e a r c ha l ep r o p o s e d k e yw o r d s ：m a g n e t i cr e s o n a n c ei m a g i n g ( m r l ) ，p a s s i v es h i m m i n g ，i n t e g e r p r o g r a m m i n g , s h i m m i n ge x p e r i m e n t i v 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 关于论文使用授权的说明 2 舢7 。；2 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：皇堡垄导师签名 加叼弓2 沈阳工业大学硕士学位论文 1 绪论 各类电磁或永磁机构均可产生磁场，特殊磁场的设计是电磁装置设计的重要组成部 分。本课题的研究对象是一种用于核磁共振成像装置的永磁型主磁体的匀场技术。 1 1 磁共振成像( m r i ) 发展概述 核磁共振( n u c l e a rm a g n e t i cr e s o n a n c e ，n m g ) 是2 0 世纪四项重要科技发明( x 射线、核磁共振、中子衍射和激光) 之一核磁共振成像( n u c l e a r m a g n e t i c r e s o n a n c e i m a g i n g ，n m p o ) 和核磁共振波谱分析( n u c l e a rm a g n e t i cr e s o n a n c es p e c t r o s c o p y ) 的 物理基础都是核磁共振现象。核磁共振成像现一般称为磁共振成像( m r j ) 。 磁共振成像是利用收集磁共振现象所产生的信号而重建图像的成像技术，因此，也 称自旋体层成像、核磁共振c t 。m r i 从原理的发现到目前临床各种先进成像技术的 应用，是基于科学家们对原子结构认识的不断深化。1 9 2 4 年p a u l i 发现电子除对原子核 绕行外，还可高速自旋，有角动量和磁矩。核磁共振现象是在1 9 4 6 年，由美国哈佛大 学的e p u r c e l l 及斯坦福大学的f b l o c h 各自独立发现的。由于该发现在物理学、化学上 具有重要意义，e p u r c e l l 与f b l o c h 共同获得1 9 5 2 年的诺贝尔物理学奖。从五十年代初 起，核磁共振越来越广泛的应用于化学与物理学的研究，以阐明物质的分子结构。1 9 7 1 年美国纽约州立大学的r d a m a d i a n 用n m r 波谱分析，发现了肿瘤组织的纵向弛豫时 间( t 1 ) 和横向弛豫时问( t 2 ) 比正常组织的弛豫时间长的现象。1 9 7 2 年，这也是x - c t 开始在临床中出现的一年，美国科学家p l a u t c r b u r 提出应用n m r 现象形成图像，并 首次从实验上得到了n m r 成像，于是核磁共振成像( m a g n e t i cr e s o n a n c ei m a g i n g ，m r l ) 学科正式诞生【2 】。1 9 7 8 年m a l l a r d 、h u t c h i s o n 和l a u t e r b u r 等人用核磁共振设备取得了第 一幅人体头、胸和腹部的图像。m r i 遂成为医学家做医学诊断的工具。 随着成像技术以及计算机与磁体技术的发展，核磁共振成像技术的分辨能力显著提 高，在x - c t 技术的基础上研制成功了m r i 系统。1 9 8 0 年m r i 设备开始商品化，并应 用于临床。它是核磁共振原理和实验方法、计算机图像处理技术和图像重建理论相结合 的产物。早期m r i 的实验及8 0 年代磁共振在医学上的应用，使m r i 成为一个具有高级 诊断技术标准的现代化诊断系统。 一种特殊永磁型磁体的匀场技术研究 目前，m r i 技术已经广泛的应用于医疗临床诊断，成为五大医疗诊断设备( 超声、 放射学、x - c t 、m r i 和核医学) 之一。 1 2 磁共振成像( m r i ) 的基本特点 m r j 涉及多学科的现代理论及多种现代的科学技术，其中包括物理学、波谱学、信 息电子技术、计算机技术、超导及磁体技术、机械技术、系统和应用软件技术、图像重 建技术以及生物诊断技术等。因此，m 砒是一种非常精密复杂的高科技产品。其综合性 能优于其它四类医用影像设备，这是由于其具有下述优点【3 4 】而决定的： ( 1 ) 多核多参数成像，对比度高，效能提高，对软组织成像效果更好，密度层次更 丰富。 ( 2 ) 不仅提供诊断学信息，而且提供与生化病理有关的信息，诊断效果更佳。 ( 3 ) 可以进行心脏，大血管形态的诊断和其它功能诊断。 ( 4 ) 可以在任意方位作断层，有助于显示病变范围，立体观察病变组织。 ( 5 ) 空间分辨率高，满足脑瘤早期诊断的特殊要求，无骨伪影。 ( 6 ) 使用技术灵活，通过改变脉冲序列参数即可改变图像对比度，从而更好显示病 变组织。 ( 7 ) 对病人无损害和危害。 由于m r i 所具备的突出的优点，这一新的医学影像诊断技术已迅速的在世界各地 的医疗中心和大医院开展起来。但m r i 检查和诊断还有一些不足的地方，主要为： ( 1 ) 对一些病例的定性诊断仍有困难。 ( 2 ) 成像速度及信噪比等方面还有不尽满意之处。 ( 3 ) 有运动伪影。 ( 4 ) 有许多禁忌，如装有心脏起搏器、体内留置金属异物和金属假体等患者不宜作 m r i 检查；监护仪器，抢救器材不能带入m r i 检查室等等。 因此，m r j 在缩短成像时间、进一步提高成像质量及发展诊断技术等方面大有文章 可做。 一2 一 沈阳工业大学硕士学位论文 1 3 课题的来源和意义 1 3 1 课题的背景 八十年代中后期，我国的专家学者和企业界均对m p d 这一涉及物理、化学、数学、 计算机科学、图像处理、生物学和临床医学等多学科的图像诊断方法产生兴趣。由于 m r i 的突出优点，故自世界上第一台医用磁共振成像技术设备在上世纪8 0 年代初面世 以来，m r i 市场在全球发展迅速，在我国的发展也很迅速。据有关资料显示，未来十年 我国应有上千亿人民币的市场容量。目前，磁共振成像仍然处于技术进一步完善和继续 扩大应用领域的发展阶段。 医用磁共振成像装置按功能可租略的分为磁体系统、谱议和计算机三大部分。其中， 磁体系统是重要的组成部分，它由主磁体、梯度线圈和射频线圈组成。主磁体是m r i 装置中体积最大、最重要的部分，其价格也相当的昂贵。为了显示人体被测部分的清晰 图像，磁共振成像要求主磁体能在较大的成像空间内产生高均匀度的磁场，称为主磁场。 例如，对于头部成像而言，工作空间中心部位直径为3 0 c m 的球域( 称为样品区) 内， 磁场不均匀度的相对误差应限制在l o 5 左右，甚至更高。磁场均匀度的提高可以改善整 个成像系统的信噪比，提高扫描图像的分辨率。因此如何提高大空间内的磁场的均匀度 是磁体设计和制造的关键问题，磁场均匀度指标也是主磁体系统最重要的指标之一。 在磁体设计和组装以后，由于加工误差，实际上磁场的均匀度远不能达到预定要求， 需要采用特殊方法进行匀场，这也是本课题的研究对象。本课题是高等学校博士学科点 专项科研基金( 2 0 0 5 0 1 4 2 0 0 3 ) 资助项目。此专项基金主要用于研究一种全新的用于开 放式磁共振成像系统永磁型磁体的匀场技术。因此，若能抓住这一宝贵时机，积极开展 这一领域的研究，则将对发展我国自己的医学仪器制造工业起着重要的推动作用。 1 3 2 课题的意义 m r i 理论要求m r 设备的主磁体能够产生一个非常均匀的静磁场。磁体方案能否 从理论设计到产品化，匀场技术( s h i n l m i i l g ) 起着举足轻重的作用f 5 棚。首先，在设计 阶段，应力求提高主磁体所产生的磁场的均匀度。但即使对于理想的设计方案，磁体安 装后的磁场均匀度也远远不能达到设计所期望的水平，其不均匀度往往会超过期望值两 3 一 一种特殊永磁型磁体的匀场技术研究 个数量级。因此，为了得到满意的主磁场均匀度，需要在磁体安装后对基础磁场进行调 整，以保证样品区磁场达到所需要的均匀度指标，这一过程就称为“匀场”又称为“垫 补”( 类比于用各种垫块去调平一个机械系统，英文称为s h i m ) 。 磁场均匀度指标的定义如下： 灯：塾= 塾2 1 0 6( 1 1 ) 1 b 。b 其中，玎表示磁场的均匀度指标，通常用p p m ( p a n p e r m i l l i o n ) 表示，即百万分之一， 曰一与坟。分别为区域内的磁感应强度的最大值与最小值。 匀场的目标是要使一个不够均匀的磁场达到预定的均匀度的要求。匀场的具体方法 与主磁场的类型( 超导型，永磁型或电磁型) 密切相关，般可分为有源匀场和无源匀 场1 9 1 。有源匀场是用通电线圈产生的磁场来进行匀场，w e s t o na a n d e r s o n 在1 9 6 1 年的文 章详细介绍了有源匀场【1 0 】；无源匀场是用小铁片或小磁片置于主磁场中来进行匀场。这 一过程相当繁复，需要调试人员付出大量的时间和精力。如果采用人工操作，经验丰富 的调试工程师也需要几天的时间，新手可能需要一个月。在磁共振成像产业中占有垄断 地位的国外企业在超导型主磁体制造上采用了先进的匀场技术，这一技术可以在较短的 时间内实现匀场目标，在磁共振成像产品制造中成为高级的商业机密。而国内在这一领 域的研究则尚处于初级阶段。 永磁型开放式的磁体结构有相当大的吸引力1 1 4 1 ，是目前磁共振成像设各发展的主 要方向。增大磁体的开放度不仅能减少病人的幽闭感和心理压力，便于对病人的监护， 而且也是功能成像和介入治疗的需要。我国是稀土永磁富产国，而且在永磁体设计方面 人才济济，开放式的磁体结构是国产磁共振成像设备的主流。因此发展我国具有自主产 权的磁共振成像设备，系统深入的研究开放式永磁型磁体的匀场技术，对发展我国的 m r i 产业、提高人民的健康水平具有实际意义。 综上所述，本课题的完成将具有重要的理论意义和应用前景。 1 3 3 国内外匀场技术的发展状况 高均匀度磁场的匀场技术涉及电磁场的逆问题、电磁场软件工程、高精度磁场与位 置测量，这一领域的研究是随着磁共振成像设备的开发与应用而发展的。目前，磁共振 一4 一 沈阳工业大学硕士学位论文 成像仍处于技术进一步完善和继续扩大应用领域的发展阶段，开放性永磁型磁体的匀场 研究也随着永磁型m r i 设备的发展而备受关注【b 】。 临床使用的m r i 系统按照主磁场的强弱可分为低场系统( 磁感应强度从0 0 2 t 到 0 3 5 t ) 、中场系统( 分0 5 t 和1 o t 两档) 和高场系统( 主要是1 5 t 和2 o t 两档，事 实上目前高场系统的磁感应强度已经远远突破2 0 t ) 0 6 1 = 类；按照主磁体的结构分类， 可分为超导型、永磁型和电磁型三种，其中超导型用于0 5 t 以上的中场和高场系统， 永磁型和极少量电磁型用于低场系统，电磁型磁体由于消耗运行电能，且磁场均匀度不 够高，基本上已被淘汰。 在传统医用m r i 仪器的研发方面，美国的g e 、荷兰的p h i l i p s 、德国s i e m e n s 以及日本的h i t a c h i 等国外公司处于领先地位，我国深圳安科公司于1 9 8 9 年开发成功 第一代国产铁氧体永磁m r i 系统，中国科学院电工所于1 9 9 3 年开发成功了国内首台以 钕铁硼材料为磁源的永磁m r i 磁体。目前国内企业除深圳安科外主要有北京万东、沈 阳东软、宁波鑫高益等几家。国内企业的产品主要在永磁低场领域，而在高场m r i 领 域，技术上领先的外资企业占据着主要市场。 国外在超导型磁体的制造方面占有着垄断地位。在超导型磁体的匀场技术方面也已 经取得了很大的进展。匀场方法通常基于球坐标的解析法，其思路是：如同对随时间变 化的电信号作傅立叶分解那样，将磁体安装后形成的不够均匀的基波磁场分解成一系列 线性无关的空间谐波的线性组合，各谐波称为球谐波，然后采用一组特殊设计的通电线 圈( 称为有源匀场) 或者一系列小铁片或小永磁片( 称为无源匀场) ，放置在适当的位 置，有目的的抵消基础场中不需要的球谐波分量。关于这种匀场方法已经发表了大量论 文【1 7 - 2 5 。对永磁型磁体，特别是开放式永磁型磁体的匀场技术的研究落后于超导型磁体， 公开发表的文献也比较少。美国g e 公司b d o r r i 等人1 9 9 3 年的文章介绍了一种超导型 磁体进行无源垫补的方法 2 6 1 ，并申请了专利。上海交通大学周涛等人在开放型电磁式磁 体的设计中研究了一种无源垫补的方法，这些方法对于开放式永磁型磁体匀场技术研究 具有参考意义。东北大学高国灿对一种永磁型磁体的匀场方法进行了研究取得了宝贵经 验叨。总之，在永磁磁体低场m r i 的匀场技术方面，尚未见到系统深入的研究报告。 一5 一 一种特殊永磁型磁体的匀场技术研究 对主磁场进行垫补的匀场技术是国内外m r j 研究者和制造商关注的问题。国外先 进的匀场技术目前是高级的商业机密，而我国的研究仍处于初级阶段。开放式m r i 主 磁场均匀度较低的特点更加重了匀场的难度。对这类磁体匀场技术的研究属于电磁场逆 问题和电磁场工程，涉及特殊磁场的设计与优化、磁场的精确测量和计算机软件工程， 并且要求高精度的磁场计算、高精度的磁场测量和高精度的空间定位三方面结合起来， 是一个交叉学科问题，也是目前电磁场工程领域的难点和热点问题。 1 4 课题的主要内容 ( 1 ) 建立适合于开放式永磁型m m 磁体匀场的数学模型。鉴于常规的球谐波分解与 消去高次项的方法不适合于开放型永磁体的匀场，采用无源垫补片的理论和方法在目前 的研究还不够充分，需要探索适用于开放式永磁型m r j 磁体匀场的新思路，建立恰当 的数学模型。 ( 2 ) 智能匀场软件的研制。匀场过程是高精度的计算与测量的结合。规定位置空间 点的磁场测量可通过恰当选择和应用目前已有的高精度磁场测量和位置测量仪器来实 现。快速高效的计算，众多垫补片的位置和大小的确定、测量数据的收集和处理需要精 心设计的计算机软件来实现，并且需要若干次反复。所以能否研制出高效智能的匀场软 件也是本课题的主要任务。 ( 3 ) 与企业合作，进行匀场实验。匀场理论、数学模型、方法与软件需要在实践中 检验和完善。本课题将与有关企业合作，迸行现场试验和调试并不断改进软件功能。 1 5 小结 本章在简要介绍了核磁共振( m r i ) 技术的发展及其特点后，着重说明了本课题的 背景、意义及国内外的发展现状，提出了课题的主要内容。 一6 沈阳工业大学硕士学位论文 2 整数规划算法 运筹学作为科学名称，最早出现在2 0 世纪3 0 年代。大英百科全书将其解释为，“运 筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目 标和数量分析的工具”。中国大百科全书的释义为，“运筹学用数学的方法研究经济、 民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际 系统有效运行的技术科学，它可以预测发展趋势，制定行动规划或优选可行方案”1 2 8 。 运筹学的早期工作历史可以追溯到1 9 1 4 年。军事运筹学中的兰彻斯特战斗方程是在 1 9 1 4 年提出的，排队论的先驱工作者丹麦工程师埃尔朗1 9 1 7 年在哥本哈根电话公司研 究电话通讯系统的时候，提出了排队论的一些著名公式。贮存论的最优批量公式是在本 世纪2 0 年代初提出的。线行规划是由丹捷格在1 9 4 7 年发表的成果。所解决的问题是美 国空军军事规划时提出的，并提出了线形规划问题的单纯形法。在我国古代文献中记载 着一些朴素运筹学思想的事例，例如，田忌赛马和丁渭主持皇宫修复等。我国第一个运 筹学小组于1 9 5 6 年在中国科学院力学研究所成立，1 9 5 8 年建立运筹学研究室。由于运 筹学在各个领域都有应用并取得许多成果，使运筹学有了飞快的发展，并形成了许多分 支，如数学规划( 线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划 等等) 、图论与网络、贮存论、排队论、对策论、决策论等。运筹学研究的基本特征是： 系统的整体观念，多学科的综合，以及模型方法的应用。 作为运筹学( o p e r a t i o n sr e s e a r c h ) 的主要分支之一的整数规划，由于其与线性规 划有着密切的联系，所以先介绍线性规划算法，然后再论述整数规划算法。 2 1 线性规划与单纯形法 线性规划是运筹学的一个重要分支，自1 9 4 7 年丹捷格( g b d a n t z i g ) 提出了一般 线性规划问题求解的方法单纯形法之后，线性规划在理论上趋向成熟，在实用中日 益广泛与深入，特别是随着现代计算机处理能力的不断提高，线性规划算法的适用范围 已经渗透到社会生产的各个领域中。 一种特殊永磁型磁体的匀场技术研究 2 1 1 线性规划问题及其数学模型 在现代生产和经营管理工作中，常常要规划如何在现有资源条件限制下，使预期目 标达到最优。 线性规划问题的数学模型由三个要素组成：变量，或称决策变量，是问题中要确定 的未知量，它用以表明规划中用数量表示的方案、措施，可由决策者决定和控制；目标 函数，它是决策变量的函数；约束条件，指决策变量取值时受到的各种条件的限制，通 常表达为含决策变量的等式或不等式。 如果一个规划问题的数学模型中，如果决策变量的取值是连续的，目标函数是决策 变量的线性函数，约束条件是包含决策变量的线性等式或不等式，则这类的规划问题称 为线性规划问题。 假定线性规划问题中含有聆个变量，分别表示为x ，c ，= 1 ，n ) ，在目标函数中x ，的 系数为c ，称为价值系数，x j 的取值受m 项资源的限制，用龟( f = l ，埘) 表示第f 种资源 的拥有量，用q ，表示变量x 。取值为1 个单位时所消耗的或含有的第f 种资源的数量，通 常称为技术系数或工艺系数。则线性规划问题的数学模型可表示为： m a x ( 或m i n ) z = c l x l + c 2 工2 + + c a l l 鼍+ d 1 2 屯+ + q 。矗( 或= ，) 执 口2 l 而+ 口2 2 而+ + 口2 一矗( 或= ，舰 ( 2 1 ) a m l 而+ 2 屯+ + q 埘矗( 或= ， ) 6 胛 毛，x 2 ，矗0 s t 垮啊蛾啦弦 ( 2 2 ) 【x 0 沈阳工业大学硕士学位论文 式中c = 如，巳，厶) ； x = 而 也 ： ； 0 = q j 啦 ： ；b = 6 l 6 2 ： 6 肿 变量吩的取值一般非负，即o ；从数学意义上可以有o 若的取值范围 为卜a o ，+ m ) ，则称一取值不受约束，或_ 无约束。 由于目标函数和约束条件在内容和形式上的差别，线性规划问题可以有很多种表达 形式。为了便于讨论和制订统一的算法，规定线性规划问题的标准形式如下： l n a x z = c ，_ s t 协- = 屯( f = 1 ， q 3 【_ o ( ，= 1 ，丹) 标准形式的线性规划模型中，目标函数为求最大值( 有的文献中规定取最小值) ，约束 条件均为等式，约束条件右端常数项6 全为非负值，变量x ，的取值均为非负值。对不符 合标准形式的线性规划问题，可以分别通过下列方法将其化为标准形式。 目标函数为求最小值，也就是m i n z = c j _ ，因为求m i n z 等价于求m a x ( _ z ) ，令 z = 一z ，即化为m 缸= c j _ 。 约束条件的右端项6 s0 ，这时只要将等式或不等式的两端同时乘( - 1 ) ，即可。 约束条件为不等式时，在不等式的左端加入松弛变量，把不等式约束条件变为等式 约束条件。 取值无约束的变量，例如x 的取值无约束，这时可令x = z 一，其中x 0 ，0 ， 将其带入线性规划模型即可。 对于x 0 的情况，只需令一= 吖。 下面举例说明如何将下面的线性规划问题化为标准形式。 一9 一 一种特殊永磁型磁体的匀场技术研究 r a i n z = 毛+ 2 x 2 + 3 屯 一2 x l + 工2 + x 3s 9 3 一+ 而+ 2 x 3 4 4 而一2 x 2 3 x 3 = - 6 而0 , x 2 0 , x 3 取值无约束 令z = 一z ，爿= - - x 1 ，x 3 = 一，其中2 0 ，0 ，按上述规则可将此线性规划问 题转化为标准形式如下： m a x z = x ：一2 x 2 3 x ；+ 3 x ；+ 0 x 4 + 0 x 5 2 工：+ 而+ 一+ x 4 = 9 3 + 也+ 2 x ；一2 x ；一= 4 4 x ；+ 2 x 2 + 3 x ；- 3 = 6 ，x 2 ，x 4 ，x 5 0 2 1 2 线性规划问题解的概念 几十年来的大量使用所取得的效果表明，单纯形法是一个效率很高的算法。到目前 为止还没有碰到过用它算不出来的线性规划问题。1 9 7 2 年，克里( k l c e ) 和明地( m i n t y ) 人为地设计出了一些线性规划问题，用单纯形法来求解它们，效果非常不好，计算时间 随问题规模的增长而成倍的增加。可是大量的实践表明单纯形法是一个好算法。1 9 8 3 年，著名数学家菲尔斯奖得主斯梅尔( s m a l e ) 从理论上证明，使单纯形法失灵的 那些线性规划问题在实际中出现的可能性是微乎其微的。实践也表明，这类问题难得碰 上，事实上就没有碰到过。因此从概率意义上讲，尽可以放心的使用单纯形法。 下面简要介绍一些线性规划问题的解的概念和几个基本定理。 可行解，即满足式2 3 中约束条件的解石= “，) t ，称为线性规划问题的可行 解，全部可行解的集合称为可行域； 最优解，使式2 3 中的目标函数达到最大值的可行解称为最优解； 基，设4 为式2 3 中约束方程组0 = 包的肌甩阶系数矩阵( 驴坍) ，其秩为m ， j = l 占是矩阵爿中的一个m m 阶的满秩子矩阵，称口为线性规划问题的一个基。不失一般 性，设 沈阳工业大学硕士学位论文 叱刊瓠刖 b 中的每一个列向量弓o = l ，小) 称为基向量，与基向量e 对应的变量称为基变量； 基解，在式2 3 约束方程中，令所有非基变量靠“= + ：一= 矗= o ，又因为有 俐o ，根据克莱姆法则，由埘个约束方程可解出m 个基变量的唯一解= “，靠) t 。 将这个解加上非基变量取0 的值有x = “，靠，o ，o y ，称x 为线性规划问题的基解； 凸集，如果集合c 中的任意两个点五，五，其连线上的所有点也都是集合c 中的点， m 舡z - - 勺勺 。骞弓巧= 包o = ，m ) 。 2 4 【_ o ( ，= l ，撑) 在其约束条件弓_ = 岛的变量系数矩阵中总会存在一个单位矩阵 一种特殊永磁型磁体的匀场技术研究 b = ，只) = 1o 0l ： oo 式中墨，只称为基向量，其对应的变量而，称为基变量，模型中的其它变量称为 非基变量，令所有的非基变量等于零，即可以找到一个解 j = b ，靠，+ p ，) t = 如，k ，o ，o ) t 因为6 o ，所以x 满足约束条件_ o 【，= l ，n ) ，即是一个基可行解。 在一般情况下，经过迭代之后，可得 而= 耳一a # x jo = 1 ，2 ，m ) ( 2 5 ) 将式2 5 带入式2 4 中的目标函数中，整理后得 z = 喇+ i q 一i nq 吩b ( 2 6 ) m 月厂、 t - i j - m + l t m l ， 令 z o = q 6 f ，乃= 嘞，j = m + l ，行 故 z = z o + 乃_ ( 2 8 ) j _ + i 然后，进行最优性检验与解的判别。对线性规划问题的求解结果可能出现唯一最优 解，无穷多最优解，无界解和无可行解四种情况，为此引入如下几个定理对所求的结果 进行判别。 力 b乃 一 b 。_ l + = = 则 0 一 勺 = 乃 令爵 沈阳工业大学硕士学位论文 定理2 4 ，若x ( o ) - - ( b ；，e ，6 二，o ，o ) t 为对应于基b 的一个基可行解，且对于一 切j = m + l ，h 有仃j o ，则x ( o ) 为最优解。称乃为检验数，此为最优解判别定理。 定理2 5 ，若x f o ) = 衙，配o ，o ) 7 为对应于基丑的一个基可行解，且对于一 切_ ，= m + l ，栉有巳o ，又存在某个非基变量的检验数+ 。= o ，则线性规划问题有 无穷多最优解。 定理2 6 ，若j ( o ) = 雠，畦， o ，o ) t 为对应于基丑的一个基可行解，有一个 “ 0 ，并且对b l ，2 ，m 有口。“s o ，那么线性规划问题具有无界解( 或称无最优 解) 。 若初始基可行解x ( o ) 不是最优解或者不能判别无界时，需要找一个新的基可行解。 这就是基变换。为了换基，先要确定换入变量，再确定换出变量，让他们相应的系数歹i j 向量进行对换，就褥到一个新的基可行解。 换入变量的确定方法如下，由式2 8 得知，当乃 o 时，t 增加则目标函数值还可 以增大，这是要将某个非基变量_ 换入到基变量当中去( 称为换入变量) 。若有不止一 个q 0 ，为了使目标函数的值增加的快，一般选择仃j o 中的大者( 可以任意选择) 即 m a x ( o j o ) = 吼 ( 2 9 ) 则对应的黾为换入变量。但也可以任选或者按照最小的仃，值选取。 换出变量的确定，设初始基可行解中的前m 个为基变量，即 x o ) = 钾，吒0 ，。冀，o ，o ) r 将其带入式2 4 中的约束方程_ = 包有 j - 1 只霹= 6 ( 2 1 0 ) i = l 式2 1 0 系数矩阵的增广矩阵为 一种特殊永磁型磁体的匀场技术研究 因为置，只是一个基，其它向量可用这个基的线性组合来表示，有 所以 将式2 1 1 乘上0 ( 0 0 ) 得： 弓一只= o 小一喜嘞p ) = 。 将式2 1 2 与式2 1 0 相加并整理后有 册，、 w 一锄k 十= 6 j # l 由式2 1 3 找到满足约束方程组弓_ = 6 f 的另一个点x ( 1 ) ，有 j - i ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 膏o ) = 钾一o a t j , - - , o ，o ，岛，o ) t 其中口是x ( 1 ) 的第，个坐标的值。要使x o ) 是一个基可行解，因规定口 o ，故应对所有 i - - 1 ，2 ，肼，存在 # 一钆o ( 2 1 4 ) 令这m 个不等式中至少有一个等号成立。因为当o 时，式2 1 4 显然成立，故可令 口= 叩卧 。离 ( 2 1 5 ) 6 慨阮卜胁 只； 一 j 0 气吒；艺； 己o o； 芝o l ；o r l o ；o 沈阳工业大学硕士学位论文 所以 # 一僦器 故j o 是个可行解。又因与变量爿，吐i ，吐l 一，靠。_ 对应的向量， 上b 列有如下增广矩阵 b 岛 如 钆 岛 k 。 ( 2 1 6 ) 经重新排列后加 又因为 0 ，所以上述矩阵元素组成的行列式不等式不为零，所以 鼻，最，最。，毋，另。，只是一个基。 在上述增广矩阵中进行行初等变换，将第f 行乘上( 1 ，) ，再分别乘以( _ 嘞) 加到各 行上去，则增广矩阵左半部变成为单位矩阵，又因为岛嘞= 口，故 b = 慨一l ，岛- l o a l _ l d , 0 ，b t “一a 码+ u ，吒一日2 阿j 1 由此x ( o 是同工( o ) 相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。 2 1 4 单纯形法的计算步骤 根据上一节论述的原理，将求解线性规划问题的单纯形法的求解步骤归纳如下： 第一步，求初始基可行解，列出初始单纯形表。首先，将非标准型的线性规划问题 化为标准形式，因为总是可以设法使约束方程的系数矩阵中包含一个单位矩阵 ，最，巴) ，以此作为基并求出问题的一个初始基可行解。由于检验一个基可行解是 否是最优解，需要比较其目标函数值与相邻基可行解的目标函数值的大小。为了便于计 算和对比，对单纯形法的计算设计了一种专门的表格，称为单纯形表( 见表2 1 ) 匕o o ；o o o ；l “o o ；o o 1 ；o b 乃嘶鲫：州卿圳； o o ：o o ；o b o l ；o o o ；o 一种特殊永磁型磁体的匀场技术研究 表2 1 单纯形表 t a b l e2 1s i m p l e xt a b l e 在表2 1 中，列中填入基变量，这里是五，x 2 ，； c 。列中填入基变量的价值系数，这里是c 。，c ：，c 。；它们是与基变量相对应的a b 列中填入约束方程组右端的常数； c ，行中填入基变量的价值系数q ，c 2 ，厶： 基变量下面列是单位矩阵，非基变量x ，下面数字是该变量系数向量只表示为基向 量的线性组合时的系数即= q ，丑+ 口2 ，昱+ + 己。 最后一行称为检验数行，检验数巳= 勺一b a l ，+ c 2 a 2 j + + 口叫) = o 一c ，气或 i - i 记为q 一乃记入表的最后一行 第二步，检验各非基变量_ 的检验数町= 乃一q 嘞，若q o ，- ，= 朋+ l ，摊， 1 = 1 则已得到最优解，可停止计算。在盯， 0 ，_ ，= 肌+ l ，撑中，若有某个吼对应黾的系数 列向量最s 0 ，则此问题无界，停止计算。否则转入下一步，根据m a 】( b ， o j = o - k ，确 定黾为换入变量，按口规则计算 口：r a i n 旦k o - 生 ( 2 1 7 ) l 衅j “雎 可确定量为换出变量。 沈阳工业大学硕士学位论文 第三步，基变换。以口雎为主元素进行迭代( 称为旋转运算) ，将j 0 列中的而换为 ，得到新的单纯形表。 第四步，重复第二，三步，一直到计算结束。 图2 1 为单纯形法计算步骤框图。 图2 ，1 单纯形法计算步骤框图 f i g 2 1b l o c kd i a g r a mo f c o m p u t a t i o nf o rs i m p l e xm e t h o d 一种特殊永磁型磁体的匀场技术研究 2 2 整数规划 2 2 1 整数规划的数学模型及其特点 前面讨论的线性规划问题的最优解，不一定就是整数，但是对于某些具体问题，常 有要求最优解必须是整数的需要，例如机器的台数，完成工作的人数，以及本文匀场过 程中所用小磁片的数目。初看起来，似乎只要将线性规划的最优解“四舍五入”取整就 可以了，但这常常是不可行的，因为化整后的解不一定是可行解，或虽然是可行解，但 不是最优解。因此有必要对最优整数解问题进行研究。要求一部分或全部决策变量必须 取整数值的规划问题称为整数规划( i n t e g e rp r o g r a m m i n g ，简记为i p ) 。若不考虑整数 条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划闯题的松弛问题 ( s l a c k p r o b l e m ) 。若松弛问题是一个线性规划，则称该整数规划为整数线性规划( i n t e g e r l i n e a rp r o g r a m m i n g ) 。整数线性规划数学模型的一般形式如下： m a x ( 或m i n ) z = 勺_ ，t i rh i 善a o x ，, 盼，溉f = 1 ，2 ，m ( 2 1 8 ) s t 户 i x ，0 _ ，= 1 , 2 ，阼 h ，x 2 ， - s 靠中部分或全部取整数 整数规划问题可以分为如下几种类型：整数规划中如果所有的变量都限制为整数， 就称为纯整数规划；如果仅有部分变量限制为整数，成为混合整数规划；如果决策变量 只能取值为0 和1 ，则称之为0 一l 整数规划。 整数规划及其松弛问题，从解的特点上来说，二者之间有着密切的联系，又有本质 上的区别。松弛问题作为一个线性规划问题，其可行解得集合是一个凸集，任何两个可 行解的凸组合仍为可行解，整数规划问题的可行解的集合是其松弛问题可行解集合的一 个子集，任何两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。 因为整数规划问题的可行解一定是其松弛问题的可行解( 反之不一定) ，所以整数规划 问题的最优解不会优于其松弛问题的最优解。 沈阳工业大学硕士学位论文 在一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整 数规划的可行解。此时若将松弛问题的最优解简单的取整，所得到的解不一定是整数规 划问题的最优解，甚至不是整数规划问题的可行解嗍。 2 2 2 分支定界解法 在求解整数规划时，如果可行域是有界的，首先容易想到的方法就是穷举变量的所 有可行的整数组合，然后比较目标函数的值得出最优解。对于小型的闯题，这个方法是 可行的。但是随着问题规模的扩大，其可行解的数目急剧增加，那么通过枚举全部可行 解的方法，没有实际的应用价值。 分支定界