多目标优化

多目标优化模型

一、多 目 标 优 化 简 介

• 优化(Optimization) : 从若干可能的方案中寻求某 种意义下的最优方案 •多目标规划（Multiple Objectives Programming） 是数学规划的一个分支，研究多于一个目标函数在给定 区域上的最优化，又称多目标最优化，通常记为 VMP。

求解算法 转化为单目标 实例1：投资的收益和风险

市场上有n种资产（如股票、债券、…）Si ( i=1,…n) 供投资者选择，某公司有数额为M的一笔相当大的资金可用作 一个时期的投资。公司财务分析人员对这n种资产进行了评 估，估算出在这一时期内购买Si的平均收益率，并预测出购 买Si的风险损失率。考虑到投资越分散，总的风险越小，公 司确定，当用这笔资金购买若干种资产时，总体风险可用所 投资的Si中最大的一个风险来度量。 购买Si要付交易费，费率已知，并且当购买额不超过最低限 额时，交易费按购买最低限额计算（不买当然无须付费）。 另外，假定同期银行存款年利率是1%, 且既无交易费又无风 险。试给该公司设计一种投资组合方案 目标一：使净收益尽可能大； 目标二：而总体风险尽可能小。

求解算法 实例2：旅游路线设计

转化为单目标

今年暑假，我校要召开“××学术会议”，届时来自国内外 的许多著名学者都会相聚成都。在会议结束后，主办方希望能 安排这些远道而来的贵宾参观四川省境内的著名自然和人文景 观，初步设想有如下线路可供选择： 一号线：九寨沟、黄龙； 二号线：乐山、峨嵋； 三号线：四姑娘山、丹巴； 四号线：都江堰、青城山； 五号线：海螺沟、康定； 每条线路中的景点可以全部参观，也可以参观其中之一。 不仅如此，一起参观景点的人数越多，每人承担的费用也会越 小。车费与车型、乘客人数、路程种类及公里数有关。

主办方在会议开始前对所有参会的100位代表 旅游意向进行了调查，充分考虑这些代表的意愿， 为主办方设计代表们合适的旅游路线，使他们在会 议结束后的10天时间内花最少的钱游尽可能多的地 方。 目标一：宾客参观意愿满意度尽可能高 目标二：宾客所花费用尽可能少 目标三：宾客游尽可能多的景点

转化为单目标的具体方法介绍：

1. 主要目标法 在多目标优化问题中，根据问题的实际 情况，确定一个目标为主要目标，而把其余目 标作为次要目标，并且根据决策者的经验，选 取一定的界限值。这样就可以把次要目标也作 为约束来处理，于是就将原多目标问题转化为 在新的约束下，求主要目标的单目标优化问 题。

转化单目标法

2. 线性加权和法：按照m个目标 fi (x) 的重要 程度，分别乘以一组权系数

，然后相加作 为目标函数。

u( f (x)) = ∑λi fi (x)

i =1

m

∑λ = 1

i =1 i

m

转化单目标法

3. 极大极小点法

1≤ i ≤ m

min u ( f ( x )) = min max{ f i ( x )}

x∈ X 1≤ i ≤ m

4. 范数理想点法

dp

(

p⎤ ⎡ f ( x ), f ;ω = ⎢ ∑ ω i f i ( x ) − f i ⎥ ⎣ i =1 ⎦ m

)

1 p

转化单目标法

5. 评价函数法 以上的各种方法都是由 f i ( x )归结成一 个目标其可看作是 f i ( x ) 的函数 U ( x ) = u( f ( x )) 我们可统一称其为评价函数，显然其 具有很大的概括性，它不仅包括以上的 一些方法，还可以构造新的方法。当然 这种构造也不是随意的，一般要根据问 题的具体背景和几何意义来构造

线性多目标规划模型---线性加权和法

品 产

例： 一个生产问题，有关数 据如表。问如何安排生产可 使总利润最大，产量之和最 小。要求第二种原料用完。

4 4 B 1 C 单位利润 80

单耗 原料

甲

乙

5 2 0 100

总量

80 48 6

A

解 设 x1 , x2 为甲，乙的产量 min z1 = x1 + x2 则 max z2 = 80 x1 + 100 x2 s .t . 4 x1 + 5 x2 ≤ 80 4 x1 + 2 x2 = 48 x1 ≤6 x1 , x2 ≥ 0

矛 盾 的

一般形式： min Q( X ) max R( X ) s .t . F ( X ) = M X ≥O 双目标规划模型

化成单目标规划模型 化法一

min Q( X ) s .t . R ( X ) ≥ a F(X ) = M X ≥O

