一类特殊二次分配问题的线性化求解新方法

格式：pdf
大小：580.99 KB
文档页数：9

下载文档原格式

导数中双变量问题的四种策略

导数中双变量问题的四种策略双变量问题的几种处理策略策略一：合并思想已知函数$f(x)=\ln x$的图像上任意不同的两点的中点为$A(x_1,y_1)$。

$B(x_2,y_2)$，线段$AB$的中点为$C(x,y)$，记直线$AB$的斜率为$k$，试证明：$k>f'(x)$。

解析：因为$f(x)=\ln x$，所以$f'(x)=\frac{1}{x}$。

又因为k=\frac{f(x_2)-f(x_1)}{x_2-x_1}=\frac{\ln x_2-\lnx_1}{x_2-x_1}=\frac{\ln\frac{x_2}{x_1}}{x_2-x_1}$$不妨设$x_2>x_1$，要比较$k$与$f(x)$的大小，即比较frac{\ln\frac{x_2}{x_1}}{x_2-x_1}\text{和}\frac{1}{x_1}$$的大小，即比较ln\left(\frac{x_2}{x_1}\right)^{\frac{1}{x_2-x_1}}\text{和}e^{\frac{1}{x_2-x_1}}$$的大小。

又因为$x_2>x_1$，所以frac{x_2-x_1}{x_2+1}<\ln\left(\frac{x_2}{x_1}\right)^{\frac{1}{x_2-x_1}}<\frac{x_2-x_1}{x_1}$$因此frac{x_2-x_1}{x_2+1}<k<\frac{x_2-x_1}{x_1}$$又因为$x_2>x_1$，所以$\frac{x_2-x_1}{x_2+1}>\frac{1}{2}$，因此$k>f'(x)$。

策略二：分离思想问题2：若$g(x)=\ln x+\frac{1}{x}$，求$a$的取值范围，使得对任意的$x_1,x_2\in(1,2)$，都有$g(x_2)-g(x_1)<-1$。

关于数学建模方面的知识

关于数学建模⽅⾯的知识关于数学建模⽅⾯的知识⼀、数学模型的定义现在数学模型还没有⼀个统⼀的准确的定义，因为站在不同的⾓度可以有不同的定义.不过我们可以给出如下定义：“数学模型是关于部分现实世界和为⼀种特殊⽬的⽽作的⼀个抽象的、简化的结构.”具体来说，数学模型就是为了某种⽬的，⽤字母、数学及其它数学符号建⽴起来的等式或不等式以及图表、图象、框图等描述客观事物的特征及其内在联系的数学结构表达式.⼀般来说数学建模过程可⽤如下框图来表明：数学是在实际应⽤的需求中产⽣的，要解决实际问题就必需建⽴数学模型，从此意义上讲数学建模和数学⼀样有古⽼历史.例如，欧⼏⾥德⼏何就是⼀个古⽼的数学模型，⽜顿万有引⼒定律也是数学建模的⼀个光辉典范.今天，数学以空前的⼴度和深度向其它科学技术领域渗透，过去很少应⽤数学的领域现在迅速⾛向定量化，数量化，需建⽴⼤量的数学模型.特别是新技术、新⼯艺蓬勃兴起，计算机的普及和⼴泛应⽤，数学在许多⾼新技术上起着⼗分关键的作⽤.因此数学建模被时代赋予更为重要的意义.⼆、建⽴数学模型的⽅法和步骤1. 模型准备要了解问题的实际背景，明确建模⽬的，搜集必需的各种信息，尽量弄清对象的特征.2. 模型假设根据对象的特征和建模⽬的，对问题进⾏必要的、合理的简化，⽤精确的语⾔作出假设，是建模⾄关重要的⼀步.如果对问题的所有因素⼀概考虑，⽆疑是⼀种有勇⽓但⽅法⽋佳的⾏为，所以⾼超的建模者能充分发挥想象⼒、洞察⼒和判断⼒，善于辨别主次，⽽且为了使处理⽅法简单，应尽量使问题线性化、均匀化.3. 模型构成根据所作的假设分析对象的因果关系，利⽤对象的内在规律和适当的数学⼯具，构造各个量间的等式关系或其它数学结构.这时，我们便会进⼊⼀个⼴阔的应⽤数学天地，这⾥在⾼数、概率⽼⼈的膝下，有许多可爱的孩⼦们，他们是图论、排队论、线性规划、对策论等许多许多，真是泱泱⼤国，别有洞天.不过我们应当牢记，建⽴数学模型是为了让更多的⼈明了并能加以应⽤，因此⼯具愈简单愈有价值.4. 模型求解可以采⽤解⽅程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学⽅法，特别是计算机技术.⼀道实际问题的解决往往需要纷繁的计算，许多时候还得将系统运⾏情况⽤计算机模拟出来，因此编程和熟悉数学软件包能⼒便举⾜轻重.5. 模型分析对模型解答进⾏数学上的分析. “横看成岭侧成峰，远近⾼低各不同”，能否对模型结果作出细致精当的分析，决定了你的模型能否达到更⾼的档次.还要记住，不论那种情况都需进⾏误差分析，数据稳定性分析.三、数模竞赛出题的指导思想传统的数学竞赛⼀般偏重理论知识，它要考查的内容单⼀，数据简单明确，不允许⽤计算器完成.对此⽽⾔，数模竞赛题是⼀个“课题”，⼤部分都源于⽣产实际或者科学研究的过程中，它是⼀个综合性的问题，数据庞⼤，需要⽤计算机来完成.其答案往往不是唯⼀的（数学模型是实际的模拟，是实际问题的近似表达，它的完成是在某种合理的假设下，因此其只能是较优的，不唯⼀的），呈报的成果是⼀编“论⽂” .由此可见“数模竞赛”偏重于应⽤，它是以数学知识为引导计算机运⽤能⼒及⽂章的写作能⼒为辅的综合能⼒的竞赛.四、竞赛中的常见题型赛题题型结构形式有三个基本组成部分：1. 实际问题背景涉及⾯宽——有社会，经济，管理，⽣活，环境，⾃然现象，⼯程技术，现代科学中出现的新问题等.⼀般都有⼀个⽐较确切的现实问题. 若⼲假设条件有如下⼏种情况：1）只有过程、规则等定性假设，⽆具体定量数据；2）给出若⼲实测或统计数据；3）给出若⼲参数或图形；4）蕴涵着某些机动、可发挥的补充假设条件，或参赛者可以根据⾃⼰收集或模拟产⽣数据.要求回答的问题往往有⼏个问题，⽽且⼀般不是唯⼀答案。

