基于混合整数规划的路径规划优化研究

混合整数规划及其应用混合整数规划（Mixed Integer Programming，MIP）是运筹学中一个重要的分支，它可以用于解决包括生产计划、物流运输、资源调度等实际问题。

本文将探讨混合整数规划的基本概念、典型模型以及应用范例。

一、基本概念1.定义混合整数规划是指在线性规划基础上加入了整数变量的限制条件，有时还将变量限制为 0/1 取值，即 0 表示不选取某个变量，1 表示选取某个变量。

2.数学模型混合整数规划的一般数学模型如下：$max\ Z=c^{T}x+d^{T}y$$s.t.$$A x+B y \leq b$$x\in R^{n}, y \in Z^{m}$其中，$x$ 是连续变量向量，$y$ 是整数变量向量，目标函数$Z$ 为一线性函数，$A$, $B$ 为系数矩阵，$b$ 为约束条件的取值。

本模型中整数变量 $y$ 的限制条件可以是 $y \in\{0,1\}^{m}$ 也可以是 $y \in Z^{m}(m>0)$。

3.求解方法求解混合整数规划可以采用分枝界限法、Gomory 切割法、随机搜索等方法。

其中，分枝界限法是运筹学中最基本的解法，其最优性原理为“不断将问题分解成子问题，逐步地去掉某些变量，直到问题变为纯整数规划问题为止，然后通过确定某些变量取值来求解”。

随机搜索法则是通过不断随机生成可行解并比较其目标值的大小进行求解。

二、典型模型1.背包问题背包问题中，有 $n$ 种不同体积和不同价值的物品，需要将它们装入一个容量为 $V$ 的背包。

每种物品只有选择或不选择两种情况。

设$w_{i}$ 为第 $i$ 种物品的价值，$v_{i}$ 为第 $i$ 种物品的体积，则该问题的混合整数规划模型为：$max\ \sum_{i=1}^{n} w_{i} x_{i}$$s.t.$$\sum_{i=1}^{n} v_{i} x_{i} \leq V$$x_{i} \in\{0,1\}$2.生产调度问题生产调度问题中，对于 $n$ 种产品需要进行加工，但是加工需要设备并且不同设备的加工能力存在差异。

基于混合整数线性规划的多目标物流路径规划数学建模多目标物流路径规划是指在满足多个目标的前提下，确定物流运输网络中各个节点之间的最佳路径和运输量。

在实际生产和配送过程中，物流路径规划的优化对于提高物流效率和降低物流成本具有重要意义。

本文将介绍基于混合整数线性规划的多目标物流路径规划数学建模方法。

首先，我们需要明确多目标物流路径规划的目标。

一般来说，物流路径规划需要同时满足以下多个目标：最短路径、最小成本、最小运输时间、最小能源消耗、最小污染排放等。

在实际问题中，可能还会根据具体需求提出其他目标。

我们将这些目标定义为优化目标函数。

其次，我们需要建立多目标物流路径规划的数学模型。

多目标规划中，常用的方法是加权法。

即将每个目标根据其重要性分配一个权重，然后将多个目标函数线性组合成一个总目标函数。

以最短路径和最小成本为例，假设分别对应的权重为w1和w2，则总目标函数可以表示为Z = w1 * f1 + w2 * f2，其中f1和f2分别表示最短路径和最小成本的目标函数。

在建立目标函数之后，我们需要确定决策变量，即模型中需要优化的变量。

在物流路径规划中，常用的决策变量包括运输路径、运输量、起点和终点等。

我们可以使用二维矩阵表示网络节点之间的路径，使用变量x[i,j]表示节点i到节点j的路径是否存在。

同时，使用变量y[i,j]表示节点i到节点j的运输量。

接下来，我们需要定义约束条件，以限制变量的取值范围。

常见的约束条件包括物流路径一致性条件、运输量限制条件、起点和终点限制条件等。

例如，路径一致性条件可以表示为sum(x[i,j]) = 1，即每个节点只能有一条进出路径。

运输量限制条件可以表示为y[i,j] <= C[i,j]，即运输量不能超过节点i到节点j的最大运输能力。

最后，我们可以使用混合整数线性规划求解器对建立的多目标物流路径规划模型进行求解。