或

max R( X ) s .t . Q ( X ) ≤ b F(X ) = M X ≥O

化法二

min {ρ Q( X ) − (1 − ρ ) R( X )} s .t . F ( X ) = M X ≥O

ρ 为目标权重或偏好系数。

a ,b, ρ 均可看成参数，对不同的参数值求出 最优解，然后加以讨论，选出满意解。

例 选课策略

课号 1 2 3 4 5 6 7 8 9 课名 微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 学分 5 4 4 3 4 3 2 2 3 所属类别 数学 数学 数学；运筹学 数学；计算机 数学；运筹学 计算机；运筹学 计算机 运筹学 运筹学；计算机 先修课要求

微积分；线性代数 计算机编程 微积分；线性代数 计算机编程 应用统计 微积分；线性代数

要求至少选两门数学课、三门运筹学课和两门计算机课 为了选修课程门数最少，应学习哪些课程 ？ 选修课程最少，且学分尽量多，应学习哪些课程 ？

0-1规划模型

课号 1 2 3 4 5 6 7 8 9 课名 微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 所属类别 数学 数学 数学；运筹学 数学；计算机 数学；运筹学 计算机；运筹学 计算机 运筹学 运筹学；计算机

决策变量 xi=1 ~选修课号i 的 课程（xi=0 ~不选） 目标函数 选修课程总数最少

Min

Z = ∑ xi

i =1

9

约束条件

最少2门数学课， 3门运筹学课， 2门计算机课。

x1 + x 2 + x3 + x 4 + x5 ≥ 2

x3 + x5 + x6 + x8 + x9 ≥ 3

x4 + x6 + x7 + x9 ≥ 2

0-1规划模型

课号 课名 微积分 线性代数 最优

化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 先修课要求

约束条件 先修课程要求 x3=1必有x1 = x2 =1

∗ 1 ∗ 2 ∗ 3 ∗ ∗ ∗

4 5 6 7 8 9

微积分；线性代数 计算机编程 微积分；线性代数 计算机编程 应用统计 微积分；线性代数

x3 ≤ x1 , x3 ≤ x 2

2 x3 − x1 − x 2 ≤ 0

x 4 ≤ x7 x4 − x7 ≤ 0

2 x 5 − x1 − x 2 ≤ 0 x6 − x7 ≤ 0

模型求解（LINDO） 最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21

x8 − x5 ≤ 0

2 x9 − x1 − x 2 ≤ 0

讨论：选修课程最少，学分尽量多，应学习哪些课程？ 课程最少 学分最多

9

Min

Z = ∑ xi

i =1

Max W = 5x1 + 4x2 + 4x3 + 3x4 + 4x5 + 3x6 + 2x7 + 2x8 + 3x9

两目标(多目标)规划

• 以课程最少为目标，不 管学分多少。 • 以学分最多为目标，不 管课程多少。

Min {Z , − W }

最优解如上，6门课 程，总学分21 。 最优解显然是选修所 有9门课程 。

多目标优化的处理方法：化成单目标优化。

多目标规划

• 在课程最少的前提下 以学分最多为目标。

课号 课名 微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 学分 5 4 4 3 4 3 2 2 3

增加约束

∑

9

i =1

x i = 6，

以学分最多为目标求解。 最优解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它为0；总 学分由21增至22。 注意：最优解不唯一！ 可将x9 =1 易为x6 =1 LINDO无法告诉优化 问题的解是否唯一。

∗1 ∗ ∗2 ∗ ∗3 ∗ ∗ ∗ ∗

4 5 6 7 8 9

∗ ∗ ∗

多目标规划

• 对学分数和课程数加权形成一个目标，如三七开。

Min Y = λ1Z − λ2W = 0.7 Z − 0.3W

课号 1 2 3 4 5 6 7 8 9 课名 微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 学分 5 4 4 3 4 3 2 2 3

Z = ∑ xi

i =1

9

∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗

W = 5x1 + 4x2 + 4x3 + 3x4 + 4x5 + 3x6 + 2x7 + 2x8 + 3x9

最优解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1， 其它为0；总学分28。

求解算法之一：

转化为单目标

求解算法之二：

目标规划法

二、多目标优化目标规划法

线性规划通常考虑一个目标函数(问题简单) 目标规划考虑多个目标函数(问题复杂) 。

例 生产安排问题

某企业生产甲、乙两种产品，需要用到A,B,C 三种设备，关于产品的盈利与使用设备的工时及限 制如下表所示。

