求解线性双层规划的割平面算法.docVIP

求解线性双层规划的割平面算法 赵茂先1 ,2 ,高自友1 (1 . 北京交通大学 交通运输学院 ,北京 100044 ;2 . 山东科技大学 应用数学系 ,山东 泰安 271019) 摘 要 :利用线性双层规划的全局最优解可在其约束域的极点上达到这一性质 ,通过对问题可行解 集合的结构进行探讨 ,引进一种割平面技术 ,提出了一个求解线性双层规划的全局收敛算法 ,并通 过一个算例说明了算法的求解过程 . 关键词 :线性双层规划 ;全局最优解 ;极点 ;割平面 中图分类号 :O221 . 1 文献标识码 :A A Cutting Plane Algorithm f or Solving L inear Bilevel Progra ms Z HA O M ao- x i a n1 , 2 , GA O Zi- you1 (1 . School of Traffic and Transport , Beijing J iaoto ng U niversit y , Beijing 100044 ,China ; 2 . Depart ment of Applied Mat hematics , Shando ng U niversit y of Science and Technology , Tai’an 271019 , China) Abstract :Based o n t he result t hat a glo bal op timal solutio n to linear bilevel p rogramming occurs at an ext reme point of it s co nst raint regio n , we discuss t he st ruct ural feat ure of it s feasible regio n and p ro2 po se a glo bal co nvergent algo rit hm w hich make use of cut ting plane technique . Finally , a simple exam2 ple is given to illust rate t he applicatio n of t he algo rit hm. Key words :linear bilevel p ro gram ; glo bal op timal solutio n ; ext reme point ; cut ting plane 在许多系统 优 化 问 题 中 , 如 生 产 计 划 , 资 源 分 配 ,政府调节和工程设计等大规模实际问题中 ,系统 可能涉及到不止一个决策者 ,并且不同的决策者具 有各自的目标函数. 传统的单层数学规划技术已经 不能很好的解决这类问题 ,多层规划正是为了研究 系统层次性而产生的 ,并正逐渐形成一个新的运筹 学分支1 . 多层规划中最简单的形式是双层规划 ,主要是 分析两个各具目标函数的决策者之间按非合作和有 序的方式进行的相互作用. 上层首先给下层一定的 信息 ,下层基于这些信息依照自己的利益做出反应 , 上层再根据下层的反应做出符合全局利益的决策 . 一方的行为影响另一方的策略选择和目标的实现 , 但任何一方又不能完全控制另一方的选择行为. 线 性双层规划是双层规划的一个特例 ,虽然上下层问 题的目标函数和约束条件都是线性的 ,但一般情况 下 ,它也是一个非凸优化问题 ,并且已经证明线性双 层规划是 N P- Hard 问题2- 4 . 到目前为止 ,人们已经提出了一些求解线性双 层规划的算法 ,但比较成功的求解全局最优解的算 法还 很 少 . Candler 和 Tow nsley5 提 出 了 第 一 个 全 局收敛算法 ,该算法反复求解两个线性规划 ,可得到 待检 查 问 题 约 束 域 上 极 点 的 单 减 序 列. Bialas 和 Karwan6 对约束域的极点进行有哪些信誉好的足球投注网站 ,提出了所谓的 “ K 次 最好”算法 ,并证明算法收敛于问题的全局最 优解. Bard 和 Falk7 利用下层问题的 K- T 条件 ,将 问题转化为一个标准的数学规划问题 ,为了绕开约 束条件中的互补松弛项 ,用分枝定界技术等价求解 一系列容易的问题 ,而 Bard 和 Moo re8 提出隐式满 足互补松弛项算法被证明效果更好 . White 和 Anan- 收稿日期 :2004211217 基金项目 :国家自然科学基金资助项目 ;国家杰出青年科学基金资助项目 ;北京市自然科学基金资助项目 (90420