完全分层多目标规划的基线算法
- 格式：pdf
- 大小：172.04 KB
- 文档页数：5
文档推荐
-
运筹学 (目标规划法)页数:18
-
数学规划法页数:73
-
运动控制算法轨迹规划ppt页数:35
-
多目标规划页数:18
-
§18运用目标达到法求解多目标规划页数:5
-
多目标规划遗传算法页数:2
-
多目标路径规划方法的研究页数:4
下载文档原格式
合集下载
分层法计算步骤范文
分层法计算步骤范文分层法是一种管理方法，常被用于项目管理、问题解决和决策制定等领域。
它通过将复杂任务或问题划分为多个层次，逐级解决，从而更好地掌控和管理整个过程。
以下是分层法的计算步骤：1.确定目标：首先，需要明确任务或问题的最终目标。
这个目标应该是明确、具体和可度量的，以便后续的层次和步骤可以与之对应。
2.划分层次：根据任务或问题的复杂程度，将其划分为多个层次。
每个层次都应该相对独立且具有明确的目标，以便可以单独进行计划和执行。
3.确定上下级关系：在每个层次内，确定上下级关系，确保每个下级层次的目标都能够对应上级层次的目标。
这样可以保证整个任务或问题的目标逻辑完整且相互衔接。
4.分解任务：对于每一层次，进一步分解任务为具体可操作的子任务。
这些子任务应该是可度量的，能够清晰地指导执行者的工作。
5.制定计划：为每个层次和子任务制定详细的计划。
这些计划需要明确包含负责人、时间表、资源需求和具体的执行措施等信息。
6.执行任务：根据计划，逐级执行任务。
每个层次的任务执行者根据上级层次的指导和目标进行工作，保证工作进度和质量。
7.监控和控制：在任务执行过程中，进行监控和控制。
及时获取任务执行的进展和结果，对偏差进行纠正或调整，确保整个过程按计划进行。
8.评估和反馈：在每个层次或任务完成后，进行评估和反馈。
评估可以衡量任务的完成情况和质量，反馈可以提供改进的建议和经验教训。
9.调整和优化：根据评估和反馈的结果，对计划和任务进行调整和优化。
这可能包括重新划分层次、调整任务分解和重新计划等。
10.执行下一层次：在当前层次的任务完成后，继续执行下一层次的任务。
重复步骤4至9，直到达到整体目标。
总结起来，分层法计算步骤包括确定目标、划分层次、确定上下级关系、分解任务、制定计划、执行任务、监控和控制、评估和反馈、调整和优化以及执行下一层次。
这个方法可以帮助管理者更好地理解和处理复杂的任务或问题，提高工作效率和质量。
多目标规划方法讲义
max(min)Z f1( x1, x2,, xn )
i ( x1, x2,, xn ) gi (i 1,2,, m)
f
min j
fj
f
max j
(
j
2,3,,
k)
方法四 目标达到法 首先将多目标规划模型化为如下标准形式：
f1( X )
min
F
(
x
)
min
f2
(X
)
fk
(
X
)
1
(
（二）对于多目标规划问题，可以将其数学模型一般地描 写为如下形式：
max(min)
f1
(
X
)
Z F ( X ) max(min) f2 ( X )
max(min) fk ( X )
1( X )
g1
s.t.
(
X
)
2(X
)
G
g2
m ( X )
gm
式中： X [ x1, x2 ,, xn ]T 为决策变量向量。
∴ d＋× d－ ＝0 成立。
2、目标约束和绝对约束
引入了目标值和正、负偏差变量后，就对某一问题 有了新的限制，既目标约束。
目标约束即可对原目标函数起作用，也可对原约束起 作用。目标约束是目标规划中特有的，是软约束。
绝对约束（系统约束）是指必须严格满足的等式或 不等式约束。如线性规划中的所有约束条件都是绝对 约束，否则无可行解。所以，绝对约束是硬约束。
目标规划的图解法
一、目标规划概述
目标规划是在线性规划的基础上，为适应经济管理 中多目标决策的需要而逐步发展起来的一个分支。
（一）、目标规划与线性规划的比较
第五章 目标规划目标规划的层次解法运筹学基础及其应用胡运权第五版
约束条件含（5.2b）至（5.2e）全部各式， 第二步：接着对P2层次进行优化。根据下一层次优化时应 在前面各层次优化的基础上进行额要求，若第一层次目标 函数最优值为z1*,则构建的P2层次的线性规划模型LP2,,其 L 目标函数为： min z 2 ( w2l d1 w2l d 2 )
因有z2*=0,故P3层次的优化模型为在LP2基础上再增 加约束d2-+d2+=0,得：
LP3 : min z 3 （d d ） d 3
3
3
4
§5.4目标规划的层次解法
Ch5 Goal Programming
2 x1 2 x 2 12 2 x1 3 x 2 d1 d1 15 2 x1 x 2 d 2 - d 2 0 4 x1 d 3 d 3 16 5 x 2 d 4 d 4 15 s.t. d1 0 d2 d2 0 x1 , x 2 , d i , d i 0(i 1,2,3,4)
L l 1 1l 1 1l 1 * 1
例：用层次算法求解§5.1中例5.1的目标规划模型 解：根据上述步骤，本例P11
1
§5.4目标规划的层次解法
Ch5 Goal Programming
2 x1 2 x 2 12 2 x 3x d d 15 1 2 1 1 2 x1 x 2 d 2 - d 2 0 s.t. 4 x1 d 3 d 3 16 5 x 2 d 4 d 4 15 x1 , x 2 , d i , d i 0(i 1,2,3,4)
§5.4目标规划的层次解法 Ch5 Goal Programming
第十章 多目标优化方法简介
q * 2
hv ( X ) 0(v 1, 2, , p)
求解上述问题得到的设计方案既考虑了目标函 数的重要性，又最接近完全最优解，因此，它是原
多目标优化问题的一个更加理想、更加切合实际的
相对最优解。
（3）功效系数法
每个分目标函数 f k ( X ) 都可以用一个对应的功效系
数 k (0 k 1)来表示该项设计指标的好坏，规定：
分层序列法及宽容分层序列法
分层序列法的基本思想是将多目标优化问 题式中的J个目标函数分清主次，按其重要程度 逐一排除，然后依次对各个目标函数求最优解。 不过后一目标应在前一目标最优解的集合域内寻 优。
现在假设f1(x)最重要，f2 (x)其次，f3 (x)再其次，…。 首先对第一个目标函数f1(x)求解，得最优值
D ( k ) x f i min x f i x f i max x
xD
min f k x (k )
统一目标法
统一目标法又称综合目标法。它是将原多目标 优化问题，通过一定方法转化为统一目标函数或综 合目标函数作为该多目标优化问题的评价函数，然 后用前述的单目标函数优化方法求解。
（1）加权组合法
加权组合法又称为线性加权法或加权因子法。
即在将各个分目标函数组合为总的“统一目标函数”
的过程中，引入加权因子，以平衡各指标及各分目
标间的相对重要性以及他们在量纲和量级上的差异，
因此，原目标函数可写为：
min f X wk f k X
k 1 q
s.t.
gu ( X ) 0(u 1,2, , m)
多目标优化问题概述
实际的工程设计和产品设计问题通常有多个设
计目标，或者说有多个评判设计方案优劣的标准。
hv ( X ) 0(v 1, 2, , p)
求解上述问题得到的设计方案既考虑了目标函 数的重要性，又最接近完全最优解，因此，它是原
多目标优化问题的一个更加理想、更加切合实际的
相对最优解。
（3）功效系数法
每个分目标函数 f k ( X ) 都可以用一个对应的功效系
数 k (0 k 1)来表示该项设计指标的好坏，规定：
分层序列法及宽容分层序列法
分层序列法的基本思想是将多目标优化问 题式中的J个目标函数分清主次，按其重要程度 逐一排除，然后依次对各个目标函数求最优解。 不过后一目标应在前一目标最优解的集合域内寻 优。
现在假设f1(x)最重要，f2 (x)其次，f3 (x)再其次，…。 首先对第一个目标函数f1(x)求解，得最优值
D ( k ) x f i min x f i x f i max x
xD
min f k x (k )
统一目标法
统一目标法又称综合目标法。它是将原多目标 优化问题，通过一定方法转化为统一目标函数或综 合目标函数作为该多目标优化问题的评价函数，然 后用前述的单目标函数优化方法求解。
（1）加权组合法
加权组合法又称为线性加权法或加权因子法。
即在将各个分目标函数组合为总的“统一目标函数”
的过程中，引入加权因子，以平衡各指标及各分目
标间的相对重要性以及他们在量纲和量级上的差异，
因此，原目标函数可写为：
min f X wk f k X
k 1 q
s.t.
gu ( X ) 0(u 1,2, , m)
多目标优化问题概述
实际的工程设计和产品设计问题通常有多个设
计目标，或者说有多个评判设计方案优劣的标准。
基于CNN-GRU度量网络的多目标跟踪算法
V Motion GRU A Appearance GRU
C Concat * Multiplication + Summation S Calculate affinity score fc Full connected layer
图 2 CNN-GRU 度量网络结构 Fig. 2 CNN-GRU metric network
整体特征的影响，在降低误报率的同时有效聚合轨迹框的特征。该算法将行人重识别网络输出
的特征计算得到的检测框和轨迹框的相似度，以及 CNN-GRU 网络直接输出的相似度作为数据
关联部分的匹配成本。在标准多目标跟踪数据集上的实验结果验证了本文算法的有效性。
关键词：多目标跟踪；基于检测的跟踪；行人重识别；GRU；数据关联
以上方法证明了深度学习方法在外观特征提 取、相似度计算以及数据关联过程中的有效性，不同 模型在数据关联算法中的融合使用可以增加模型的 性能，但是针对相似目标难区分、目标轨迹框误报率 高的问题，仍有进一步提高的空间。
针对复杂多目标跟踪场景中行人目标 ID 切换 率高和误报率高的问题，本文提出了一个基于 CNNGRU 度量网络的多目标跟踪框架。该框架主要包括 行人重识别模型、CNN-GRU 度量网络和数据关联算 法。在 CNN-GRU 深度度量网络中统一提取目标的 外观特征和运动特征，并学习其时间关联性，使得目 标 具 有 更 好 的 判 别 性 ， 降 低 目 标 的 ID 切 换 率 。 同 时，通过训练使网络学习目标不同时序历史轨迹框 正确匹配的概率值，抑制目标轨迹中的误检以及低 质量目标框对目标整体特征的影响，降低误报率；在 CNN-GRU 度量网络结构中直接聚合不同时序的目 标历史轨迹框的外观特征，再由该度量网络直接输
基于 CNN-GRU 度量网络的多目标跟踪算法
C Concat * Multiplication + Summation S Calculate affinity score fc Full connected layer
图 2 CNN-GRU 度量网络结构 Fig. 2 CNN-GRU metric network
整体特征的影响，在降低误报率的同时有效聚合轨迹框的特征。该算法将行人重识别网络输出
的特征计算得到的检测框和轨迹框的相似度，以及 CNN-GRU 网络直接输出的相似度作为数据
关联部分的匹配成本。在标准多目标跟踪数据集上的实验结果验证了本文算法的有效性。
关键词：多目标跟踪；基于检测的跟踪；行人重识别；GRU；数据关联
以上方法证明了深度学习方法在外观特征提 取、相似度计算以及数据关联过程中的有效性，不同 模型在数据关联算法中的融合使用可以增加模型的 性能，但是针对相似目标难区分、目标轨迹框误报率 高的问题，仍有进一步提高的空间。
针对复杂多目标跟踪场景中行人目标 ID 切换 率高和误报率高的问题，本文提出了一个基于 CNNGRU 度量网络的多目标跟踪框架。该框架主要包括 行人重识别模型、CNN-GRU 度量网络和数据关联算 法。在 CNN-GRU 深度度量网络中统一提取目标的 外观特征和运动特征，并学习其时间关联性，使得目 标 具 有 更 好 的 判 别 性 ， 降 低 目 标 的 ID 切 换 率 。 同 时，通过训练使网络学习目标不同时序历史轨迹框 正确匹配的概率值，抑制目标轨迹中的误检以及低 质量目标框对目标整体特征的影响，降低误报率；在 CNN-GRU 度量网络结构中直接聚合不同时序的目 标历史轨迹框的外观特征，再由该度量网络直接输
基于 CNN-GRU 度量网络的多目标跟踪算法
多目标邻近梯度算法
多目标邻近梯度算法简介多目标邻近梯度算法（Multi-Objective Proximity Gradient Algorithm，简称MOPGA）是一种用于解决多目标优化问题的算法。
它基于邻近梯度法（Proximity Gradient Algorithm）的思想，在处理多个目标函数的情况下，能够找到一组最优解来平衡多个目标。
目标函数与多目标优化问题多目标优化问题是指在最小化或最大化某个目标函数的同时，还要满足一系列其他目标函数的约束条件。
这类问题常常在实际生活中遇到，比如工程设计、投资决策等。
传统的单目标优化只能得到一个最优解，而多目标优化则能够找到多个最优解，从而帮助决策者了解权衡不同目标之间的关系。
邻近梯度法简介邻近梯度法是一种用于解决单目标优化问题的可行解算法。
它通过利用目标函数的梯度信息来指导搜索方向，以逐步逼近最优解。
邻近梯度法的核心思想是在当前解的邻域内搜索，更新解的位置以减小目标函数的值。
这个过程重复进行，直到达到预先设定的停止条件。
MOPGA算法步骤步骤一：初始化种群•设置种群大小、变量范围和目标函数个数等参数。
•随机生成初始解作为种群的初始状态。
步骤二：计算目标函数值•对于种群中的每个个体，计算其目标函数值，得到一个目标函数矩阵。
步骤三：计算邻近梯度•对于目标函数矩阵中的每个个体，计算其邻近梯度。
•邻近梯度是指目标函数在该个体附近的变化趋势。
步骤四：更新个体位置•根据邻近梯度的方向，更新种群中每个个体的位置。
•位置更新的方式可以使用梯度下降法或其他搜索算法。
步骤五：非支配排序•对种群中的个体进行非支配排序，将它们划分为不同的层次。
•非支配排序是根据个体在多个目标函数上的表现来确定其排名。
步骤六：计算拥挤度距离•计算每个个体的拥挤度距离，用于衡量其在种群中的稀疏性。
•拥挤度距离表示个体周围的密度，越密集的个体拥挤度距离越小。
步骤七：选择个体•根据非支配排序和拥挤度距离，选择新一代种群。
多目标规划问题的几种常用解法
多目标规划问题的几种常用解法(1) 主要目标法其基本思想是：在多目标问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。
这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。
(2) 线性加权和法其基本思想是：按照多目标f i (x) (i=1, 2, … ,m)的重要程度，分别乘以一组权系数λj (j=1, 2, … ,m)然后相加作为目标函数而构成单目标规划问题。
即 ∑==m j j j x f f 1)(min λ，其中∑==≥mj j j 110λλ且(3) 极大极小法其基本思想是：对于极小化的多目标规划，让其中最大的目标函数值尽可能地小，为此，对每个 x ∈R ，我们先求诸目标函数值f i (x)的最大值，然后再求这些最大值中的最小值。
即构造单目标规划：{})(max min 1x f f j mj ≤≤= (4) 目标达到法（步骤法）对于多目标规划：[])(,),(),(m in 21x f x f x f ms.t g j (x) ≤0 j=1, 2, … ,n先设计与目标函数相应的一组目标值理想化向量),,(**2*1m f f f ，再设γ为一松弛因子标量。
设),,,(21m w w w W =为权值系数向量。
于是多目标规划问题化为：()kj x g m j f w x f j j j j x ,,2,10)(,,2,1min *, =≤=≤-γγγ（5）字典序法对目标的重要性进行排序，依次求解各单目标规划（前一个目标的最优解不唯一，其结果作为下一个目标的约束），到有唯一解时结束。
多目标规划求解方法介绍
多目标规划求解方法介绍多目标规划（multi-objective programming，也称为多目标优化）是数学规划的一个分支，用于处理具有多个冲突目标的问题。
在多目标规划中，需要找到一组解决方案，它们同时最小化（或最大化）多个冲突的目标函数。
多目标规划已经在许多领域得到了应用，如工程、管理、金融等。
下面将介绍几种常见的多目标规划求解方法。
1. 加权和法（Weighted Sum Method）：加权和法是最简单和最直接的多目标规划求解方法。
将多个目标函数通过赋予不同的权重进行加权求和，得到一个单目标函数。
然后使用传统的单目标规划方法求解该单目标函数，得到一个最优解。
然而，由于加权和法只能得到权衡过的解，不能找到所有的非劣解（即没有其他解比它更好），因此它在解决多目标规划问题中存在局限性。
2. 约束方法（Constraint Method）：约束方法是将多目标规划问题转化为一系列带有约束条件的单目标规划问题。
通过引入额外的约束条件，限制目标函数之间的关系，使得求解过程产生多个解。
然后使用传统的单目标规划方法求解这些带有约束条件的问题，得到一组最优解。
约束方法可以找到非劣解集合，但问题在于如何选择合适的约束条件。
3. 目标规划算法（Goal Programming Algorithms）：目标规划算法是特别针对多目标规划问题设计的一类算法。
它通过将多个目标函数转化为约束关系，建立目标规划模型。
目标规划算法可以根据问题的不同特点选择相应的求解方法，如分解法、交互法、加权法等。
这些方法与约束方法相似，但比约束方法更加灵活，能够处理更加复杂的问题。
4. 遗传算法（Genetic Algorithms）：遗传算法是一种启发式的优化方法，也可以用于解决多目标规划问题。
它模仿自然界中的进化过程，通过不断地进化和迭代，从初始种群中找到优秀的个体，产生一个适应度高的种群。
在多目标规划中，遗传算法通过构建适应度函数来度量解的好坏，并使用交叉、变异等操作来产生新的解。
5-4 求解目标规划的层次算法
§4．求解目标规划的层次算法
求解目标规划是从高优先级到低优先级逐层优化的， 求解目标规划的层次算法就是根据这样的思想构造的。
层次算法步骤：
第一步： 对目标函数中的 P1 层次进行优化，建立 第一层次的线性规划模型 LP1 并求解。 LP1的目标函数为
min z1 w d w d
l 1 1l 1 1l
求解 LP3 得：
x1 2.0, x2 4.0 , d d d d d 0 d 1.0, d 8.0 , d 5.0 , z 29.0
* 3 1 3 4
1
2
2
3
4
到此时，所有各层次的优化都已经完成，而最后一个
层次的最优值 z3*=29.0 ，因此并没有取得最优解，这个
2
2
3
3
3 4
解：第一层次的优化模型LP1为：
LP1 : min z1 d1
2 x1 2 x 2 12 2 x 3 x d d 2 1 1 15 1 2 x x d d 0 1 2 2 2 s.t . 4 x d d 3 3 16 1 5 x2 d 4 d4 15 x1 , x2 , d i , d i 0 (i 1, ,4)
例.
用层次算法求解下述目标规划。
1 1
min z P d P2 d d 3P3 d d P d 2 x1 2 x2 12 2 x1 3 x2 d1 d1 15 2 x x d d 0 1 2 2 2 s.t . d 3 d 3 16 4 x1 5 x2 d 4 d4 15 x , x , d , d 1 2 i i 0 (i 1,,4)
求解目标规划是从高优先级到低优先级逐层优化的， 求解目标规划的层次算法就是根据这样的思想构造的。
层次算法步骤：
第一步： 对目标函数中的 P1 层次进行优化，建立 第一层次的线性规划模型 LP1 并求解。 LP1的目标函数为
min z1 w d w d
l 1 1l 1 1l
求解 LP3 得：
x1 2.0, x2 4.0 , d d d d d 0 d 1.0, d 8.0 , d 5.0 , z 29.0
* 3 1 3 4
1
2
2
3
4
到此时，所有各层次的优化都已经完成，而最后一个
层次的最优值 z3*=29.0 ，因此并没有取得最优解，这个
2
2
3
3
3 4
解：第一层次的优化模型LP1为：
LP1 : min z1 d1
2 x1 2 x 2 12 2 x 3 x d d 2 1 1 15 1 2 x x d d 0 1 2 2 2 s.t . 4 x d d 3 3 16 1 5 x2 d 4 d4 15 x1 , x2 , d i , d i 0 (i 1, ,4)
例.
用层次算法求解下述目标规划。
1 1
min z P d P2 d d 3P3 d d P d 2 x1 2 x2 12 2 x1 3 x2 d1 d1 15 2 x x d d 0 1 2 2 2 s.t . d 3 d 3 16 4 x1 5 x2 d 4 d4 15 x , x , d , d 1 2 i i 0 (i 1,,4)
6-多目标规划方法
①根据市场信息，甲种产品的需求量有下降的 趋势，因此甲种产品的产量不应大于乙种产 品的产量。
②超过计划供应的原材料，需用高价采购，这 就会使生产成本增加。
③应尽可能地充分利用设备的有效台时，但不 希望加班。
④应尽可能达到并超过计划产值指标56元。
这样，该企业生产方案的确定，便成为一个多 目标决策问题，这一问题可以运用目标规划方
绝对约束 非负约束
多 目 标 规 划 d
l
,
d
l
0
(l 1,2, , L)
非负约束
二、求解目标规划的单纯形方法
目标规划模型仍可以用单纯形方法求解，在求解 时作以下规定：
①因为目标函数都是求最小值，所以，最优判别 检验数为： c j z j 0( j 1,2, , n)
K
c j z j akj Pk ( j 1,2 , n；k 1,2 , K) k 1
可以进一步写作: max(min) Z AX
BX b
A策为变k量*n向矩多量阵.，B为目m*n矩阵标，b为m维规向量，划X为n维决
（2）多目标规划的非劣解 对于上述多目标规划问题，求解就意味着需要 做出如下的复合选择： ▲每一个目标函数取什么值，原问题可以得到 最满意的解决？ ▲每一个决策变量取什么值，原问题可以得到 最满意的解决 ？
偏差变量的权系数分别为
kl
、
，则多目
kl
标规划问题可以表示为：
型 的 一 般
K
L
min Z
Pk
(
kl
dl
kl
dl
)
n
k 1 l1
c
(l j
)
x
j
d
l
d
②超过计划供应的原材料，需用高价采购，这 就会使生产成本增加。
③应尽可能地充分利用设备的有效台时，但不 希望加班。
④应尽可能达到并超过计划产值指标56元。
这样，该企业生产方案的确定，便成为一个多 目标决策问题，这一问题可以运用目标规划方
绝对约束 非负约束
多 目 标 规 划 d
l
,
d
l
0
(l 1,2, , L)
非负约束
二、求解目标规划的单纯形方法
目标规划模型仍可以用单纯形方法求解，在求解 时作以下规定：
①因为目标函数都是求最小值，所以，最优判别 检验数为： c j z j 0( j 1,2, , n)
K
c j z j akj Pk ( j 1,2 , n；k 1,2 , K) k 1
可以进一步写作: max(min) Z AX
BX b
A策为变k量*n向矩多量阵.，B为目m*n矩阵标，b为m维规向量，划X为n维决
（2）多目标规划的非劣解 对于上述多目标规划问题，求解就意味着需要 做出如下的复合选择： ▲每一个目标函数取什么值，原问题可以得到 最满意的解决？ ▲每一个决策变量取什么值，原问题可以得到 最满意的解决 ？
偏差变量的权系数分别为
kl
、
，则多目
kl
标规划问题可以表示为：
型 的 一 般
K
L
min Z
Pk
(
kl
dl
kl
dl
)
n
k 1 l1
c
(l j
)
x
j
d
l
d
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第13卷 第4期运 筹 与 管 理Vol.13,No.42004年8月OPERAT IO NS RESEARCH AN D M ANA GEM EN T SCI EN CEAug.2004收稿日期:2003-10-27基金项目:陕西省教育厅专项科研基金资助项目(03jk065);西安建筑科技大学基础研究基金资助项目(02BR01)作者简介:卢志义(1973-),男,内蒙古包头市人,硕士研究生,从事最优化理论研究;徐裕生(1950-),西安建筑科技大学理学院教授,主要从事最优化理论和不动点理论的研究。
完全分层多目标规划的基线算法卢志义, 徐裕生, 马春晖(西安建筑科技大学理学院,陕西西安710055)摘 要:本文采用基线算法求解完全分层多目标规划问题。
给出了简单完全分层多目标规划基线算法的求解步骤,并对其进行了修正,从而得到完全分层多目标规划的宽容基线算法。
并给出了两个计算实例。
关键词:运筹学;宽容算法;基线算法;多目标规划中图分类号:O22116 文章标识码:A 文章编号:1007-3221(2004)04-0050-05Th e Basic Line Algorithm for Complete Tratified Mu ltiobjective Programmin gLU Zh-i yi,XU Yu -sheng,MA Chun -hui(College of Science,X i .an University o f A rchitecture and Technology ,Xi .an 710055,China)Abstract:In this paper,we make use of the basic line algorithm to solve the complete tratified multiobjective prog ramming.The procedures of solv ing the simple com plete tratified multiobjective program ming are g iven.M eanw hile,w e rev ise it so as to succeed in obtaining the compromise solution of the complete tratified mult-i objective programm ing.T wo examples also are g iven.Key words:operations research;comprom ise algorithm;the basic line algorithm;multiobjective programming0 引言基线算法是一种线性规划的新算法,具有操作方便,迭代次数小,效率高,数值稳定性好等特点,是单纯形法的发展(参见[1])。
我们陆续将此算法推广到与线性规划有关的其它规划。
本文旨在将此算法推广到多目标规划。
较单纯形法而言,用基线算法解决完全分层多目标规划,步骤更简洁,易操作,运算速度更快。
1 简单完全分层多目标规划的基线算法1.1 算法的形成讨论完全分层多目标规划问题L -max [v s =P s c T s x ]ms =1(1)s.t.Ax [bx \0其中c s =(c s 1,,,c sn )(s =1,,,m ),x =(x 1,,,x n )T ,A =a 11,a 1n,,,a q 1,a qn,b =(b 1,,,b q )T .此模型的特点是:每一优先层次只有一个目标函数,且每一优先层次的问题都是一个线性规划问题,因而可以逐层地采用基线算法求解。
将上述模型变为标准型:L -max [v s =P s c Ts x ]m s =1(2)s.t.a 11x 1+,+a 1n x n +x n +1 =b 1,, , ,,a i 1x 1+,+a in x n +x n +i=b i ,,,,,a q 1x 1+,+a qn x n +x n +q=b qx i \0(i =1,,,n +q )或将约束条件简写为s.t.A x +(x n +1,,,x n +q )T =bx i \0(i =1,,,n +q )首先用基线算法求解第一优先层的最优值。
即求解线性规划问题max v 1=c 11x 1+,c 1n x ns.t.A x +(x n +1,,,x n +q )T =bx i \0(i =1,,,n +q )其初表为(表1):表1x 1x 2,x n x n +1,x n +q RH S c 11c 12,c 1n 0,0v 1a 11a 12,a 1n a 1,n +1,a 1,n +qb 1,,,,,,,,a i 1a i 2,a in a i,n +1,a i,n +q b i ,,,,,,,,a q 1a q 2,a qn a q,n +1,a q,n +qb q设求得的最优值为v *1,其最优表为表2,将v 1=v *1代入此最优表,并将第二层目标列入此表得新表(表3),进入第二层次目标的求解过程。
表2x 1x 2,x n x n +1,x n +q RH S c c 11c c 12,c c 1n c c 1,n +l ,c c 1,n +q A 0+B 0v 1a c 11a c 12,a c 1n a c 1,n +1,a c 1,n +qA 1+B 1v 1,,,,,,,, ,a c i 1a c i 2,a c in a c i ,n +1,a c i,n +qA i +B i v *1,,,,,,,, ,a c q 1a c q 2,a c qna c q,n +1,a c q,n +qA q +B q v 1表351第4期 卢志义,等:完全分层多目标规划的基线算法52运筹与管理2004年第13卷表3相当于将条件c11x1+,+c1n x n=v*1作为求解第二层目标最优值的约束条件。
用基线算法求得最优值,这样逐层进行下去直到第m层目标。
由上述求解过程易知,最后一层的最优解必为原问题的有效解。
1.2简单完全分层多目标规划基线算法的步骤step1化为标准形式(2)step2由第一层目标函数与约束条件构成初表用基线算法求解,并令k:=1;step3若k=m,输出最优解与各层目标函数的最优值v*i;否则进入step4;step4将第k层最优表中v k用v*k代换并将第k+1层目标函数加入第k层最优表,用基线算法求解,令k:=k+1,转step3。
1.3例1L-max[P1(x1+3x2),P2(x1+2x3),P3(-x1-2x2-x3)]s.t.x1+x2[5x2[2-x1-x2+x3[4x1,x2,x3\0解第一步,引入松弛变量x4,x5,x6.化为标准型L-m ax[P1(x1+3x2),P2(x1+2x3),P3(-x1-2x2-x3)]s.t.x1+x2+x4=5x2+x5=2-x1-x2+x3+x6=4x i\0(i=1,,,6)第二步,列出第一层初表(表4)表4x1x2x3x4x5x6RH S130000v111010050100102-1-110014x1进基,得基线表(表5)。
表5x1x2x3x4x5x6RH S130000v1v1\00[-2]01005-v1v1[501001020210014+v1v1\-4旋转得(表6):表6x1x2x3x4x5x6RH S1003/20015/2-v1/2v1[15010-1/200-5/2+v1/2v1\50001/2109/2-v1/2v1[9*0011019已知最优表,v*1=9。
第三步,令代入初表并将第二层目标函数加入最优表(表7):表7x 1x 2x 3x 4x 5x 6RH S 102000v 21003/2003010-1/20020001/210001119x 1、x 2进基,得基线表(表8),表8已是最优表。
表8x 1x 2x 3x 4x 5x 6RH S 001-3/400v 2/2-3/2v 3\31003/2003010-1/20020001/21007/41-v 2/2+21/2v 2[21*第四步,将v 2=v *2=21代入上表8,并将第三层目标加入表8得表9,经初等变换,变成表10,此表是最优表,其最优值为v *3=-16。
代入表10得最优解为x =(3,2,9,0,0,0)。
于是得此题的有效解为x =(3,2,9,0,0,0),各优先层次目标的最优值为:v 1=v *1=9,v 2=v *2=21,v 3=v *3=-16。
1.4 说明若到某一层得到的基线表行数等于n +q ,此时,下一层次的求解不必再进行,出现这种情况时说明,以后各优先层次的目标函数在问题中不起作用。
为避免出现这种情况,可进行如下的修正)))宽容完全分层多目标规划的基线算法。
表9x 1x 2x 3x 4x 5x 6RH S -1-2-1000v 3001-3/40091003/2003010-1/20020001/210007/401表10x 1x 2x 3x 4x 5x 6RH S 000100-4v 3-64v 3[-16*001000-3v 3-69v 3[-131000006v 3+99v 3\-33/2010000-2v 3-30v 3[-150000102v 3+32v 3\-16017v 3+112v 3\-162 宽容完全分层多目标规划的基线算法宽容分层算法的基本思想是:从第二层起,在对每一层求解之后给其最优值以适当的宽容,使得下一层次的可行域以适当的放宽,以前一层次目标函数的最优值的偏差,换取后一层次目标函数值的改善。
设给出第k 层次的宽容量为D k \0(k =1,,,m -1),其算法的步骤为:step 1、step 2、step 3同简单完全分层多目标规划基线算法的对应步骤;step 4将第k +1层目标函数加入第k 层最优表,将第k 层最优表中第一行中v k 用v *k -D k 代换,其余行中的v k 仍用v *k 代换,并增加变量列x n +q +k -1,其系数为(0,-1,0,0,0,0)T,继续用基线算法求解.53第4期 卢志义,等:完全分层多目标规划的基线算法54运筹与管理2004年第13卷令k:=k+1,转step3.下面的定理给出了由宽容分层基线算法所求得的解的意义。
定理设X={x I R n|Ax[b,x\0},E X(f,X)是问题(1)的弱有效解,D k\0(k=1,,,m-1).若x I E X(f,X)。