甲 2 A/(h/件) 4 B/(h/件) 0 C/(h/件) 赢利/(元/件) 200 乙 设备的生产能力/h 2 12 0 16 5 15 300

问该企业应如何安排生产，使得在计划期内 总利润最大？

1. 线性规划建模

该例是一个线性规划问题，直接考虑它的线性规划模型 设甲、乙产品的产量分别为x1,

x2,建立线性规划模型：

Max

z = 200 x 1 + 300 x 2 ;

s. t. 2x1 + 2x2 ≤ 12 , 4x1 ≤ 16, 5x2

≤ 15, x1, x2 ≥ 0.

用Lindo或Lingo软件求解,得到最优 解 *

x1 = 3, x2 = 3, z = 1500.

Max

z = 200 x 1 + 300 x 2 ;

2. 目标规划建模

若在上例中，企业的经营目标不仅要考

s. t. 2 x1 + 2 x2 ≤ 12 ,

4 x1 ≤ 16, 5 x2 ≤ 15, x1 , x2 ≥ 0.

虑利润，还需要考虑多个方面，因此增加下列因素(目标)：

• 力求使利润指标不低于1500元 • 考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2 • 设备A为贵重设备，严格禁止超时使用 • 设备C可以适当加班，但要控制；设备B既要求充分利用，又 尽可能不加班，在重要性上，设备B是设备C的3倍 从上述问题可以看出，仅用线性规划方法是不够的，需 要借助于目标规划的方法进行建模求解

目标规划的数学模型

目标规划的基本概念

为了克服线性规划的局限性,目标规划采用如下手段： 1. 设置偏差变量; 2. 统一处理目标与约束; 3. 目标的优先级与权系数。

1. 设置偏差变量

用偏差变量(Deviational variables)来表示实际值与目标值 之间的差异，令 + ---- 超出目标的差值，称为正偏差变量 d d d − ---- 未达到目标的差值，称为负偏差变量 + − 其中d 与 d 至少有一个为0

+

约定如下： •当实际值超过目标值时，有 d − = 0, d + > 0; •当实际值未达到目标值时，有 d + = 0, d − > 0; •当实际值与目标值一致时，有 d − = 0, d + = 0.

2. 统一处理目标与约束

在目标规划中，约束可分两类，一类是对资源有严格限制 的，称为刚性约束(Hard Constraint)；例如在用目标规划 求解生产安排问题中设备A禁止超时使用，则有刚性约束

2 x1 + 2 x 2 ≤ 12 .

另一类是可以不严格限制的，连同原线性规划的目标,构 成柔性约束(Soft Constraint).例如在求解生产安排中，我 们希望利润不低于1500元，则目标可表示为

⎧min{d − }; ⎪ ⎨ ⎪200 x1 + 300 x2 + d − − d + = 1500. ⎩

甲 乙 设备的生产能力/h 2 2 12 A/(h/件) 4 0 16 B/(h/件) 0 5 15 C/(h/件) 赢利/(元/件) 200 300

• 力求使利润指标不低于1500元 • 考虑到市场需求,甲、乙两种产品的产量比应尽量保持1:2 • 设备A为贵重设备，严格禁止超时使用 • 设备C可以适当加班，但要控制；设备B既要求充分利用，又 尽可能不加班，在重要性上，设备B是设备C的3倍 设甲、乙产品的产量分别为x1,

x2,建立模型：

设备C可以适当加班，但要控制， 则目标可表示为 甲、乙两种产品的产量尽量保 持1:2的比例，则目标可表示为 设备B既要求充分利用，又尽可能 不加班，则目标可表示为

⎧min{d + }; ⎪ ⎨ ⎪5 x2 + d − − d + = 15. ⎩ ⎧min{d + + d − }; ⎪ ⎨ ⎪2 x1 − x2 + d − − d + = 0. ⎩

⎧min{d + + d − }; ⎪ ⎨ ⎪4 x1 + d − − d + = 16. ⎩

x2;

Max z = 200 x 1 + 300 从上面的分析可以

看到： s. t. 2 x1 + 2 x2 ≤ 12 , •如果希望不等式保持大于等于，则极小化负偏差； 4 x1 ≤ 16, 5 x2 ≤ 15, •如果希望不等式保持小于等于，则极小化正偏差； x1 , x2 ≥ 0. •如果希望保持等式，则同时极小化正、负偏差．

3.目标的优先级与权系数

在目标规划模型中，目标的优先分为两个层 次，第一个层次是目标分成不同的优先级，在计 算目标规划时，必须先优化高优先级的目标，然 后再优化低优先级的目标。通常以P1,P2,...表示 不同的因子,并规定Pk>>Pk+1，第二个层次是目标 处于同一优先级，但两个目标的权重不一样，因 此两目标同时优化，用权系数的大小来表示目标 重要性的差别。

