（运筹学与控制论专业论文）环境因素下城市交通若干问题的模型及算法研究.pdf

北方交通大学硕十论文摘要 环境因素下城市交通若干问题的模型 及算法研究 y 5 8 6 1 3 9 杨文国 北方交通人学理学院，北京 1 0 0 0 4 4 摘要 近三十年来，由于交通所带来的污染日益恶化和加重，如何 协调交通发展和环境保护二者之间的关系，业已引起了国内外人 十尤其是交通专家学者的普遍关注。本文主要以优化理论和双层 规划模型为基础，对考虑环境因素下的城市交通若干问题的模型 及算法进行了研究。具体工作有: 本文在第一章提出了本论文所研究的城市交通坏境问题及解 决策略， 并简单介绍了双层规划模型和非线性规划的灵敏度分析， 它们为其它章节提供了理论依据。在第二章主要研究了考虑环境 因素的广义用户平衡和广义系统最优配流模型。本章首先介绍了 城市交通分析中公平目标和广义费用函数的概念，建立了考虑环 境因素的广义用户平衡和广义系统最优配流模型，并用著名的 f r a n k - w o l f e 算法对所给模型进行了 求解。 最后给出了一个简单的 数值算例，对所给模型及算法进行了验证并得出了相应结论。 本文分别在第三章和第四章研究了城市交通分析中固定需求 和弹性需求条件下考虑部分路段上一氧化碳 ( c o)排放量限制的 用户平衡配流模型及算法。第三章考虑的是固定需求的情形，首 先建立了城市交通分析中考虑部分路段上一氧化碳 ( c o) 排放量 限制的用户平衡配流模型，并给出了基于惩罚函数的求解算法。 最后用一个简单的算例说明了该模型及算法的应用。 在此基础上， 第四章则建立了弹性需求条件下考虑部分路段上一氧化碳 ( c o) 排放量限制的用户平衡配流模型，给出了等价性证明。根据弹性 需求配流模型解的特性进而给出了双层规划模型，该模型上层要 求网络容纳尽量多的 o - d需求量，同时要求排放到网络中的 c o 总量最少;而下层是一个标准的弹性用户平衡配流问题。最后简 单的介绍了基于灵敏度分析的双层规划模型的求解算法。 在第五章中，建立了环境污染下确定车辆最优行使速度的双 宋经作者、 导师同慧 勿全文公布 北方交通大学硕 卜 论文 摘要 层规划城市交通配流模型，上层要求系统总的出行时间和 c o排 放总量最小，下层是一个弹性需求的 u e问题。并分析了城市交 通网络中流量与速度之间的关系，在此基础上，设计了一个平衡 迭代算法对所给模型进行了求解，从而能得到车辆在各路段上的 最优行驶速度。最后用一个简单的算例说明了该模型及算法的应 用。 第六章主要研究了坏境因素下城市交通的诡异现象。本章在 引入广义网络备用能力概念基础之上，给出了两个考虑环境污染 因素的双层规划交通配流模型，上层分别要求系统总的出行时间 和车辆排放尾气总量最小，或者在满足一定的尾气排放总量限制 条件下，系统所容纳的o - d需求量最大;下层要求网络用户的出 行行为符合 w a r d r o p 平衡原则。 这些模型不但能解释环境因素下 由于o - d需求量的变化所产生的一类诡异现象，而且能给出环境 因素下确定最佳o - d需求量的方法。本章在简要介绍了基于灵敏 度分析的求解算法之后， 用两个简单的算例说明了该模型的应用。 关键词:广义费用函数， 用户平衡配流模型，弹性需求， 双层 规划，内惩罚函数，求解算法，备用能力 r e s e a r c h o n t h e m o d e l s a n d s o l u t i o n a l g o r i t h m s o f u r b a n t r a f f i c a s s i g n me n t p r o b l e m u n d e r e n v i r o n me n t a l o b j e c t i v e y a n g w e n g u o c o l l e g e o f s c i e n c e , n o rt h e r n j i a o t o n g u n i v e r s i t y , b e ij i n g 1 0 0 0 4 4 ab s t r a c t o v e r t h e r e c e n t 3 0 y e a r s , t h e r e l a t i o n s h i p b e t w e e n t h e m o d e r n t r a f f i c d e v e l o p m e n t a n d t h e e n v i r o n m e n t a l p o l l u t i o n h a s a r o u s e d t h e 北方交通大学硕 卜 论文 摘要 w o r l d w i d e a w a r e n e s s o f t h e r e l a t e d s c h o l a r s , e s p e c i a l l y t h a t o f t h e t r a f f i c e n g i n e e r s , b e c a u s e o f t h e d e t e r i o r a t i n g u r b a n p o l l u t i o n . t h i s p a p e r i s f o c u s e d m a i n l y o n t h e s t u d y o n t h e m o d e l s a n d s o l u t i o n a l g o r i t h m s o f u r b a n t r a f f i c a s s i g n m e n t p r o b l e m s u n d e r e n v i r o n me n t a l o b j e c t i v e b a s e d o n o p t i m a l t h e o r y a n d b i - l e v e l p r o g r a m m i n g m e t h o d s . t h e m a i n c o n t e n t s o f t h i s p a p e r a r e i n t r o d u c e d a s f o l l o w i n g : i n c h a p t e r 1 t r a f f i c a s s i g n m e n t p r o b l e m s a n d s o l u t i o n s t r a t e g i e s u n d e r e n v i r o n m e n t a l o b j e c t i v e a r e d e s c r i b e d a s t h e f o c u s e d i s s u e s o f t h i s p a p e r . t h e n t h e r e s u l t s o f b i - l e v e l p r o g r a m m i n g m o d e l a n d s e n s i t i v i t y a n a l y s i s f o r n o n l i n e a r p r o g r a m m i n g a r e b r i e fl y i n t r o d u c e d w h i c h p r o v i d e t h e t h e o r e t i c a l b a s i s o f t h e s u b s e q u e n t c h a p t e r s . i n c h a p t e r 2 a g e n e r a l i z e d u s e r e q u i l i b r i u m ( g u e ) a s s i g n m e n t m o d e l a n d a g e n e r a l i z e d s y s t e m o p t i m i z a t i o n ( g s o ) a s s i g n m e n t m o d e l u n d e r e n v i r o n m e n t a l a n d e q u i t y o b j e c t i v e s a r e e s t a b l i s h e d . t h e h i s t o r i c s o l u t i o n a l g o r i t h m , s u c h a s f r a n k - wo l f e a l g o r i t h m, l e n d s i t s e l f w e l l t o t h e g u e m o d e l a n d g s o m o d e l . a n u me r i c a l e x a m p l e i s u s e d t o i l l u s t r a t e t h e a p p l i c a t i o n s o f t h e g u e m o d e l a n d t h e g s o mo d e l , a n d a t l a s t s o m e c o n c l u s i o n s a r e d r a w n . u s e r e q u i l i b r i u m m o d e l s a n d s o l u t i o n a l g o r i t h m s w i t h fi x e d d e m a n d a n d e l a s t i c d e m a n d a r e p r o p o s e d t o d e s c r i b e t h e t r a f f i c a s s i g n m e n t p r o b l e m u n d e r t h e c o n d i t i o n o f c o n s t r a i n o f c o a m o u n t o n s o m e l i n k s i n c h a p t e r 3 a n d c h a p t e r 4 r e s p e c t i v e l y . t h e f i x e d d e m a n d c a s e i s d i s c u s s e d i n c h a p t e r 3 , a u s e r e q u i l i b r i u m a s s i g n m e n t m o d e l i s p r e s e n t e d a n d t h e s o l u t i o n a l g o r i t h m b a s e d o n t h e i n n e r p e n a l t y f u n c t i o n l e n d s i t s e l f w e l l t o t h e m o d e l . a t l a s t a s i m p l e n u m e r i c a l r e s u l t i s g i v e n t o i l l u s t r a t e t h e a p p l i c a t i o n s o f t h e m o d e l a n d i t s s o l u t i o n a l g o r i t h m . i n w h a t f o l l o w s , a u s e r e q u i l i b r i u m m o d e l w i t h e l a s t i c d e m a n d i s p r o p o s e d t o d e s c r i b e t h e t r a f f i c a s s i g n m e n t p r o b l e m u n d e r t h e c o n d i t i o n o f c o n s t r a i n t o f c o a m o u n t o n s o m e。 l i n k s i n c h a p t e r 4 a n d t h e e q u i v a l e n c e i s g i v e n . a b i - l e v e l p r o g r a m m i n g m o d e l , w h i c h b a s e d o n t h e s o l u t i o n p r o p e r t y o f t h e u s e r e q u i l i b r i u m m o d e l w i t h e l a s t i c d e m a n d , i s p r o p o s e d . t h e u p p e r - l e v e l p r o g r a m m i n g p r o b l e m i s t o m a x i m i z e t h e s y s t e m o - d d e m a n d a n d mi n i mi z e t h e t o t a l a m o u n t o f c o e m i s s i o n s , w h i l e t h e l o w e r - l e v e l o n e e n a b l e t h e u s e r r o u t e c h o i c e b e h a v i o r t o s a t i s f y t h e u s e r e q u i l i b r i u m m o d e l w i t h e l a s t i c d e m a n d . a t l a s t t h e s e n s i t i v i t y 北方交通大学硕十论文摘 要 a n a l y s i s b a s e d s o l u t i o n a l g o r i t h m i s d e s c r i b e d t o s o l v e t h e b i - l e v e l mo d e l . a b i - l e v e l p r o g r a m m i n g m o d e l a n d i t s s o l u t i o n a l g o r i t h m a r e p r e s e n t e d t o d e s c r i b e t h e o p t i m a l v e l o c i t y p r o b l e m u n d e r e n v i r o n m e n t i n c h a p t e r 5 . t h e u p p e r - l e v e l p r o g r a mm i n g p r o b l e m mi n i m i z e s t h e s y s t e m t r a v e l c o s t a n d t h e t o t a l a m o u n t o f c o p r o d u c e d w h i l e t h e l o w e r - l e v e l o n e i s a u s e r e q u i l i b r i u m p r o b l e m u n d e r e l a s t i c d e m a n d . t h e e q u i l i b r i u m i t e r a t i v e s o l u t i o n a l g o r i t h m, w h i c h b a s e d o n t h e r e l a t i o n s h i p b e t w e e n fl o w a n d v e l o c i t y i n u r b a n t r a n s p o r t a t i o n n e t w o r k a n a l y s i s , i s r e p r e s e n t e d s o t h e o p t i m a l v e h i c l e s s p e e d i s o b t a i n e d o n e a c h l i n k . i n o r d e r t o i l l u s t r a t e t h e a p p l i c a t i o n s o f t h e m o d e l a n d i t s s o l u t i o n a l g o r i t h m , a s i m p l e n u m e r i c a l r e s u l t i s g i v e n a s t h e e n d i n g p a r t o f t h i s c h a p t e r . i n c h a p t e r 6 a b i - l e v e l p r o g r a m m i n g m o d e l , w h i c h b a s e d o n t h e c o n c e p t o f g e n e r a l i z e d r e s e r v e c a p a c i t y , i s p r o p o s e d t o d e s c r i b e t h e t r a f f i c a s s i g n m e n t p r o b l e m u n d e r e n v i r o n m e n t a l o b j e c t i v e . t h e u p p e r - l e v e l p r o g r a m m i n g p r o b l e m i s t o m i n i m i z e t h e s y s t e m t r a v e l c o s t a n d t h e t o t a l a mo u n t o f e mi s s i o n s , w h i l e t h e l o w e r - l e v e l o n e e n a b l e t h e u s e r r o u t e c h o i c e b e h a v i o r t o s a t i s f y t h e wa r d r o p s e q u i l i b r i u m p r i n c i p l e . t h e h e u r i s t i c s o l u t i o n a l g o r i t h m b a s e d o n s e n s i t i v i t y a n a l y s i s i s i n t r o d u c e d t o t h e m o d e l b r i e fl y . t h e b i - l e v e l p r o g r a m m i n g m o d e l f o r t h e o p t i m a l o - d t r a v e l d e m a n d n o t o n l y c a n e f f e c t i v e l y i n t e r p r e t t h e p a r a d o x e s p h e n o m e n a c a u s e d b y t h e c h a n g e s o f o - d t r a v e l d e m a n d b u t a l s o c a n d e t e r m i n e t h e o p t i m a l o - d t r a v e l d e m a n d u n d e r e n v i r o n m e n t a l o b j e c t i v e . a t l a s t s o m e s i m p l e n u m e r i c a l r e s u l t s a r e g i v e n t o i l l u s t r a t e t h e a p p l i c a t i o n o f t h e m o d e l k e y w o r d s : g e n e r a l i z e d c o s t f u n c t i o n ; u s e r e q u i l i b r i u m a s s i g n m e n t mo d e l ; e l a s t i c d e m a n d ; b i - l e v e l p r o g r a m m i n g ; i n n e r p e n a l t y f u n c t i o n ; s o l u t i o n a l g o r i t h m ; r e s e r v e c a p a c i t y - i v - 北方交通人学硕十论文 第一章 绪论 近 年 来 ，在 发 达 国家 ， 随着 智 能 交 通 道 路 系 统 ( i v h s -i n t e l l i g e n t v e h i c l e h i g h w a y s y s t e m ) 特别是城市交通中的 路径导驶系统 ( r g s -r o u t e g u i d e s y s t e m ) 在实际交通网络中的 应用，城市交通严重的拥挤状况得到了有效地缓解，相应的车辆 行驶的平均出行时间也得到了较大程度的降低。在我国，随着 2 0 世纪后2 0 年经济的快速运行， 城市道路交通基础设施和管理有了 很大的发展，政府各职能部门都投入了很大力量来解决交通的供 求矛盾。 特别是进入2 0 0 0 年以来， 全国所有城市都组织实施了城 市 “ 畅通工程” ， 这对改善城市交通面貌， 解决交通问题， 提高城 市的交通管理水平起到了较大的推动作用。然而，许多城市交通 问题仍然十分突出，城市交通拥挤和堵塞相当严重，交通事故频 繁发生，交通噪声和废气污染日趋严重，制约和阻碍着社会经济 的快速发展和人民生活质量的进一步提高。传统的城市交通配流 模型 一 般没有考虑如何减少车辆尾气的量和降低噪声水平等问 题。近二十年来，由于政府和公众都越来越意识到交通污染物的 严重危害，因此现代城市道路交通发展与环境保护之间的协调问 题，业已引起了国内外有关学者的广泛重视 ( 参见文献 1 3 , 2 3 , 2 8 - 3 0 , 5 0 - 5 3 1 ) 。 第一节城市道路交通环境问题研究及对策 一、城市道路交通所面临的环境问题 随着城市道路交通的飞速发展，交通与坏境之间的矛盾日益 突出，这主要表现在: 第一章绪论 . 空气污染 城市道路交通空气污染是由机动车辆排出的尾气引起的。车 辆尾气所含的主要污染物有:一氧化碳 ( c o) .碳氢化合物，氮 氧化物 ( n o x ) ，二氧化硫 ( s 0 2 )含铅化合物，碳烟等颗粒物及 恶臭物质等。它们大部分是有害有毒物质，有些还带有强烈刺激 性，甚至有致癌作用。 例如c o经呼吸道吸进肺部被血液吸收后， 能与血液中的血红蛋白结合合成 c o - c o h b( 血红蛋白) 。c o 与 c o h b的亲和力比氧大 2 5 0倍，很易导致人体内各组织缺氧，而 n o与c o h b 的结合力比氧高3 0 万倍， 极易造成体内缺氧，严重 是可引起意识丧失，甚至死亡。而有关调查表明:城市污染物中 约有9 0 %的c o和约有5 0 %的n o x 来源于城市道路交通中机动车 辆行驶所排放的尾气，城市道路交通己经成为构成城市环境污染 最主要的因素。 2车辆噪声 机动车辆在道路上行驶辐射的噪声，主要由动力噪声和轮胎 噪声两部分构成。车辆动力噪声主要指动力系统辐射的噪声，其 强度主要取决于发动机的转速，与车速有直接关系，一般随车速 的增大而增强。轮胎噪声是指轮胎与路面的接触噪声，由轮胎直 接辐射的噪声和轮胎激振车体振动产生的噪声构成。城市道路交 通所引起的噪声引起听力损伤，对人体的健康和正常的生活与工 作都有很大的影响。据研究:在4 0 - 4 5 d b的噪声刺激下，睡着人 的脑电波开始出现惊醒信号， 对于突发性的噪声在6 0 d b时， 可使 7 0 %的人惊醒。可见，城市道路交通噪声污染也是困扰着城市道 路交通网络规划者和管理者的又一重要问题。 3 . 其他环境问题 城市道路建设和营运过程中，对沿线一定范围内的生态环境 和人文景观也会产生不同程度的影响和破坏。 北方交通人学硕 f 论文 二、城市道路交通环境保护的对策 城市道路交通环境的保护是一项复杂的系统工程。解决城市 道路环境污染的对策， 既要从制度上加大管理力度， 运用法律的、 经济的各种手段，又要从技术创新上寻找解决城市道路交通环境 保护的有效途径，做到定性分析与定量研究的有机结合。首先从 管理层面看: 建立城市道路交通环境质量评价体系 为了控制城市交通对城市环境产生新的污染，必须建立城市 道路交通环境质量评价体系。城市环境空气质量可以采用综合质 量指数进行评价。综合质量指数的计算式为: p = 艺w , p ,且 艺 w , 二 式中:p 一一环境空气综合质量指数: 月 一 一 第 l 种 污 染 物 的 污 染 指 数 ， p = 冤, ; c 一一第i 种污染物的 实测( 或预测) 浓 度，m g 1 m ; c 0 一一第i 种污染 物的 评 价标准 值，m g 1 m 3 ; w一一第i 种污染物的权重值; n 一一参与评价的污染物数量。 2 . 城市道路交通环境管理 城市道路交通部门环境管理以建设项目环境管理为主。 其主要任务是执行国家有关的城市环境管理、环境保护的法规和 制度，制定城市道路交通行业相应的规范，规定和细则， 市道路建设，营运给周围环境造成的污染， 对因城 损害和影响采取相应 的坏保对策，使城市道路交通建设与环境建设实现可持续发展。 第一章绪论 3 . 建立健全城市道路交通环境保护的经济手段 环境保护经济手段是环境管理的一种主要方式，它可以弥补 行政法律手段的一些不足，能够使管理系统以最小的经济代价获 得所需要的环境效益。环境保护的经济手段可分为鼓励性手段和 限制性手段两类。 鼓励性手段有利于培养和巩固利于环保的行为， 而限制性手段则能够实现环境污染 “ 内部成本外部化”的还原。 从技术层面看，从车用燃料组成部分的改善 ( 如实现燃料的 无铅化和清洁化)到寻找合适的替代燃料，其核心技术己基本解 决，电动汽车，甲醇汽车已进入了实验化阶段。这主要是就硬件 技术而台的。城市道路交通环境保护之所以是一项复杂的系统工 程，其主要原因还在于它要描述进而试图影响和改变城市交通网 络出行者 ( 网络用户)的行为。从城市道路交通配流技术方面看， 建立合适的城市交通配流模型，实现城市道路交通发展和城市环 境污染治理这一矛盾的定量化研究，能有效地模拟城市道路交通 污染的实际情况，为制定合理有效现代城市的交通管理体制和城 市的可持续发展打下坚实的理论基础。考虑环境因素的配流技术 包括: 1广义用户最优配流模型和广义系统最优配流模型。 与传统的配流模型相比，该模型要求网络用户在选择出行路 径时，既要考虑行驶阻抗，包括出行时间、安全性、舒适性等; 又要考虑出行行为对环境造成的影响，包括空气污染和噪声污染 等。其目标函数不仅要求网络用户的出行阻抗或系统总的出行阻 抗最小，而且要求因车辆出行所产生的城市交通环境污染最轻。 2 . 考虑重点路段上环境污染限制的配流模型。 该模型不但能实现对特殊路段的环境保护，而且能实现释放 到城市道路交通网络中所有街道和街道支线上的污染物尽量相 i司 ，即能够实现所谓的公平目 标 ( e q u i t y o b j e c t i v e s ) . 北方交通大学硕士论文 3 . 环境因素下的确定车辆行驶最优速度的双层规划模型。 该 模型既能保证网络用户的出行行为符合w a r d r o p 平衡原则， 又能使网络管理者实现系统总阻抗 ( 包括环境因素)最低。在智 能交通条件下，该模型对于合理的分流具有十分重要的意义。 城市道路交通智能化进程既带来了城市交通发展的机遇，同 时也带来了环境保护的挑战。只有综合运用各种管理手段，同时 推广各种高新技术，才能有效地解决城市道路交通环境问题，实 现城市道路交通发展与环境保护的可持续发展。 第二节 双层规划模型 由于实际的规划、决策问题都是庞大而异常复杂的系统，涉 及到各种各样的影响因素，关系着各个部门、单位和个人的具体 利益，因此所采用的决策方法应该是多层次的系统决策方法，而 不能是单一层次的决策方法。一般而言，决策机构都是一个分级 或分层次的管理机构，在总体目 标一致的前提条件下，各级都有 其各自独立或相互矛盾的目标。因此，在作出科学而系统的最终 决策之前，需要综合考虑彼此之间存在相互作用的、有其各自目 标的各个层次上的部门、机构和个人的意见，力求最终的决策能 使整个系统达到最优的目的。 多层规划问题的一个重要特点就是可以应用在多层决策问题 中，多层规划使用一个分层次的结构，在各个层次上的决策者都 有其各自的目标函数，在某种程度上，本层的决策空间是由其它 层次决定的。此外，某一层次上的决策者通过特定的方法和手段 以影响其它各层的决策制定，从而达到优化其自身目标函数的目 的。例如，这些方法和手段可以是控制较低层次的资源分配和使 用、调整分配给各层的利益等。在多层规划中，所有的决策者优 化其自身的目标函数，而不考虑他们的决策对其它各个层次的影 a i- j 。 多层规划问题的另一个重要特点是:决策变量的控制权分别 属于各层的决策者，而在传统的单层规划中，决策者同时控制所 有的决策变量。但在政府部门的实际决策过程中，对决策变量的 第一章绪论 控制和处理并不是同时进行的，而是采用自上而下的多层次决策 方法。例如，在大多数国家中，中央政府首先在各个省之间分配 资源( 指的是广义的资源) ，然后各个省在中央政府所分配的资 源基础上，决定其各自的行为、政策。 在城市交通系统中，政府部门对交通基础设施投入大量资金 和财政补贴，采用建设新的道路、改善己有路段、更新公交汽车 等等措施以维护整个交通系统的正常运行，满足日 益增长的交通 需求，同时，政府部门也应考虑到公众出行行为对环境的影响， 以实现城市交通的可持续发展:而公众则调节自己的出行行为以 适应这些给定的交通设施和环境要求。也就是说在政府部门为出 行者提供交通基础设施和坏境要求之后，出行者根据具体的交通 状况来决定是否出行和如何出行。 可见在多层规划中，以优化自己的目标函数为目的的决策者 在高层决策者事先确定决策变量值之后，对自己能控制的决策变 量进行优化，以达到最优目的。多层规划比单层规划具有优势， 包括能够明确建模表示顺序的决策过程的能力，能够明确表示不 同层次优化过程或不同决策系统之间的相互作用的能力。 双层规划问题是多层规划问题的一种特例，其中只有两个层 次，两种决策者。由于交通投资决策过程涉及到政府部门和公众 的相互作用或者他们之间的联合决策行为，是一个典型的双层决 策问题，因此双层规划模型成为描述城市交通配流问题的理想工 具。本节将具体介绍双层规划的基本概念 ( 参见文献 4 3 1 ) . 一、双层规划模型的定义和特性 1 . 定义 一般来说，双层规划模型具有如下形式: c 尸i ) ( u1 ) m i n f ( x , y ) s . t . g( x , y ) _ e .i ， 双层规划模型 组成，式 ( 1 - 1 )一 s .七 y 已 e _ ， g ( x , y ) 0 f : e x e - a e ( 1 - 3 ) ( 1 - 4) g : 创- e a - e 0 . g : e i x e 2 - + e . ( p i )是由上层模型 ( 1 - 2 )构成上层问题， ( ul )和下层模型 ( l i ) 式 ( 1 - 3 )一( 1 - 4 )构成 下层问题。上层决策者通过设置x 的值影响下层决策者，因此限 制了下层决策者的可行约束集，上层决策者通过下层决策者的目 标函数与下层决策者相互作用。必须注意到:下层决策变量y 是 上层决策变量x 的函数，即y = y ( x ) ， 这个函数一般被称为反应函 数。 2 . 可行性和最优性 假设 r _ 层决策者控制的决策变量的集合为xce ，下层决策 者控制的决策变量的集合为y c e a ， 并且假设xn y = o 。 在双层 优化过程中，上层决策者首先选择变量x ，这样一来，就会影响 下层决策者的可行策略集合。对固定的x ，下层决策者所要解决 的问题变为: m i n ( f ( x , y ) : y x ) s . t . x , y e s= ( x , y ) : g ( x , y ) o , g ( x , y ) 0 ) ( 1 - 5 ) ( 1 - 6 ) 下层决策者的解集属于定义如下的合理反应集 ( r a t i o n a l r e a c t i o n s e t ) : 定义 如果对给定的一个点x c- x， 存在唯一的解y e y , 由方 程 ( 1 - 6 )所定义的集合s 上f的合理反应集如下: 叱( s ) = x e x , y e y : ( x y ) e s , f ( x , y ) = m in (f ( x , y ) : y l x ) )( 1 - 7 ) _进 一 步 ， 对 于 每 一 个 x ， 如 果 存 在 一 个 y 使 f (x ,y ) 在 所 有 的 点 ( x , y ) e s 上唯一最小，那么可定义如下的合理映射: y = (d 1 ( x ) ( 1 - 8) 上层决策者控制两个变量的问题变为: m in ( f ( x , y ) : ( x , y ) 。 叽( s ) ) ( 1 - 9) 定 义 如 果 满 足y = (d , ( x ) ， 这 里 映 射中 .(d / 为 点夏 处 的 合 理 映 第一章绪论 射，即点歹 对点又 来说 就 是最 优的， 则 称这 样的 一 对点( x , y ) 是 双 层规划问题 ( p )的可行解。 定义 如果( x , y + ) 满足以下两条就认为( x . y) 是双层规划的 最优解。 ( 1 ) ( x * , y * ) 是可行的。 ( 2 ) 对所有的( x , y ) e s，都有: f ( x , y ) f ( x , y ) 其中:假设s 为非空有界 紧集合 ( n o n e m p t y a n d c o m p a c t ) . 设( x , y ) 是双层规划的最优解，则其一阶必要条件为: ( 1 ) f, g, f, g 都是一次连续可微函数; ( 2 )对x * e x，下层jq题 ( 1 - 3 )一( 1 - 4 )有唯一解; ( 3 ) 存在,u e e o 2 ，使得( x , y , 4 ) 是下列问题的可行解: m in f ( x , y )( 1 一 1 0 ) % . y . 臼 s . t . g ( x , y ) 0( i 一 1 1 ) o y f ( x , y ) 一 /z d y g ( x , y ) = 0 ( 1 - 1 2 ) u ( g ( x , y ) ) = 0( 1 一 1 3 ) g ( x , y ) e . 假 设函 数厂 、 g , ) , 气 在( x . , e . ) 的 邻域内 两 阶 连续可 微， 且 v , f , v x g , v , h 关于。 一阶连续可微。 与p ( e ) 对应的拉格朗日 函 数定义如下: l (x ,e ,兀 ， ) 一 ， (x , a ) 一 艺 二 ， 9 (x , a ) 十 艺 、 ， 权 (x , e )( 1 -3 5 ) 其中:二 。 e , g e e 0 o 假设w r , u ) 满 足使问 题p ( e ) 达到 严格局部最小值的二阶充分条件， o , l ( x ， 7c . , u . ， e ) 二 0 具体的二阶充分条件描述如下: ( 1 - 3 6 ) 二 厂 g , ( x , 8 9( x , , e * =0 ) ?0 ，i = =1 , 2 , ， m 1 , 2 ,，m 1 4 ( 1 - 3 7 ) ( 1 - 3 8 ) 北方交通大学硕士论文 衬? 0 ，i = 1 , 2 ， 一 m 气 ( x , e ) = 0 , j = 1 , 2 , ， p ( 1 - 3 9 ) ( 1 - 4 0 ) 进一步，有: y t v ; l ( x ， 二 . u , e ) y 0 对所有的 y t- 0 使得: o . g ; ( x , e ) y - 0 ， 对 所有g , ( x ) = 0 的i ( 1 - 4 1 ) o . g , ( x * , e * ) y = 0 ， 对 所 有ir , 0 的i ( 1 - 4 2 ) o . h , ( x * , e * ) y = 0 ，1 = 1 , 2 , ， p( 1 - 4 3 ) 因此，若有: ( 1 ) 所定义的具有扰动参数的非线性规划问题p ( e ) 在 ( x * , e , ) 的邻域内两次连续可微. ( 2 ) 在( x ax， 二 r ， 拼 . r ) 上 ， 满 足 使 问 题p ( e ) 达 到 严 格 局 部 最小值的二阶充分条件。 ( 3 )对所有的i = 1 , 2 , ， m使得g , ( x 矿 ) - 0 的梯度 . g , ( x , e ) 和 梯 度o , h , ( x , e * ) ( j = 1 , 2 , . . .， p ) 线 性 独 立 。 ( 4 ) 满足 严格互 补 松弛 条件， 即: 当g i ( x * , e * ) = 0 时凡 。 。 那么，可以得出以下结论: ( 1 ) x 就是所定义的具有扰动参数的非线性规划问 题p ( e ) 的 严格局部最小值，并且相对应的拉格郎日 乘子二 和拜 是唯一的。 ( 2 ) 在e . 的一个邻域内对于。 存在一个唯一的一次连续可 微 函数如下: z 伪 ) = ( x ( e ) r , 8 ( e ) t , f ! ( e ) r t 并且满足问 题p ( e ) 达到局部最小值的二阶充分条件，如下: x ( e ) t ， 二 ( e * ) t , , ( e , ) t t _ x .t ， 二 t ， tt t t 因此， x ( e ) 是问 题p