２０１７年第１期 １８２ 低维线性分式规划的高效全局优化算法 胡勇文１，２陈国华１，２孟凡净１，２ （１．湖北文理学院机械与汽车工程学院，湖北襄阳４４１０５３；２．汽车零部件制造装备数字化 湖北省协同创新中心，湖ｊ匕襄阳４４１０５３） 摘要：针对低维线性分式规划问题，本文提出了一种分支定界的全局优化算法，建立了原问题的等价模型。该模 型由线性目标函数以及一组线性和非线性约束组成，通过将非线性约束进行线性松弛得到原问题的强化线性 松弛模型，与直接去掉等价模型中的非线性约束的线性松弛方法相比，后者能得到更好的界，提高了算法的收 敛速度。数值实验表明，算法的平均（最大，最小）分支数、ＣＰＵ时间以及迭代次数有明显改善。 关键词：低维线性分式规划；非线性约束；线性松弛；分支定界 中图分类号：Ｏ２２１．２ 文献标识码：Ａ 文章编号：１６７１—４７９２（２０１７）１－００１１－０６ Ｅｆｆｉｃｉｅｎｔ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｌｉｎｅａｒ－ｆｒａｃｔｉｏｎａｌ－ｐｒｏｇｒａｍｍｉｎｇ ｗｉｔｈ Ｌｏｗｅｒ Ｄｉｍｅｎｓｉｏｎ Ｈｕ Ｙｏｎｇｗｅｎ ＇。Ｃｈｅｎ Ｇｕｏｈｕａ ＇ Ｍｅｎｇ Ｆａｎｊｉｎｇ ＇ （１．Ｓｃｈｏｏｌ ｏｆＭｅｃｈａｎｉｃａｌ ａｎｄ Ａｕｔｏｍｏｂｉｌｅ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｕｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＡｒｔｓ ａｎｄ Ｓｃｉｅｎｃｅ， Ｈｕｂｅｉ Ｘｉａｎｇｙａｎｇ ４４１０５３：２．Ｃｏｌｌａｂｏｒａｔｉｖｅ Ｉｎｎｏｖａｔｉｏｎ Ｃｅｎｔｒｅ ｏｆＨｕｂｅｉ Ｐｒｏｖｉｎｃｅ ｆｏｒ Ａｕｔｏ Ｐａｒｔｓ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｅｑｕｉｐｍｅｎｔ Ｄｉｇｉｔｉｚａｔｉｏｎ，Ｈｕｂｅｉ Ｘｉａｎｇｙａｎｇ ４４１０５３） Ａｂｓｔｒａｃｔ：Ａ ｎｅｗ ｂｒａｎｃｈ ａｎｄ ｂｏｕｎｄ ａｌｇｏｒｉｔｈｍ ｏｒｆ ｓｏｌｖｉｎｇ Ｌｉｎｅａｒ－Ｆｒａｃｔｉｏｎａｌ—Ｐｒｏｇｒａｍｍｉｎｇ（ＬＦＰ）ｗｉｔｈ ｌｏｗｅｒ ｄｉｍｅｎｓｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ．ＬＦＰ ｉｓ ｅｑｕｉｖａｌｅｎｔｌｙ ｔｒａｎｓｆｏｒｍｅｄ ｉｎｔｏ ａ ｐｒｏｂｌｅｍ ｗｉｔｈ ｌｉｎｅａｒ ｏｂｊｅｃｔｉｖｅ ａｎｄ ａ ｓｅｔ ｏｆ ｌｉｎｅａｒ ａｎｄ ｎｏｎ－ｌｉｎｅａｒ ｃｏｎｓ￣ａｉｎｓ，ａｎｄ ｔｈｅ ｎｏｎｌｉｎｅａｒ ｃｏｎｓｔｒａｉｎｔｓ ａｒｅ ｌｉｎｅａｒｌｙ ｒｅｌａｘｅｄ．Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｍｏｄｅｌ ｔｈａｔ ｄｉｓｃａｒｄｉｎｇ ｎｏｎｌｉｎｅａｒ ｃｏｎ— ｓｔｒａｉｎｔｓ ｆｒｏｍ ｅｑｕｉｖａｌｅｎｔ ｍｏｄｅｌ，ｔｈｅ ｎｅｗ ｍｏｄｅｌ ｉｓ ｇｅｎｅｒａｌｌｙ ｔｉｇｈｔｅｒ ｔｈａｎ ｔｈｅ ｐｒｅｖｉｏｕｓ ｏｎｅ．Ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｔｈｅ ａｌｇｏ－ ｒｉｈｔｍ ｉｓ ｐｒｏｖｅｄ，ａｎｄ ｎｕｍｅｒｉｃａｌ ｅｘｐｅｉｒｍｅｎｔｓ ｉｎｄｉｃａｔｅ ｔｈａｔ ｔｈｅ ａｖｅｒａｇｅ（ｍａｘｉｍａｌ，ｍｉｎｉｍａ１）ｎｕｍｂｅｒ ｏｆ ｔｈｅ ｎｅｗ ａｌｇｏ— ｒｉｔｈｍ ｉｓ ｉｍｐｒｏｖｅｄ ｇｒｅａｔｌｙ ｗｈｅｎ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｏｒｉｇｉｎａｌ ｍｅｔｈｏｄ． Ｋｅｙｗｏｒｄｓ：Ｌｉｎｅａｒ—ｆｒａｃｔｉｏｎａｌ－ｐｒｏｇｒａｍｍｉｎｇ ｗｉｔｈ Ｌｏｗｅｒ Ｄｉｍｅｎｓｉｏｎ；Ｎｏｎｌｉｎｅａｒ Ｃｏｎｓｔｒａｉｎｔｓ；Ｌｉｎｅａｒ Ｒｅｌａｘａｔｉｏｎ；Ｂｒａｎｃｈ ａｎｄＢｏｕｎｄ ０引言 其中，Ｄｉ，ｄｉ∈ ，ｉ＝ｌ，２，…，ｐ；ａｉ，ｂｉ∈Ｒ；Ａ∈Ｒ “，Ｃ ∈ 。 线性分式规划是全局优化中的一类特殊优化问 题，具有如下结构： 此问题受到众多学者及实践者的强烈关注。一 （Ｐ） ｍｉｎ ）： Ｐ面ｎ￣ｒｘ ＋ａｉ 方面，由于问题（Ｐ）是ＮＰ难问题［１】，故在理论及计算 上研究该问题具有重要意义。此外，实际生活中的许 ｓ．ｔ． ∈Ｘ＝｛ ∈ＲｎｌＡｘ Ｃ， ０｝ 多问题，如运输计划［２］、金融投资【３ 、计划翻等问 题或其中子问题，均可归结为问题（Ｐ）。 ★基金项目：国家自然科学基金（编号：５１６０５１５０）；湖北省教育厅 自然科学重点项目（编号：Ｄ２０６２６１１）；机电汽车湖北省优势特色 学科群２０１６年度开放基金项Ｎ（ｆ；￣－：ＸＫＱ２０１６０２１） 一般情况下，问题（Ｐ）不具备基本性质（如凸性、 拟凸性等），因而一般难以寻求其全局最优解。另外， １ １ 求解该问题的主要困难取决于分式数目的大小，且 随着分式数目增加，求解困难也明显增加。目前，求 解问题（Ｐ）的算法中， 用分支定界方法最为流行。 申培萍、赵小科【６ｊ提出了一种求解线性比式和问题 的全局最优解的近似算法，并从理论上给出了算法 复杂度。结果表明，当 定时，提出的算法是完全多 项式时问算法。但当Ｐ增大时，算法需要的迭代次 数呈指数增加。裴永刚等【７Ｊ针对非凸区域上的凸函 数分式规划问题，通过引入变量，将原问题转化为 Ｄ．Ｃ．规划问题，在ｎ＋ｐ维空间中求解一系列的线性 规划问题以求得问题的下界，并利用分支定界方法 不断寻求问题的最优解。任舒萍【８ｊ等利用凹凸性包 络技术将问题（Ｐ）通过求解一系列线性规划问题以 确定问题下界，并在Ｐ维空问中通过分支定界方法 求得原问题的近似最优解。此外，文献【９】通过提出 可加速算法收敛速度的分支定界算法用以求解线性 分式规划问题。然而，有研究表明【１ｏＪ，当在超过ｌ６维 的空问中利用该方法不能得到问题（Ｐ）的最优解。 在实际生活中，有许多问题，如分层制造【ｍ “】 （Ｌａｙｅｒｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ）、摄像机校准【Ｉ２Ｊ（Ｃａｍｅｒａ ｎ Ｒｅｓｅｃｔｉｏｎｉｎｇ）、星覆盖问题ｎ３】（Ｓｔ∑烈 ａｒ Ｃｏｖｅｒ ｐｒｏｂｌｅｍ）、估 算单应矩阵ｌ＇４Ｊ（Ｈｏｍｏｇｒａｐｈ Ｅｓ＋一＋ Ｚ—ｔｉ ｍａｔｉ：，、一ｏｎ）、ｊ角剖分 Ｊｕ ∑ Ｔ．ｎ （Ｔｒｉａｎｇｕｌａｔｉｏｎ Ｐｒｏｂｌｅｍ）等问题或其子问题均可归 ＋ ０ 结为线性分式规划问题。这些问题具有变量少、分 式数目较大等特点。Ｃａｒｓｓｏｎ及Ｓｈｉｌ ５】提出了求解低 维线性分式规划问题的算法，该算法通过引入变量， 将问题（Ｐ）转化为线性的目标函数及具有线性及非 线性的约束。并通过在ｎ维空问中求解一系列线性 规划问题而得到问题（Ｐ）的最优解。然而，文献［１５１ 通过去掉约束中所有的非线性约束而得到线性松弛 模犁，本文将非线性约束进行线性松弛，理论上得到 问题（Ｐ）的强化线性松弛问题，以得到更好的目标 函数的下界，从而减少迭代次数及计算时间。 １等价问题及其线性松弛 为寻求问题（Ｐ）的最优解，先将该问题转化为 其等价的非凸规划问题（ＥＰ），再对问题（ＥＰ）进行线 性松弛。不失一般性，在问题（Ｐ）中假设ｄＴｘ＋ｂｊ＞０， Ｖｘ∈Ｘ，ｉ＝ｌ，２，…，Ｐ。定义Ｂ＝【１，ｕ］，其中ｌ＝【ｌ１，１２，…， ｌｎ］，１．１￣－［Ｕｌ，Ｕ２，…，ｕｎ］，日 ： （１） ｌｌ：＝ｒａｉｎ ｘｊ 一１ ２一 ｓ－ｔ・ ｘ∈Ｘ （２） ｕｊ： ｍａＸ ｘｊ Ｓ。ｔ． ∈Ｘ 定义ａ ｉ：－ｍｉｎ｛ｄＴｉｘ＋ｂｉＩｘ∈ｘ｝，ｐ ｉ：－ｍａｘ｛ｄＴ。ｘ＋ｂｉＩｘ ∈ｘ），ｙｌ：＝ｚ ｘ ：＝＝＝ １面，ｉ＝ｌ，２，…，ｐ。现考虑以 下两个问题（Ｐ。），（ＥＰ）。 ｍｌｎ （Ｐ１） （３） ｓ．ｔ． ｓ．ｔ．ｄ ＋ ＝１ （ＥＰ） 一ＣＺｉ ０， １ １ 一， ，Ｊ １，２，…，Ｐ （４） 矿 ＝ｙ３Ｚｉ， ｚｉ２ Ｙ ＺｉＵ 显然，根据以上定义，Ａｘ＜ｃ，Ｖｘ∈Ｘ，当日．仪当 Ａｙ—ｃｚｓ ０；１＜ｘ≤１３，当 日－仅当ｌｚ—ｙ－＜０及ｕｚ－－ｙ￣ ０。 为寻求问题（Ｐ ）的最优解，问题（ＥＰ）与问题 （Ｐ，）的等价性由以下定理给出： 定理１：问题（ＥＰ）与问题（Ｐ ）等价。 证明：设ｘ 为问题（Ｐ ）的最优解， Ｙｉ ： 著 ， ：。赤，ｉ：ｌ，２，…，ｐ。 此时，（ｙ ｉ，ｚ ｉ）为问题 Ｅ上Ｊ川 ．ａｌｊ １丁Ｈ拌。 ＾Ｊ吐 ，ｊ ＬＹ ｉ，Ｚ ｉ ８１，７Ｊｊ日Ｊ ＥｔＪ ｔｆ＇３取１儿 解，设 （Ｖ． Ｚ’ｉ）为问题（ＥＰ）的可行解，且满足： 喜 ）＜娄 引（０５） 南于（ｎ 喜（）佗＝妻 ＋ ）＝ Ｐ而ｎｆｘｐ ｑ－ａｉ，喜 糍＜渊ｉ ＝１ｄ￣ｘ＊ ＋ ｂｉ。南郝 口，ｐ ｎ［ｘ＊ｎｔ，－ａｉ…似Ｘ，Ｘ＋均为问题 成立因此（ｙ ，导 ’ ｚ ｉ）为问题（ＥＰ）的最优解。同理可以 ，矾首艋明关种≤ １ ／…Ｚ＇一丽ｌ 刀：日儿虬 不 １／ａ ｊ）ｓ ｏ，即ｔｉｊ＝３，ｉ ｓ １ ＋麦勺一 ｌ瓦。同理 ．证明当（ｙ ｉ，Ｚ ）为问题（ＥＰ）的最优解时， ｉ＝荨为 成立。Ｖ‘ ， ， ’∈Ｂ。’ｉ，ｊ ，２，…，ｐ，‘ｙｉ一邶ｉ’‘ 一 问题（Ｐ。）的最优解。定理１的证明过程可看出，问题 （Ｐ ）的最优解可通过求解问题（ＥＰ）的最优解获得。 一 一 ＜一 ＜一 一 ＾但问题（ＥＰ）的约束中存在非线性约束ｙｉｚｊ＝ｙｉｚ ，ｉ， ｊ＝ｘ，２，…，ｐ。显然，若舍弃问题（ＥＰ）约束中的非线性 可证其余有关ｙ＇ｚｊ的线性不等式。 扩 上述引理表明，通过求解以下线性规划问题可 ． 约束，则得到问题（ｐ ）的线性松弛模型。 文献【１５］通过取消问题（ＥＰ）直接去掉该模型中 的非线性约束得到以下线性松弛模型： ｐ ａｒ—ｉ—ｎ∑（ ＋ 麓） （尸２（ｚ， ）） 壶矿一≤ 壶，％Ｓ ０＇， １ Ｉ１Ｉ … （）（（）６ ｚｄ≤暑『． 名‘ Ｊ 本文将非线性约束进一步进行线性松弛，得到 问题（Ｐ，）的线性松弛问题。与问题比较，针对同一可 行域，在理论上，本文能得到比问题（Ｐ ）更优的下 界，因此求解原问题的迭代次数及运行所需时间将 会降低。由于邶ｉｓ ｙｉ＜ｕ／ａ ｉ，ｌ／Ｂ ｉ Ｚｉｓ １／ａ ｉ且 ０，Ｖｉ＝ｌ，２，…，Ｐ，故可构造关于 ，Ｖｉ，ｊ＝ｌ，２，…， Ｐ的线性不等式。现考虑如下两个集合 ，Ｂｆ： Ｂ。：＝｛（【Ｉ ｔｉｊ，Ｙ ， ）ｉＩＩ １＝ 。 ， １ ２ ／岛≤ Ｙ ｕ／１／ａｉａｊ Ｊ，｝ Ｂｒ： （ｔｉｊ，Ｙ。， ） ｆ／ ｙ Ｕ／Ｏｔｉ 根据以上定义，以下关系成立： 弓ｆ理１：Ｖ（ ， ， ），ｉ，ｊ＝ｌ，２，…，Ｐ，关系Ｂ。Ｃ＿Ｂ 成立。 得到问题（Ｐ。）的下界。 ｐ 勿 ｍｉⅡ∑（ ！『ｆ懈） ｓ．ｔ． ＋ ＝１， Ａ矿一％ Ｏ， ｌ，２ ．，ｐ 啦 鹏 １，，１ ＬＲＰ（Ｉ） 盏 一，， 啦 瘩一扩＋ｋ １￣溶ｕ 一 一 ｕ Ｏ， ｌ ｉ 瓦ｌ弓：一囊去 ｊ＝１ ２ Ｐ （７） 本文利用分支定界法通过求解一系列线性规划 问题（７）而得到问题（Ｐ，）的最优解，具体算法描述如 下。 ２算法及算法收敛性 由ａ ，ｐ ，ｙｉ，ｚｉ的定义知，若对超矩形Ｂ。＿【ｌ，ｕ］ 及其子区域Ｂ Ｃ＿Ｂ。进行剖分，则对应的ｙｉ，Ｚｉ范围 也不断缩小。基于此，本文的分支规则是在 中不 断剖分Ｂ＝［１，１１］其子区域Ｂ Ｂ。，通过求解问题 （ＬＥＰ），逐步改进问题（ＥＰ）的上界及下界，直至找到 给定误差范围内亏．的最优解。 在迭代过程中，设Ｂ ｛Ｘ∈ １．ｘｉ＜ｘｉ＜Ｘｉ￣ｉ＝ｌ， ２，…，ｎ｝为包含最优解的超矩形，按照下列二分规 则，Ｂ 将被分为Ｂ强，Ｂ２ｋ＋‘两个子区域： Ｓｔｅｐｌ：定义 ｉｏ∈ａｒｇ ｍａｘ｛ｘｉ一 ｉ）ｆｊ＝Ｉ，２，…，Ｉ１｝。 Ｓｔｅｐ２：定义 。＝ （鲍。＋ 。） Ｓｔｅｐ３：则 Ｂ ＝｛ｘ￣Ｒ＂ｌｘ ｘｉ＜Ｘｉ ｉ≠ｉｏ， ｘｉ Ｖ ｉｏ｝，Ｂ 。＝ ｛ｘ∈Ｒ ｉ≤ｘｉ≤Ｘｉ，ｉ≠１‘０，Ｖ ｘｉ０ｓ Ｘｉ０｝。 １ ３ 彩设问题（ＥＰ）的当前最优解为ｘ ｙ ｚ小ｉ。∈ ａｒｇｍｉｎ｛ｆ（ｘ ）ｌｉｋ＝ｌ，２，…，ｐ｝。若在算法第ｋ次迭代过 程中，在超矩形Ｂｋ中，问题（ＬＥＰ）的最优目标函数 值大于问题（ＥＰ）的当前最优解，则Ｂｋ中不含问题 （ＥＰ）的最优解，因而该区域可从原始区域中去掉。 算法的具体描述如下： ＳｔｅｐＩ：令ｋ＝ｌ，Ｂｋ－＝｛［１ｋ，ｕ 】｝＝｛［１，ｕ］｝，Ｌ—ＯＯ，Ｕ： ＋ｏｏ。 Ｓｔｅｐ２：在超矩形Ｂｊ∈Ｂ 中求解问题ＬＲＰ（Ｐ， ｕｊ）。若问题ＬＲＰ（ｐ，ｕＪ）可行，则求解最优解Ｌｋ及 ｘｉｌ‘＝ｙ ｚＩｋ，令Ｕｋ＝ｍｉｎ｛ｆ（ｘ ），ｉｋ＝ｌ，…，Ｐ｝， ＝Ｌｋ， Ｕ＝Ｕ 。若问题ＬＲＰ（ｐ， 不可行，算法终止。 Ｓｔｅｐ３：设定误差的值乏。 Ｓｔｅｐ４：当Ｕ－－￣ ＞毛时，转Ｓｔｅｐ５；否则算法结 束，找到误差范嗣内的最优解。 Ｓｔｅｐ５：在超矩形 ∈Ｂ 中求解问题ＬＲＰ（１ｉ， ｕｊ），去掉问题ＬＲＰ（ ， ）的目标函数值大于Ｕｋ对应 的超矩形Ｂｊ。 Ｓｔｅｐ６：选取超矩形Ｂｊ０，ｊ。∈｛ｊ。｛ ∈Ｂｋ，Ｕｏ＝， ｝。 Ｓｔｅｐ７：将超矩形 。按照前述对分剖分规则剖 分为两个超矩形Ｂ ，Ｂ２㈨日．Ｂｋ－＝（Ｂｋ￣｛Ｂｉ。｝）ｕ｛Ｂ弧｝ Ｕ｛Ｂ ｝。 Ｓｔｅｐ８：求解问题ＬＲＰ（ｐ，ｕＪ），ｊ＝２ｋ，２ｋ＋ｌ。若问题 ＬＲＰ（１ｊ，ｕ０不可行，则去掉区域ＢＪ；否则计算Ｌｋ，ｕ ， Ｌ２ｋ十 ，ｕ 及ｘ ｋ／ｚｉｋ，ｋ＝ａｒｇｍｉｎ｛ｆｘ ），ｉｋ＝ｌ，…，Ｐ｝。 Ｓｔｅｐ９：若 ≤ｒａｉｎ｛ ，Ｌ２ｋ｝ ｝，令 ＝ｒａｉｎ｛ ， Ｌ ｎ ｝。若Ｕ＞ｍｉｎ｛Ｌ ，Ｌ ｝，令Ｕ＝｛Ｌｋ，Ｌ ｝。 Ｓｔｅｐｌ０：令ｋ＝ｋ＋ｌ，转Ｓｔｅｐ４。 下面定理给出算法的全局收敛性： 定理２：上述算法能在有限迭代次数内找到亏． 近似最优解。 证明：算法收敛到全局问题的最优解的充要条 件是界运算一致及界选取有改善【ｌ６１。界运算一致即 每一迭代过程中可进一步剖分任一最优解可能存在 区域，日 任一可无限被剖分满芷： ｌ ｍ＾ （ 一￡ ）：０ （、 ８） —卜 ｏｏ 其中，ｕ，Ｃ 分别为求解问题的上界及第ｋ次迭 代时的最优下界。 Ｆ｝１于本算法采用的是具有收敛的对分剖分规 一１ ４一 则，因此式（８）成立，亦即算法的界运算具有一致性。 界选取有改善是指在有限次剖分后，选择出至 少一个下界在其上达到的超矩形，并将该超矩形作 为下一迭代中进一步剖分的超矩形。根据以上算法 可知，下一迭代中要剖分的矩形恰好满足问题在该 超矩形上的最优目标函数值为当前问题的最优下 界，因此，本文的算法的界选取是有改善的。 综上，本文算法满足界运算一致，并日＿界选取有 改善，因此本算法是全局收敛的。 ３数值实验 定义超矩形的Ｏｋ，ｕｌ（】‘‘长度”６（ ，ｕｌ（］）：－－ｍａｘ｛ｕ ｉ～ １ｋｉｌｉ＝ｌ，２，…，ｎ｝，其反应了变量在不同维度可变化的 区域的最大范围。数值实验中，设定ｎ＝ｌ，乏＝０．０５， １１ ，ｄ。均是随机产生的并且服从同一分布，日－一５－＜１１ ｄｉｊ＜－５，ｉ＝ｌ，２，…，ｐ；ｊ＝ｌ，２，３。巩（ｉ＝ｌ，２，…，Ｐ）为 【０，５０］之间随机产生的实数，ｂｉ＝５０，ｉ＝ｌ，２，…，Ｐ。数 值实验通过在不同“长度”的超矩形中求解问题（６） 及问题（７），比较其所得到的下界。此外，在同一可行 域中，通过求解问题（６）及问题（７）求得全局王．近 似最优解，比较两问题各自所需的平均（最小，最大） 迭代次数，平均（最小，最大）ＣＰＵ时问。平均（最小， 最大）分支次数。本文的算法采用ＭＡＴＬＡＢ２０ｌ２ｂ 编程，所有算法均在ｉＭａｃ ４ ＣＰＵ，３．２ＧＨｚ，８ＧＢ内存 计算机上运行。 例１：（Ｆａｌｌ等 ｊ） －． Ｘ１十２ ２＋２ ４ｘｌ一３ｘ２＋４ 删ｎ －４－—－２ｘｌ＋—ｘ２＋３ ｓ．ｔ・Ｘｌ＋Ｘ２ １．５ （９） １ ２ ０≤ｚｌ １，０ Ｘ２ １ 以下是利用两种不同模型（模 （Ｐ ）及模刭 （ＬＲＰ））求解例ｌ的数值实验结果。 图一用不同模型求解例１时的迭代次数与上 （下）界的关系，§＝Ｏ．Ｏ５ 图一表明：利用模型（Ｌ１ ）求解例１所需的迭 小，最大）迭代次数，平均（最小，最大）ｃｅｕ时间，平 均（最小，最大）分支次数，其具体结果分别如图四、 代次数（５次）明显小于模型（Ｐ２）所需迭代次数（６５ 次）。为探究两种模型在不同“长度”的超矩形中求 解同一问题最优目标函数值的关系，针对ｐ＝５，ｎ＝３ 的分式规划问题，所得结果如图二所示。 图二当ｐ＝５。ｎ＝３时。模型ＬＲＰ及模型Ｐ２在两种不同 “长度”的超矩形中的目标值 图二表明：（１）不同“长度”的超矩形中，模型 （ＬＲＰ）所得的目标函数值均大于模型（Ｐ ）的目标函 数值，即针对同一分数规划问题，利用模型（ＬＲＰ）所 得该问题的下界优于模型（Ｐ：）所求得的下界；（２）超 矩形的“长度”越大，两种模型所求得问题的下界越 劣；（３）超矩形的“长度”越大，模型（ＬＲＰ）所得问题 的下界与模型（Ｐ ）所求得的下界的差越大。 图三不同Ｐ下，模型模型ＬＲＰ及模型Ｐ 的平均（最 大。最小）ＣＰＵ时间 图三给出在不同分数数目的条件下，针对同一 分数数目，利用两种不同模型求解２０个随机产生 的分式规划问题，比较两问题各自所需的平均（最 图五所示。 图四不同Ｐ下，模型ＬＲＰ及模型Ｐ 的平均（最大， 最小）迭代次数 图同Ｐ下，模型ＬＲＰ及模型Ｐ 的平均（最大， 最小）分支数 图五表明：与模型（Ｐ２）相比，利用模型（ｕ ）求 解问题（２．３）时，迭代过程中的平均分支数只有前者 的０．３４％。通常情况下，分支数越少，所需的ＣＰＵ时 问越短，且图三也印证该结论（后者平均ＣＰＵ时间 只有前者的１２％。图三、图五均表明：本文算法在平 均（最大，最小）ＣＰＵ时间、迭代次数及分支数目上 都较文献［１５】中的算法有巨大改进。 ４结束语 本文通过引入变量，将分式规划问题等价地转 换为目标函数为线性，约束为一组线性及非线性不 等式（等式）。通过将约束中的非线性不等式进行线 １ ５ 性松弛，得到原问题的强化松弛模型，同时给出了算 法的收敛性。通过不断剖分原始空间（ｎ维），并改善 和问题的全局优化方法［Ｊ】．应用数学，２０１０，２３（０３）：５８２—５８８． 【８】任舒萍，高岳林，玛小华．线性分式和规划问题的伞局 优化算法【Ｊ】．内蒙古师范大学学报（自然科学汉文版），２０１３， （０３）：２５９—２６３． 原问题的上界及下屑，直至找到原问题的Ｅ．近似 最优解。数值实验表明，与文献［１５１中的算法相比， 本文算法的平均分支数目只有前者的０．３４％，平均 ＣＰＵ时问只有前者的１２％。 【９】陈艳霞，任舒萍．一类线性分式规划问题的分支定界 算法【Ｊ】．科技广场，２０１３，（０１）：２１—２５． ［１ ０］Ｋｕｎｏ Ｔ．Ａ ｂｒａｎｃｈ—ａｎｄ・ｂｏｕｎｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍａｘｉｍｉｚｉｎｇ ｔｈｅ ｓｕｍ ｏｆ ｓｅｖｅｒａｌ ｌｉｎｅａｒ ｒａｔｉｏｓ【Ｊ】．Ｊｏｕｒｎａｌ ｏｆ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａ— ｔｉｏｎ，２００２，２２（１—４）：１５５．１７４． 本文数值实验中，Ｆ｝１于计算机内存原因，能测试 的最大的分式数目为８０（即ｐ＝８０），但模型（ＬＲＰ）中 变量数为ｎｐ ＋ｐｎ＋ｐ，因此，当分式规划问题规模变 【１ １】Ｍａｊｈｉ，Ｊ．ｅｔ ａｌ，Ｍｉｎｉｍｉｚｉｎｇ ｓｕｐｐｏｒｔ ｓｔｒｕｃｔｕｒｅｓ ａｎｄ 大时（ｐ增大），变量数也显著增大，求解时问也会增 加。囚而探究缩减约束矩阵规模技术以求解更大规 模分式规划问题并进行数值实验值得进一步研究。 参考文献 ［１】Ｍａｔｓｕｉ，Ｔ—ＮＰ—ｈａｒｄｎｅｓｓ ｏｆ ｌｉｎｅａｒ ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｐｒｏ— ｇｒａｍｍｉｎｇ ａｎｄ ｒｅｌａｔｅｄ ｐｒｏｂｌｅｍｓ【Ｊ１．Ｊｏｕｒｎａｌ ｏｆ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａ— ｔｉｏｎ，ｌ９９６，９（０２）：ｌ】３ １１９． 【２］Ｚｈａｎｇ Ｄ，Ａｄｅｌｍａｎ Ｄ．Ａｎ ａｐｐｒｏｘｉｍａｔｅ ｄｙｎａｍｉｃ ｐｒｏ— ｇｒａｍｍｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｎｅｔｗｏｒｋ ｒｅｖｅｎｕｅ ｍａｎａｇｅｍｅｎｔ ｗｉｔｈ ＣＵＳ ｔｏｍｅｒｃｈｏｉｃｅ【ＪＪ．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｓｃｉｅｎｃｅ，２００９，４３（０３）：３８１—３９４． 【３］Ｋｏｎｎｏ Ｈ，Ｉｎｏｒｉ Ｍ．Ｂｏｎｄ ｐｏｒｔｆｏｌｉｏ ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ ｂｉｌｉｎ— ｅａｒ ｆｒａｃｔｉｏｎａｌ ｐｒｏｇｒａｍｍｉｎｇ【Ｊ】．Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ Ｏｐｅｒａｔｉｏｎｓ Ｒｅ— ｓｅａｒｃｈ Ｓｏｃｉｅｔｙ ｏｆＪａｐａｎ，１９８９，３２（０２）：１４３—１５８． 【４］Ｃｈｏｉ Ｊ Ｃ，Ｂｒｉｃｋｅｒ Ｄ Ｌ．Ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ａ ｇｅｏｍｅｔｒｉｃ ｐｒｏ— ｇｒａｍｍｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｍａｃｈｉｎｉｎｇ ｅｃｏｎｏｍｉｃｓ ｍｏｄｅｌｓ【Ｊ】．Ｃｏｍｐｕｔｅｒｓ＆ｏｐｅｒａｔｉｏｎｓ ｒｅｓｅａｒｃｈ，ｌ ９９６，２３（１ ０）： ９５７—９６１． 【５］Ｃｏｌａｎｔｏｎｉ Ｃ Ｓ，Ｍａｎｅｓ Ｒ Ｐ，Ｗｈｉｎｓｔｏｎ Ａ．Ｐｒｏｇｒａｍｍｉｎｇ， ｐｒｏｆｉｔ ｒａｔｅｓ ａｎｄ ｐｒｉｃｉｎｇ ｄｅｃｉｓｉｏｎｓ［Ｊ】．Ｔｈｅ Ａｃｃｏｕｎｔｉｎｇ Ｒｅｖｉｅｗ； １９６９，４４（０３）：４６７—４８１． 【６］申培萍，赵小科．线性分式规划问题的多项式时『甘】近 似算法［ＪＪ．应用数学，２０１３，２６（０２）：３５５ ３５９． 【７】裴永刚，顾敏娜，申培萍．求解非凸区域卜凸函数比式 １ ６一 ｔｒａｐｐｅｄ ａｒｅａ ｉｎ ｗｔｏ—ｄｉｍｅｎｓｉｏｎａｌ ｌａｙｅｒｅｄ ｍａｎｕｆａｃｔｕｒｉｎｇ［Ｊ［．Ｃｏｍ— ｐｕｔａｔｉｏｎａｌ Ｇｅｏｍｅｔｒｙ，ｌ９９９，２（０３）：２４１—２６７． 【ｌ ２］Ｋｉｍ，Ｊ．－Ｓ．ａｎｄ Ｋ．一Ｓ．Ｈｏｎｇ．Ａ ｒｅｃｕｒｓｉｖｅ ｃａｍｅｒａ ｒｅｓｅｃ— ｔｉｏｎｉｎｇ ｔｅｃｈｎｉｑｕｅ ｆｏｒ ｏｆｆ－ｌｉｎｅ ｖｉｄｅｏ—ｂａｓｅｄ ａｕｇｍｅｎｔｅｄ ｒｅａｌｉｔｙ…． Ｐａｔｔｅｍ ｒｅｃｏｇｎｉｔｉｏｎ ｌｅｔｔｅｒｓ，２００７，２８（０７）８４２－８５３ 【１ ３］Ｄａｎｉｅｌｓ Ｋ．Ｔｈｅ ｒｅｓｔｒｉｃｔ／ｅｖａｌｕａｔｅ／ｓｕｂｄｉｖｉｄｅ ｐａｒａｄｉｇｍ ｏｆｒ ｔｒａｎｓｌａｔｉｏｎａｌ ｃｏｎｔａｉｎｍｅｎｔ【Ｃ１．Ｆｉｆｔｈ ＭＳＩ Ｓｔｏｎｙ Ｂｒｏｏｋ Ｗｏｒｋｓｈｏｐ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｇｅｏｍｅｔｙｒ．１ ９９５． ［１ ４］Ｄｕｂｒｏｆｓｋｙ Ｅ．Ｈｏｌｏｇｒａｐｈｙ ｅｓｔｉｍａｔｉｏｎ［Ｄ［．Ｖａｎｃｏｕｖｅｒ：Ｕ— ｎｉｖｅｒｓｉｔｙ ｏｆ Ｂｒｉｔｉｓｈ Ｃｏｌｕｍｂｉａ，２００９． ［１５［Ｃａｒｌｓｓｏｎ Ｊ，Ｇ，Ｓｈｉ Ｊ．Ａ ｌｉｎｅａｒ ｒｅｌａｘａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｔｈｅ ｓｕｍ－ｏｆ－ｌｉｎｅａｒ－ｒａｔｉｏｓ ｐｒｏｂｌｅｍ ｗｉｔｈ ｌｏｗｅｒ ｄｉｍｅｎｓｉｏｎ ［Ｊ】．Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ Ｌｅｔｔｅｒｓ，２０１３，４ｌ（０４）：３８１—３８９． 【１ ６］Ｈｏｒｓｔ Ｒ．，Ｔｕｙ Ｈ．Ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ：Ｄｅｔｅｒｍｉｎｉｓｔｉｃ印一 ｐｒｏａｅｈｅｓ［Ｍ］．Ｓｐｒｉｎｇｅｒ Ｓｃｉｅｎｃｅ＆Ｂｕｓｉｎｅｓｓ Ｍｅｄｉａ．２０１ ３． ［１７］Ｆａｌｋ Ｊ Ｅ，Ｐａｌｏｃｓａｙ Ｓ Ｗ．Ｉｍａｇｅ ｓｐａｃｅ ａｎａｌｙｓｉｓ ｏｆｇｅｎｅｒ— ａｌｉｚｅｄ ｆｒａｃｔｉｏｎａｌ ｐｒｏｇｒａｍｓ［ＪＪ．Ｊｏｕｒｎａｌ ｏｆ Ｇｌｏｂａｌ Ｏｐｔｉｍｉｚａｔｉｏｎ， １９９４，４（０１）：６３ ８８． 作者简介 胡勇文（１９８４～），男，博上，丰要研究方向：Ｉ 业１ 程、系 统优化理论、算法及其应用； 陈闽华（１９７６～），男，博ｌ上，丰要研究疗向：ｆ：业ｌ 程、系 统呵靠性、先进制造技术（通讯作者）。
