文摘

优化问题包含有限数目的变量和无限数量的约束被称为半无限规划问题。在某些情况下,一个类可以表示为这些问题的双层规划问题。双层的问题是一个特殊的类的优化问题,其中还有一个优化问题嵌入到一个约束。用半无限问题变成一个双层的问题,然后使用Kuhn-Tucker为单层非线性最优性条件。结果再形成允许我们使用分支界限法方案优化解决问题。计算实验在著名的实例显示了开发方法的有效性结论,它能够有效地解决线性半无限规划问题。此外,一些线性双层的问题从文学是用来验证该算法的鲁棒性。

1。介绍

半无限规划的一般情况(SIP)问题发生在有限数量的半无限约束被认为是。每个约束包含在一组约束被无限的基数,在这种情况下,一个广义半无限规划(GSIP)问题。先前的工作已经报告了问题,包括连续和可微函数(1- - - - - -3]。因此,线性广义半无限规划问题(LGSIP) GSIPs可以被认为是一个特定的案例中,所有的定义功能足够光滑。在[4),逆优化方法提出了解决LGSIP。一般来说,半无限规划是一个非常具有挑战性的领域,吸引了研究人员的注意。例如,评估解决方案的方法和不同的应用程序出现在[5]。同样,GSIPs已经提出的各种实际的应用程序模型,如设计中心,优化生产线,时间最少的控制和鲁棒优化(6]。

关于这个主题的一个基本的参考(7,回顾经典方法GSIP出现在[8]。当一组 不依赖于变量 ,我们有一个标准的半无限编程(SSIP)问题GSIP的另一个特殊的案例。关于后者的问题,在9),一个广泛的研究他们的主要特点是,在[10,11),一些算法方面进行了综述。最近的结果提供了一个线性用例(12- - - - - -15]。广大SSIP应用的概述,我们指的是(7]。GSIP的一些应用程序可以在机器人的可操作性问题(见[16])和反向切比雪夫逼近(见[17,18])。

理论和解决方案方法口是相应的双层的制定密切相关。两类之间的连接依赖的问题,在一定条件下,半无限问题可以作为双层规划的新配方(1,3]。双层规划(BLP)问题已经被用于模型应用广泛,例如,在位置、网络设计、定价、人道主义后勤、和电信系统(19,20.]。BLP可以被视为按等级排列的情况决策者更高层次结构(领袖)旨在优化他/她自己的目标函数根据其决策和决策者的决策层次较低(追随者)。在这种情况下,跟随者认为他/她自己的优化问题,但根据领导者的决策参数化。有必要提到BLP不能被视为两级优化问题,由于领导人的决定限制了从动件的问题,然后,追随者的决定影响领导者的目标函数。因此决策都是相互关联的,但尊重一个预定义的决策者之间的层次结构。

像上面提到的,存在一些方法求解广义半无限优化,利用获得的密切关系的双层的结构问题(8]。尽管上述,提出解决GSIPs稀缺和计算实验的方法是有限的。后者激发我们进行这项研究。因此,为了受益于GSIPs和BLPs之间的关系,下面的想法可能是:用低级问题,一些知名的方法。例如,在凸的情况下,Kuhn-Tucker是常用的最优性条件。之后,一些经典算法用于解决线性双层的问题,等K的算法,Kuhn-Tucker方法,互补的方法,变量消除算法,和罚函数的方法21,22),可以实现解决新配方GSIP。在这种情况下,我们决定实施不同的具体方法,基于分支定界方法,已成功地用于解决非线性口(见[23])。