求解过程中，需要根据具体情况设置目标函数权重和约束条件，并根据求解结果进行调整和改进。

基于混合整数规划的电网调度优化研究电网调度优化研究一直是电力领域的热门话题，随着社会的发展和人们对能源需求的日益增长，对电网调度优化质量的要求也越来越高。

近年来，混合整数规划在电网调度优化中的应用得到了越来越多的关注和研究。

本文将从混合整数规划的基本概念入手，探讨其在电网调度优化中的应用与发展趋势。

一、混合整数规划基础知识混合整数规划（MIP）是线性规划的一种扩展，是指在约束条件下优化一个线性函数，其中部分或全部变量被限制为整数或0-1变量。

混合整数规划广泛应用于制造业、物流、能源、电力等领域，可用于决策模型中的资源调度、产品设计和生产安排等问题。

二、电网调度优化问题电网调度优化问题是在满足各种约束条件（如电网的安全、稳定以及各种实际需求）的基础上，尽可能最优地使用发电、输电等资源以达到目标。

常常要应对变化莫测的负荷需求、发电设备运行状态、天气等因素的影响，同时还要考虑能源效率、运行成本和环保要求等因素。

电网调度优化的主要目标是：保证电网的安全、稳定、经济和环保。

三、混合整数规划在电网调度优化中的应用混合整数规划在电网调度优化中的应用涉及到发电、输电、储能等方面的调度问题。

其中，常见的电网调度优化问题有：发电机组的调度、输电网的拓扑优化、配电网络优化以及储能调度优化等问题。

（一）发电机组调度问题发电机组调度问题是电网调度优化问题中的重要方面之一。

其主要目标是使得发电设备的运行方式达到安全、高效、经济和环保等标准。

混合整数规划可以将问题建模为一个数学优化模型，然后运用相关的算法进行求解。

优化结果可用于发电厂的生产安排以及电力市场的参考，从而提高发电厂的经济效益和社会效益。

（二）输电网的拓扑优化输电网拓扑优化问题是电网调度优化中的另一个重要方面。

其主要目标是在输电过程中降低能量损耗、提高能源利用效率和电力质量。

混合整数规划可以将输电网络的拓扑结构问题表示为一个数学优化模型，通过求解优化模型得到最优的输电线路配置方案。

1引言线性规划是用来寻求变量处于线性关系时的有效方法，在项目选择、投资组合优化、季节收益预测等问题中有多种应用。

整数规划与线性规划非常相似，但它要求所有或部分变量是整数。

某些情况下，整数规划更可取，如二元变量的管理决策。

部分决策变量为整数的模型，称为混合整数规划。

本文将会研究整数线性规划在投资组合优化中的应用。

模型A ，即整数线性规划（ILP ）模型可以看作NP 完全问题中的0-1背包问题，通过模型A 找出可选入投资组合的股票。

另一个模型是混合整数线性规划（MILP ），这里使用的是有限资产平均绝对偏差（LAMAD ）模型的演变来确定投资所选股票的确切数量，分配最合适的权重，以达到风险最小化、回报最大化的效果。

本文采用3种算法求解：分支剪界算法、动态规划算法和贪心算法。

分支剪界算法用CPLEX 12.6实现，动态规划算法和贪心算法在Eclipse 标准4.4平台上，用Java 语言实现，所采用的股票信息和数据由NASDAQ 和yahoo finance 网站获取。

2算法介绍以下介绍的算法都可以归属于启发法的范畴。

启发法是指不以找到问题的最佳或最确切的解决方案为目标的技术，而是找到一个足够可信的解决方案的方法。

直觉判断、刻板印象和常识都属于这个“范畴”。

它非常适用于在计算或搜索过于详尽和不实际的情况下，通过心理捷径来加快得到满意解决方案的过程，以减轻作出决策的认知负担。

它有常见的几种策略：第一种是将问题的目标状态进行切分，然后通过实现子目标逐渐实现总的目的；第二种是从最终目标状态逆向去寻找达到这个状态的途径；第三种是逐步收缩初始状态和目标状态的距离的方法。

元启发式是指导搜索过程的策略或上层方法论，元启发式的目标是有效地探索搜索空间，以找到最接近的最优解。

启发式依赖于问题，用于确定特定问题的“足够好”的解决方案，而元启发式就像一种设计模式，可以应用于更广泛的问题。

