运筹学多目标规划

运筹学多目标规划演示文稿目前一页\总数五十七页\编于五点运筹学多目标规划目前二页\总数五十七页\编于五点一、多目标决策问题实例干部评估－德、才兼备教师晋升－教学、科研、论文等购买冰箱－价格、质量、耗电、品牌等球员选择－技术、体能、经验、心理找对象－容貌、学历、气质、家庭状况§1多目标决策简介目前三页\总数五十七页\编于五点二、多目标决策与多目标规划多目标决策多目标规划（MultipleObjectiveProgramming，决策变量连续）多准则决策（MultipleCriteriaDecisionMaking，决策变量离散，即有限方案）§1多目标决策简介目前四页\总数五十七页\编于五点三、多目标决策与单目标决策区别点评价与向量评价 单目标：方案dj←评价值f(dj)

多目标：方案dj←评价向量(f1(dj)，f2(dj)…，fp(dj))全序与半序:

方案di与dj之间 单目标问题:di<dj;di=dj;di>dj

多目标问题：除了这三种情况之外,还有一种情况 是不可比较大小决策者偏好：多目标决策过程中，反映决策者对 目标的偏好。§1多目标决策简介目前五页\总数五十七页\编于五点

解概念区别单目标决策的解只有一种（绝对）最优解;多目标决策的解有下面三种情况：绝对最优解d1807588d2758185d3767889d5787486d4858292绝对最优解数学外语专业解的类型目前六页\总数五十七页\编于五点

解概念区别单目标决策的解只有一种（绝对）最优解;多目标决策的解有下面三种情况：d1807588有效解d2758185有效解d3767889有效解劣解d4787486数学外语专业解的类型

绝对最优解劣解（如d4劣于d1

）有效解(pareto解)——非劣解目前七页\总数五十七页\编于五点§2多目标规划模型及其解的概念一、多目标规划举例例1：【喜糖问题】设市场上有甲级糖及乙级糖，单价分别为4元/斤及2元/斤。今要筹办一桩喜事。“筹备小组”计划总花费不超过40元，糖的总斤数不少于10斤，甲级糖不少于5斤。问如何确定最佳的采购方案。

约束条件：决策变量：甲级糖数量为x1，乙级糖数量为x2目前八页\总数五十七页\编于五点§2多目标规划模型及其解的概念目标函数：何为最佳？（1）总花费最小：minf1(x1,x2)=4x1+2x2

（2）糖的总数量最大：maxf2(x1,x2)=x1+x2

（3）甲级糖的数量最大：maxf3(x1,x2)=x1多目标规划问题目前九页\总数五十七页\编于五点§2多目标规划模型及其解的概念例2【投资决策问题】某投资开发公司拥有总资金A万元，今有n(≥2)个项目可供选择。设投资第i(i=1,…,n)个项目要用资金ai万元，预计可得到收益bi万元。问应如何使用总资金A万元，才能得到最佳的经济效益？1，投资第i个项目0，不投资第i个项目解：令

xi=约束条件：目前十页\总数五十七页\编于五点§2多目标规划模型及其解的概念目标函数：何为最佳的经济效益？（1）收益最大：（2）投资最少：多目标0-1规划问题目前十一页\总数五十七页\编于五点§2多目标规划模型及其解的概念二、多目标规划的模型决策变量：目标函数：…约束条件：目前十二页\总数五十七页\编于五点向量数学规划(VectorMathematicalProgramming)§2多目标规划模型及其解的概念多目标规划模型的向量表达形式记：则模型为：或目前十三页\总数五十七页\编于五点§2多目标规划模型及其解的概念一、多目标规划举例二、多目标规划的模型三、多目标规划解的概念目前十四页\总数五十七页\编于五点§2多目标规划模型及其解的概念三、多目标规划解的概念目前十五页\总数五十七页\编于五点§2多目标规划模型及其解的概念定义1

设X*∈R，若对任意X∈R，均有F(X*)≦F(X)，则称X*为问题（VMP）的绝对最优解。其全体记为R*ab。0f1(x)f2(x)x绝对最优解示意图

x*f注：绝对最优解往往不存在！目前十六页\总数五十七页\编于五点§2多目标规划模型及其解的概念定义2设X0∈R，若存在另一个可行解X1∈R，有F(X1)≤F(X0)，则称可行解X0相对于X1来说是劣解。注：决策中，劣解不会被考虑！x0f1(x)f2(x)x1*

Rpa*

x2*

f定义3