一类特殊二次分配问题的线性化求解新方法

张惠珍，，十魏欣马良
摘要许多抽象于实际的二次分配问题，其流矩阵与距离矩阵中有很多零元素，求解该类二次分配问题时，可通过先行利用零元素的信息减小问题规模，缩短计算时间．以二次分配问题的线性化模型为基础，提出了一种求解流矩阵与距离矩阵中同时存在大量零元素的二次分配问题新方法，不仅从理论上证明了方法的可行性，而且从实验的角度说明了该方法比以
ｌｉｎｅａｒｉｚａｔｉｏｎｏｆｔｈｅＱＡＰ，ｗｅｐｒｏｐｏｓｅｄａｎｅｗｓｏｌｕｔｉｏｎｍｅｔｈｏｄｆｏｒｔｈｅＱＡＰｗｉｔｈｍａｎｙ
ｋｉｎｄｏｆｑｕａｄｒａｔｉｃａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ
ＺＨＡＮＧＨｕｉｚｈｅｎｌ，２，十ＷＥＩＸｉｎＭＡＬｉａｎｇ
ＡｂｓｔｒａｃｔＵｓｕａｌｌｙ．ｔｈｅｒｅａｒｅｍａｎｙｚｅｒｏｅｌｅｍｅｎｔｓｉｎｔｈｅｆｌｏｗｍａｔｒｉｘａｎｄｄｉｓｔａｎｃｅ
ｚｅｒｏｅｌｅｍｅｎｔｓｉｎｂｏｔｈｌｆｏｗｍａｔｒｉｘａｎｄｄｉｓｔａｎｃｅｍａｔｒｉｘｉｎｔｈｉｓｐａｐｅｒ．Ｍｏｒｅｏｖｅｒ．ｔｈｅｆｅｓｉａ —
ｃａｌｐｒｏｂｌｅｍｓ，ａｎｄｔｈｅｃｏｍｐｕｔａｔｉｏｎｔｉｍｅｏｆｓｏｌｖｉｎｇｔｈｉｓｋｉｎｄｏｆＱＡＰｃａｎｂｅｄｒａｍａｔｉｃａｌｌｙ

求一类常系数线性常微分方程特解的有限递推法

求一类常系数线性常微分方程特解的有限递推法
有限递推法是求解一类常系数线性常微分方程特解的一种有效技术。

这种方法可以将复杂的常微分方程中的不可解的问题分解成一系列的有限次问题，从而解决复杂的特解问题，是有着重要意义的一个算法。

有限递推法是从不断更新参数值出发，从给定的解析解开始，按照一定的规律不断求解后续解，直至求得最后一个解为止。

实现这种方法的具体步骤是：首先，将原问题看成是参数的一个连续变量；其次，确定当参数的值改变时，微分方程的解也跟着改变的函数；最后，构造一种渐近格式，以此来求解微分方程的解。

有限递推法得到的解的准确性跟参数的选择密切相关，而参数的选择则是通过识别三元组 (x_i, y_(i-1), y_i) 来得到，这种三元组分别代表参数改变之前与之后的数值和解。

这样，可以通过求解三元组不断重复出微分方程的解。

有限递推法是解决一类常系数线性常微分方程特解的有效技术，有限递推法可以将复杂的常微分方程中的一些难以解决或不可解的问题分解成一系列的有限次问题，这样就可以解决复杂的特解问题。

由于其简洁、实用的特点，有限递推法被广泛地应用到科学研究和工程实际中去。

二阶线性偏微分方程的解法和特解

二阶线性偏微分方程的解法和特解在数学领域中，二阶线性偏微分方程是一种重要的方程类型。

它在物理学、工程学以及其他领域的建模和问题求解中具有广泛的应用。

解决这类方程的问题既有理论上的方法，也有实用的数值解法。

本文将介绍二阶线性偏微分方程的求解方法，包括一般解法和特解法。

一、一般解法对于形如：\[a(x, y) \frac{{\partial^2 u}}{{\partial x^2}} + b(x, y) \frac{{\partial^2 u}}{{\partial x \partial y}} + c(x, y) \frac{{\partial^2 u}}{{\partial y^2}} + d(x, y) \frac{{\partial u}}{{\partial x}} + e(x, y) \frac{{\partial u}}{{\partial y}} + f(x, y) u = g(x, y)\]的二阶线性偏微分方程，其中$a(x, y), b(x, y), c(x, y), d(x, y), e(x, y), f(x, y), g(x, y)$是已知函数，我们希望求解未知函数$u(x, y)$满足该方程。

首先，我们可以采用变量分离法将方程化简。

令$u(x, y) = X(x)Y(y)$，代入原方程，可以得到两个方程：\[ a(x) \frac{{X''(x)}}{{X(x)}} + d(x) \frac{{X'(x)}}{{X(x)}} + f(x) = -\lambda \]\[ c(y) \frac{{Y''(y)}}{{Y(y)}} + e(y) \frac{{Y'(y)}}{{Y(y)}} +\lambda = -g(x, y) \]其中$\lambda$是常数。