其他方法,用于解决GSIPs通过双层的配方不同于彼此在较低级别的新处方。例如,斯坦(2)使用低水平均衡约束模型。在[8),互补约束是用来取代低水平。数值方法来近似替代所产生的最初的问题是这些互补约束的光滑的3,24]。该方法已应用于解决(见[定心设计和宝石的切割问题1,25),分别)。另一种方法是将低水平的相应的对偶问题。在[24被认为是,沃尔夫的双重问题。表明,在其他情况下,由此产生的问题是数值处理。从理论上讲,可行方向方法和离散化算法(6)已经提出了解决GSIPs。然而,计算实验是复杂多维的指标。大多数这些方法被开发来解决特定类GSIPs或取得重大假设防止他们的再现性,。相反,所提出的算法是出于思想给出了(3]求解半无限规划问题的一般情况,但详细描述和结果报告。因此,一个详细的一步一步的描述算法包括促进其实现和再现性。

本研究的主要贡献是一种算法的建议,可以用来解决特定类的广义半无限规划问题。特别是,考虑半无限约束线性问题。该方法利用了条件,允许一个广义半无限问题作为一个双层规划处理。为了应用这种方法,半无限问题的表示一个双层的是必需的。然后,Kuhn-Tucker最优条件用于表述成一个单层,双层的问题通过和解决方案。通过计算实验显示了算法的有效性。验证结果,我们分析解决测试线性半无限规划问题,显示了代数和图形解决方案配合解决方案获得的算法。

本研究的其余部分组织如下。节2,一些预赛和符号被认为是在这个研究。节3,发达算法描述。因此,计算实验,验证了算法的有效性,提出了部分4。此外,一些例子是解决几何和代数方法证实了解决方案。调查结论,包括重要讲话的主题研究和进一步的研究方向提出了部分5。

2。预赛

让我们介绍必要的符号在这项研究中,以及一些概念和必要GSIP BLP,结果将被使用。

在本研究中,我们考虑 , , , , , 是一个 - - - - - -矩阵,是一个 - - - - - -矩阵,是一个 - - - - - -矩阵,是一个 - - - - - -矩阵。

我们考虑线性广义半无限规划(LGSIP)被定义为的问题 在哪里

除非另有说明,否则我们会考虑 和 ,在集和还会有更多的限制决策变量。特别是, 和 ,也就是说, 和 ,对所有 和 ,分别。此外,我们将考虑这一点 ,在哪里 ;通过添加在这个条件总是可以满足适当的(如额外的条件 或其他人只依赖变量 )。

下面的符号(21),一个线性双层规划被定义为(LBLP)问题 在哪里被定义为在 。

与条件 ,问题SIP可以看作一种特殊结构,低层LBLP问题目标函数得到上层约束。提出下一个问题,结果(见[3):

为了明确的考虑问题,我们假设集值映射 均匀致密 。换句话说,存在一个球 与 对于任何 这样紧凑,表示的拓扑闭包 。因此,在这些假设下,映射关闭和上半河岸,然后呢是一个闭集。重要的是评论,通过考虑后者条件,低级的问题吗 , ,总是有一个最佳的解决方案。

第二集是关联到一个双层的问题。让 的一系列解决方案 。考虑 解决方案图 ,和 作为上层约束集。同时,让 是可行的 。

现在,与半无限问题相关的概念定义的介绍。首先,它的可行集定义如下:

假设下的设置 ,我们有(见[3]) ,在哪里表示正交投影空间 。

后者平等允许使用方法提出解决LBLP问题获得LGSIP问题的解决方案。

在介绍中提到的,算法的主要思想,旨在解决线性双层的问题是用双层的问题转化为一个等价的单级。后者可以通过使用描述的重要的结果。

考虑 和 相应的对偶变量的约束与低级问题,也就是说,约束由方程(3)。使用符号的问题 ,我们适应下列命题中给出21]。

命题1。的必要条件 来解决存在(列)向量吗和这样 解决了

这单级再形成有效在双层规划低级问题是凸。因此,它并不总是存在的所有类的BLP问题。然而,在这项研究中,我们正在考虑线性情况下,这个问题可以新配方在这个计划。

3所示。一个算法使用Kuhn-Tucker最优性条件和求解LGSIPs和方案

众所周知,最常见的一种方法来解决线性双层的问题通过使用其等效单层再形成,给出了方程(5)- (10)。可以欣赏,生成的单层模型是一个非线性(见方程(9)),使优化过程更加复杂。注意的是,方程(9)是唯一的非线性约束,通常试图处理再形成没有解决这种改进的非线性方程,而不是单一层次模型。

一个选项来解决新配方的非线性模型是通过忽略非线性项(这导致松弛的问题)和解决结果放松限制问题。实现这一点,让我们考虑所有出现在低层的不平等问题在以下方式: , 。同时,识别,非线性约束 ( ,在哪里 , )暗示的互补松弛约束。记得放松再形成收益率线性子问题。

结果线性子问题被解决后,检查如果方程(9)持有。如果是这样,所获得的最优解是一个可行的解决方案的问题由方程(5)- (10),这意味着它是一个可行的解决方案为双层的问题来源于SIP;如果不是,一种方法基于分支界限法实现方案来满足互补松弛约束。实现后者,考试的所有可能的组合的值,保证隐式互补松弛。一个完整的周期,这个过程称为迭代。

中引入的符号(21),这是一个隐式枚举的经典符号,用于描述解决方案的方法所考虑。让 是一组与之关联的索引互补松弛条件(见方程(9))。考虑单层重构的目标函数,对应于上层的双层的问题的目标函数,并考虑作为现任上限上层的目标函数。索引的一个子集 被认为是在th的搜索树,一条路使用。路径表明如果 或 ,为 。常见的集 , ,和使用隐式的分支界限法。因此,

的变量和 ,的 ,认为是负的,解决单级新配方的松弛问题定义为方程(6)- (11)。回忆,在前面提到的放松,方程(9)是省略了。因此,互补松弛约束可能会满意。

算法的描述基于和方案,认为互补松弛约束提出了下一步。重要的是要强调,这个算法是建立在Kuhn-Tucker方法求解线性双层的问题(见[21])。在非线性问题中,Kuhn-Tucker条件使用在全球化26]。(我)初始化:设置 , , , ,和 。(2)(主要步骤th迭代):集 ,为 ,和 ,为 。试图解决放松的单一问题,也就是说,问题方程中定义(定义的问题6)- (11)省略方程(9)。如果一个最优解, ,记录解决方案 ,继续理解步骤;否则,后退一步。理解:如果获得的解决方案产生一个目标函数值最差,现任需要回溯。也就是说,如果 ,去后退一步;否则,继续分支的一步。分支:如果 , ,进入下一步;否则,选择的产品 是最大的一个,标签吗 。更新设置如下: , ,和 。附加当前路径 ,并返回到主的一步。更新:现任目标函数值 。回溯:如果当前路径中的所有节点已经被探索,去下一个步骤;否则,分支的th组件最近引入的路径和更新 , ,和 。回归的主要步骤。终止:如果初始现任值保持不变( ),因此,双层的问题没有可行的解决方案。否则,考虑相关的可行解为最优。

