（航空宇航推进理论与工程专业论文）飞机排班的算法模型及软件实现.pdf

一一 生里垦旦鲢窆里堕型! ：堂丝迨塞 ： 摘要 对于一个航空公司来说有四大资源，它们是航班资源、机队资源、枫组资源、维修 资源。飞机排班是在航班资源和维修资源配霞给定的情况下，优化实际机队资源的利用。 因此飞机排班优化必然带来机组费用和维修费用的节省，从而提高效益、减少运营成本， 缓解运力紧张、供不应求的局面。 根据当前国内航空公司的运营组织模式特点，以及飞机排班工作的实际需求，本文 提出了描述飞机排班问题的数学模型，构造出相应的满足工程需要的单纯形算法，单纯 形法的最大特点是计算简便、运算速度快、易于推广，因为这个方法一般只要用到加、 减、乘、除运算。从而满足了航空公司的时效性要求，在很大程度上提高了航空公司的 效益。 本文主要由航班串生成器、航班串优化器、飞机排班生成器三部分组成。以一周之 内中国南航集团公司的航班时刻表为数据源：考虑飞机应该返回基地机场、飞机每天的 飞行时间限制、过站时闻等约束条件生成航班串；保证航班时刻表中的每一个航班必须 而且只能被一条航班串覆盖，作为航班串优化器的约束条件，目标函数是使需要的航班 串最少，即所用的飞机架次最少，运用单纯形法生成航班串优化器。一般针对某机型 天的航班串的运算过程不超过十分钟。 同时排班系统也可以广泛应用于其它相关行业。 关键词：飞机排班，航班串，单纯形法，约束条件，目标函数 a b s t r a c t t h e r ea r ef o u rk i n d so fr e s o u r c e si na na i r l i n ec o m p a n y ，t h e ya r es c h e d u l e df l i g h t r e s o u r c e ，f l e e tr e s o u t t , e ，a i r c m wr e s o u r c e ，m a i n t e n a n c er e s o u r c e u n d e rt h ec i r c u m s t a n c eo f g i v e ns c h e d u l e df l i g h tr e s o u r c ea n dm a i n t e n a n c er e s o u r c e ，a i r p l a n es c h e d u l i n gi st oo p t i m i z e t h eu t i l i t yo fa c t u a lf l e e tr e s o u r c e s oi ti ss u r et h a tt h ea i r p l a n es c h e d u l i n go p t i m i z a t i o nw i l l c a u s et h es a v i n go fa i r e r e we x p e n s ea n dm a i n t e n a n c ee x p e n s e ，a n di n c r e a s i n gt h eb e n e f i t ， r e d u c i n gt h ew o r k i n gc o s t ，r e l e a s i n gt h ep h a s et h a tt r a n s p o r t a t i o nr e s o u r c ei ss c a r c ea n dt h e s u p p l yf a l l ss h o r to f d e m a n d b yt h em a n a g i n gm o d ec h a r a c t e r i s t i c so f c u r r e n td o m e s t i ca n dt h ea c t u a ln e e do f a i r p l a n e s c h e d u l i n gw o r k ，i tp u tf o r w a r dt ot h em a t h e m a t i c a lm o d e lo fd e s c r i b i n ga i r p l a n es c h e d u l i n g p r o b l e m ，c o n s t r u c t e dt h ec o r r e s p o n d i n gs i m p l e xm e t h o dt os a t i s f yp r o j e c tr e q u i r e m e n t ，t h e m o s tc h a r a c t e r i s t i c so fs i m p l e xm e t h o di st h a ti t sc o m p u t i n gi sc o n v e n i e n t ，t h eo p e r a t i n g s p e e di sq u i c ka n di t i se a s yt os p r e a d ，b e c a u s et h i sk i n do fm e t h o dg e n e r a l l ym a k e su s eo f a d d i t i o n ，s u b t r a c t i o n ，m u l t i p l i c a t i o n ，d i v i s i o n i ts a t i s f i e sa g i n gr e q u i r e m e n t ，e n h a n c e st h e b e n e f i to fa i r l i n ec o m p a n yt ot h ec e r t a i ne x t e n t i ti sm a i n l ym a d eu po ft h r e ep a r t s ：t h ea i r l i n e rs t r i n gp r o d u c i n gd e v i c e ，t h ea i r l i n e rs t r i n g o p t i m i z i n gd e v i c ea n d t h ea i r p l a n es c h e d u l i n gp r o d u c i n gd e v i c e t h ed a t as o u r c ei ss c h e d u l e d f l i g h tt i m e t a b l eo fc h i n as o u t h e r na i rh o l d i n gc o m p a n yi naw e e k t u r ni n t ot h ea i r l i n e r s t r i n g sc o n s i d e r i n gp l a n es h o u l dr e t u r nt ob a s ea i r p o r t ，t h el i m i to ff l i g h tt i m e ，t h el i m i tt i m e o fp a s s i n gs t a t i o n ，e t c ；i ti st h el i m i t i n gc o n d i t i o no fa i r l i n e rs t r i n go p t i m i z i n gd e v i c e g u a r a n t e e i n ge v e r yf l i g h ti nf l i g h to ft i m e t a b l ec a no n l yb ec o v e r e dw i t ho n l yo n ea i r l i n e r s t r i n g ，t h eo b j e c t i v ef u n c t i o ni st h a t a i r l i n e rs t r i n gn e e d e di sf e w e s t ；u t i l i z et h es i m p l e x m e t h o di no p e r a t i o n a lr e s e a r c ht op r o d u c et h ea i r l i n e rs t r i n go p t i m i z i n gd e v i c e ，v i z ，t h et o t a l n u m b e ro fa i r p l a n e si st h el e a s t i t so p e r a t i o np r o c e s sd o e sn o tg e n e r a l l ye x c e e dt ot e nm i n u t e s t oo n ec e r t a i nk i n do f m o d e lo f a i r l i n ei nad a y i tc a na l s ob ee x t e n s i v e l ya p p l i e dt oo t h e rr e l e v a n tt r a d e s k e yw o r d s ：a i r p l a n es c h e d u l i n g ，a i r l i n e rs t r i n g ，s i m p l e xm e t h o d ，l i m i t i n gc o n d i t i o n o b j e c t i v ef u n c t i o n 中国民用航空学院学位论文独创性声明 本人声明所节交的学位论文是我个人在导师指导r 进行的研究1 作及取得的研究成果。尽我所 知，除了文中特别加以标注羽j 致谢的地方外，论文中不包含其他人已经发表歧撰弓过的研究成果， 也不包含为获得中国吣刚航空学院域其它教育机构的学位或 i i5 而使h j 过的材料。与我一同1 ：作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：二篮垄燧日删：螋生笠 中国民用航空学院学位论文使用授权声明 中国民j _ f j 航空学院、中国科学技术信息研究所、国家豳馆铂权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文 的内容相一致。除在保密期内的保密论文外，允许论文被商阅和借阅，可以公布( 包括刊登) 论文 的全部或部分内容。论文的公布( 包括刊登) 授权中国【t 用航空学院研究生部办理。 研究生签名：盔筮堡奎导师签名： 渤日期：一量咝兰一研究生签名：盈筮婪叁导师签名：坳翌班日期：一塑茎兰：兰一 主垦基旦照窑鲎堕堕! ：竺堡地塞： 一、民航业现状及未来发展 绪论 我国民航事业的发展有目共睹：中国的民航事业创建于1 9 4 9 年1 1 月2 日，初期的 中国民航规模很小，基础十分薄弱，仅有1 2 架小型飞机、1 2 条短程航线和4 0 多个小型 机场，1 9 5 0 年航空运输总周转量15 7 万吨公里，旅客运输量l 万人。经过5 5 年的不懈 努力，中国民航业快速发展，取得了举世瞩目的成就：中国航空运输总周转量在国际民 航组织缔约国中的排位，由1 9 7 8 年的第三十七位上升至2 0 0 3 年的第五位。截至2 0 0 4 年1 0 月底，国内民航旅客运输量超过了1 亿人次，货运量合计2 2 52 7 力1 吨，国内各航 空公司共完成运输总周转量1 9 2 5 亿吨公里。 中国民航业发展非常迅速。其主要特点是： a 运输网络不断扩大。截至2 0 0 3 年底，定期航班航线达到1 1 5 条，通航里程2 3 7 2 5 万公里。国际航线1 9 4 条，通航3 2 个国家的7 2 个城市。 b 机场建设成就显著。到2 0 0 3 年末，全国民航定期航班通航机场1 2 6 个，其中能起降 波音7 4 7 机型的机场2 5 个。 c 配套基础设施持续完善。加速了航管、通信、导航和气象保障系统的技术改造。加 快了三大区域管制中心、航路二期工程等空管设施的建设。 d 运输能力显著增强。目前中国民航主力机队均为世界上最先进的机型，技术新、机 龄短、性能好。部分飞机利用率已达到或接近国际先进水平。 截止到2 0 0 2 年1 2 月3 l 曰，中国四大航空集团的实力如下： 表1 一l 中国四太航空集团实力“ 公司名称客机数量( 架)航线( 条)定期航班( 次每周) 国内国际 中国国际航空集团1 1 82 6 65 62 4 7 2 中国南方航空集团 1 2 22 8 66 34 2 8 2 中国东方航空集团 7 01 4 96 02 9 0 0 中国新华航空集团 9 24 8 0 待定 飞机这个效益的承载者，它单位数量少，单位成本高，对它的航线进行优化，充分 利用它的飞行时间，可以提高经济效益、减少运营成本，缓解运力紧张、供不应求的局 面。 ! 旦匿亟堕至兰堕堡f ：堂垡迨塞 二、飞机排班的研究现状 如何对航线进行效益最大化、成本最小化的安排，是航空运行和维修生产管理最重 要的内容，也是所有的大大小小航空集团考虑的问题，而国内外的许多研究人员也在努 力开发出实用、高效的飞机排班系统。 a 国外研究现状 经过一系列大型的兼菇之后，欧美国家的航空公司规模越来越巨大，美国美利颦航 空公司、美国西北航空公司、德国汉莎航空公司等大型航空公司分别拥有数酉架飞机 他们纷纷建立了自己的运作控制中心即s o c ( s y s te mo p e r a t i o nc o n t r 0 1 ) 系统，集中管 理和统一控制航班、飞机、枧组、维修四大资源。美国美利坚航空公司早在上世纪八十 年代，就开始探索集中签派、济调运作，在1 9 9 3 年建立了世界规模最大的s o c 中心， 每年节约飞行成本达到二千多万美元。相关的研究工作包括下面两个方面： 带有航班时间窗的飞机排班问题 在编制航班计划时，经常需要根掘运力安排的需要对航班时刻进行调整通过引入 航班时间窗可以定量评估航班时刻对公司运力安排的影响，从而更好地优化航班时刻， 因此，该项研究在生产实际中有较大的应用价值。这方面的6 开究工作主要有：b r i a n r e x i n g 在美国联合航空公司的协助下研究带有航班时间窗的航班机型分配问题。1 。在一 般的飞机排班问题的研究中，般均假定每个航班的出发和到达时刻是固定不可改变 的，而在编制实际生产计划时，允许对航班计划的出发和到达时刻做定程度的调整以 便于获得更灵活、成本更低的飞机排班方案，并且这种航班时刻的调整事实上对运输生 产不会构成重大影响。在此之i i ，l e v i n 等人在研究单机型的航班时刻优化及飞机路径 安排问题时首先引入了航班时刻窗的概念”。之后b a n d e r 与d e s a u l n i e r s 等人进一步研究 了多机队的航空公司的机型分配和飞机维护路径安排问题，通过目标分解，生成最优航 班路径的方法寻找最优的机队调度方案，解决了日航班量在4 0 0 个以下的航空公司飞机 排班问题”。b r i a nr e x i n g 在这些研究的基础上，通过对时刻窗鲍离散化处理，提出了 两种适用于解决大规模机型分配问题的算法：一种是基于提高处理速度的直接算法 ( d s t ) ，一种是基于减小内存占用的迭代算法( i s t ) i “。”1 飞机交换问题 在生产调度工作中，经常需要对某些航班的机型及其执行的飞机进行调整，称为飞 机交换问题。c l a r k e 和t a l l u r i 等人分别利用图论对此问题进行了研究”“”。 b 国内研究现状 国内各大航空公司：中国南方航空集团公司( 以下简称“南航”) 耗资亿三予多 月元人民币引进了的s o c 系统：中国国际航空集团公司( 以下简称“国航”) 的运行管 理系统是由国航与北京东方新宏信息公司合作丌发的其有自主知识产权的生产管理系 统：中国东方航空股份有限公司( 以下简称“东航”) 的运行控制中心( a i r p i a n e o p e r a t i n gc o n t r o l ，a o c ) 也已经正式启动运行：上海航空公司已经实施了f o c 、营销 ! 垦垦旦堕窒竺蟹曼主竺堡重塞 管理、财务结算、电子商务、航材管理等信息系统；成都同飞科技有限责任公司与中国 民航飞行学院合作，模仿排班专家的思维，建立飞机排班问题的数学模型和优化算法， 每架飞机的当前状态以g a n t t 图显示，侧重于对优化完成的飞机航线，根据维修、适航 限制、调度通告等安排合适的飞机。西南交通大学的杜文、孙宏的思想是：首先建立一 个描述航班节衔接关系的二部图，根据“先对航班节编组，再对航班节组指派飞机”的 原则，将原问题转化为两个二部图的最小权虽大匹配问题m ，。 对于排班的研究采用的其它算法是：单纯形法、遗传算法、人工神经网络、基于模 拟退火算法的启发式算法、分阶段指派算法m ，。 三、本文的研究课题 a 课题来源 本课题来源于民航总局的飞机正常与非正常排班算法研究，基本数据采自南航一- 周 的旅客运营表。 b 研究内容 本文采用传统的运筹学中的单纯形法。首先把飞机排班问题抽象出数学模型，根据 约束条件：飞机的过站时间、飞机一天的飞行时间限制、飞机最后到站的飞彳j = 时间限制， 采用优化组合方法生成航班串；然后采用单纯形法进行优化，尽量使用最少的航班串覆 盖每一个航班。飞机排班软件采用s q ls e r v e r 为后台支持数据库，m i c r o s o rc + + n e t 为前台开发工具，有很好的人机交互界面。 四、论文内容安排 绪论就课题的背景进行了阐述，分析了飞机排班问题的国内外研究现状，对论文做 了简单的介绍。 第一章介绍了飞机排班数学模型的创建。 第二章介绍了飞机排班数学模型的解法单纯形法。 第三章对数据源、模块的实现进行了介绍。对象是周之内南航所有的航班。 第四章对软件的实现及框架进行了详细的介绍，以周的7 5 7 机型为例进行了运算。 结束语对课题的工作内容作了简短的总结，对航班串优化器的模型作了拓展。 l 1 基本术语 第一章飞机排班问题数学模型的建立 航班计划是航空公司一切生产活动的基础和核心，其它任何生产计划都是围绕并建 立在航班计划的基础上并为航班计划的顺利实施提供保障的，完整的航班计划包括以下 基本要素：” 航线：即航空公司开展运营的路线，包括起点、终点、经停等要素，航线资源 是航空公司的宝贵财富，航空公司要想在某条航线上丌展运营，必须首先取得航线的运 营权，1 9 8 3 年美国泛美航空公司破产后，其太平洋航线经营权的拍卖价达到1 8 7 亿美 元：“。 航班：航班包括航线、航班号、航班的出发时刻和到达时刻等要素，同航线一 样，航班资源也是航空公司的宝贵资源。 基地：飞机执管维修单位的所在机场。 航班串( 飞行回路) ：出依次连接的航班构成，每个机队从各自基地出发，到各 自基地结束的闭合航线图，如图l l 。 图1 1 航妍串示意图 主堕墨旦丛全里壁鲤：鲎丝丝塞 班期：指某一航班在一周中的哪几天执行。 机型：指执行该航班所使用的飞机型号，不同机型有不同的飞行性能( 如航程、 升限、最大起飞全重、爬升能力等) ，因此不是所有的机型都能用来飞同一航线，此外， 不同机型对应不同的座位布局：如b 7 e 7 3 0 0 型飞机的座位数2 5 0 3 0 0 座，而a 3 8 0 型 飞机的座位数达到5 5 5 人。 飞机排班计划优化问题可分为三大部分( 用三个方面建立模型) ： a 产生可能的航班串。 b 生成一个最优化的航班串集合。 c 将各飞机的机尾号指派给优化完的航班串集合中的任一条航班串。 飞机排班计划按各机型的机队各自排班。最优化的飞机排班模型同时还能给出满足 公司排班计划的各基地配置飞机的最佳数量。 1 2 航班串生成器模型 航班串是由若干首尾依次相继的航班组成，通常是从机队基地所在的机场出发，最 后回到基地机场，一般由一架飞机完成一个航班串的飞行任务。在特殊情况下，个航 班串的最终到达的目的地可以不是其最初出发的基地机场，而是其它目的地，例如：蘖 架飞机要到某地做飞机定检，应尽可能在完成航班任务的同时，飞到浚目的地作检修： 有特殊包机任务也属这种情况。而在下面的算法模型中暂不包括这些特殊情况，规定 个航班串最终目的地是丌始出发的基地机场。 航班串生成器是根据公司的航班计划时刻表，自动生成所有可行的航班串。一条可 行的航班串要满足种种限制条件。主要的限制条件有： 飞机应该返回基地机场( 远程国际航线不包括在内) 。 飞机每天的总飞行时间限制。 飞机每天的任务时间( 包括航班飞行结束时间要求，即机场宵禁时间控制：飞 机过站时间要求，即二次航班之问的停留时间规定，一般为3 0 分钟或4 0 分钟) 。 同一个航班串中包含的各航班的时刻不准相互冲突。 由航班时刻表生成的航班串要远远多于实际使用的航班串。航班串生成器的任务是 自动生成所有航班串的编码及楣关数据供航班串优化嚣使用。 首先，由航班时刻表( 表l 一1 ) 生成按时间先后顺序排列的航班网络图，如表1 2 所示。 表卜1 航妍时刻表 城市时刻 序号航班号 山发刨达山发到达 l2 2 lo r dd e n0 8 0 00 9 3 4 22 2 3o r do e n0 9 0 01 0 3 9 38测0 ；04 4 2 3 0 d e n o r d 1 2 0 01 5 2 1 52 3 8o e no r d1 8 0 02 1 2 1 67 6 6l a xd e n1 6 0 01 9 1 2 ；50 船0 喀士朝4 82 5 9o r dl a x1 4 0 01 6 0 9 92 7 4l a x d e n 0 8 ( 0 1 1 1 6 1 02 9 3d e nl a x1 4 0 01 , 5 1 0 l l4 1 2l a xo r d1 4 0 01 9 5 9 ；一表示种子航班 弘表示不可行航班 2 3 0 一表示可行航班 表卜2 航班网络幽( 表中a 表示刮达航班，d 表示出发航班) 城市时间第一天 第一大 第三天 0 8 0 0dod 0 9 0 0dud o r d 1 3 1 4 dd d 1 4 2 3aaa 0 9 3 4aaa 1 0 3 9 aa a 1 1 0 0ddd 1 1 1 6aaa d e n 1 2 0 0ddd 1 4 0 0ddd 1 8 0 0ddd 1 9 1 2aaa 1 5 1 0aaa l a x 1 6 0 0 dd d 接着，航班串生成器找出从基地城市出发的航班称为种子航班。航班串生成器的援 索是从各种子航班出发，找到该航班的目的地城市( 记录到达时间) ，再搜索从该域市 出发的各航班。判断连接时问是否大于规定的最小过站停留时间，蓿满足，则将该航班 加入该条航班串，在表卜1 中从种子航班( o r d 0 9 ：0 0 航班，航班号2 2 3 ) 到达d e e 后 有三个可行的航班( 分别在1 2 ：0 0 、1 4 ：0 0 、1 8 ：0 0 出发，11 ：0 0 出发的航班不可行匿 为它不满足过站停留时间) 。这样，开始形成三条不同的航班串，分别继续搜索下去。 每搜索到一点( 城市) ，在航班串上加入可行航班以后计算累加的飞行小时和过站时 间是否小于规定值，若小于规定值且最后一个航班的目的地是第一个航班的出发地便 是找到了一个可行的航班串，记下该航班串中前后相继的各个航班。若这个可行的航班 串的累加飞行时间和累加任务时间小于规定值，或者展后个航班的目的地不是第一个 航班的出发地，则将前段航班加上后继可行航班作为一条新发现的可行航班串继续搜索 下去。正在搜索的航班串，一旦触犯约束条件，则该条航班串是不可行的，停止搜索， 退回去寻找新的航班串。航班串生成器搜索工作完成的重要判据之，是飞机航班时 刻表中的每一个航班至少被一条可行航班串覆盖。另一个判据是搜索机时的限制。近矗 估计。如果航班数超过1 0 0 0 ，可行航班串数估计会超过1 0 万。因此，实际不可能真l j 二 地将全部可行航班串搜索出来。 1 3 航班串优化器模型 航班串优化器的实现运用的是组合优化算法。它将来自航班串生成器的一组完全e j 航班串集合划分出一组最优的航班串子集。组成航班串子集，必须满足两类约束条件： 第一类约束条件是必须保证航班时刻表中的每一个航班必须而且只能被一条航班串覆 盖，或者说二条航班串不能相交不能有共同的航班；第二类约束条件是从一一个基地首 发的航班串数必须小于或等于在该基地的可用飞机架数。在上述两类约束条件满足的情 况下，优化器的优化目标是：使实际执行的航班串总数最少。通常一条航班串由一架飞 机执行任务，因此该目标函数也取为要求实际利用的飞机数最少，其数学模型构造如下： 设集合m = 1 ，2 ，。m 表示航班集合，集合n ： 1 ，2 ，n 表示的航班串集合 由航班串生成器生成，k = 1 ，2 ，k 表示基地集合。 定义。一l 变量x ，j n 。 。一j l ，表示匆条航班串选上 。 i o ，表示第，条航班串未选上 目标函数：m i nz = xi i - 1 约束条件：a x = e“， d x s “2 ， 其中，矩阵a 称为航班约束矩阵，是m r l 阶矩阵。 a = q 1 ，q 2 q 。 口2 l 】a 2 2口2 h 口m l ，a _ 2 口m 月 元素a 。的下标：i 代表航班，j 代表航班串 l ，表示第f 航班被第，条航班串覆盖 ”1 0 ，表示第f 航班来被嚣，条航班串覆盖 矩阵a 2 口。 的取值由航班串生成嚣生成。 e = 1 ，1 ，1 ，共m 个元素为1 的向量。 矩阵d 称为基地约束矩阵，是k x r l 阶矩阵。 磷。，4 ：嗣 吐。，吐。4 j d k ，d dk 。 d 2 d 。 。中元素d 月的下标p 代表基地。j 代表航班串。 ，l ，表示第，条航班串是从第p 基地首发 ” 10 ，表示第，条航班串不是从第p 基地首发 这里，k 为基地的总数。矩阵d = d 。 h 中元素的取值由航班串生成器生成，向量 s 是k 维向量。 s 2 s ，s ：，s - 。s ，代表第p 基地可用飞机架数。 航班串优化器模型中：两组约束条件的物理意义为： 公式1 1a x ；e 衷示飞机航班时刻表中每一个航班必须并且只能被一条航班串覆 盖。 公式1 2d x o l = a l 口*j ( 2 1 【) 设b , a 。为最小值，则x 。为出基变量，并称a “为中心元素。 d 迭代求新基本可彳亍解及其检验数 迭代求新解的方法 实际中用到的方法就是对矩阵作初等行变换。例如，没约束条件的增广矩阵具 有如下形式： x lx 2 x 3x 4x 5x 6 r 1 0 0 a ha 1 5a 1 6 ： b 、| f 。 -0 赴 ；b ：l l 0 0l a ，a 3 5a 3 6 ：b 3j 由此形式可知，当前解的基变量为：x 。、x 。、，非基变量为 定x 。为进基变量，x 。为出基变量，为中心元素。为求新解 行变换，使x 。的列系数向量变为单位向量： 刚弱 l2 1 2 、 x 4 、x ，、x 。现在已确 对此增广矩降做初等 ( 2 13 ) 即第二行元素均除以中心元素a 2 。，使a 。变为l ，然后再用初等行变换将a ，。及a 。，变 为零。注意，右端列一起参加变换。设变化后矩阵成为： x x 3墨x 。 k x 6 广i互：0 戈。0 瓦。i 丘、1 l o瓦：0 。 l 瓦! 瓦l 2 1 4 l 0 瓦 l瓦；0氟：瓦j 由此矩阵可以得出新解为( 五，0 ，嚣，0 ，瓦，o ) 7 。 求对应的检验数的方法 在上面求新解时，如果把当前基本可行解的梭验数作为增广矩阵2 1 2 的最后一 行元素，一起参加初等变换，就可以得到新解对应的检验数。具体做法如下： 设当前的解的检验数为 ，( j = l ，2 ，3 ，4 ，5 ，6 ) ，其中 。= 九：= 。- - 0 ( 基变量对应的 检验数为零) ，把它们放在矩阵2 1 2 的最后一行，得到： 1 6 一生璺垦旦丛! 堂堡鲤! ：堂丝堡塞 进行初等行变换，使向量变为单位向量 ( 2 】5 ) 即使进基变量x ；的检验数xj 变 为零。设经过变化后得到： x 。x 。x ；x x jx 。 r i 虿z d互；0 互e ；6 ，、 i o 瓦： o 瓦 l 瓦e i 瓦 l ( 2 1 6 ) l 0 瓦。 l瓦。0 瓦。：瓦l l 0瓦0 f 0 云： 其中五、五、五即为新解的非基变量的x ：、x 、x 。的检验数。 目标函数值的确定方法 在矩阵2 i 6 中，发现其右下角空着个位置没有元素，其实可以利用这个位置 确定基本可行解对应的目标函数值。其方法如下： 设初始解对应的目标函数值为z 。= o ，那么在开始时将零填在右下角的位置，以 后在每次傲初等变换的迭代中，这个右下角都一起参加变换，变换后得到的元素的 负值，就是新基本可行解对应的目标函数值。 单纯形法的主要步骤可以整理成一个框图，如图2 - 2 所示。此框图适用于约柬 条件不等式为“”、目标函数求极小值的情形。 、，、 h b b n m j n h x a a a 一凡 k 酝 c ；芋；| k 扎 帅一 x o 0 ，一0 k 0 0 0 k ， o o o ，l 中田民用航空学院碗士学位论文 图2 - 2 单纯形法求解流程图 2 3 线性规划问题的解法之二人工变量法 231 人工变量法之一大m 法 在一个线性规划问题的约束条件中加入人工变量后，要求目标函数的取值不受人工 变量影响，为此假定人工变量在目标函数中的系数为m ( m 为任意大的正数) ，这样目标 函数要实现最小化时，必须把人工变量从基变量换出，否则目标函数不能实现最小化。 j 见，大m 对人工变量具有惩罚作用只有人工变量取零值，这种惩罚作用才能消失。 使用大m 法时遇到的几种隋况： 新规划有最优解，并且在最优解中人工变量皆取零值。这种情况下，在这个最 优解中去掉人工变量的部分之后，就是原规划的最优解。 新规划有最优解，但在最优解中人工变量不全为零。这种情况下，原规划没有 可行解。 新规划没有最优解。这种睛况下，原规划没有最优解。 232 人工变量法之二两阶段法 用计算机求解含人工变量的线性规划问题时，存在大m 的确定问题。故介绍两阶段 法求线性规划问题。“4 1 第一阶段：不考虑原问题是否存在基可行解：给原线性规划问题加入人工变最，并 构造仅含人工变量的目标函数和要求实现最小化。如：