足球比分直播

双层规划.doc

返回
双层规划.doc_第1页
第1页 / 共12页
双层规划.doc_第2页
第2页 / 共12页
双层规划.doc_第3页
第3页 / 共12页
双层规划.doc_第4页
第4页 / 共12页
双层规划.doc_第5页
第5页 / 共12页
点击查看更多>>
资源描述:
1双层规划一、 双层规划的定义及背景双层规划(Bilevel Programming Problem,简称 BLPP)是一种具有二层递阶结构的系统优化问题,上层问题和下层问题都有各自的决策变量、约束条件和目标函数。双层系统优化研究的是具有两个层次系统的规划与管理问题。上层决策者只是通过自己的决策去指导下层决策者,并不直接干涉下层的决策;而下层决策者只需要把上层的决策作为参数,他可以在自己的可能范围内自由决策。这种决策机制使得上层决策者在选择策略以优化自己的目标达成时,必须考虑到下层决策者可能采取的策略对自己的不利影响。首先提出层次规划模型的是 H.VStackelberg,上世纪 50年代,为了更好的描述现实中的经济模式,H.V Stackelberg在他的专著中首次提出了层次规划这种概念,虽然多层规划与之有共同点,但各层决策者依次做出决策,并且各自的策略集也不必再是分离的。20世纪 60年代,Dantaig 和 Wolfe提出了大规模线性规划的分解算法,承认有一个核心决策者,它的目标高于一切,但与多层规划有很大区别,多层规划承认有最高决策者,大不是绝对的,他允许下层决策者有各自不同的利益。20 世纪 70年代发展起来的多目标规划通常寻求的是一个决策者的互相矛盾的多个目标额折衷解,而多层规划强调下层决策对上层目标的影响,并且多层规划问题通常不能逐层独立求解。上世纪 70年代以来,在解决实际问题的过程中,人们才逐渐形成多层规划的概念和方法。多层规划(Multilevel Programming)一词是 Candler和 Norton在奶制品工业模型和墨西哥农业模型的研究报告中首先提出来的。上世纪 70年代,人们对多目标规划进行了深入的研究,也形成了一些求解多目标规划的有效方法,如分层优化技术,这种技术也可以用来求解层次问题,但这种技术建立在下层的决策不影响上层的目标基础上,而多层规划正是强调下层决策对上层目标的影响。因此多层规划同城不同于多目标规划。在过去的几十年中,多层规划的理论、方法及应用都有了很大的发展,并且已经成为规划论中的一个新的重要分支,而在多多层规划的研究中,双层规划是一个重要的研究对象,这是因为双层规划是多层规划中的一个特例,同时多层规划可以看作是一系列的双层规划的复合。双层规划是在研究非平衡经济市场竞争时首先提出的,1973 年,在 Bracken和 Mcgill的文章中,出现了双层规划的数学模型。1977 年,在 Candler和 Norton的科学报告中正式出现了双层规划和多层规划名词。双层规划研究的是两个各具目标函数的决策者之间按有序的和非合作方式进行的相互作用,上层决策者优先做出决策,下层决策者在上层决策信息下按自己的利益做出反应,由于一方的行为影响另一方策略的选择和目标的实现,并且任何一方又不能完全控制另一方的选择行为,因此上层决策者要根据下层的反应做出符合自身利益的最终决策。根据上述定义,双层规划具有以下一些主要特点(1)层次性。研究的系统是分层管理的,各层决策者依次做出决策,下层服从上层。(2)独立性。各层决策者各自控制一部分决策变量,以优化各自的目标。(3)冲突性。各层决策者有各自不同的目标,且这些目标往往是相互矛盾的。(4)优先性。上层决策者优先做出决策,而下层决策者在优化自己的目标而选择决策2时,不能违背上层的决策。(5)自主性。下层并不是完全无条件服从上层,它有相当的自主权。(6)制约性。下层的决策不但决定着自身目标的达成,而且影响着上层目标的实现。(7)依赖性。各层决策者的容许策略集通常是不可分的,他们往往形成一个相互关联的整体。二、 常见双层规划的分类(1)线性双层规划线性双层规划(Linear Bilevel Programming,简称 LBM)是双层规划的一个特例,其上、下层目标函数和约束条件都是线性的,是双层规划中最为常见且形式最为简单的一种情况,在实际中应用十分广泛,主要涉及管理决策、交通网络布局、工程设计等诸多方面。一般来说,求解线性双层规划问题是非常困难的,Jeroslow 指出线性双层规划是一个NPhard问题,BenAyed 及 Bard对此结论给出了简短的证明;Hallsen 对性双层规划是强 NP一 hard问题给出了严格的证明。后来,Vicente 指出,寻找线性双层规划的局部最优解也是 NP一 hard问题,不存在多项式求解算法。即使双层规划上、下层中目标函数和约束函数都是线性的,它也可能是一个非凸问题,.并且是非处处可微的。非凸性是造成求解线性双层规划问题异常复杂的重要原因。自 20世纪 70年代以来,己提出了几十种求解线性双层规划的算法,主要有以下几类不同的算法(a)极点算法极点搜索思想的理论基础是线性双层规划的最优解必在诱导域的极点处取得。首先可以利用各种方法来寻找诱导域的极点,然后从中再找出线性双层规划问题的局部最优解或全局最优解。(b)分枝定界法其基本思路是,根据事先选定的分枝准则,将所求解的问题分成一系列子问题,并从中选取一个子问题进行检验,决定其取舍。分枝定界法计算量很大,但它能求得全局最优解。(c)K-T 法其基本思路是将线性双层规划问题中的下层规划问题用它的 Kuhn一Tucke条件代替,将线性双层规划问题化为单层非线性规划问题求解,最初用于求解线性双层资源控制问题。这种算法仅对线性约束的上层和凸二次规划的下层这种特殊情况有效。(d)模糊数学算法其基本思路是充分利用模糊集理论中隶属函数及模糊算子的概念和性质,分别建立上层决策变量的隶属函数和上、下层决策者目标函数的偏好隶属函数,双层决策问题转化为单层优化问题,分别对各单层规划的解进行讨论,最终把线性双层规划转化为求解一个线性规划问题,求得两层决策问题的满意解。(2)凸双层规划凸双层规划(Convex Bilevel Programming) ,即上层目标函数是凸函数,下层目标函数是凸二次函数,约束条件均为线性的一类非线性双层规划。对这类问题,在一定条件保证下,将原问题转化为一个单层的数学规划,通过对其对应的松弛问题有关性质的讨论,给出恰当的定界规则和分支原则,隐含地考虑到互补松弛条件的所有组合,利用分支定界技术给出一种求全局解的算法。(3)混合整数线性双层规划整数规划一类要求问题中的全部或一部分变量为整数的数学规划。 一般认为非线性的整数规划可分成线性部分和整数部分,因此常常把整数规划作为线性规划的特殊部分。在3线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求解答必须是整数。例如,所求解是机器的台数,工作的人数或装货的车数等。为了满足整数的要求,初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解,所以应该有特殊的方法来求解整数规划。在整数规划中,如果所有变量都限制为整数,则称为纯整数规划;如果仅一部分变量限制为整数,则称为混合整数规划。(4)非线性双层规划双层规划(Non-linear Bilevel Programming,简称 NLBP)的一般形式为yXxF,min?(a)解其 中 yGts0.? (b)yf ,i(c,.xgts (d)其中, , 。则上层变量 ,下层变量 。同样,函数1nxR?2ny1nR?2nyR、 分别是上层、下层目标函数,而向量值函数12nF??12f?、 分别是上层、下层约束条件。上层约束条件中121mG122nmg包含着来自两层变量(与用 表示的约束不同)是一个特殊的角色,因为这些条件不能约X束下层决策者,它们不直接的被强制执行。如果上下层目标函数 、 至少有一个非线性的,称之为非线性双层规划。,Fxy,f此外,如果上下层变量在 增加整数约束,称之为证书双层规划。三、 常见双层规划的模型及其应用在双层规划模型中,不同的决策者控制着相应的决策变量,并优化各自的目标函数。下层决策者首先进行决策,这样上层决策者必须预测到下层可能的反应。下层根据上层的决策进行反应,以优化个人的目标函数。因为双方可供选择的策略集是相互依赖的,上层的决策会影响下层可选的决策和目标的实现,反之亦然。设上层决策者控制的变量为 ;下层决策者控制的变量为12,.TnnxxXR???。12,.TnnyyYR???(a)下层以最优解反馈到上层的双层规划数学模型为(BP) X xymiF,?解其 中,0,.?Gts Yyf?in40,.?yxgts(b)下层以最优值反馈到上层的双层规划数学模型为 XxvF?,min0,.?xGtsYyyxgfv?? }0,|,i{其中 , , , ,集合 和集合FfXYR??nmpR?nmqR??X包含了变量的其他约束,如变量的非负性或整数要求等。Y对于上述双层规划问题( ) ,即使当 , , , 均是连续函数,并且集合BPFfGg和 是紧集, ( )也可能没有最优解。导致这种可能性的原因是对某个 ,下X x?层问题可能有多个最优解,下面的例子将说明这种情况。例 1.1 1min0 xxy??解其 中,.?ts12iyfy.stx???12y,0?点 实现了上、下层目标函数的最小值,但对于固定的 点 , 120xy??, , x0?下层决策者可以选择任何满足 和 的正数 , ,这样的12y??12y?10y?2, 对下层都是可行的,而且都是最优的,但上层目标函数值却是不一样的,1y?2当 ,?时 , ;而下层也可以选择 , ,这样下层目标函数值20y1F?f?10y?2,而上层目标函数值 。因此下层问题懂得多解性导致上层问题可能得不到最f 0F优解。 当然下层问题的多解性不仅会导致双层规划的无解,而且还会对双层规划问题产生许多影响。51、双层规划在区域港口内陆运输网络上的应用 [2]361)基本参数可以建设港口内陆集散中心的潜在地点的数量;n在第 j 地建港口内陆集散中心的最大允许容量;j?在第 j 地建内陆集散中心的固定成本费用;1jf在第 j 地建内陆集散中心的变动成本费用;ja从生产地 i 到内陆集散中心 j 的单位运输费用;ijc从内陆集散中心 j 到出口港 k 的单位运输费用;ijg生产地 i 的生产量;ip出口港 k 的容量;kqd总运输需求量。2)决策变量, ,表示在第 j 地建内陆集散中心; 0 ,表示在第 j 地不建内陆集散中心。jy1j?jy,表示在第 j 地建内陆集散中心的容量;ja,货物从生产地 i 到集散中心 j 的运输量;ijx,货物从集散中心 j 到出口港 k 的运输量。jkz上层规划可以描述为物流规划部门在满足运输总需求的条件下确定货物集散中心的数量和规模,使得总成本(固定成本和变动成本)最小;下层规划描述了在多个货物集散中心和出口港口存在的条件下,物流服务企业的运输量在不同运输路线的分配,使得物流服务企业的总运输成本最小。对于上层规划来说,其数学模型为 1minffjfSya???1.0,;jffjjadsty????????(P)当上层规划达到最优时,即确定了各港口内陆集散中心的容量 ,则下层规划便根据ja上层规划确定的各集散中心的容量 ,,寻求最优的运输方案,这里包含两个运输问题,一ja6个是从生产地运到内陆集散中心,另一个是从内陆集散中心运往出口港。从生产地到内陆集散中心的运输问题即下层规划的第一个模型为11minnijfScx??11,.,,.,.0,.,;1,.ijjnijimijijzaxpstdxjn??????????(LP1)其中 由上层规划决策确定。ja从内陆集散中心到出口港的运输问题即下层规划的第二个模型为 21mintnijkfSgz??11,.,,.,.0,.,;1,.tijjknijitijkijaxpmsdzljn??????????(LP2)因而整个问题形成一个双层规划问题,即求解如下的数学规划问题 112minffjfSyaSa????1.0,;jffjjadsty????????(BP)其中 , 由下述规划所确定1Sa2 11minnijfScx??711,.,,.,.0,.,;1,.mijjnijimijijzanxpstdxjn???????????(LP1) 21intnijkfSgz??11,.,,.,.0,.,;1,.tijjknijitijkijaxpmsdzljn??????????(LP2)其中 12 .Tnaa我们把上述双层规划归结成一个值型双层规划。上层规划确定了各个内陆集散中心的容量 ,,下层规划根据内陆集散中心的容量确定最佳运输方案,以求得最小费用。j2、双层规划在宏观调控上的应用 [1]2国民经济系统包含了众多个厂商、众多个消费者和政府等三类行为主体。整个市场体系既涉及了产品市场,又涉及了要素市场。其中产品市场不仅考虑了其供求状况。同时还考虑了国际市场中的对外贸易情况;而要素市场主要考虑了资金市场和劳动市场的供求状况。1)厂商设国民经济系统中共有 l 个厂商,生产 m 种产品,并记厂商集合为 ,{1,2.}El?记产品集合为 。{1,2.}G?2)消费者设国民经济系统中共有 个消费者,并记消费者集合为 ,其个人收入n{1,2.}Cn?分别记为 , 。0kIC?83)政府在现代宏观经济中。政府是极其重要的行为主体, 它要对国民经济进行干预和调控。进而保证其平稳有序地运行(政府的另外一个作用在于它是构成总需求的重要方面)。4)市场产品市场记第 种产品的价格为 ,这里 是模型的外生变量。无论对于单个厂商jjPj还是对于单个消费者来说它都是常数, 。设第 j 种产品的投资需求、政府需求以及G?净出口总和为 IGNX。A、 上层规划模型根据上面的描述可以得到政府追求社会福利最大化的上层规划模型为;1maxnkWqu??11 1, 1, 2, .lml nijgjigjkjlijjiijjbaxIGNXyMxLst?????????1001 3, 4lnijjkkxGITI?????,12,., 5, 0,0,. 6kjjjjkLkHntrwNXTCTjG??????????????其中 式1是产品市场供求平衡约束条件,式2是资金市场供求约束条件, 式3 是劳动市场供求约束条件,式4 是转移支付约束条件 它表明政府的个税收入至多全部补贴于低收入者,式5 是基本效率约束条件 它要求政府对消费者征收个人所得税后, 其个人可支配收入的排序与初始收入的排序应是一致的,式6是政府宏观调控变量和其他模型内生变量非负或非正约束条件。需要特别指出的是 厂商的决策变量和消费者的决策变量 由下层规划模型求解得出。,ijxEjG?,kjyCjG?B、 下层规划模型在国民经济系统这一递阶系统中,处于下层的是众多厂商和众多消费者。他们在产品价格和政府宏观调控变量给定的前提下进行最优决策。可得到厂商追求利润最大化的优化模型为;11 11maxmmmjjijgjgijijijijf jptaxbptaxMrxLwx?????????1, 7.0.ijfijstxEjG???? ????9其中 式 7 是厂商生产可行性约束条件, 式8是厂商决策变量的非负约束条件。可得到消费者追求效用最大化的优化模型为;maxuk01, 9.,. 10jkfkjPyITstCjG??????????其中 式9是消费者收入约束条件,式10是消费者决策变量的非负约束条件。由此可见,下层规划模型是由 个以产品税率、资金利率、劳动工资率为参数的线性l规划和 个以个人所得税率为参数的非线性规划共计 个规划组成. 所以基于双层规n ln?划的宏观经济调控模型为;1maxnkWqu?1111001 ,,,,,, 0,,0,..max1lmnijigijjgklijjilijjnkkkjjjjkLkHijjbaxIGNXyGMLxITtrwIGNXTCTjGsp????????????????????其 中是 下 述 下 层 子 规 划 的 最 优 解 1 11101 ,,. ,2.;,. 12,.,mmmjijgigijijijijj ffijfijkjmjkkfjtaxbptaxMrxLwxstilxEjGyPITst nyCj????????????????????????????是 下 述 下 层 子 规 划 的 最 优 解 ?3、双层规划在供应链中的应用 [3]10供应链网络设施选址是一个重要的基础性决策问题, 它直接影响到供应链系统运作中的相关成本。由于顾客需求的日益多样化和全球动态经济环境的逐渐形成, 使企业间的竞10争日趋激烈。目前解决此问题已形成了多种方法, 按选择的离散程度大致可分为连续选址模型和离散选址模型两种。供应链选址双层规划模型的建立在实际的物流中心选址决策中,在新物流中心建立前一般已存在若干个旧物流中心,这些物流中心之间存在着竞争,也就是说客户需求不仅仅由新建的物流中心满足, 有一部分需求可能由已有物流中心提供。针对于此建立了改进的基于竞争的供应链物流中心选址双层规划模型。A、上层规划模型上层规划 U可以描述为决策部门在允许的固定范围内确定最佳的新选物流中心的中点以使总成本最小(包括固定成本和可变成本) 。而下层规划 L 则描述了在多个物流中心存在的条件下,客户需求量在不同物流中心之间的分配模式,它的目标是使每个客户的费用最低。具体模型如下所示。 minijjjqi jUFcxfzpw???(1)1. jstfzB??(2)1njz??(3) 1mjqjwM???1,.qp??(4) 1mikiV?(5)11pmijjqixw??1,.jn??(6) {0,}jz?(7) 式中 地点的配送中心为第 个客户提供服务所需支出的单位费用;ijci第 个客户在 地点的配送中心得到满足的需求量;ijxj在 地点建配送中心的固定投资费用;jf
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播