启发式方法特别适用于混合整数规划，因为混合整数规划太大而无法求解最优，而线性规划较为松弛，可以在合理的时间内求解。

基于混合整数线性规划的路径规划算法研究1. 引言路径规划是指在给定起点和终点的情况下，确定从起点到终点的最优路径。

在许多实际应用中，如物流运输、交通调度等领域，路径规划问题都是非常重要的。

随着计算机科学和优化算法的发展，基于混合整数线性规划的路径规划算法逐渐成为研究的热点。

本文将重点介绍基于混合整数线性规划的路径规划算法的研究进展和应用。

2. 混合整数线性规划简介混合整数线性规划（Mixed Integer Linear Programming，MILP）是一类数学规划问题，旨在通过合理地分配有限资源以满足一系列约束条件，从而达到最优化的目标。

MILP问题中，变量可以是连续的（整数）或者离散的（整数），目标函数和约束条件都是线性的。

路径规划问题可以转化为MILP问题，以提高求解效率和优化路径选择结果。

3. 基于混合整数线性规划的路径规划算法基于混合整数线性规划的路径规划算法通常分为两个步骤：建模和求解。

在建模阶段，需要将路径规划问题抽象成一个MILP模型。

在求解阶段，可以利用现有的优化求解算法，如分支定界法、割平面法等，求解该MILP模型，得到最优路径。

4. 实例分析：物流路径规划问题为了更好地理解基于混合整数线性规划的路径规划算法，我们以物流路径规划问题为例进行实例分析。

假设有一家物流公司需要在多个仓库和多个客户之间运输货物，目标是使总运输成本最小。

根据给定的仓库、客户和货物运输需求，我们可以将该问题建模成一个MILP模型，并通过求解该模型得到最优路径规划结果。

5. 算法优缺点及改进方向基于混合整数线性规划的路径规划算法有其优点和缺点。

优点包括能够灵活处理复杂约束条件和具备较高的求解准确度。

然而，由于MILP问题本身的困难性，该算法在处理规模较大的问题时可能存在求解时间过长的问题。

为了进一步提升算法效率，可以采用一些改进策略，如引入启发式算法、模糊搜索等。

6. 应用前景基于混合整数线性规划的路径规划算法在物流运输、交通调度等领域具有广阔的应用前景。

线性规划问题的混合整数规划算法研究线性规划是一种常见的数学优化方法，广泛应用于各个领域的决策问题中。

它通过构建数学模型，寻找可以使目标函数最小或最大的变量值，帮助决策者更好地制定方案。

但是，在某些实际问题中，变量需要满足整数约束，而线性规划只能解决实数问题，所以需要混合整数规划算法来解决这类问题。

一、混合规划问题混合规划问题是指线性规划问题中包含整数（0或正整数）变量的约束条件，也就是说，它在线性规划的基础上增加了一定的约束。

这种情况下，原本的线性规划算法无法得到满足整数要求的最优解。

混合规划问题的解决方法是使用混合整数规划算法。

二、混合整数规划算法混合整数规划算法（Mixed Integer Programming，MIP）是指解决包含整数、实数变量的线性规划问题的算法。

MIP算法的核心思想是将整数规划问题转化为线性规划问题，然后利用线性规划算法求得最优解。

它的过程包括建立问题的数学模型、求解线性规划问题、判断是否满足整数约束、选择分支策略、再次求解线性规划问题等等。

在其中，转换整数规划问题的线性松弛问题是MIP算法求解混合整数规划问题的重要环节。

线性松弛问题是将整数规划中整数变量的约束条件转换为线性约束条件的问题。

三、分支定界算法分支定界算法（Branch and Bound Algorithm）是解决混合整数规划问题的一种常用的方法。

在混合整数规划问题中，得到的线性规划问题无法满足整数约束条件，因此，需要将解空间划分为子集，在每个子集上进行测算，再通过分支判定来进一步判断是否继续搜索。

该算法的核心思想是通过每次分支，将问题分成两个子问题，然后只对其中一个问题进行搜索，直到找到最优解。

这个搜索过程的组织和管理是通过数学模型的剪枝法来进行的。

四、混合整数规划软件混合整数规划算法的使用需要专门的数学模型软件，如GAMS、AMPL、CPLEX等软件。