用目标规划方法求解

解：在生产安排问题中设备A是刚性约束，其余是 柔性约束．首先，最重要的指标是企业的利润， 将它的优先级列为第一级；其次，甲、乙两种产 品的产量保持1:2的比例，列为第二级；再次，设 备 B和C的工作时间要有所控制，列为第三级，设 备B的重要性是设备C的三倍，因此它们的权重不 一样。由此可以得到相应的目标规划模型。

+ − + min z = Pd1− + P2 (d2 + d2 ) + P (3d3+ + 3d3− + d4 ); 1 3

s. t. 2x1 + 2x2 ≤ 12,

200x1 + 300x2 + d1− − d1+ = 1500 ,

− + 2x1 − x2 + d2 − d2 = 0,

4x1 + d3− − d3+ = 16,

− + 5x2 + d4 − d4 = 15,

x1, x2 , di− , di+ ≥ 0, i = 1,2,3,4.

目标规划模型的实例

前面介绍了目标规划的求解方法，接着再介绍 几个目标规划模型的实例。

例 计算机公司生产管理问题

某计算机公司生产三种型号的笔记本电脑A,B,C。 这三种笔记本电脑需要在复杂的装配线上生产，生 产1台A,B,C型号的笔记本电脑分别需要5,8,12小时。 公司装配线正常的生产时间是每月1700小时。公司 营业部门估计A,B,C三种笔记本电脑的利润分别是 每台1000,1440,2520元，而公司预测这个月生产的笔 记本电脑能够全部售出。

例 计算机公司生产管理问题

公司经理考虑以下目标：

第一目标：充分利用正常的生产能力，避免开工不足； 第二目标：优先满足老客户的需求，A,B,C三种型号的电脑 50,50,80台，同时根据三种电脑的纯利润分配不同的权因子； 第三目标：限制装配线加班时间，不允许超过200小时； 第四目标：满足各种型号电脑的销售目标,A,B,C型号分别为 100,120,100台,再根据三种电脑的纯利润分配不同的权因子； 第五目标：装配线的加班时间尽可能少。

请列出相应的目标规划模型,并用LINGO软件求解。

解 建立目标约束。 (1) 装配线正常生产 设生产A,B,C型号的电脑为x1, x2, x3台， − d1 装配线正常生产时间未利用数， + d1 装配线加班时间， 希望装配线正常生产,避免开工不足,因此装配线 约

束目标为

⎧ min{ d }; ⎪ ⎨ ⎪5 x1 + 8 x 2 + 12 x 3 + d 1− − d 1+ = 1700 . ⎩

− 1

(2) 销售目标 优先满足老客户的需求，并根据三种电脑的纯 利润分配不同的权因子，A,B,C三种型号的电脑每 1000 1440 2520 小时的利润是 5 , 8 , 12 , 因此,老客户的

− − − ⎧ min{ 20 d 2 + 18 d 3 + 21 d 4 }; ⎪ − + ⎪ x 1 + d 2 − d 2 = 50 , ⎨ − + x 2 + d 3 − d 3 = 50 , ⎪ ⎪ − + x 3 + d 4 − d 4 = 80 . ⎩

销售目标约束为

(2) 销售目标 (接上) 再考虑一般销售，类似上面的讨论，得到

− − − ⎧ min{ 20 d 5 + 18 d 6 + 21 d 7 }; ⎪ − + ⎪ x1 + d 5 − d 5 = 100 , ⎨ − + x 2 + d 6 − d 6 = 120 , ⎪ ⎪ − + x 3 + d 7 − d 7 = 100 . ⎩

(3) 加班限制 首先是限制装配线加班时间，不允许超过200 小时，因此得到 ⎧ min{ d 8+ }; ⎪ ⎨ ⎪ 5 x1 + 8 x 2 + 12 x 3 + d 8− − d 8+ = 1900 . ⎩ 其次装配线的加班时间尽可能少，即

⎧ min{ d 1+ }; ⎪ ⎨ ⎪ 5 x1 + 8 x 2 + 12 x 3 + d 1− − d 1+ = 1700 . ⎩

− − − − min z = P1 d 1− + P2 ( 20 d 2 + 18 d 3 + 21 d 4 ) + P3 d 8 − − − + P4 ( 20 d 5 + 18 d 6 + 21 d 7 ) + P5 d 1+ ;

写出相应的目标规划模型：

s. t . 5 x1 + 8 x 2 + 12 x3 + d1− − d1+ = 1700 ,

