论文部分内容阅读
摘 要：混合整数的双层线性规划是指上层变量为0～1型变量，下层变量为连续型变量的线性规划，在求解过程中，根据分支定界法原理对下层问题的对偶问题可行域上的极点进行计算，然后将上下层变量的上层线性规划进行转换使之成为有限个混合整数线性规划问题，从中求得全局最优解。
关键词：混合整数双层线性规划 全局最优解 对偶间隙
层次性是大系统和复杂系统的主要特征。多层规划产生的主要目的是为了研究层次性，在研究的过程中逐渐形成一个新的运筹学分支。由于人们一般将决策系统看作双层决策系统，从而使得双层规划成为多层规划中最常见的形式。要使双层规划的情况下作出符合全局利益决策的规划，就必须将非合作层进行有序组合，首先让上层给下层一定的信息，下层按照自己的利益对这些信息给予一定的反应，上层再根据下层的反应做出决策，这样才能够使得决策体现全局性。
一、混合整数双层线性规划的全局优化方法模型及其定义
1.混合整数双层线性规划的全局优化方法模型
双层优化问题中，在变量的取值上面都有一定的要求，一般要求取整数值的变量较多。比较有代表性的规划是城市交通网络的设计中、企业生产设备的分配中、企业人力资源的规划等，对于这些规划的变量一般都要求取整数值。变量的离散性分析一般会使得一些较为简单的混合整数双层线性规划问题出现无解的情况。为了保证分支定界求解算法收敛，采用Moore和Bard讨论上下层都有离散变量的混合整数上层线性规划问题，当分支定界求解算法上层无连续变量的时候，就会出现收敛现象。Moore和Bard主要研究的是上下层变量为0～1型变量的混合整数上层线性规划问题，对参数整数的规划求解从中得到分支定界的方法。
假设x为上层决策者控制的n维列向量，y为下层决策者控制的m维列向量，可以将混合整数双层线性规划问题的一般形式写为：
（P1）minF（x，y）=c1x+d1y，s.t.A1x+B1y≤b1 xj=0或1（1≤j≤n）。
其中，y解为（P2）minyf（x，y）=d2y，s.t.A2x+B2y≤b2 y≥0。
其中 ，（P1）为混合整数双层线性规划的全局优化方法的上层问题，（P2）为混合整数双层线性规划的全局优化方法的下层问题。MIBLPP的约束域为S，其中S={（x，y）：A1x+B1y≤b1A2x+B2y≤b2，xj=0或1（1≤j≤n），y≥0}，设T为S在上层决策空间上的投影，则T={x：（x，y）∈S}。对于规划中的x∈T，记作S（x）={y：（x，y）∈S}。
2.混合整数双层线性规划的全局优化方法定义
（1）下层问题的合理反应集为P（x）={y：y∈argmin[f（x，y）：y∈S（x）]}，则混合整数双层线性规划的全局优化方法的诱导域为IR={（x，y）∈S：y∈P（x）}。
（2）对于一个集合（x，y）∈IR，如果存在（X*，y*）∈IR满足条件F（x*，y*）≤F（x，y），则可以将（x*，y*）称为混合整数双层线性规划的全局优化方法的全局最优解。
下层问题的合理反应集Px一定程度上定义了下层决策者的反应情况，IR作为可行解集合对上层决策者给出了一定的优化空间，通常情况下，可以将连续双层线性规划问题称作混合整数双层线性规划的全局优化方法的松弛问题：
（RP）minF（x，y）=c1x+d1y s.t.A1x+B1y≤b1 x≥0
其中y解为minf（x，y）=d2y 当s.t.A2x+B2y≤b2 得出y≥0
将S={（x，y）：A1x+B1y[b1，A2x+B2y≤b2，x≥0，y≥0}记作是（RP）的约束，域，从中可以得出S在上层决策空间上的投影即：T={x：（x，y∈S）}。综合定义可以得到P（x）为（RP）下层问题的合理反应集，IR为（RP）的诱导域。如果将S设为非空紧凸集，并且满足决策x∈T，此外，（RP）的下层问题都有唯一最优解，就可以得到如下结论。
结论1：S∈S，IRIR，结论2：如果S≠φ则IR≠φ，IR中的可行点就会落在凸多面体S的边界上，结论3：如果S≠φ，则混合整数双层线性规划的全局优化方法一定会有最优解，并且其最優解可以在S的边界上面找到。
二、双层线性规划的理论与算法
为了将混合整数双层线性规划的全局优化方法的问题方便地叙述出来，需要将枚举数中节点的序号用k表示出来。
当上层给出x∈T的决定之后，混合整数双层线性规划的全局优化方法的下层就会及时反应为解线性规划问题：（Px）minyf（x，y）=d2y s.t.B2y≤b2-A2x y≥0。
从中可以得出Px的对偶规划为（Dx）maxz（x，u）=u（A2x-b2） s.t.-uB2≤d2 u≥0 uT∈E，U={uT∈Eq：-uB2≤d2，u≥0}，其中，U中所有极点组成的集合为uT。通过线性规划对偶理论可以得到两个定理。
定理1：当存在u*∈UE，（x*，y*，u*）是一个特定函数的最优解时，则有（x*，y*）是混合整数双层线性规划的全局优化方法的最优解，具体证明如下：
当（x*，y*）为混合整数双层线性规划的全局优化方法的最优解时，对于给定的x*，y*，则认为其为下层问题的唯一最优解。通过对偶理论可以得出u*∈UE，其中u*为（Dx*）的最优解。并且d2y*=u*（A2x*-b2）由对偶理论得出y，u分别为Px的最优解。通过上述证明可以得出当给定x∈T时候，就会有（x，y）∈IR，F（x，y） 定理2：（xk，yk）是混合整数双层线性规划的全局优化方法的全局最优解。
证明：通过结论3和定理1可以得出5个步骤：
1.令F=+∞，使用线性规划的方式求出UE={u1，u2…ut}然后再转向步骤2。
2.使用混合整数线性规划的方法可以解出MILP（uk），如果不能得到有效解，可以转向步骤4，若是能够算出有效解，可以将最优解记作（xk，yk），将最优目标函数记作Fk=F（xk，yk）然后再转向步骤3。
3.若是Fk≥F，将计算转向步骤4，否则，令（x*，y*）=（xk，yk），F=Fk，再转向步骤4。
4.如果k 5.若F=+∞则混合整数双层线性规划的全局优化方法无可行解，否则，混合整数双层线性规划的全局优化方法的一个全局最优解为（x*，y*），从中可以找出对应的目标函数值F。
通过算法可以得出，双层规划作为多层规划的特例，主要对两个各具目标函数决策者之间非合作和有序的方法相互作用情况进行分析。上下层之间的行为和决策是相互影响相互作用的，但是上下层之间的选择行为不受对方的控制和左右。在双层规划性问题中，不论上层所取的允许决策如何，下层对偶问题的可行域都不会发生相应的变化。一定程度上也会使得可行域所对应的有限个极点保持不变。从整个问题的角度进行考虑，当下层问题的规模和变量都不大时，就会使得线性规划问题的极点比较容易实现。算法的关键也就是线性规划的极点问题。通过讨论混合整数双层线性规划问题，对于U中对求的最优解的问题起到关键作用和不起作用的现象应该进行深层研究和探讨。
三、结语
在经济模型领域或是网络交通、数据库、集成电路设计、化学工程、图像处理等控制中，全局优化的应用相当广泛。传统的非线性问题只能用于求得局部最优解，不能将其应用于全局优化问题中。由于全局优化在各个领域的重要性使得全局优化分析方法相对复杂，从而出现了一种混合整数双层线性规划的全局优化分析方法。本文主要针对上层所有变量0～1型变量和下层所有变量为连续型变量的混合整数上层线性规划问题进行求解，从中寻找全局最优解的方法。在求解的过程中，首先对下层问题的对偶问题可行域上的极点进行计算，使用的方法是线性规划技术。求出极点以后，再将问题转化为标准的混合整数线性规划问题，可以得出原问题的最优解是目标函数达到最小值的混合整数线性规划的最小值。
参考文献
[1]贾新花 赵茂先 胡宗国 等 一类混合整数双层线性规划的枚举法[J].山东科技大学学报（自然科学版），2009，（1）。
[2]武莹莹 刘卫伟 混合整数双层线性规划的全局优化算法[J].中国科技博览，2009，（21）。
[3]刘浪 陈建宏 郑海力 等 模糊预测型线性规划在矿山产能分配中的应用[J].中南大学学报（自然科學版），2012，（2）。
[4]张端 高岩 章苗根 等 线性规划实现动态优化的模型预测控制策略[J].化工学报，2010，（8）。
[5]刘杰 张涛 张天军 等 改进填充函数法求解一类非线性规划全局极小点[J].西安科技大学学报，2009，（6）。
关键词：混合整数双层线性规划 全局最优解 对偶间隙
层次性是大系统和复杂系统的主要特征。多层规划产生的主要目的是为了研究层次性，在研究的过程中逐渐形成一个新的运筹学分支。由于人们一般将决策系统看作双层决策系统，从而使得双层规划成为多层规划中最常见的形式。要使双层规划的情况下作出符合全局利益决策的规划，就必须将非合作层进行有序组合，首先让上层给下层一定的信息，下层按照自己的利益对这些信息给予一定的反应，上层再根据下层的反应做出决策，这样才能够使得决策体现全局性。
一、混合整数双层线性规划的全局优化方法模型及其定义
1.混合整数双层线性规划的全局优化方法模型
双层优化问题中，在变量的取值上面都有一定的要求，一般要求取整数值的变量较多。比较有代表性的规划是城市交通网络的设计中、企业生产设备的分配中、企业人力资源的规划等，对于这些规划的变量一般都要求取整数值。变量的离散性分析一般会使得一些较为简单的混合整数双层线性规划问题出现无解的情况。为了保证分支定界求解算法收敛，采用Moore和Bard讨论上下层都有离散变量的混合整数上层线性规划问题，当分支定界求解算法上层无连续变量的时候，就会出现收敛现象。Moore和Bard主要研究的是上下层变量为0～1型变量的混合整数上层线性规划问题，对参数整数的规划求解从中得到分支定界的方法。
假设x为上层决策者控制的n维列向量，y为下层决策者控制的m维列向量，可以将混合整数双层线性规划问题的一般形式写为：
（P1）minF（x，y）=c1x+d1y，s.t.A1x+B1y≤b1 xj=0或1（1≤j≤n）。
其中，y解为（P2）minyf（x，y）=d2y，s.t.A2x+B2y≤b2 y≥0。
其中 ，（P1）为混合整数双层线性规划的全局优化方法的上层问题，（P2）为混合整数双层线性规划的全局优化方法的下层问题。MIBLPP的约束域为S，其中S={（x，y）：A1x+B1y≤b1A2x+B2y≤b2，xj=0或1（1≤j≤n），y≥0}，设T为S在上层决策空间上的投影，则T={x：（x，y）∈S}。对于规划中的x∈T，记作S（x）={y：（x，y）∈S}。
2.混合整数双层线性规划的全局优化方法定义
（1）下层问题的合理反应集为P（x）={y：y∈argmin[f（x，y）：y∈S（x）]}，则混合整数双层线性规划的全局优化方法的诱导域为IR={（x，y）∈S：y∈P（x）}。
（2）对于一个集合（x，y）∈IR，如果存在（X*，y*）∈IR满足条件F（x*，y*）≤F（x，y），则可以将（x*，y*）称为混合整数双层线性规划的全局优化方法的全局最优解。
下层问题的合理反应集Px一定程度上定义了下层决策者的反应情况，IR作为可行解集合对上层决策者给出了一定的优化空间，通常情况下，可以将连续双层线性规划问题称作混合整数双层线性规划的全局优化方法的松弛问题：
（RP）minF（x，y）=c1x+d1y s.t.A1x+B1y≤b1 x≥0
其中y解为minf（x，y）=d2y 当s.t.A2x+B2y≤b2 得出y≥0
将S={（x，y）：A1x+B1y[b1，A2x+B2y≤b2，x≥0，y≥0}记作是（RP）的约束，域，从中可以得出S在上层决策空间上的投影即：T={x：（x，y∈S）}。综合定义可以得到P（x）为（RP）下层问题的合理反应集，IR为（RP）的诱导域。如果将S设为非空紧凸集，并且满足决策x∈T，此外，（RP）的下层问题都有唯一最优解，就可以得到如下结论。
结论1：S∈S，IRIR，结论2：如果S≠φ则IR≠φ，IR中的可行点就会落在凸多面体S的边界上，结论3：如果S≠φ，则混合整数双层线性规划的全局优化方法一定会有最优解，并且其最優解可以在S的边界上面找到。
二、双层线性规划的理论与算法
为了将混合整数双层线性规划的全局优化方法的问题方便地叙述出来，需要将枚举数中节点的序号用k表示出来。
当上层给出x∈T的决定之后，混合整数双层线性规划的全局优化方法的下层就会及时反应为解线性规划问题：（Px）minyf（x，y）=d2y s.t.B2y≤b2-A2x y≥0。
从中可以得出Px的对偶规划为（Dx）maxz（x，u）=u（A2x-b2） s.t.-uB2≤d2 u≥0 uT∈E，U={uT∈Eq：-uB2≤d2，u≥0}，其中，U中所有极点组成的集合为uT。通过线性规划对偶理论可以得到两个定理。
定理1：当存在u*∈UE，（x*，y*，u*）是一个特定函数的最优解时，则有（x*，y*）是混合整数双层线性规划的全局优化方法的最优解，具体证明如下：
当（x*，y*）为混合整数双层线性规划的全局优化方法的最优解时，对于给定的x*，y*，则认为其为下层问题的唯一最优解。通过对偶理论可以得出u*∈UE，其中u*为（Dx*）的最优解。并且d2y*=u*（A2x*-b2）由对偶理论得出y，u分别为Px的最优解。通过上述证明可以得出当给定x∈T时候，就会有（x，y）∈IR，F（x，y）
1.令F=+∞，使用线性规划的方式求出UE={u1，u2…ut}然后再转向步骤2。
2.使用混合整数线性规划的方法可以解出MILP（uk），如果不能得到有效解，可以转向步骤4，若是能够算出有效解，可以将最优解记作（xk，yk），将最优目标函数记作Fk=F（xk，yk）然后再转向步骤3。
3.若是Fk≥F，将计算转向步骤4，否则，令（x*，y*）=（xk，yk），F=Fk，再转向步骤4。
4.如果k
通过算法可以得出，双层规划作为多层规划的特例，主要对两个各具目标函数决策者之间非合作和有序的方法相互作用情况进行分析。上下层之间的行为和决策是相互影响相互作用的，但是上下层之间的选择行为不受对方的控制和左右。在双层规划性问题中，不论上层所取的允许决策如何，下层对偶问题的可行域都不会发生相应的变化。一定程度上也会使得可行域所对应的有限个极点保持不变。从整个问题的角度进行考虑，当下层问题的规模和变量都不大时，就会使得线性规划问题的极点比较容易实现。算法的关键也就是线性规划的极点问题。通过讨论混合整数双层线性规划问题，对于U中对求的最优解的问题起到关键作用和不起作用的现象应该进行深层研究和探讨。
三、结语
在经济模型领域或是网络交通、数据库、集成电路设计、化学工程、图像处理等控制中，全局优化的应用相当广泛。传统的非线性问题只能用于求得局部最优解，不能将其应用于全局优化问题中。由于全局优化在各个领域的重要性使得全局优化分析方法相对复杂，从而出现了一种混合整数双层线性规划的全局优化分析方法。本文主要针对上层所有变量0～1型变量和下层所有变量为连续型变量的混合整数上层线性规划问题进行求解，从中寻找全局最优解的方法。在求解的过程中，首先对下层问题的对偶问题可行域上的极点进行计算，使用的方法是线性规划技术。求出极点以后，再将问题转化为标准的混合整数线性规划问题，可以得出原问题的最优解是目标函数达到最小值的混合整数线性规划的最小值。
参考文献
[1]贾新花 赵茂先 胡宗国 等 一类混合整数双层线性规划的枚举法[J].山东科技大学学报（自然科学版），2009，（1）。
[2]武莹莹 刘卫伟 混合整数双层线性规划的全局优化算法[J].中国科技博览，2009，（21）。
[3]刘浪 陈建宏 郑海力 等 模糊预测型线性规划在矿山产能分配中的应用[J].中南大学学报（自然科學版），2012，（2）。
[4]张端 高岩 章苗根 等 线性规划实现动态优化的模型预测控制策略[J].化工学报，2010，（8）。
[5]刘杰 张涛 张天军 等 改进填充函数法求解一类非线性规划全局极小点[J].西安科技大学学报，2009，（6）。