我们先考虑第一个方程，它可以化为一个常系数齐次线性微分方程：\[ a(x) X''(x) + d(x) X'(x) + \left(f(x) + \lambda\right) X(x) = 0 \]接下来根据常系数线性微分方程的解法，可以求得$X(x)$的解。

代数Riccati方程数值解的一种牛顿迭代法

Байду номын сангаас
ＡｗｔｎｉｅａｉｎｅｈｏｏｕｅｉａｏｕｔｏｏＮｅｏｔｒｔｏｍｔｄｆｒｎｍｒｃｌｓｌｉｎｆａｇｂｒｉｃａｉｅａｉｎｓｌｅａｃＲｉｃｔｑｕｔｏ
ＺＯＵ — ｐｎＨＬｉｉｇ，ＬＮＩＹｉ— ｑｎｉ
ｉｅａｉｔｄｆｒｑａａｉｑｕｔｏｓａａａｔｒｆｅｔｒａｉｇｄｉｅｔｏｓｉｌｃｔｍｅｈｏａｅｃｍｂｉｄ，ａｄａｔｒｔｏｎｍｅｈｏｏｕｄｒｔｃｅａｉｎｎｄｐｒｍｅｅｒｅａｅｎｔｎｒｃｉｎｍｐｉｉｔｄｒｏｌｎｅｎ
Ｋｅｏｄ：ｇｂａｃＲｃａｑａｏ；ｅｔｎｉｒｔｎＬａｕｏｑａｏ；ｌｒａｎｉｃｏｐｉｔＡＩｙｗｒｓａｅｒｉｆｅｕｔｎＮｗｏｅｉ；ｙｐｎｖｅｕｔｎＡｔｎｔｇＤｒｔｎＩｌｉＤ）ｌｉｃｉｉｔａｏｉｅｉｅｉｍｃ（
周立平，依勤林
（湖南科技学院数学与计算科学系，国永州中４５０）２１０
摘要：数Ｒｃａ方程在优化控制理论中具有十分重要的作用．结合了二次方程的牛顿迭代法与Ｌａ代ｉｔｃｉｙ—
ｎｗｔｏｓｐｏｏｅｏｕｒａｏｕｉｎｏｇｂａｃＲｉｃｔｅｕｔｎ．Ｔｅｅｃｎｅｇｎｅｏｉｔｏｓｅｍｅｈｄｉｒｐｓｄｆｒｎｍｅｉｌｓｌｔｆａｅｒｉｃｏｌｃａｉｑａｉｓｈｎｔｏｖｒｅｃｆｓｍｅｈｄｉｏｈｈｔｐｏｅｎｅｎｍｅｉａｘｅｍｅｔｈｓｂｅｏｅｒｖｄａｄｔｕｒｌｅｐｒｎａｅｎｄｎ．ｈｃｉ

解读支持向量机中的二次规划问题与求解方法

解读支持向量机中的二次规划问题与求解方法支持向量机（Support Vector Machine，简称SVM）是一种常用的机器学习算法，广泛应用于分类和回归问题中。

在SVM的训练过程中，二次规划问题是关键步骤之一，它的解决方法对于SVM的性能和效率具有重要影响。

本文将解读支持向量机中的二次规划问题与求解方法。

一、SVM的基本原理SVM的目标是找到一个超平面，将不同类别的样本分开。

超平面的选择是基于最大间隔原则，即使得样本点到超平面的距离最大化。

为了实现这一目标，SVM将问题转化为一个二次规划问题。

二、二次规划问题的定义给定一组线性约束条件和一个二次目标函数，二次规划问题的目标是找到一组变量的取值，使得目标函数最小化或最大化，同时满足线性约束条件。

在SVM中，二次规划问题的目标是最小化一个二次函数，同时满足一组线性不等式约束。

三、二次规划问题的形式在SVM中，二次规划问题的形式如下：minimize 1/2 * x^T * Q * x + p^T * xsubject to G * x <= hA * x = b其中，x是待求解的变量，Q是一个正定矩阵，p是一个向量，G是一个矩阵，h是一个向量，A是一个矩阵，b是一个向量。

四、求解二次规划问题的方法针对SVM中的二次规划问题，有多种求解方法。

常用的方法包括序列最小最优化（Sequential Minimal Optimization，简称SMO）、内点法等。

1. 序列最小最优化（SMO）SMO是一种迭代的优化算法，通过每次选择两个变量进行优化，并固定其他变量，来求解二次规划问题。

SMO算法的核心思想是将原问题分解为一系列子问题，并通过求解子问题的最优解来逐步逼近原问题的最优解。

SMO算法具有较好的收敛性和高效性，因此在SVM中得到了广泛应用。

2. 内点法内点法是一种基于迭代的优化算法，通过在可行域内搜索最优解来求解二次规划问题。

内点法的核心思想是通过引入松弛变量，将不等式约束转化为等式约束，从而将原问题转化为一个无约束的优化问题。

二次指派问题的理论与算法

二次指派问题的理论与算法二次指派问题的理论与算法一、什么是二次指派问题二次指派问题是在计算机最优化理论中常见的一个问题。

它的基本结构由资源的使用者、被指派的资源以及求解的目标组成。

它的主要任务是尽可能将资源高效地指派给不同的使用者，以达到令行知名的目标。

二次指派问题已被用于机器人任务指派，交通路线指派，被指派任务的决策，人工智能规划，医疗工作调度系统以及众多其他等实际应用。

二、二次指派问题的理论二次指派问题具有四个重要的理论框架：最优性条件、正交性原理、资源分配一致性以及决策规划的综合理论。

1、最优性条件：指在给定的实力限制下，总是能找到一个最优的解决方案。

2、正交性原理：指给定资源规模、使用者能力以及求解目标之后，需要找到每一个使用者和资源之间的唯一正交解，以达到最优化效果。

3、资源分配一致性：指在使用者之间的资源分配是一致的，也就是说资源的分配要保持一致。

4、决策规划的综合理论：指要根据不同的实力限制以及指派的资源，采用决策规划的综合理论来进行资源指派，并且获得最佳的分配结果。

三、二次指派问题的算法对于二次指派问题，一般有四种不同的算法进行解决：单层搜索、直觉式搜索、混合算法以及哈密顿算法。

1、单层搜索：指以不断地遍历节点/路径为基础，深度优先搜索或广度优先搜索等手段，最终找到最优解。

2、直觉式搜索：采用极大量的迭代来收敛到最优解，是一种速度较快的搜索算法。

3、混合算法：将单层搜索和总结式搜索融合在一起，形成一种综合性的搜索技术，使搜索效率较高。

4、哈密顿算法：是一种图形搜索的算法，它通过图搜索的思想，搜索出一条遍历所有点的最佳路径，来获取最优解。

四、总结二次指派问题在最优化理论中被广泛应用，它包括四个重要的理论框架：最优性条件、正交性原理、资源分配一致性以及决策规划的综合理论；而其解决的算法也常用单层搜索、直觉式搜索、混合算法以及哈密顿算法等。

未来在二次指派问题中，仍需不断追求更高性能、更有效率和更全面性的算法方法，使指派任务更加高效。

《数据、模型与决策》第2节：线性规划与图解法

第2章线性规划：建立模型与图解法（Mathematica & QM 授课）第2章线性规划：建立模型与图解法（Mathematica & QM 授课）2.1线性规划的历史2.2 线性规划模型2.2.1 基本概念2.2.2 模型假设1.比例假设2.非负假设3.确定性假设2.2.3 线性规划的标准形2.3 非线性规划线性化的转换技巧2.3.1 目标函数最大化2.3.2 消除不等式约束2.3.3 消除自由变量2.3.4 消除绝对值符号1.目标函数中有绝对值符号2.约束条件中有绝对值符号3.约束条件中有最大最小值的判断（非线性约束）2.4 图解法（MATHEMATICA+processon）2.4.1 线性约束作图2.4.2 线性目标函数作图 (平移)2.5 线性规划案例 (QM for Windows)2.5.1 资源分配生产问题2.5.2 营养问题本章参考文献本章带大家走进线性规划（LP）的世界。

首先介绍线性规划的历史，让大家了解在线性规划领域作出杰出贡献的学者及其成就；接下来的内容为线性规划的基本概念，模型假设和“标准形”，并介绍了将一个般的线性规划模型转化为标准形的技巧；最后给出了线性规划案例。

2.1线性规划的历史1939年，苏联学者Kantorovich为前苏联政府解决优化问题时提出了极值问题，并且提出了解乘数法的新方法，可惜他的工作在当时并未引起足够的重视。

事实上，他所提出的问题正是线性规划的雏形。

与此同时，美国的线性规划却获得了飞快的发展。

1941年，Hitchcock提出运输问题；1945年，Stigler 提出了营养问题；1945年，Koopmans提出了经济问题。

而奠定线性规划整套理论方法的，还要说是G.B.Dantzig，他被誉为“线性规划之父”。

他在1947年担任美国空军审计官的数学顾问，为找到解决问题的机制化工具，提出了“在一组线性方程或不等式约束下，求某一线性形式极小值问题的数学模型”，这便是“线性规划”（linear programming）这一经典优化模型。

二次分配问题及其求解方法的研究进展(Ⅱ)

的热点。这主要由于：方面，Ａ一ＱＰ应用范围广。
日常生活中，多问题像集成电路布线、字机诸打
ｍ ∑ ∑ ∑ ∑ｇｉ
ｉｉｋ＝ｉ＝１＝１＝１
∑ ∑ｃ
＝１＝１
（）１
键盘设计、业调度问题等等．可形式化为二作都次分配问题［５２－。并且一些Ｎ —ａｄ组合优化问３Ｐｈｒ
Ａｓｒｃ：ｕｄａｃａｓｎｅｔｒｂｍ（Ａ）ｓａＮ —ａｄｃｍｂａｒｌｐｉห้องสมุดไป่ตู้ｚｔｎｐｏｌＩｅｐｓｙａｓｌ — ｂｔｔＱａｒｔｓｉｍｎｏｌａｉｇｐｅＱＰｉＰｈｒｏｉｔａｏｔａｏｒｂｅｎｔａｔｅｒ，ｎｎｏｍｉｉｉｍ．ｈｉｅｒａｏｓｏｅＱＰ，ｅｓｌｏｎｓｆｒＡｒｖｒｉｐｒｎｉｓｌｎＡｏｏｔａｉｙｅａｔｌｏａｉｔｎｆｈＡａｗｌａｏｂｕｄｏＱＰａｅｅｙｍｏａｔｎｏｉｇＱＰｔｐｉｌｙｂｘｃａｇ— ｚｉｔｓｌｗｔｖｍｔ
Ｆｒｅｒ，ｅｒｓａｃｎｅｃｆｏｖｇＱＰｂｎａｉｔｎｌｉｕｓｄｕｔｒｅｔｅｅｒｈｔｄｎｙｌｎＡｙｌｅｒａｉｓｉａｓｄｓｓｅ．ｈｍｏｈｅｏｓｉｉｚｏｓｏｃ
Ｋｅｙｗｏｒｄｓ：ａａｉｓｉｎｅｔｐｒｂｅ，ｉａｉａｉｎ，ｏｂｕｑｕｄｒｔｃａｓｇｍｎｏｌｍｌｎｅｒｚｔｏｌｗｏｎｄｓ

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2013c12 $ÊÆÆ 117ò14ÏDec.,2013Operations Research Transactions Vol.17No.4˜a AÏ g© ¯K ‚5z¦)#•{∗Ü¨û1,2,†Ÿ!1êû1Á‡NõÄ–u¢S g© ¯K,Ù6Ý †ålÝ ¥kéõ" ƒ,¦)T a g© ¯Kž,ŒÏL k1|^" ƒ &E~ ¯K5 ,áOŽžm.± g©¯K ‚5z .•Ä:,JÑ ˜«¦)6Ý †ålÝ ¥Óž•3Œþ" ƒ g© ¯K#•{,Ø=l nØþy² •{ Œ15, …l¢ Ý`² T•{'±•{•\` .'…c g© ¯K§‚5z§DÕ g© ¯K§ .¥ã©aÒO221.72010êÆ©aÒ90C27A new solution method by linearization for a specialkind of quadratic assignment problem∗ZHANG Huizhen1,2,†WEI Xin1MA Liang1Abstract Usually,there are many zero elements in theﬂow matrix and distance matrix of the quadratic assignment problem(QAP)instances abstracted from the practi-cal problems,and the computation time of solving this kind of QAP can be dramaticallydecreased by using its zero elements to reduce the size of the problem.Based on thelinearization of the QAP,we proposed a new solution method for the QAP with manyzero elements in bothﬂow matrix and distance matrix in this paper.Moreover,the feasi-bilities and advantages of solving this special kind of QAP by using the new linearizationare approved from the theoretical and experimental point of view,respectively.Keywords quadratic assignment problem(QAP),linearization,sparse quadratic assignment problem(SQAD),modelChinese Library Classiﬁcation O221.72010Mathematics Subject Classiﬁcation90C270Úóg© ¯K´´u Lã%J±¦) |Ü`z NP J K§Ù˜…Œ£ã•µ‰½n‡Âv FÏµ2012c9 26F*Ä7‘8µþ°½˜6Æ‰ï (No.S1201YLXK)§p Æ Æ¬Æ‰:;‘‰ïÄ7éÜ]Ï‘K(No.20123120120005)§þ°p “c “ ]ÏO y(No.slg12010)§þ°½ ˜” ¬‰ïM #(No.14YZ090)§þ°nóŒÆÆ¬‰ïéÄ‘8(No.1D-10-303-002)1.þ°nóŒÆ+nÆ ,þ°200093§School of Management,University of Shanghai for Science and Technology,Shanghai200093,China2.þ°nóŒÆ‡ ä(¥I)ïÄ¥%,þ°200093§Center for Supernetworks Research,University of Shanghai for Science and Technology,Shanghai200093,China†ÏÕŠöCorresponding author,Email:zhzzywz@88Ü¨û,Ÿ!,êû17ò–Ún‡/:§3‡n×nÝ §F=(f ij)∈R n×n§D=(d ij)∈R n×n§C=(c ij)∈R n×n§Ù¥§f ij L« –iÚjƒm 6þ§d ij L«˜iÚjƒm ål§c ij L« –i u˜j s¤§‡¦‰z‡ –© ˜‡˜§¿¦ –ƒm o6þ(½¤^)• §min x∈Xni=1nj=1nk=1nl=1f ik d jl x ij x kl+ni=1nj=1c ij x ij,(0.1)Ù¥§X÷vX=xnj=1x ij=1,i=1,···,n;ni=1x ij=1,j=1,···,n;x ij∈{0,1},i,j=1,···,n. NõÄ–u¢S¯K g© ¯K§Ù6Ý †ålÝ ¥kéõ" ƒ§ …š" ƒ ©ÙéØþ![1].3 g© ¯K ¦)¥§X J U k1|^" ƒ&E ~ ¯K5 §ò¬!ŽŒþ$Žžm.©z[2§3]®éùaäkŒþ" ƒ AÏ g © ¯K ¦)?1 &?§¿‰Ñ =äk"6½"ål QAP¦)•{§ ¿™ 9Óžäk"6Ú"ål QAP¦)•{.©Ú\# V g§ò6Ý †ålÝ ¥kéõ" ƒ g© ¯K½Â•DÕ g ¯K(SQAP)§¿± g© ¯K ‚5z .•Ä:§éDÕ g© ¯K ¦)?1 &?§‰Ñ nØ•â.Óž§é g© ÄO¯K¥QAPLIB¥Ü©äk DÕ6Ý ÚDÕålÝ ¢~?1 ÿÁ§l¢ Ý`² ƒA nØ¿ÂÚ|^" ƒ&E -‡5.1QAP‚5z .g© ¯K8I¼ê¥ g‘3˜½§ÝþO\ ¯K ¦)E,Ý§•d§ÏL˜½•{òÙ g‘‚5z§ † ¯K d (·Ü) ê5y .§l ¦¯K ¦)E,Ý ˜½ü$§U A^Q k (·Ü) ê5y¦)•{¦)QAP¯K¶ … ¯K5 Œ§ J¦)ž§ŒÏL¦)T(·Ü) ê5y . ‚5tµ§¦ QAP¯K•`) e.Š.î8•Ž§Nõ g© ¯K‚5z•{® JÑ§ÙŒNŒ©•o aµ(1)ÏLÚ\Cþy ij:=x ijnk=1nl=1q ijkl x kl(1 i,j n)9ÙƒA å^‡ QAP‚5z.[4−6]¶(2)ÏLÚ\0-1(½ëY)Cþy ijkl:=x ij x kl(1 i,j,k,l n)9ÙƒA å^‡ QAP‚5z .[7−9]¶(3)Äu6Ý QAP‚5z .[10]¶(4)QAP p .[11,12].•,þãA«QAP‚5z .3nØþƒp d§ 3¦)QAP¢~ž§<‚•“àu¤Ñ¤ OŽ] §|^ÙëY½‚5tµ¤¦) e. C u•`8I¼êŠ ..nÜ•Äù Ïƒ§Adams-Johnson .´ –8c A^ƒé õ 2 QAP‚5z .§ T .¥E•3ŒþP{CþÚ å.©z[3]Ú[13]ÏLžØAdams-Johnson4Ï˜a AÏ g© ¯K ‚5z¦)#•{89 .¥ P{CþÚ å§ X e¦)5 … tµ QAP .QAPLP-RIIIµQAPLP-RIII minx∈X n−1i=1nj=1nk>inl=j˜q ijkl y ijkl+ni=1nj=1˜c ij x ij(1.2)s.t.−x kl+l−1j=1y ijkl+nj=l+1y ijkl=0,i,k,l=1,···,n,k>i,(1.3)−x ij+j−1l=1y ijkl+nl=j+1y ijkl=0,i,j,k=1,···,n,k>i,(1.4)y ijkl 0,1 i<k n,1 j=l n,(1.5)Ù¥§˜q ijkl=f ik d jl+f ki d lj§˜c ij=q ijij+c ij=f ii d jj+c ij.2SQAP‚5z .©±QAP ‚5z .QAPLP-RIII•Ä:§ïÄDÕ g© ¯K ¦)•{. FÚD©O•QAP8I¼ê¥ 6Ý ÚålÝ .Ä–u¢S QAP¯K¥§Nõó‚ƒm 6þ½Nõ/:ƒm ål•0§=FÚD¥•3f i0k0=f ki0=0(1 i0=k0n)§d j0l0=d lj0=0(1 j0=l0 n)§ù¦ Cþy i0jk0lÚy ij0kl0 8I¼êXê•0§=˜q i0jk0l=0(1 j=l n§1 i0<k0 n)§˜q ij0kl0=0(1 j0=l0 n§1 i<k n).©òCþy i0jk0lÚy ijkl0©O¡•"6CþÚ"ål Cþ§Ú¡•"Cþ.l8I¼êŠ Ý•Ä§Ø+"Cþy i0jk0lÚy ijkl0Š•0½1§§‚é8I¼êŠ zþþ•0.@o§X JÏL˜½ •{òù 8I¼êXê•0 CþžØ§ò¬~ ¯K ¦)5 §!ŽŒþ$Ž] [2,3].½n2.1e y ijkl(1 i<k n,1 j=l n)• .QAPLP-RIII¥ "Cþ§K "Cþy ijklØU üÕžØ.y²Ø”˜…5§b Cþy i0j0k0l0(1 i0<k0 n§1 j0=l0 n)•"6Cþ.x0∈X§x0i0j0=x0k0l0=1(1 i0<k0 n§1 j0=l0 n)…˜q i0j0k0l0=0.eòCþy i0j0k0l0žØ§dnl=1,l=jy ijkl=x ij§Œ µnl=1l=j0,l0y ij0k0l=x0ij0=1.lþªŒ•§•3y i0j0k0l1=1…l1=l0.? §dl−1j=1y ijkl+nj=l+1y ijkl=x kl§ µ1=y i0j0k0l1l1−1j=1y ijk0l1+nj=l1+1y ijk0l1=x0kl11.Ïd§x0k0l1=1(l1=l0).ù†x0∈X…x0kl0=1ƒgñ.90Ü¨û,Ÿ!,êû17òíØ2.1?¿ÏLÚ\y ijkl:=x ij x kl(1 i,j,k,l n)9ÙƒA å^‡ QAP‚5z .¥ "CþØU üÕžØ.½n2.1ÚíØ2.1L²µ• † QAP d SQAP‚5z .§žØQAP‚5 z .¥ "Cþž§7LÓžžØ•¹"Cþ å.P N={1,2,···,n}¶F0={(i,k)|f ik=f ki=0,i∈N,k∈N,i=k}¶D0={(j,l)|d jl= d lj=0,j∈N,l∈N,j=l}.I§J§KÚL©O•N f8§…÷vµ∀i∈I§∃k∈K§¦ (i,k)∈F0§‡ƒ½,¶∀j∈J§∃l∈L§¦ (j,l)∈D0§‡ƒ½,.©z[2]©O òAdams-Johnson .¥ "6CþÚ"ål Cþ9ÙƒA åžØ§ X e SQAP‚5z .SQAP-IÚSQAP-IIµSQAP-I minx∈Xni,k=1k>i(i,k)/∈F0nj,l=1j=l˜q ijkl y ijkl+ni=1nj=1˜c ij x ij(2.6)s.t.−x ij+i−1k=1y klij+nk=i+1y ijkl=0,i,j,l=1,···,n,j=l,i/∈I,(2.7)−x ij+j−1l=1y klij+nl=j+1y klij=0,i,j,k=1,···,n,k<i,(i,k)/∈F0,(2.8)−x ij+j−1l=1y ijkl+nl=j+1y ijkl=0,i,j,k=1,···,n,k>i,(i,k)/∈F0,(2.9)y ijkl 0,k>i,j=l,(i,k)/∈F0.(2.10)SQAP-II minx∈Xni,k=1k>inj,l=1j=l(j,l)/∈D0˜q ijkl y ijkl+ni=1nj=1˜c ij x ij(2.11)s.t.−x ij+i−1k=1y klij+nk=i+1y ijkl=0,i,j,l=1,···,n,j=l,(j,l)/∈D0,(2.12)−x ij+j−1l=1y klij+nl=j+1y klij=0,i,j,k=1,···,n,k<i,j/∈J,(2.13)−x ij+j−1l=1y ijkl+nl=j+1y ijkl=0,i,j,k=1,···,n,k>i,j/∈J,(2.14)y ijkl 0,k>i,j=l,(j,l)/∈D0(2.15)4Ï˜a AÏ g© ¯K ‚5z¦)#•{91éu6Ý FÚålÝ DÓ•DÕÝ QAP§ .SQAP-IÚSQAP-II¥E•3Œþ"Cþ§• žØ¤k"Cþ§½ÂX e Cþz ijk:z ijk:=nl=1(j,l)∈D0y ijkl,1 i,j,k n,i<k,(i,k)/∈F0,j∈J,(2.16)¿±QAPLP-RIII•Ä:§ ˜«‚5z# .SQAP-IIIµSQAP-III minx∈Xni,k=1k>i(i,k)/∈F0nj,l=1j=l(j,l)/∈D0˜q ijkl y ijkl+ni=1nj=1˜c ij x ij(2.17)s.t.nl=1l=jy ijkl=x ij,1 i,j,k n,i<k,(i,k)/∈F0,j/∈J,(2.18)nl=1(j,l)/∈D0y ijkl+z ijk=x ij,1 i,j,k n,i<k,(i,k)/∈F0,j∈J,(2.19) x ij+nl=1(j,l)∈D0x kl 1+z ijk,1 i,j,k n,i<k,(i,k)/∈F0,j∈J,(2.20) z ijknl=1(j,l)∈D0x kl,1 i,j,k n,i<k,(i,k)/∈F0,j∈J,(2.21)nl=1(j,l)/∈D0y ijkl x ij,1 i,j,k n,i<k,(i,k)/∈F0,j∈J,(2.22) y ijkl∈{0,1},1 i,j,k,l n,i<k,(i,k)/∈F0,(j,l)/∈D0,(2.23) z ijk∈{0,1},1 i,j,k n,i<k,(i,k)/∈F0,j∈J.(2.24)½n2.2SQAP-III´SQAP ‚5z ..y²P F QAPLP-RIIIÚF SQAP-III©O•QAPLP-RIIIÚSQAP-III Œ1)8.d y ijkl =x ij x kl§Œnl=1 (j,l)∈D0y ijkl=x ijnl=1(j,l)∈D0x kl.y²T½n¤á§ …= eã(2.25)¤á§z ijk=nl=1(j,l)∈D0y ijkl=x ijnl=1(j,l)∈D0x kl,1 i,j,k n,i<k,(i,k)/∈F0,j∈J.(2.25)92Ü¨û,Ÿ!,êû17òÄk §∀(x,y )∈F QAPLP -RIII §÷v y ijkl =x ij x kl (1 i,j,k,l n,k >i,j =l ).-z ijk :=nl =1,(j,l )∈D 0y ijkl §w ,§(2.25)¤á.Ùg §∀(x,y,z )∈F SQAP -III §•ÄX e 3«œ¹µ•e x ij =0§d (2.19)Œ §z ijk =0,1 i,j,k n §(i,k )/∈F 0,j ∈J ¶•e nl =1,(j,l )∈D 0x kl =0§d (2.21)Œ µz ijk =0§1 i,j,k n §(i,k )/∈F 0,j ∈J ¶•e x ij =nl =1,(j,l )∈D 0x kl =1§K d (2.20)9(2.21)•§z ijk =1.d d Œ•µ∀(x,y,z )∈F SQAP -III §÷v ª(2.25).Ïd §F QAPLP -RIII =F SQAP -III .3Ž~©ÛÀJ g © ÄO ¯K ¥QAPLIB ¥10‡äk “L 5 J )QAP ¢~5ÿÁ ©J Ñ •{§ù10‡¢~ 6Ý Úål Ý þ•D ÕÝ .¢ ‚¸µIntel(R)Core(TM)i5CPU,3.20GHz §4GB S •§öŠX Ú•Win XP §`z ^‡•Cplex12.1§êâc Ï?n d Matlab R2008b ¤§Cplex ••CPU O Žžm •4 ž.L 1‰Ñ ¤¦¢~9Ù5 n §•`8I ¼êŠ½ c ®••`8I ¼êŠ(Opt.or BK Sol.)§¤¦¢~ 6Ý †ål Ý —Ý(DOM(%))§±9|^SQAP-I §SQAP-II ÚSQAP-III ¦)QAP ¢~ž C þê(No.of Vars.)Ú åê(No.of Cons.).L 116‡QAP ¦)¢~Ins ©n Opt.orBK Sol.DOM(%)No.of Vars.No.of Cons.Flow Dis.I II IIII II III Esc16h 16996(Opt.)89.8468.75278562137622336611228487392Esc16i 1614(Opt.)11.7268.7538562137631365122848992Esc16j 168(Opt.)9.3868.7531362137625604162848800Esc32a 32130(B)14.4581.2574432413696649604800266889536Esc32b 32168(B)21.0981.251081604136969433669762668813888Esc32c 32642(B)25.5981.2513097641369611420884482668816832Esc32d 32200(B)17.5881.25903044136967878458242668811584Esc32f 322(Opt.) 1.1781.256976413696620844826688832Esc32g 326(Opt.) 1.7681.2599524136968800640266881216Esc32h3243827.5481.2514089641369612284890882668818112L 2—L 4©O ‰Ñ QAP ¢~d SQAP-I §SQAP-II ÚSQAP-III ¦) (J .4 žO Žžm S Cplex v k ‰Ñ?ÛB&B Gap (%)ž§^/¨0L «¶du O Žžm •›§O ŽL §3™ •`)c r 1(å§^/*0L «.L 2—L 4¥B&B Gap (%)ÚLP4Ï˜a AÏ g© ¯K ‚5z¦)#•{93 Gap(%) OŽúª©O•µB&B Gap=Cost-bestnode×100%(3.1)LP Gap=Opt.or BK Sol.-LPCostOpt.or BK Sol.×100%(3.2)Ù¥§bestnode•OŽL§¥Cplex¤‰Ñ e.Š.L2|^SQAP-I¦)QAP¢~ $1(JIns©(Mixed)Integer programming LP RelaxationCostB&BGap(%)Cputime(Sec.)No.ofNodesLPCostLPGap(%)Cputime(Sec.)Esc16h996 2.4314400(*)49869030.72467.75 Esc16i140.00 1.411800100.000.05 Esc16j80.000.53370100.000.03 Esc32a15283.2214400(*)12850100.0054.59 Esc32b21287.8414400(*)5560100.00180.23 Esc32c66088.6414400(*)5680100.00239.72 Esc32d21685.1914400(*)15900100.00102.17 Esc32f20.000.2820100.000.02 Esc32g60.007.925940100.000.06 Esc32h45488.5514400(*)5260100.00268.00L3|^SQAP-II¦)QAP¢~ $1(JIns©(Mixed)Integer programming LP RelaxationCostB&BGap(%)Cputime(Sec.)No.ofNodesLP CostLPGap(%)Cputime(Sec.)Esc16h99602182.56622534065.868.67 Esc16i1406942.53257330100.00 6.44 Esc16j802568.2244610100.00 5.86 Esc32a368-14400(*)10100.0014400(*) Esc32b320-14400(*)10100.0014400(*) Esc32c86610014400(*)10100.0014400(*) Esc32d340-14400(*)10100.0014400(*) Esc32f30-14400(*)10100.0014400(*) Esc32g28-14400(*)10100.0014400(*) Esc32h630-14400(*)10100.0014400(*)d L1Œ•:¤¦10‡Ž~¥§ØŽ~Esc16h §Ù{9‡Ž~ 6Ý —Ýþ uålÝ —Ý§Ïd§¦‚|^SQAP-I ¦)5 u|^SQAP-II ¦)5 .• ÓžžØQAPLP-RIII¥ "6CþÚ"ål Cþ§¿… †QAPLP-RIII d QAP‚5z .§SQAP-III¥Ú\ #Cþ9ÙƒA å§Ïd§ ¤¦¯KålÝ —Ý94Ü¨û,Ÿ!,êû17ò96Ý —Ý Œž§|^SQAP-III¦)¯K Cþê9 åêŒUŒu|^SQAP-I½SQAP-II¦)¯K Cþê9 åê§XµŽ~Esc16h|^SQAP-III¦)ž 5 Œu|^SQAP-II ¦)5 .ØL§ù• — ¤¦¢~ 6Ý —Ý½ålÝ —ÝA O$ž§|^SQAP-I½SQAP-II¦)T¢~ J(OŽžm½CostŠ)`u|^SQAP-III ¦) J§Xµ|^SQAP-I¦)Esc16i§Esc16j§Esc32a§Esc32g ¦) J`u| ^SQAP-III ¦) J¶|^SQAP-II¦)Esc16h ¦) J`u|^SQAP-III ¦) J.Œ…§SQAP-III·^u¦)5 Œ…6Ý —ÝÚålÝ —Ýþ $ SQAP¢~.é'L2—L4¥ OŽ(J§ØJ u yµdu .SQAP-III¥ Cþê u SQAP-IÚSQAP-II¥ Cþê, —Ó˜¦)Ž~|^SQAP-III¦) (J(CostŠ)`u|^ SQAP-IÚSQAP-II¦) (J(CostŠ)§ du|^SQAP-III¦)ž åêŒud SQAP-I¦)ž åê§Ïd|^SQAP-III¦)ž OŽžmŒu|^SQAP-I¦)ž OŽžm.d §du¤¦¯K ålÝ —Ý Œ§Ïd|^SQAP-II¦)ž¤s¤ OŽžm••.• §d L2—L4¥ êâN´ •§d SQAP-III¦)Ž~Esc16h¤¦ e.'d SQAP-IÚSQAP-II OŽ e. §=|^SQAP-III ëY tµOŽ e.Ø˜½`ud SQAP-IÚSQAP-II ëY tµOŽ e.§ù´SQAP-III Øvƒ?.L4|^SQAP-III¦)QAP¢~ $1(JIns©(Mixed)Integer programming LP RelaxationCostB&BGap(%)Cputime(Sec.)No.ofNodesLP CostLPGap(%)Cputime(Sec.)Esc16h99683.9314400(*)975810100.000.19 Esc16i140.0015.9814430100.000.02 Esc16j80.000.981720100.000.00Esc32a15881.0114400(*)101540100.00 2.17Esc32b19694.3714400(*)55010100.00 3.44 Esc32c65297.2414400(*)36880100.00 1.41Esc32d21283.3814400(*)190860100.00 1.05 Esc32f20.000.2220100.000.02Esc32g60.0090.8666190100.000.02Esc32h44894.5514400(*)35070100.00 3.524(Ø©± g© ¯K ‚5z .•Ä:§ïÄ ˜a AÏ g© ¯K—-DÕ g© ¯K ¦)#•{§‰Ñ ·^u DÕ g© ¯K ‚5z .SQAP-III.†±¦)•{SQAP-IÚSQAP-IIƒ'§ ¤¦¯K 6Ý ÚålÝ þ• Œ5 D ÕÝ ž§SQAP-III U k1¿©|^¤k" ƒ &E§~¦)¯K 5 §3k •OŽžm S¦ `).QAP õ‡‚5z .§XµFrieze-Yadegar .§Adams-Johnson .§p .§9dù .C/ Ù¦QAP .§Ù Ÿþ´ÏLÚ\y ijkl:=x ij x kl§òQAP84Ï˜a AÏ g© ¯K ‚5z¦)#•{95I¼ê¥ g‘=z•‚5‘ .@o§Šâ©z[2§3]§9 ©½n2.1Ú½n2.2 ?Ø§·‚Œ±‰Ñ†Ù¦a q QAP .ƒA DÕ‚5z .§ duŸÌ¤•§ ©Ø2˜˜Kã.• §ÒSQAP ¦)•{ ó§Šö8 ïÄ üŒ•••µ(1)|^Œ.‚K F tµ•{ÚSQAP-III¦)SQAP¯K¶(2)/•ïáSQAP-III gŽ§ïÄÄu Lawler QAP‚5z .ÚKaufman-Broeckx a QAP‚5z .¦)SQAP ~•{.ë•©z[1]Misevicius A.An improved hybrid genetic algorithm:new result for the quadratic assignmentProblem[J].Knowledge-Based Systems,2004,17(2-4):65-73.[2]Ü¨û,êû.˜a AÏ g© ¯K9Ù¦)[J].XÚó§,2008,26(8):113-117.[3]Zhang H Z,Beltran-Royo C,Constantino M.Eﬀective formulation reductions for the quadraticassignment problem[J].Computers&Operations Research,2010,37(11):2007-2016.[4]Kaufman L,Broeckx F.An algorithm for the quadratic assignment problem using Bender’sdecomposition[J].European Journal of Operational Research,1978,2(3):204-211.[5]Xia Y,Yuan Y X.A new linearization method for quadratic assignment problems[J].Opti-mization Methods and Software,2006,21(5):805-818.[6]Zhang H Z,Beltran-Royo C,Ma L.Solving the quadratic assignment problem by means ofgeneral purpose mixed integer linear programming solvers[J].Annals of Operations Research, 2013,207(1):261-278.[7]Lawler E L.The quadratic assignment problem[J].Management Science,1963,9(4):586-599.[8]Frieze A M,Yadegar J.On the quadratic assignment problem[J].Discrete Applied Mathematics,1983,5(1):89-98.[9]Adams W P,Johnson T A.Improved linear programming-based lower bounds for the quadraticassignment problem[C]//Quadratic Assignment and Related Problems.New York:American Mathematical Society,1994,16:43-75.[10]Erdoˇg an G,Tansel B.A branch and cut algorithm for quadratic assignment problems basedon linearizations[J].Computers and Operations Research,2007,34(4):1085-1106.[11]Ramachandran B,Pekny J F.Higher order lifting techniques in the solution of the quadraticassignment problem[C]//State of the Art in Global Optimization:Computational Methods and herlands:Kluwer Academic Publishers,1996:75-92.[12]Ramakrishnan K G,Resende M G C,Ramachandran B,et al.Tight QAP bounds via lin-ear programming[C]//Combinatorial and Global Optimization.Singapore:World Scientiﬁc Publishing Co.2002,297-303.[13]Ü¨û,êû.˜«¦) g© ¯K #•{[J].XÚ+nÆ ,2010,19(6):645-650.。

一类特殊二次分配问题的线性化求解新方法

合集下载

导数中双变量问题的四种策略

关于数学建模方面的知识

一类特殊二次分配问题的线性化求解新方法

求一类常系数线性常微分方程特解的有限递推法

二阶线性偏微分方程的解法和特解

代数Riccati方程数值解的一种牛顿迭代法

解读支持向量机中的二次规划问题与求解方法

二次指派问题的理论与算法

《数据、模型与决策》第2节：线性规划与图解法

二次分配问题及其求解方法的研究进展(Ⅱ)

文档推荐

最新文档