设∈R，若不存在X∈R，使F(X)≤F()，则称为问题的非劣解，又称有效解，或Pareto解。其全体记为。目前十七页\总数五十七页\编于五点§2多目标规划模型及其解的概念定义4

设∈R，若不存在X∈R，使F(X)<F()，则称为问题的弱有效解。其全体记为。注：有效解必是弱有效解。x0

Rwp*

ff1(x)f2(x)目前十八页\总数五十七页\编于五点§2多目标规划模型及其解的概念f20f1ABCDE劣解与有效解两个目标的最大化问题：目前十九页\总数五十七页\编于五点§2多目标规划模型及其解的概念多目标规划——解的关系定理1

，其中为单目标fi(X)上最优点集合。定理20

Rwp*

ff1(x)f2(x)xR1*

R2*Rpa*=Rab*目前二十页\总数五十七页\编于五点§2多目标规划模型及其解的概念多目标规划——解的关系定理3定理4目前二十一页\总数五十七页\编于五点§2多目标规划模型及其解的概念多目标规划——解的关系例1下图中，R1*=｛x1｝，R2*=｛x2｝，

x0f1(x)f2(x)x1Rpa*

x2f目前二十二页\总数五十七页\编于五点§2多目标规划模型及其解的概念多目标规划——解的关系

R3*Rp=3Rab*=φp=3Rab*≠φRR1*R2*RpaRwp*Rab*=Rpa*R1*R2*R3**目前二十三页\总数五十七页\编于五点§1多目标决策简介§2多目标规划模型及其解的概念§3多目标规划的解法多目标规划目前二十四页\总数五十七页\编于五点§3多目标规划的解法

求：有效解或弱有效解其中

方法分类评价函数法目标排序法

准备工作：目标函数规范化目前二十五页\总数五十七页\编于五点一、评价函数法:§3多目标规划的解法目前二十六页\总数五十七页\编于五点§3多目标规划的解法目前二十七页\总数五十七页\编于五点§3多目标规划的解法目前二十八页\总数五十七页\编于五点§3多目标规划的解法一、评价函数法

1.线性加权和法

2.理想点法

3.目标规划法二、目标排序法目前二十九页\总数五十七页\编于五点§3多目标规划的解法三种目前三十页\总数五十七页\编于五点§3多目标规划的解法目前三十一页\总数五十七页\编于五点§3多目标规划的解法

确定权系数常用方法：特尔菲法、层次分析法、α-法

α-法的步骤（以两个目标为例）：

U［F(X)］=α1f1(X)+α2f2(X)

(1)求解单目标优化问题(问题一)，记(问题二)，记目前三十二页\总数五十七页\编于五点§3多目标规划的解法（2）α-方法的出发点：U［F(X1)］=U［F(X2)］

(3)求解得X*

目前三十三页\总数五十七页\编于五点§3多目标规划的解法α-方法的几何意义：目标值空间0f2f21f22AU*=minUf11f12f1CB（1）平行直线簇α1f1+α2f2=c

；（2）同一条直线上X1与X2有相同的评价值，即有U［F(X1)］=U［F(X2)］。

目前三十四页\总数五十七页\编于五点§3多目标规划的解法例设有试用α-法求解。解：求解单目标优化问题，得求解LP目前三十五页\总数五十七页\编于五点§3多目标规划的解法一、评价函数法

1.线性加权和法（α-法确定权系数）

2.理想点法

3.目标规划法二、目标排序法目前三十六页\总数五十七页\编于五点§3多目标规划的解法2.理想点法基本思想：X的评价向量F(X)=(f1(X),f2(X),……,fp(X))越接近理想点越好。理想点：一般指由各单目标最优值组成的p维点0f1f2F(X)目前三十七页\总数五十七页\编于五点§3多目标规划的解法理想点法的步骤：（1）求理想点。求解p个单目标最优化问题

得理想点：（2）检验理想点。绝对最优点，则输出绝对最优解，，求解完毕。否则，转（3）。目前三十八页\总数五十七页\编于五点§3多目标规划的解法理想点法的步骤：（3）作评价函数。（4）求解Note:

上述评价函数是严格增函数，故按其求得的解是(VMP)的有效解。目前三十九页\总数五十七页\编于五点§3多目标规划的解法例：设f1(X)=-3x1+2x2，f2(X)=4x1+3x2都要求实现最大，约束集为R＝｛X|2x1+3x2≤18，2x1+x2≤10，x1，x2≥0，X∈R2｝，试用理想点法求解。

解：先分别求解两个单目标问题X(1)=(0,6),f1*=12；X(2)=(3,4)

，f2*=24