这个算法和方案解决完全等效的单级再形成的线性双层规划问题。后者来自线性广义半无限问题。因此,这个算法是用来解决LGSIPs优化。

4所示。数值实验

在本节中,上述算法是用来解决一组十个线性半无限问题具有不同特点。解决LGSIPs显示其有效性和适用性。自不同的例子将显示,半无限问题,它的可行集,最优值和最优组是有区别的 , , ,和 ,分别在哪里表示数量的例子。此外,双层的形式,我们也区分其相应的设置 , , ,和 。

本节的目的是展示该算法能够解决LGSIPs在一个有效的方式。测试问题的最优解与解析获得的最优解。八个附加线性双层的问题也强劲计算部分测试表明,该算法能够有效地解决这些问题。因为这里大多数的半无限问题测试提出的我们,我们不比较效率我们的算法与其他方法的结果。然而,比较有关的质量解决方案。

前三个例子展示特定的情况 。虽然研究感兴趣的只是在一般情况下(因为在标准口,他们本质上是有限的顶点定理),标准小口被认为表明该算法是有效的在这两种情况下。

例1。考虑以下问题: 图1表明问题可行解, 和 。
的双层的配方是 算法的同时,得到的解决方案的解决方案获得几何。

例2。考虑以下问题: 相应的双层的配方 该算法表明, 和 。

例3。考虑以下问题: 在哪里 双层的配方是 由算法获得的结果 和 。
下面的例子表明,该算法也有效解决半无限问题在一般情况下。

例4。考虑以下问题: 在哪里 这个例子给出了(23),双层的问题有最优组 和它的最优值 。
解决半无限问题使用文中提出的算法,推导出双层的配方: 然后,其等效单层再形成如下: 为了解决这个问题,非线性约束(互补松弛约束)省略,轻松解决线性问题: 松弛问题的最优解 ,的最优值 。现在,放松的互补松弛约束验证。当该算法首先探讨了分支 。在这种情况下,由此产生的问题是不可行的,分支是清楚。然后,考虑的分支 探讨了。在这种情况下,最优的解决方案 ,屈服 。继续搜索全局最优 是强加的。通过这样做,同样的解决方案的问题。在这一点上,获得的解决方案是一个候选人的全球最佳半无限问题,因为所有的互补松弛约束。完成搜索,约束条件 被替换的 以及由此产生的问题是解决了。获得的解决方案是 和目标函数的值 。该算法停止和双层的问题的最优解 与 。因此,半无限问题的最优解 y 。
在图2,显示了搜索树的表示。

例5。考虑以下问题: 在哪里 相应的双层的配方 其单级再形成如下: 同样的,在前面的例子中,分支和边界方案探讨了搜索树图中描述3为了实现最优的解决方案。
算法得到的解决方案作为最优组和最优值,显示 和 。结果验证了解决几何。我们有 的解决方案图如图4。contraru,如图5,我们表明, 作为 ,可行集 的最优解从上面的描述问题获得可行的设置是一样的一个算法获得的。