这些软件对MIP算法进行编程优化，使得在求解过程中，可以有效地进行剪枝和搜索，从而得到最优解。

组合优化问题中的混合整数规划模型研究组合优化问题是一个重要的数学领域，涉及到许多实际应用。

其中一种常见的问题就是如何有效地选择和组合一系列的元素，以达到最优的效果。

这类问题叫做组合优化问题，混合整数规划模型是其中的一种常用的数学模型。

混合整数规划模型通常用于解决二元决策问题，即决策集合只包含0和1两种情况的问题。

在混合整数规划模型中，一部分变量为整数，一部分变量为实数。

通常情况下，混合整数规划问题很难求解。

因为这类问题的可行解空间很大，因此需要采用优化算法来求解。

混合整数规划模型的求解可以分为线性规划和整数规划两个步骤。

由于线性规划是一个简单而又高效的求解方法，因此通常是先求解线性规划问题，然后再用整数规划方法来求解整数解。

这种方法称为分支定界法，是求解混合整数规划问题中最常用的方法。

在混合整数规划模型中，目标函数通常是一个线性函数。

例如，考虑一个生产调度问题，其中一家公司需要决定如何制造一批产品，以达到最大利润。

每个产品可以在不同的时间内生产，而且每个产品都有不同的成本和利润。

在这种情况下，生产调度问题可以被描述为一个混合整数规划模型，其中目标函数是最大化总利润。

假设有n个产品，它们可以在m个时间段内制造。

令x_{i,j}表示第i个产品在第j个时间段内是否被制造。

在每个时间段内，公司只能制造一个产品，因此有以下约束条件：\sum_{i=1}^n x_{i,j} <= 1, for j=1,2,...,m.另外，每个产品有一个成本c_i和一个利润p_i。

公司需要考虑利润和成本之间的平衡，以最大化整个调度周期的利润。

因此，目标函数可以表示为：maximize \sum_{i=1}^n \sum_{j=1}^m (p_i - c_i) x_{i,j}.上述混合整数规划模型中涉及到了许多变量和约束条件，因此需要采用分支定界法进行求解。

这种方法能够同时考虑到实数优化和整数优化两个问题，因此通常是解决混合整数规划问题的最佳方法。

混合整数规划混合整数规划（Mixed Integer Programming, MIP）是运筹学中重要的整数规划问题，它是指线性规划最优化模型中部分变量被限定为整数，即模型中含有整数变量和连续变量的最优化模型。

混合整数规划的实现机理有：假如，在最优化模型中仅限一个变量为整数，则我们可以将这个模型等价地转化为一个具有多向分支的离散模型，每个分支对应一个整数取值；假如，所有变量都被限定为整数，则它就成为全整数规划模型，是NP完备问题，无法使用最优化技术近似求解。

混合整数规划在企业决策分析中具有重要意义，如在市场选择活动分析中，此类模型中需要在多种情况下选择投入最优数量而不是最优受益，留有余地於投资计划中。

此外，混合整数规划可以用于分配问题，其中线性约束提供了问题的结构及信息；整数约束可以特殊的表达投资的整数上限，满足商业需求。

混合整数规划模型是一种复杂的问题，它既具有线性规划模型的特征又具有全整数规划模型的特征，相比而言，混合整数规划往往更具有挑战性和实用性。

混合整数规划方法可以有效地生成局部最优解，但严格来讲其无法得到全局最优解。

人们也提出了算法来弥补缺点。

近年来，大量的算法从理论、算法、实践上都在不断发展，基于分支定界的方法，包括定界算法、启发式算法、最优性算法、加权增量法等，已经成为求解混合整数规划模型有效算法的主要手段。

混合整数规划在工程和管理科学研究中有重要应用，其分析方式可以逺源地求解一定条件下变量和约束条件最优化模型。

混合整数规划问题研究也涉及到一系列复杂问题，包括如何在给定有限的计算资源时解决多变量视图、如何实现启发式算法、如何生成整数可行解等等。

随着技术的进步，人们将继续努力以改进混合整数规划的求解技术。

最优化问题的混合整数规划算法研究及应用随着社会的快速发展和科技的不断进步，人们对于生产、经济、物流等方面的效率要求也越来越高。

这就催生了一个新的研究领域——最优化问题。