理想点F*=(f1*,f2*)=(12,24)

评价函数

X*=(0.53,5.65)，f1*=9.72,f2*=19.06。

目前四十页\总数五十七页\编于五点§3多目标规划的解法一、评价函数法

1.线性加权和法（α-法确定权系数）

2.理想点法

3.目标规划法二、目标排序法目前四十一页\总数五十七页\编于五点3目标规划法

（GoalProgramming）

是求解多目标规划的一种常用方法。该方法不考虑对各个目标进行极小化或极大化，而是希望在约束条件的限制下，每一目标尽可能地接近于事先给定的目的值。

（一）目标规划的思想目前四十二页\总数五十七页\编于五点例：某工厂生产Ⅰ、Ⅱ两种产品，有关数据如下表：ⅠⅡ资源量原材料2111设备1210利润810决策者在原材料供应受严格限制的基础上，考虑尽量满足如下条件：（1）首先，产品Ⅱ的产量不低于产品Ⅰ的产量；（2）其次，充分利用设备有效台时，不加班；（3）再次，利润额不小于56元。目前四十三页\总数五十七页\编于五点（二）目标规划的数学模型（1）在每个目标fi(X)上预先确定一个希望达到的目标值，得一目标值向量分析：（2）构造评价函数

（3）多目标决策问题单目标问题（其中R为问题的可行域）目前四十四页\总数五十七页\编于五点（4）为了求解(3)，引入类偏差变量负偏差正偏差可以证明（3）等价于目标约束（软约束）绝对约束（硬约束）目前四十五页\总数五十七页\编于五点实际问题中：①各目标可赋于不同的优先因子Pj；②相同优先因子的两个目标的差别，可分别赋于它们不同的权系数ωij

于是得到目标规划模型：目前四十六页\总数五十七页\编于五点目标规划模型的特点：（1）目标函数都是最小化，只有偏差变量和优先因子（不含一般决策变量）；（2）约束条件中既可包含目标约束，还可包含绝对约束；（3）目标约束均为等式；且一般在一个约束中同时含有正、负偏差变量；目前四十七页\总数五十七页\编于五点

另外，根据决策者的不同要求，目标函数有三种基本形式：

（2）要求超过目标值，评价函数为

（1）要求恰好达到目标值，评价函数为

（3）要求不超过目标值，评价函数为目前四十八页\总数五十七页\编于五点（三）目标规划建模举例例1：某工厂生产Ⅰ、Ⅱ两种产品，有关数据如下表：ⅠⅡ资源量原材料2111设备1210利润810决策者在原材料供应受严格限制的基础上，考虑尽量满足如下条件：（1）首先，产品Ⅱ的产量不低于产品Ⅰ的产量；（2）其次，充分利用设备有效台时，不加班；（3）再次，利润额不小于56元。目前四十九页\总数五十七页\编于五点例1：某工厂生产Ⅰ、Ⅱ两种产品，有关数据如下表：ⅠⅡ资源量原材料2111设备1210利润810决策者在原材料供应受严格限制的基础上考虑：（1）首先，产品Ⅱ的产量不低于产品Ⅰ

的产量；（2）其次，充分利用设备有效台时，不加班；（3）再次，利润额不小于56元。目前五十页\总数五十七页\编于五点有一纺织厂生产尼龙布和棉布，平均生产能力都是1km/h，工厂生产能力为每周80h。根据市场预测，下周最大销售量为：尼龙布为70km，棉布45km。尼龙布利润为2.5元/m，棉布利润为1.5元/m。工厂领导的管理目标如下：P1：保证职工正常上班，避免开工不足；P2：尽量达到最大销售量；

P3：尽量减少加班时间，限制加班时间不得超过10h。解：设决策变量x1、x2分别表示尼龙布和棉布的下周计划产量例2（P100例4.6）目前五十一页\总数五十七页\编于五点（四）目标规划的求解（1）图解法先考虑绝对约束；再考虑目标约束，并令目标约束中的偏差变量为0，作直线。①d1-d1+d2-d2+d3-d3+CBADHGEFx1x2O③②

Step1P1→△OBC

Step2P2→线段ED

Step3P3→目标规划的解：线段GD.其中，G(2,4),D(10/3,10/3)

注：该例求得最优解，且Z*=0.但大多问题可能无法满足所有约束，此时求满意解。目前五十二页\总数五十七页\编于五点例：求解目标规划①d4-d2-d2+d3-d3+CBADHGEF③②x1x2Od1+d1-d4+④分析：1）目标P1,P2→四边形ABCD；2）d3-的权系数大于d