例6。考虑以下问题: 在哪里 双层的配方是 算法表明,这个问题没有可行解(从后退一步去终止一个)。结果是合理的几何因为的交集和是空的。

例7。考虑以下问题: 在哪里 双层的形式是 的解决方案图如图6。相反,在图7,我们表明, 自 ,可行集 。最优的解决方案是 。我们有相同的结果的算法。

示例8。考虑以下问题: 在哪里 相应的双层的配方 解决方案获得的算法 和 。
如果限制 省略的问题吗 ,然后问题是无限的。此外,如果和没有标志的约束,可行集展览一个所谓的凹角角落点在原点(见[2])。

示例9。考虑以下问题: 在哪里 相应的双层的配方 解决方案获得的算法 和 。

示例10。考虑以下问题: 在哪里 相应的双层的配方 解决方案获得的算法 和 。
如果限制 省略的问题吗 ,然后问题是无限的。此外,如果和没有标志的约束,可行集不是关闭(见[2])。
总结了实例和计算结果表1,问题是第一列所示,最佳解决方案是在第二个,数学规划解决问题的数量,直到获得最优解第三列,给出了数学规划解决问题的总数量,保证最优第四列所示,和所需的总CPU时间是在最后一列。所有测试都是使用个人电脑执行有英特尔(R)的核心处理器8 GB的内存,和该算法编码和运行使用FICO XPRESS 8.5商业软件。同时,正如前面提到的在每个例子中,最佳的解决方案从提出每个问题的引用的引用。
显示了算法的有效性,通过求解一组额外的问题出现在[3,21,22,27]。这里,双层的问题被认为是显示发达方法的鲁棒性。算法开始从一个双层的再形成的线性广义半无限规划问题。上面的解释,该算法目的是找到最优的解决方案,但是,必须保证全局最优。因此,需要额外的迭代。然而,解决测试问题所需的时间是很短的。结果展示在表2我们跟随作者的符号。

5。应用程序一个现实的问题

在本节中,一个案例研究在供应链方面,配送中心和制造商,用于展示发达算法的适用性。所考虑的问题是提出了(28和考虑27]。在上层,配送中心整体利润最大化目标,在较低的水平,制造商的目标是最小化成本。

让是上层决策变量,表示产品的数量将在配送中心 同时,让是低级的决策变量和代表客户的需求从配送中心提供 。因此,上层目标函数是由销售获得的好处产品价格减去生产成本 。低级的目标函数是由制造成本从其他制造商和采购成本。强加的约束是这种类型的典型问题;也就是说,有能力在配送中心,客户的需求不能从封闭的配送中心,提供至少必须满足最低需求的客户。

考虑到特定的案例研究,获得的数据被认为和生成的双层的模型如下:

以应用该算法,其单级再形成了应用Kuhn-Tucker条件如下:

获得解决方案是一样的(27,28),也就是说, ,对应的目标函数值为105000。算法解决5数学问题,保证最优解在第五迭代。它需要0.031秒才能达到最优解。提到是很重要的,在27),混合遗传和粒子群优化算法解决了这个问题在8迭代,而6迭代以人群为基础的metaheuristic(需要28]。引用不报告计算时间,但对于算法的类型,这可能是我们的方法是为解决这一现实应用程序更快。

6。结论

在这项研究中,线性广义半无限规划问题的双层的配方是利用提出一种易于实现精确解的算法。方法的核心依赖Kuhn-Tucker最优条件的使用减少双层的配方具有互补约束的非线性规划问题。本研究的主要贡献是满足互补约束的方法和方案。的策略是利用双层规划,但适应解决线性广义半无限规划问题是小说在这个研究领域的贡献。

此外,计算实验进行验证该算法及其有效性。多元线性广义半无限规划问题具有不同特点被认为验证实现算法的鲁棒性。一个有趣的真实应用程序被认为是在数值的经验,这演示了该方法的便利和适用性。

因此,该方法会导致另一种解决特定类型的问题,避免额外的功能调节的包容互补约束,如(8]。然而,在这两种方法,类似的假设在应用之前。

泛化方法的情况下提出了许多半无限约束被认为是在3]。他们的建议以理论的方式描述,但其应用到特定的半无限问题和计算实验是不报道。后者可能是一个具有挑战性的进一步的研究方向。另一个机会是扩展了算法求解其他变体的啜饮。同时,算法的泛化与许多半无限约束也可以视为未来的工作。

数据可用性

的数据支持本研究的发现可以从相应的作者在合理的请求。

的利益冲突

作者宣称没有利益冲突有关的出版。