最优化问题是通过数学模型、算法、软件工具等手段，寻找最优解的过程。

其在人们的生产生活中，有着重要的应用价值。

其中，混合整数规划算法是最常用的一种优化方法，本文将探讨其研究与应用。

一、混合整数规划算法混合整数规划（Mixed Integer Programming，MIP）是一种决策问题的数学优化模型，它是将线性规划（Linear Programming，LP）与整数规划（Integer Programming，IP）相结合的方法。

混合整数规划在解决线性规划问题时，需要对某些变量进行限制，使它们只能采取整数值。

这类问题被称为混合整数线性规划问题（Mixed Integer Linear Programming，MILP）。

混合整数规划算法的核心思想是将问题模型转化为一个数学形式，并根据一定的规则求解出最优解。

它广泛应用于生产、物流、金融等领域。

例如，企业优化生产计划、物流配送网络、最优化资产配置等。

二、混合整数规划算法的研究现状混合整数规划算法的研究可以追溯到20世纪50年代。

随着计算机技术的不断发展，现代混合整数规划算法的研究也在不断深入。

其中，最基础和流行的求解混合整数规划问题的方法就是分支定界算法（Branch and Bound，BB）。

分支定界算法通过不断将问题划分为更小的子问题，并对子问题进行求解，找到最优解。

它是混合整数规划算法中的一个基础方法，并被广泛使用。

但是，由于其计算量大、时间复杂度高，随着问题规模的不断扩大，分支定界算法却变得难以应对。

针对此类问题，学者们提出了一些改进算法。

例如，利用启发式算法、割平面算法等对分支定界算法进行了改进，以期提高问题求解效率。

同时，研究者们也在探究新的算法，比如整合约束规划算法（Integrated Constraint Programming，ICP）、混合整数非线性规划算法（Mixed Integer Nonlinear Programming，MINLP）等。