− + x1 + d 2 − d 2 = 50 , − + x 2 + d 3 − d 3 = 50 , − + x 3 + d 4 − d 4 = 80 , − + x1 + d 5 − d 5 = 100 , − + x 2 + d 6 − d 6 = 120 , − + x 3 + d 7 − d 7 = 100 , − + 5 x1 + 8 x 2 + 12 x 3 + d 8 − d 8 = 1900

x1 , x 2 , d i− , d i+ ≥ 0, i = 1, 2,

,8 .

例音像店管理问题

某音像商店有5名全职售货员和4名兼职售货员。全职售货员 每月工作160小时，兼职售货员每月工作80小时。根据过去的 工作记录，全职售货员每小时销售CD25张，平均每小时工资 15元，加班工资每小时22.5元。兼职售货员每小时销售CD10 张，平均每小时工资10元，加班工资每小时10元。现在预测 下月CD销售量为27500张，商店每周开门营业6天，所以可能 要加班。另每出售一张CD盈利1.5元。 该商店经理认为，保持稳定的就业水平加上必要的加班，比 不加班但就业水平不稳定要好。但全职售货员如果加班过 多，就会因疲劳过度而造成效率下降，因此不允许每月加班 超过100小时。建立相应的目标规划模型，并运用LINGO软 件进行求解。

例2.3音像店管理问题

解 首先建立目标约束的优先级。 P1：下月的CD销售量达到27500张； P2： 保持全体售货员充分就业(即尽量满工作量）， 因为充分工作是良好劳资关系的重要因素，但对全 职售货员要比兼职售货员加倍优先考虑； P3： 限制全职售货员加班时间不超过100小时； P4： 尽量减少加班时间，但对两种售货员区别对 待，优先权因子由他们对利润的贡献而定。

第二，建立目标约束。 (1) 销售目标约束。设 x1 ：全体全

职售货员下月的工作时间； x2 ：全体兼职售货员下月的工作时间； d1− ：达不到销售目标的偏差； d1+ ：超过销售目标的偏差。 希望下月的销售量超过27500张CD片，因此销售 目标为

⎧ min{ d }; ⎪ ⎨ − + ⎪ 25 x1 + 10 x 2 + d 1 − d 1 = 27500 . ⎩

− 1

第二，建立目标约束。 (2) 尽量满工作量约束，设 − d 2 ：全体全职售货员下月的停工时间； + d 2 ：全体全职售货员下月的加班时间； − d3 ：全体兼职售货员下月的停工时间； d 3+ ：全体兼职售货员下月的加班时间。 由于希望保持全体售货员充分就业，同时加倍优 先考虑全职售货员,因此工作目标约束为

⎧ min{ 2 d 2− + d 3− }; ⎪ x 1 + d 2− − d 2+ = 800 , ⎨ ⎪ − + ⎩ x 2 + d 3 − d 3 = 320 .

第二，建立目标约束。 (3) 正常工作时间约束，设 − d 4 ：全体全职售货员下月加班不足100小时的偏差； + d 4 ：全体全职售货员下月加班超过100小时的偏差。 限制全职售货员加班时间不超过100小时，将加班约 束看成正常上班约束，不同的是右端加上100小时，因此 加班目标约束为

⎧ min{ d }; ⎪ ⎨ − + ⎪ x1 + d 4 − d 4 = 900 . ⎩

− 4

第二，建立目标约束。 接上(3) 另外，全职售货员加班1小时，商店得到的利润 为15元(25*1.5-22.5=15)，兼职售货员加班1小时，商店得 到的利润为5元(10*1.5-10=5)，因此加班1小时全职售货员 获得的利润是兼职售货员的3倍，故权因子之比为

d : d = 1 : 3,

所以，另一个加班目标约束为：

+ 2

+ 3

⎧ m in{3 d 2+ + d 3+ }; ⎪ − + ⎨ x1 + d 2 − d 2 = 800, ⎪ x 2 + d 3− − d 3+ = 320. ⎩

第三，按目标的优先级，写出相应的目标规划模型：

min z = P d + P2 d + P3 (2d + d ) + P4 (d + 3d );

− 1 1

+ 4

− 2

− 3

+ 2

+ 3

s. t. 25x1 + 10x2 + d − d = 27500 ,

− 1

+ 1

x1 + d − d = 800, x2 + d − d = 320, x1 + d − d = 900, x1, x2 , d , d ≥ 0, i = 1,2,3,4.

− i + i − 4 + 4 − 3 + 3

− 2

+ 2

Excel与Lingo数据交换

x