2005年7月系统工程理论与实践第7期　文章编号:100026788(2005)0720113204一种混合整数双层线性规划的全局优化方法赵茂先1,2,高自友1(11北京交通大学系统科学研究所,北京100044;21山东科技大学应用数学系,山东泰安271019)摘要:　通过求得下层问题的对偶问题可行域上的极点,将上层所有变量为021型变量和下层所有变量为连续型变量的双层线性规划转化为有限个混合整数线性规划问题,从而用求解混合整数线性规划的方法获得问题的全局最优解.由于下层问题的对偶问题可行域只有有限个极点,所提出的方法具有全局收敛性.关键词:　混合整数双层线性规划;混合整数线性规划;对偶问题;极点中图分类号:　O221.1;O221.4 文献标识码:　A A G lobal C onvergent Alg orithm for S olving the M ixedInteger Bilevel Linear Programming ProblemZHAO Mao2xian,G AO Z i2y ou(11Institute of System Sciences,Beijing Jiaotong University,Beijing100044,China;21Department of Applied Mathematics,Shandong University of Science and T echnology,T ai’an271019,China)Abstract:　The mixed integer bilevel linear programming problem(MI BLPP),where the upper2level decision makercontrols all zero2one variable and the lower2level decision maker controls all continuous variables,is discussed.Bys olving the extreme points of the follower’s dual problem,the MI BLPP is decomposed into a series of mixed integerlinear program ing mixed integer linear program methods,a global optimal s olution to the MI BLPP can beobtained.K ey w ords:　mixed integer bilevel linear programming;mixed integer linear program;dual problem;extreme point对于大系统和复杂系统,层次性是系统的主要特征之一.多层规划正是为了研究系统层次性而产生的,并正逐渐形成一个新的运筹学分支.在多层规划应用中,以双层规划最为常见,这是因为现实中的决策系统大都可看作双层决策系统,并且任何多层决策系统都是一系列双层决策系统的复合.双层规划问题是由非合作且有序的两个优化问题组成,上层首先给下层一定信息,下层在这些信息下按自己的利益做出反应,上层再根据下层的反应作出符合全局利益的决策.在许多双层优化问题中,要求某些变量只能取整数,例如企业人力资源规划问题、生产设备分配问题以及城市交通网络设计问题等.变量的离散性使得问题变得复杂,即使对较简单的混合整数双层线性规划,也可能导致问题无解.M oore和Bard[1]对上、下层都有离散变量的混合整数双层线性规划问题进行了讨论,并给出了一种分支定界求解算法,该算法只有在上层无连续变量的情况下,才能保证收敛.Bard和M oore[2]对上、下层所有变量都为021型变量的混合整数双层线性规划问题加以了研究,通过对构造出的参数整数规划不断进行求解,提出了一种分支定界方法.本文将讨论上层所有变量为021型变量和下层所有变量为连续型变量的双层线性规划问题,通过求得下层问题的对偶问题可行域上的极点,将问题转化为有限个含021型变量的混合整数线性规划问题,从而用混合整数线性规划的方法求得问题的全局最优解.1　模型与定义设x为021型变量组成的n维列向量,y为连续变量组成的m维列向量,本文讨论的混合整数双层收稿日期:2004206201资助项目:国家杰出青年科学基金(70225005);教育部高等学校优秀青年教师教学科研奖励计划(2001) 作者简介:赵茂先(1966-),男,江苏江都人,副教授,在职博士,主研方向为最优化理论与算法.线性规划问题(MIBL PP )一般形式可以写为:(P 1) min xF (x ,y )=c 1x +d 1y s.t.　A 1x +B 1y ≤b 1 x j =0或1(1≤j ≤n ),其中y 解(P 2) min yf (x ,y )=d 2y s.t.　A 2x +B 2y ≤b 2 y ≥0其中c T1∈E n ,d T 1,d T 2∈E m ,b 1∈E p,b 2∈E q ,A 1∈E p ×n ,B 1∈E p ×m ,A 2∈E q ×n ,B 2∈E q ×m .称(P 1)为(MIBL PP )的上层问题,(P 2)为(MIBL PP )的下层问题.记(MIBL PP )的约束域S ={(x ,y ):A 1x +B 1y ≤b 1,A 2x +B 2y ≤b 2,x j =0或1(1≤j ≤n ),y ≥0},S 在上层决策空间上的投影为T ={x :(x ,y )∈S }.对每个固定的x ∈T ,记S (x )={y :(x ,y )∈S }.定义1　称P (x )={y :y ∈arg min[f (x , y ): y ∈S (x )]}为下层问题的合理反应集,IR ={(x ,y )∈S :y ∈P (x )}为(MIBL PP )的可行解集合(或称为诱导域).定义2　对任意的(x ,y )∈IR ,若存在(x 3,y 3)∈IR 满足F (x 3,y 3)≤F (x ,y ),称(x 3,y 3)为(MIBL PP )的全局最优解,简称最优解.合理反应集P (x )定义了下层决策者的反应情况,而可行解集合IR 给出了上层决策者可以优化的空间(通常IR 非凸).对(MIBL PP ),称下述连续双层线性规划问题为它的松弛问题:(RP ) min xF (x ,y )=c 1x +d 1y s.t.　A 1x +B 1y ≤b 1 x ≥0,其中y 解min yf (x ,y )=d 2y s.t.　A 2x +B 2y ≤b 2 y ≥0 记(RP )的约束域为 S ={(x ,y ):A 1x +B 1y ≤b 1,A 2x +B 2y ≤b 2,x ≥0,y ≥0}, S 在上层决策空间上的投影为 T ={x :(x ,y )∈ S }.对每个固定的x ∈ T ,记 S (x )={y :(x ,y )∈ S }.对应于定义1,可定义 P (x )和IR 分别为(RP )的下层问题的合理反应集和(RP )的诱导域.设 S 是非空紧凸集,且对所有决策x ∈ T ,(RP )的下层问题都有唯一最优解,显然有以下结论成立:结论1　S Α S ,IR ΑIR .结论2　若S ≠<,则IR ≠<,且IR 中对应的所有可行点都落在凸多面体 S 的边界上.结论3　若S ≠<,则(MIBL PP )一定有最优解,且最优解可在 S 的边界上找到.2　理论与算法当上层给定某个允许决策x ∈T 后,(MIBL PP )的下层最佳反应是解如下线性规划问题:(P x )　min yf (x ,y )=d 2y s.t.　B 2y ≤b 2-A 2x y ≥0 问题(P x )的对偶规划为:(D x )　max uz (x ,u )=u (A 2x -b 2)s.t.　-uB 2≤d 2 u ≥0其中u T ∈E q .记U ={u T ∈E q:-uB 2≤d 2,u ≥0},U E 为U 中所有极点(基可行解)组成的集合.由线性规划对偶理论得如下结果:411系统工程理论与实践2005年7月定理1　(x3,y3)是(MIBL PP)最优解当且仅当存在u3∈U E,(x3,y3,u3)为下列问题的最优解:minx,y,uF(x,y)=c1x+d1ys.t.　A1x+B1y≤b1A2x+B2y≤b2d2y-uA2x+ub2=0x j=0或1(1≤j≤n)y≥0,u∈U(2.1) 证明　必要性:设(x3,y3)为(MIBL PP)的最优解,则对给定的x3,y3为下层问题(P x3)的唯一最优解,由对偶理论,一定存在u3∈U E,使得u3为(D x3)的最优解,且d2y3=u3(A2x3-b2),即有d2y3-u3A2x3+u3b2=0.又因为(x3,y3)∈S,所以(x3,y3,u3)是问题(211)的可行解.假设(x3,y3,u3)不是问题(211)的最优解,即存在问题(211)的另一可行解( x, y, u),有F( x, y)<F(x3,y3).由于 u∈U,B2 y≤b2-A2 x和 y≥0,所以对给定的 x, y和 u分别是(P x)和(D x)的可行解,且d2 y= u(A2 x-b2),由对偶理论得 y, u分别为(P x)和(D x)的最优解.上述证明说明了对给定的 x∈T,有( x, y)∈IR,且F ( x, y)<F(x3,y3),这与(x3,y3)为(MIBL PP)的最优解矛盾,从而必要性得证.充分性:设(x3,y3,u3)是问题(211)的最优解,则u3∈U,(x3,y3)∈S,且对给定的x3,y3和u3分别是(Px3)和(D x3)的可行解.因为d2y3=u3(A2x3-b2),所以由对偶理论得y3是(P x3)的最优解,从而(x3,y3)也是(MIBL PP)的可行解.假设(x3,y3)不是(MIBL PP)的最优解,则存在( x, y)∈IR,有F ( x, y)<F(x3,y3).因为( x, y)∈IR,则对给定的 x,由对偶理论,一定存在 u∈U E,使得 y和 u分别是(P x)和(D x)的最优解,且d2 y= u(A2 x-b2),从而( x, y, u)是问题(211)的可行解.由假设知F( x, y)< F(x3,y3),这与(x3,y3,u3)是问题(211)的最优解矛盾,所以充分性成立,从而定理得证.根据定理1,可通过求解问题(211)来获得(MIBL PP)的全局最优解,但问题(211)约束中的等式约束d2y-uA2x+ub2=0是非线性的,无法直接对其求解.重新审视问题(D x)会发现,不论x∈T如何选取,问题(Dx)的约束条件不会发生变化,从而x的变化不构成对U和U E的影响.首先用线性规划方法求出U E中的有限个极点,记U E={u1,u2,…,u t},然后将这t个极点分别代入问题(211)的约束条件中,根据定理1,可将问题(211)等价地转化为下列形式的t个混合整数线性规划问题:(MIL P(u i))　minx,yF(x,y)=c1x+d1ys.t.　A1x+B1y≤b1A2x+B2y≤b2d2y-u i A2x=-u i b2x j=0或1(1≤j≤n),y≥0其中,i∈{1,2,…,t}.因为(MIBL PP)的约束域S是非空的,所以对任意的i∈{1,2,…,t},问题MI L P(u i)要么无可行解,要么有最优解.记IΑ{1,2,…,t},使得当i∈I时,问题MI L P(u i)有最优解;当i|I时,问题MI L P(u i)无可行解.定理1和结论3保证至少存在一个i∈{1,2,…,t},对应的问题MI L P(u i)有最优解,因此I≠<.对i∈I,设(x i,y i)是问题MI L P(u i)的最优解,记F(x k,y k)=min{F(x j,y j):j∈I},有以下结论:定理2　(x k,y k)是(MIBL PP)的全局最优解.证明　由结论3和定理1,定理显然成立.由以上结论,给出一个求解(MIBL PP)全局最优解的算法,具体描述如下:步骤1　用线性规划方法求出U E={u1,u2,…,u t}.令 F=+∞,置k←1,转步骤2.步骤2　用混合整数线性规划方法解MI L P(u k),若无可行解,转步骤4;否则,记最优解为(x k,y k),最优目标函数值为Fk=F(x k,y k),转步骤3.步骤3　如果Fk ≥ F,转步骤4;否则,令(x3,y3)=(x k,y k), F=Fk,转步骤4.步骤4　如果k<t,置k←k+1,转步骤2;否则,转步骤5.511第7期一种混合整数双层线性规划的全局优化方法611系统工程理论与实践2005年7月步骤5　停止.如果 F=+∞,则(MIBL PP)无可行解;否则,(x3,y3)为(MIBL PP)的一个全局最优解,对应的最优目标函数值为 F.3　算例考虑如下所给的一个混合整数双层线性规划问题:min F(x,y)=x1+2x2+4x3+ys.t.x1,x2,x3=0或1,其中y解min f(x,y)=-ys.t.-2x1-4x2-8x3-y≤-4-x1-2x2-4x3+4y≤82x1+4x2+8x3+y≤16x1+2x2+4x3-2y≤4y≥0 该例下层问题的对偶约束为:s.t.　-u1+4u2+u3-2u4≥1u1,u1,u3,u4≥0 用线性规划方法可求得U中的极点分别为u1=(0,1Π4,0,0)和u2=(0,0,1,0).由于只有两个极点,所以可将问题转化为两个混合整数线性规划问题MI L P(u1)和MI L P(u2).用标准的021混合整数线性规划方法解问题MI L P(u1)得最优解为x1=(1,0,0)T,y1=9Π4,F1=-13Π4;解问题MI L P(u2)得最优解为x2 =(1,1,1)T,y2=2,F2=9.由于F1<F2,所以该例的最优解为x3=(1,0,0)T,y3=9Π4,F3=-13Π4.4　结论本文给出了一个求解上层所有变量为021型变量和下层所有变量为连续型变量的混合整数双层线性规划问题全局最优解的方法.该方法首先用线性规划技术求出下层问题的对偶问题可行域上的有限个极点,然后将问题转化为一系列标准的021混合整数线性规划问题,其中最优目标函数值达到最小的混合整数线性规划问题的最优解就是原问题的最优解.对本文所讨论的混合整数双层线性规划问题,不论上层所取的允许决策x∈T如何,下层问题的对偶问题可行域U不会发生变化,从而可行域U对应的有限个极点始终保持不变.相对于整个问题,当下层问题控制的变量个数和约束个数规模不大时,用线性规划技术求所有极点的工作容易实现,当然这部分工作也是算法的关键.通过对混合整数双层线性规划有关性质的进一步讨论,U中哪些极点对求解问题的最优解起作用,哪些极点不起作用,从而不必求出U中的所有极点,这应是进一步研究的工作.参考文献:[1]　M oore J T,Bard J F.The mixed integer linear bilevel programming problem[J].Operations Research,1990,38:911-921.[2]　Bard J F,M oore J T.An alg orithm for the discrete bilevel programming problem[J].Naval Research Logistics,1992,39:419-435.[3]　Wen U P,Y ang Y H.Alg orithm for s olving the mixed integer tw o2level linear programming problem[J].C omputers and OperationsResearch,1990,17:133-142.[4]　Edmunds T A,Bard J F.An alg orithm for the mixed integer nonlinear bilevel programming problem[J].Annals of OperationsResearch,1992,34:149-162.[5]　Bard J F.S ome properties of the bilevel programming problem[J].Journal of Optimization Theory and Applications,1991,68:371-378.[6]　Bialas W F,K arwan M H.T w o2level linear programming[J].Management Science,1984,30:1004-1020.[7]　Dempe S.A simple alg orithm for the linear bilevel programming problem[J].Optimization,1987,18:373-385.[8]　Tuy H,Migdalas A,Varbrand P.A global optimization approach for the linear tw o2level program[J].Journal of G lobalOptimization,1993,3:1-23.[9]　Bard J F.Practical Bilevel Optimization:Alg orithms and Applications[M].K luwer Academic Publishers,Boston,1998.[10]　Dempe S.F oundations of Bilevel Programming[M].K luwer Academic Publishers,Boston,2002.。