多目标决策讲义 课件_第1页
多目标决策讲义 课件_第2页
多目标决策讲义 课件_第3页
多目标决策讲义 课件_第4页
多目标决策讲义 课件_第5页
已阅读5页,还剩119页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

管理决策分析裴凤peifeng@合肥工业大学管理学院

1管理决策分析裴凤1主要内容:第三章

多目标决策第一节多目标决策问题第二节化多目标为单目标的方法第三节目标分层法第四节目的规划法第五节逐步法2主要内容:第三章

多目标决策第一节多目标决策问题21.什么是多目标决策?干部选拔、大学生择业、购物2.多目标决策问题的特点目标多于一个目标之间的不可公度性目标之间的矛盾性31.什么是多目标决策?2.多目标决策问题的特点33.多目标决策问题的分类多属性决策问题(有限方案的多目标决策问题)多目标决策问题(无限方案的多目标决策问题)多准则决策问题前者的决策空间是离散的,后者是连续的;前者的选择余地是有限的、已知的,后者是无穷的、未知的。区别:43.多目标决策问题的分类多属性决策问题(有限方案的多目标准则(criteria)是对决策事物或现象有效性的某种度量,是事物或现象评价的基础。它在实际问题中有两种基本表现形式,即目标和属性。目标(objective)是关于被研究问题的某种决策者所希望达到的状态的陈述,它表示决策者的愿望或决策者所希望达到的、努力的方向。属性(attribute)是指方案所固有的特征、品质或性能参数,它是对基本目标达到程度的直接度量。对于每一种属性应该能够使用一定的方法来测量其水平的高低,即属性是可测得量,它反映了特定目标(该属性所联系的目标)被达到的程度。

4.基本术语5准则(criteria)是对决策事物或现象有效性的某种度量,第一节多目标决策问题一、多目标决策问题的一般形式f1(x),f2(x),…,fN(x)为目标函数gi(x)≤0,i=1,2,…,m为约束条件x为决策变量目标函数约束条件向量优化问题(Vectoroptimizationproblems,简称VOP)

Maxf(x)=(f1(x),f2(x),…,fN(x))gi(x)≤0,i=1,2,…,m(Vp)6第一节多目标决策问题一、多目标决策问题的一般形式f1(x)二、多目标决策问题解的概念最优解

设x*∈X,如果对任意的x∈X,均有f(x)≤f(x*),即对一切的j=1,2,…,N,均有fj(x)≤fj(x*),则称x*为多目标决策问题(Vp)的最优解。第一节多目标决策问题7二、多目标决策问题解的概念最优解第一节多目标决策问题7非劣解选好解f1f2ABCDEf1f2YABCDEFG二、多目标决策问题解的概念第一节多目标决策问题8非劣解选好解f1f2ABCDEf1f2ABCDEFG二、多目三、多目标决策方法的分类1.优化之前给出偏好2.优化之后给出偏好3.优化之中逐步给出偏好第一节多目标决策问题9三、多目标决策方法的分类1.优化之前给出偏好第一节多目标决第二节化多目标为单目标的方法1.数学规划法

设有N个目标f1(x),f2(x),…,fN(x),从中选择一个最重要的目标fk(x),使它满足最大或最小,而其它目标只要满足一定规格要求即可。从而构成了一个以重要目标fk(x)为单目标,以其余目标为约束的一个数学规划问题。10第二节化多目标为单目标的方法1.数学规划法设有N个例:某厂生产A、B两种产品以供应市场的需要。生产两种产品所需的设备台时、原料消耗定额及其限制量、单位产品利润等如下表所示。在制定生产计划时工厂决策者考虑了如下三个目标:第一,计划期内生产产品所获得的利润为最大;第二,为满足市场对不同产品的需要,产品A的产量必须为产品B的产量的1.5倍;第三,为充分利用设备台时,设备台时的使用时间不得少于11个单位。

产品资源AB资源限制设备台时原料单位利润234433.21212第二节化多目标为单目标的方法11例:某厂生产A、B两种产品以供应市场的需要。生产两种产品所需解:设x1为产品A的产量,x2为产品B的产量,则以利润最大作为目标,其它两个目标可作为约束条件,其数学模型如下:

第二节化多目标为单目标的方法12解:设x1为产品A的产量,x2为产品B的产量,则以利润最大作2.线性加权和法

当目标函数

f1(x),f2(x),…,fN(x)都要求最小(或最大)时,可构造新的目标函数

注:在运用线性加权和法时,所有的目标都必须具有相同的量纲。如果量纲不同,则需要统一量纲或做无量纲化处理。在多目标决策问题中,或由于各个目标的量纲不同,或有些目标值要求最大而有些要求最小,则可首先将目标值变换成效用值或无量纲值,然后再用线性加权和法计算新的目标函数值并进行比较,以决定方案取舍。

第二节化多目标为单目标的方法132.线性加权和法当目标函数f1(x),f2(x3.平方和加权法

基本思想:为所有目标fj(x),j=1,2,…,N确定一个预期达到的目标值fj*,使作出的决策与这些目标值越接近越好。构造评价函数

要求U(x)最小。其中权系数wj反映了各个偏差的重要性。第二节化多目标为单目标的方法143.平方和加权法基本思想:为所有目标fj(x),j4.理想点法

设有N个目标f1(x),f2(x),…,fN(x)

,每个目标单独优化后的最优值为则F*=(f1*,f2*,…,fN*)T是一个理想点。基本思想:定义一个范数,在这个范数意义下找一个点尽量接近理想点。第二节化多目标为单目标的方法154.理想点法设有N个目标f1(x),f2(x)5.费用——效益分析法

f1(x),f2(x),…,fs(x),fs+1(x),…,fN(x)费用型目标效益型目标第二节化多目标为单目标的方法165.费用——效益分析法f1(x),f2(x),…,6.功效系数法(几何平均法)

当目标达到最满意值时,取dj=1;当目标达到最差值时,取dj

=0。f1(x)f2(x)…fN(x)d1d2…dN功效系数dj∈[0,1],j=1,2,…,N适用情形:有的目标要求越大越好,有的要求越小越好,有的要求适中为好。用函数来描述目标fj(x)与功效系数dj之间的关系,称之为功效函数,表达式为dj=Fj(x)第二节化多目标为单目标的方法176.功效系数法(几何平均法)当目标达到最满意值时,取dj0xFj(x)(a)0x(b)0x(c)当fj越大越好时选用(a),越小越好时选用(b),适中时选用(c)。不同类型的目标应选用不同类型的功效函数Fj(x)Fj(x)第二节化多目标为单目标的方法180xFj(x)(a)0x(b)0x(c)当fj越大越好时

把fj(x)转化为dj后,用各目标的功效系数值的几何平均值作为评价函数,即

显然D越大越好(0≤D≤1)。

D的综合性很强,例如当某项指标dk很不满意时,dk=0,则D=0;如果各项指标都令人满意,di

≈1,则D=1。其实,功效系数D是加权平均法中乘法规则的特例:第二节化多目标为单目标的方法19把fj(x)转化为dj后,用各目标的功效系数值的几何平均第三节目标分层法1.完全分层法(字典序法)基本思想:把所有目标按照其重要性递减的顺序排列,首先求出第一重要目标的最优解集合X1,然后在集合X1中再求出第二重要目标的最优解集合X2,如此下去,直到把所有目标都求完为止,最后一个目标的最优解就是原多目标决策问题的最优解。

20第三节目标分层法1.完全分层法(字典序法)基本思想:把2.分层评价法基本思想:把N个目标分为s个优先层次,0≤s≤N。记第k层(k=1,2,…,s)所有目标的下标构成的集合为Ik。优先考虑第一层目标,其次考虑第二层目标,如此下去,最后再考虑第s层目标。

第三节目标分层法212.分层评价法基本思想:把N个目标分为s个优先层次,0≤3.重点目标法基本思想:先求出单目标fk(x)下的最优解集X1,然后在X1中求解由其余N-1个目标构成的新问题的有效解或弱有效解。适用情形:多目标决策问题中有一个最重要的目标fk(x),其余N-1个目标的重要程度难以区分。第三节目标分层法223.重点目标法基本思想:先求出单目标fk(x)下的最优解第四节目的规划法目的规划的数学模型目的规划的图解法目的规划的单纯形法

目的规划是在线性规划的基础上,为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。23第四节目的规划法目的规划的数学模型目的规划的图解法目的规

例1某厂计划在下一个生产周期内生产甲、乙两种产品,已知资料如表所示。试制定生产计划,使获得的利润最大?同时,根据市场预测,甲的销路不是太好,应尽可能少生产;乙的销路较好,可以扩大生产。试建立此问题的数学模型。一、目的规划模型产品资源甲乙资源限制钢材943600煤炭452000设备台时3103000单件利润70120第四节目的规划法24例1某厂计划在下一个生产周期内生产甲、乙两种产品,设:甲产品→

x1,乙产品→x2

MaxZ=70x1+120x29x1+4x2

≤36004x1+5x2

≤20003x1+10x2≤3000

x1

,

x2

≥0MaxZ1=70x1+120x2MinZ2=x1MaxZ3=x29x1+4x2

≤36004x1+5x2

≤20003x1+10x2≤3000

x1,x2

≥0在上例中,若工厂提出下列要求:

1.完成或超额完成利润指标50000元;2.产品甲不超过200件,产品乙不低于250件;3.现有钢材3600吨必须用完。第四节目的规划法25设:甲产品→x1,乙产品→x2MaxZ=70x1+目标值:预先给定的某个目标的一个期望值。实现值或决策值:当决策变量xj

被求出以后,目标函数的对应值.偏差变量(事先无法确定的未知数):实现值和目标值之间的差异,记为d。正偏差变量:实现值超过目标值的部分,记为d+。负偏差变量:实现值未达到目标值的部分,记为d-。1.目标值和偏差变量相关概念在一次决策中,实现值不可能既超过目标值又未达到目标值,故有

d+×d-

=0,并规定d+≥0,d-≥0第四节目的规划法26目标值:预先给定的某个目标的一个期望值。1.目标值和偏差变量例2

对例1中的三个目标进行处理

其结果有两种可能:70x1+120x2≥50000→70x1+120x2-d1+=50000或70x1+120x2≤50000→70x1+120x2+d1-=50000实际情况只有一种可能,当然优化前并不知道,而建模时却都要考虑到,因此,将上两式合成:(1)完成或超额完成利润指标50000元第四节目的规划法27例2对例1中的三个目标进行处理其结果有两种可能:实际情(2)产品甲不超过200件,产品乙不低于250件;(3)3600吨钢材必须用完第四节目的规划法28(2)产品甲不超过200件,产品乙不低于250件;(3)

线性规划问题的目标函数,在给定了目标值并引入正、负偏差变量后,可变换为目标约束。2.目标约束和绝对约束

绝对约束:必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束,有一个不满足就无可行解。所以,绝对约束是硬约束。目标约束(软约束)绝对约束(硬约束)第四节目的规划法29线性规划问题的目标函数,在给定了目标值并引入正、负偏差变3.目标函数⑴要求恰好达到规定的目标值,即正、负偏差变量要尽可能小,则MinZ=f(d++d-)。⑵要求不超过目标值,即允许达不到目标值,也就是正偏差变量尽可能小,则MinZ=f(d+)。⑶要求不低于目标值,即超过量不限,也就是负偏差变量尽可能小,则MinZ=f(d-)。

对于由绝对约束转化而来的目标函数,也照上述处理即可。目标函数要求总偏差量最小,记为MinZ=f(d+,d-)。一般说来,有以下三种情况,但只能出现其中之一:第四节目的规划法303.目标函数⑴要求恰好达到规定的目标值,即正、负偏差变量要

优先因子Pk

是将决策目标按其重要程度排序并表示出来。P1>>P2>>…>>Pk>>Pk+1>>…>>PK,k=1,2,…,K。

权系数ωk

区别具有相同优先因子的两个目标的差别,决策者可视具体情况而定。

对于这种解来说,前面的目标可以保证实现或部分实现,而后面的目标就不一定能保证实现或部分实现,有些可能就不能实现。4.优先因子(优先等级)与权系数

5.满意解(具有层次意义的解)第四节目的规划法31优先因子Pk是将决策目标按其重要程度排序并表示对于例1中的目标:1.完成或超额完成利润指标50000元;2.产品甲不超过200件,产品乙不低于250件;3.现有钢材3600吨必须用完。若实现值没有达到目标,则存在偏差,希望按目标先后尽可能使偏差最小。

目标2有两个要求,且具有相同的优先因子,因此需要确定权系数。本题可用单件利润比作为权系数即70:120,化简为7:12。第四节目的规划法32对于例1中的目标:目标2有两个要求,且具有相同的优先因子,因目的规划模型为:第四节目的规划法33目的规划模型为:第四节目的规划法33例3

某厂生产Ⅰ、Ⅱ两种产品,有关数据如表所示。试求获利最大的生产方案。要求考虑:1.产品Ⅱ的产量不低于产品Ⅰ的产量;2.充分利用设备有效台时,不加班;3.利润不小于56元。设:Ⅰ、Ⅱ产品产量分别为x1,x2

ⅠⅡ限量原材料2111设备(台时)1210单件利润810第四节目的规划法34例3某厂生产Ⅰ、Ⅱ两种产品,有关数据如表所示。试求获目的规划模型:第四节目的规划法35目的规划模型:第四节目的规划法35目的规划模型的一般形式:第四节目的规划法36目的规划模型的一般形式:第四节目的规划法36目的规划的建模步骤1.根据问题所提出的各目标与条件,确定目标值,列出目标约束与绝对约束;4.对同一优先等级中的各偏差变量,若需要可按其重要程度的不同,赋予相应的权系数ωkl+和ωkl-。3.给各目标赋予相应的优先因子Pk(k=1,2,…,K)。2.根据决策者的需要,将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。其中,ωkl-和ωkl+分别为第k个目标中第l个子目标的优先权。第四节目的规划法37目的规划的建模步骤1.根据问题所提出的各目标与条件,确定目标5.根据决策者的要求,按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的、要求实现极小化的目标函数,即达成函数。⑴恰好达到目标值,取dl++dl-。⑵不希望低于目标值,取dl-。⑶不希望超过目标值,取dl+。第四节目的规划法385.根据决策者的要求,按下列情况之一构造一个由优先因子和权系

图解法同样适用两个变量的目标规划问题,但其操作简单,原理一目了然。同时,也有助于理解一般目标规划的求解原理和过程。步骤:1.确定各约束条件的可行域,即将所有约束条件(包括目标约束和绝对约束,暂不考虑正负偏差变量)在坐标平面上表示出来;2.在目标约束所代表的边界线上,用箭头标出正、负偏差变量值增大的方向;二、目的规划的图解法第四节目的规划法39图解法同样适用两个变量的目标规划问题,但其操作简单3.求满足最高优先等级目标的解;4.转到下一个优先等级的目标,在不破坏所有较高优先等级目标的前提下,求出该优先等级目标的解;5.重复4,直到所有优先等级的目标都已审查完毕为止;6.确定最优解或满意解。例4

用图解法求解目标规划问题第四节目的规划法403.求满足最高优先等级目标的解;例4用图解法求解012345678123456

⑴⑵⑶Ax2

x1BC

B(0.6250,4.6875)C(0,5.2083),B、C线段上的所有点均是该问题的解(无穷多最优解)。第四节目的规划法4101234练习:用图解法求解下列目标规划问题第四节目的规划法42练习:用图解法求解下列目标规划问题第四节目的规划法42⑴⑵⑶⑷CD结论:有无穷多最优解。C(2,4),D(10/3,10/3)第四节目的规划法43⑴⑵⑶⑷CD结论:有无穷多最优解。C(2,4),D(10/三、目的规划的单纯形法单纯形法的基本思想:确定初始基可行解检验结束Y旋转运算寻找新的基可行解N第四节目的规划法44三、目的规划的单纯形法单纯形法的基本思想:确定初始基可行解检例5

已知一个生产计划的线性规划模型为其中目标函数为总利润,x1,x2为产品A,B产量。现有下列目标:

1.要求总利润必须超过2500元;

2.为避免积压,A,

B的生产量不超过60件和100件;

3.由于甲资源供应比较紧张,不要超过现有量140。试建立目标规划模型,并用单纯形法求解。第四节目的规划法45例5已知一个生产计划的线性规划模型为其中目标函数为总利润P1P3P2第四节目的规划法46P1P3P2第四节目的规划法46cj00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-250030121-10000000d2-14021001-100000d3-601000001-1000d4-100010000001-1σkjP1

-2500-30-1201000000P2

000000002.501P3

00000010000θ=min{2500/30,140/2,60/1,-}=60,故d3-为换出变量。σ

=2.5P2-(0×P1+0×0-1×0+0×0)=2.5P2,将2.5填P2行。第四节目的规划法47cj00P100P302.5P20P2CBXBbx1x2d1cj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-7000121-100-3030000d2-2001001-1-22000x1601000001-1000d4-100010000001-1σkjP1

-7000-12010030-3000P2

000000002.501P3

00000010000θ=min{700/30,20/2,-,-}=10,故d2-为换出变量。σ

=2.5P2-(30P1+2×0-1×0+0×0)=2.5P2-30P1第四节目的规划法48cj00P100P302.5P20P2CBXBbx1x2dcj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-4000-31-1-151500002.5P2d3+1001/2001/2-1/2-11000x17011/2001/2-1/200000d4-100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min{400/15,-,-,-}=10,故d1-为换出变量。σ

=0-(-15P1+2.5P2/2+1/2×0+0×0)=15P1-2.5/249cj00P100P302.5P20P2CBXBbx1x2dcj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P3d2+80/30-1/51/15-1/15-1100002.5P2d3+70/302/51/30-1/3000-11000x1250/312/51/30-1/300000000d4-100010000001-1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min{-,350/6,1250/6,100/1}=75,故d3+为换出变量。第四节目的规划法50cj00P100P302.5P20P2CBXBbx1x2dcj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P3d2+115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000d4-125/300-1/121/12005/2-5/21-1σkjP1

00010000000P2

000000005/201P3

-115/300-1/121/12101/2-1/200表中P3行有负检验数,说明P3

级目标没有实现,但已无法改进,得到满意解

x1=60,x2=175/3,d2+

=115/3,d4-

=125/3。第四节目的规划法51cj00P100P302.5P20P2CBXBbx1x2d

结果分析:计算结果表明,工厂应生产A产品60件,B产品175/3件,2500元的利润目标刚好达到。d4-

=125/3,表明产品B比最高限额少125/3件,满足要求。d2+

=115/3表明甲资源超过库存115/3公斤,该目标没有达到。即甲资源多消耗115/3公斤,刚好实现2500元的利润目标。而按现有消耗水平和资源库存量,无法实现利润目标。

可考虑如下措施:降低A、B产品对甲资源的消耗量,以满足现有甲资源库存量的目标;或改变P3级目标值,增加甲资源115/3公斤。

若很难实现上述措施,则需改变现有目标的优先等级,以取得可行的满意解果。第四节目的规划法52结果分析:计算结果表明,工厂应生产A产品60件1.建立初始单纯形表。

一般假定初始解在原点,即以约束条件中的所有负偏差变量或松弛变量为初始基变量,按目标优先等级从左至右分别计算出各列的检验数,填入表的下半部。2.检验是否为满意解。判别准则如下:

按优先级别从高到低依次检查各检验数行。

单纯形法的计算步骤检查Pk这一行的检验数σkj(j=1,2,…,n+2m).若Pk这一行某些负检验数的同列上面(较高优先等级)没有正检验数,说明未得到满意解,应继续改进,转到第3步;若Pk这一行全部负检验数的同列上面(较高优先等级)都有正检验数,说明目标虽没达到,但已不能改进,故得满意解,转到第6步。第四节目的规划法531.建立初始单纯形表。2.检验是否为满意解。判别准则如下:3.确定进基变量。

在Pk行,从那些上面没有正检验数的负检验数中,选绝对值最大者,对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者,则依次比较它们各列下部的检验数,取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定,则选最左边的变量(变量下标小者)为进基变量。4.确定出基变量

其方法同线性规划,即依据最小比值原则。故确定xr为出基变量。若有几个相同的行可供选择时,选最上面那一行所对应的变量为xr。第四节目的规划法543.确定进基变量。4.确定出基变量第四节目的规划法545.旋转运算(变量迭代)。

以为ars主元素进行旋转运算,得到新的单纯形表,获得一组新解,返回到第2步。6.对求得的解进行分析

若计算结果满意,停止运算;若不满意,需修改模型,即调整目标优先等级和权系数,或者改变目标值,重新进行第1步。第四节目的规划法555.旋转运算(变量迭代)。6.对求得的解进行分析第四节目练习:用单纯形法求解下列目的规划问题第四节目的规划法56练习:用单纯形法求解下列目的规划问题第四节目的规划法56cj

000P1

P2

P2P3

00CBXBbx1x2d1-d1+d2-d2+d3-d3+

x3

0d1-01-11-100000P2d2-1012001-1000

P3

d3-5681000001-100

x3

11210000001σkjP1

0000100000P2

-10-1-20002000P3

-56-8-100000010θ=min{-,10/2,56/10,11/1}=5,故d2-为换出变量。第四节目的规划法57cj000P1P2P2P300CBXBbx1x2dcj

000P1

P2

P2P3

00CBXBbx1x2d1-d1+d2-d2+d3-d3+

x3

0d1-53/201-11/2-1/20000x251/21001/2-1/2000

P3

d3-63000-551-100

x3

63/2000-1/21/2001σkjP1

0000100000P2

0000011000P3

-6-30005-5010θ=min{10/3,10,2,4}=2,故d3-为换出变量。第四节目的规划法58cj000P1P2P2P300CBXBbx1x2dcj

000P1

P2

P2P3

00CBXBbx1x2d1-d1+d2-d2+d3-d3+

x3

0d1-2001-13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300

x3

300002-2-1/21/21σkjP1

0000100000P2

0000011000P3

0000000100最优解为x1=2,x2=4。但非基变量d3+的检验数为零,故此题有无穷多最优解。θ=min{4,24,-,6}=4,故d1-为换出变量。第四节目的规划法59cj000P1P2P2P300CBXBbx1x2dcj

000P1

P2

P2P3

00CBXBbx1x2d1-d1+d2-d2+d3-d3+

x3

0d3+4002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000

x3

100-1-1-11001σkjP1

0000100000P2

0000011000P3

0000000100最优解为x1=10/3,,x2=10/3。第四节目的规划法60cj000P1P2P2P300CBXBbx1x2d例6

某纺织厂生产尼龙布和棉布,平均生产能力是每小时1千米。工厂开工能力为每周80小时。根据市场预测,每周最大销售量尼龙布70千米,棉布45千米。尼龙布单位利润为每米2.5元,棉布每米1.5元。厂家确定四级管理目标:

P1:保证正常生产,避免开工不足;

P2:限制加班时间,不超过10小时;

P3:尽量达到最大销售量,尼龙布70千米,棉布45千米。

P4:尽可能减少加班时间。试建立这个问题的目标规划模型。设x1,x2分别为尼龙布和棉布的周产量第四节目的规划法61例6某纺织厂生产尼龙布和棉布,平均生产能力是每小时1千米。

P1:保证正常生产,避免开工不足

P2:限制加班时间,不超过10小时

P3:尽量达到最大销售量

P4:尽可能减少加班时间

P1、P4

P3

P3

P2目的规划模型为:第四节目的规划法62P1:保证正常生产,避免开工不足P1、P4目的规划模型管理决策分析裴凤peifeng@合肥工业大学管理学院

63管理决策分析裴凤1主要内容:第三章

多目标决策第一节多目标决策问题第二节化多目标为单目标的方法第三节目标分层法第四节目的规划法第五节逐步法64主要内容:第三章

多目标决策第一节多目标决策问题21.什么是多目标决策?干部选拔、大学生择业、购物2.多目标决策问题的特点目标多于一个目标之间的不可公度性目标之间的矛盾性651.什么是多目标决策?2.多目标决策问题的特点33.多目标决策问题的分类多属性决策问题(有限方案的多目标决策问题)多目标决策问题(无限方案的多目标决策问题)多准则决策问题前者的决策空间是离散的,后者是连续的;前者的选择余地是有限的、已知的,后者是无穷的、未知的。区别:663.多目标决策问题的分类多属性决策问题(有限方案的多目标准则(criteria)是对决策事物或现象有效性的某种度量,是事物或现象评价的基础。它在实际问题中有两种基本表现形式,即目标和属性。目标(objective)是关于被研究问题的某种决策者所希望达到的状态的陈述,它表示决策者的愿望或决策者所希望达到的、努力的方向。属性(attribute)是指方案所固有的特征、品质或性能参数,它是对基本目标达到程度的直接度量。对于每一种属性应该能够使用一定的方法来测量其水平的高低,即属性是可测得量,它反映了特定目标(该属性所联系的目标)被达到的程度。

4.基本术语67准则(criteria)是对决策事物或现象有效性的某种度量,第一节多目标决策问题一、多目标决策问题的一般形式f1(x),f2(x),…,fN(x)为目标函数gi(x)≤0,i=1,2,…,m为约束条件x为决策变量目标函数约束条件向量优化问题(Vectoroptimizationproblems,简称VOP)

Maxf(x)=(f1(x),f2(x),…,fN(x))gi(x)≤0,i=1,2,…,m(Vp)68第一节多目标决策问题一、多目标决策问题的一般形式f1(x)二、多目标决策问题解的概念最优解

设x*∈X,如果对任意的x∈X,均有f(x)≤f(x*),即对一切的j=1,2,…,N,均有fj(x)≤fj(x*),则称x*为多目标决策问题(Vp)的最优解。第一节多目标决策问题69二、多目标决策问题解的概念最优解第一节多目标决策问题7非劣解选好解f1f2ABCDEf1f2YABCDEFG二、多目标决策问题解的概念第一节多目标决策问题70非劣解选好解f1f2ABCDEf1f2ABCDEFG二、多目三、多目标决策方法的分类1.优化之前给出偏好2.优化之后给出偏好3.优化之中逐步给出偏好第一节多目标决策问题71三、多目标决策方法的分类1.优化之前给出偏好第一节多目标决第二节化多目标为单目标的方法1.数学规划法

设有N个目标f1(x),f2(x),…,fN(x),从中选择一个最重要的目标fk(x),使它满足最大或最小,而其它目标只要满足一定规格要求即可。从而构成了一个以重要目标fk(x)为单目标,以其余目标为约束的一个数学规划问题。72第二节化多目标为单目标的方法1.数学规划法设有N个例:某厂生产A、B两种产品以供应市场的需要。生产两种产品所需的设备台时、原料消耗定额及其限制量、单位产品利润等如下表所示。在制定生产计划时工厂决策者考虑了如下三个目标:第一,计划期内生产产品所获得的利润为最大;第二,为满足市场对不同产品的需要,产品A的产量必须为产品B的产量的1.5倍;第三,为充分利用设备台时,设备台时的使用时间不得少于11个单位。

产品资源AB资源限制设备台时原料单位利润234433.21212第二节化多目标为单目标的方法73例:某厂生产A、B两种产品以供应市场的需要。生产两种产品所需解:设x1为产品A的产量,x2为产品B的产量,则以利润最大作为目标,其它两个目标可作为约束条件,其数学模型如下:

第二节化多目标为单目标的方法74解:设x1为产品A的产量,x2为产品B的产量,则以利润最大作2.线性加权和法

当目标函数

f1(x),f2(x),…,fN(x)都要求最小(或最大)时,可构造新的目标函数

注:在运用线性加权和法时,所有的目标都必须具有相同的量纲。如果量纲不同,则需要统一量纲或做无量纲化处理。在多目标决策问题中,或由于各个目标的量纲不同,或有些目标值要求最大而有些要求最小,则可首先将目标值变换成效用值或无量纲值,然后再用线性加权和法计算新的目标函数值并进行比较,以决定方案取舍。

第二节化多目标为单目标的方法752.线性加权和法当目标函数f1(x),f2(x3.平方和加权法

基本思想:为所有目标fj(x),j=1,2,…,N确定一个预期达到的目标值fj*,使作出的决策与这些目标值越接近越好。构造评价函数

要求U(x)最小。其中权系数wj反映了各个偏差的重要性。第二节化多目标为单目标的方法763.平方和加权法基本思想:为所有目标fj(x),j4.理想点法

设有N个目标f1(x),f2(x),…,fN(x)

,每个目标单独优化后的最优值为则F*=(f1*,f2*,…,fN*)T是一个理想点。基本思想:定义一个范数,在这个范数意义下找一个点尽量接近理想点。第二节化多目标为单目标的方法774.理想点法设有N个目标f1(x),f2(x)5.费用——效益分析法

f1(x),f2(x),…,fs(x),fs+1(x),…,fN(x)费用型目标效益型目标第二节化多目标为单目标的方法785.费用——效益分析法f1(x),f2(x),…,6.功效系数法(几何平均法)

当目标达到最满意值时,取dj=1;当目标达到最差值时,取dj

=0。f1(x)f2(x)…fN(x)d1d2…dN功效系数dj∈[0,1],j=1,2,…,N适用情形:有的目标要求越大越好,有的要求越小越好,有的要求适中为好。用函数来描述目标fj(x)与功效系数dj之间的关系,称之为功效函数,表达式为dj=Fj(x)第二节化多目标为单目标的方法796.功效系数法(几何平均法)当目标达到最满意值时,取dj0xFj(x)(a)0x(b)0x(c)当fj越大越好时选用(a),越小越好时选用(b),适中时选用(c)。不同类型的目标应选用不同类型的功效函数Fj(x)Fj(x)第二节化多目标为单目标的方法800xFj(x)(a)0x(b)0x(c)当fj越大越好时

把fj(x)转化为dj后,用各目标的功效系数值的几何平均值作为评价函数,即

显然D越大越好(0≤D≤1)。

D的综合性很强,例如当某项指标dk很不满意时,dk=0,则D=0;如果各项指标都令人满意,di

≈1,则D=1。其实,功效系数D是加权平均法中乘法规则的特例:第二节化多目标为单目标的方法81把fj(x)转化为dj后,用各目标的功效系数值的几何平均第三节目标分层法1.完全分层法(字典序法)基本思想:把所有目标按照其重要性递减的顺序排列,首先求出第一重要目标的最优解集合X1,然后在集合X1中再求出第二重要目标的最优解集合X2,如此下去,直到把所有目标都求完为止,最后一个目标的最优解就是原多目标决策问题的最优解。

82第三节目标分层法1.完全分层法(字典序法)基本思想:把2.分层评价法基本思想:把N个目标分为s个优先层次,0≤s≤N。记第k层(k=1,2,…,s)所有目标的下标构成的集合为Ik。优先考虑第一层目标,其次考虑第二层目标,如此下去,最后再考虑第s层目标。

第三节目标分层法832.分层评价法基本思想:把N个目标分为s个优先层次,0≤3.重点目标法基本思想:先求出单目标fk(x)下的最优解集X1,然后在X1中求解由其余N-1个目标构成的新问题的有效解或弱有效解。适用情形:多目标决策问题中有一个最重要的目标fk(x),其余N-1个目标的重要程度难以区分。第三节目标分层法843.重点目标法基本思想:先求出单目标fk(x)下的最优解第四节目的规划法目的规划的数学模型目的规划的图解法目的规划的单纯形法

目的规划是在线性规划的基础上,为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。85第四节目的规划法目的规划的数学模型目的规划的图解法目的规

例1某厂计划在下一个生产周期内生产甲、乙两种产品,已知资料如表所示。试制定生产计划,使获得的利润最大?同时,根据市场预测,甲的销路不是太好,应尽可能少生产;乙的销路较好,可以扩大生产。试建立此问题的数学模型。一、目的规划模型产品资源甲乙资源限制钢材943600煤炭452000设备台时3103000单件利润70120第四节目的规划法86例1某厂计划在下一个生产周期内生产甲、乙两种产品,设:甲产品→

x1,乙产品→x2

MaxZ=70x1+120x29x1+4x2

≤36004x1+5x2

≤20003x1+10x2≤3000

x1

,

x2

≥0MaxZ1=70x1+120x2MinZ2=x1MaxZ3=x29x1+4x2

≤36004x1+5x2

≤20003x1+10x2≤3000

x1,x2

≥0在上例中,若工厂提出下列要求:

1.完成或超额完成利润指标50000元;2.产品甲不超过200件,产品乙不低于250件;3.现有钢材3600吨必须用完。第四节目的规划法87设:甲产品→x1,乙产品→x2MaxZ=70x1+目标值:预先给定的某个目标的一个期望值。实现值或决策值:当决策变量xj

被求出以后,目标函数的对应值.偏差变量(事先无法确定的未知数):实现值和目标值之间的差异,记为d。正偏差变量:实现值超过目标值的部分,记为d+。负偏差变量:实现值未达到目标值的部分,记为d-。1.目标值和偏差变量相关概念在一次决策中,实现值不可能既超过目标值又未达到目标值,故有

d+×d-

=0,并规定d+≥0,d-≥0第四节目的规划法88目标值:预先给定的某个目标的一个期望值。1.目标值和偏差变量例2

对例1中的三个目标进行处理

其结果有两种可能:70x1+120x2≥50000→70x1+120x2-d1+=50000或70x1+120x2≤50000→70x1+120x2+d1-=50000实际情况只有一种可能,当然优化前并不知道,而建模时却都要考虑到,因此,将上两式合成:(1)完成或超额完成利润指标50000元第四节目的规划法89例2对例1中的三个目标进行处理其结果有两种可能:实际情(2)产品甲不超过200件,产品乙不低于250件;(3)3600吨钢材必须用完第四节目的规划法90(2)产品甲不超过200件,产品乙不低于250件;(3)

线性规划问题的目标函数,在给定了目标值并引入正、负偏差变量后,可变换为目标约束。2.目标约束和绝对约束

绝对约束:必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束,有一个不满足就无可行解。所以,绝对约束是硬约束。目标约束(软约束)绝对约束(硬约束)第四节目的规划法91线性规划问题的目标函数,在给定了目标值并引入正、负偏差变3.目标函数⑴要求恰好达到规定的目标值,即正、负偏差变量要尽可能小,则MinZ=f(d++d-)。⑵要求不超过目标值,即允许达不到目标值,也就是正偏差变量尽可能小,则MinZ=f(d+)。⑶要求不低于目标值,即超过量不限,也就是负偏差变量尽可能小,则MinZ=f(d-)。

对于由绝对约束转化而来的目标函数,也照上述处理即可。目标函数要求总偏差量最小,记为MinZ=f(d+,d-)。一般说来,有以下三种情况,但只能出现其中之一:第四节目的规划法923.目标函数⑴要求恰好达到规定的目标值,即正、负偏差变量要

优先因子Pk

是将决策目标按其重要程度排序并表示出来。P1>>P2>>…>>Pk>>Pk+1>>…>>PK,k=1,2,…,K。

权系数ωk

区别具有相同优先因子的两个目标的差别,决策者可视具体情况而定。

对于这种解来说,前面的目标可以保证实现或部分实现,而后面的目标就不一定能保证实现或部分实现,有些可能就不能实现。4.优先因子(优先等级)与权系数

5.满意解(具有层次意义的解)第四节目的规划法93优先因子Pk是将决策目标按其重要程度排序并表示对于例1中的目标:1.完成或超额完成利润指标50000元;2.产品甲不超过200件,产品乙不低于250件;3.现有钢材3600吨必须用完。若实现值没有达到目标,则存在偏差,希望按目标先后尽可能使偏差最小。

目标2有两个要求,且具有相同的优先因子,因此需要确定权系数。本题可用单件利润比作为权系数即70:120,化简为7:12。第四节目的规划法94对于例1中的目标:目标2有两个要求,且具有相同的优先因子,因目的规划模型为:第四节目的规划法95目的规划模型为:第四节目的规划法33例3

某厂生产Ⅰ、Ⅱ两种产品,有关数据如表所示。试求获利最大的生产方案。要求考虑:1.产品Ⅱ的产量不低于产品Ⅰ的产量;2.充分利用设备有效台时,不加班;3.利润不小于56元。设:Ⅰ、Ⅱ产品产量分别为x1,x2

ⅠⅡ限量原材料2111设备(台时)1210单件利润810第四节目的规划法96例3某厂生产Ⅰ、Ⅱ两种产品,有关数据如表所示。试求获目的规划模型:第四节目的规划法97目的规划模型:第四节目的规划法35目的规划模型的一般形式:第四节目的规划法98目的规划模型的一般形式:第四节目的规划法36目的规划的建模步骤1.根据问题所提出的各目标与条件,确定目标值,列出目标约束与绝对约束;4.对同一优先等级中的各偏差变量,若需要可按其重要程度的不同,赋予相应的权系数ωkl+和ωkl-。3.给各目标赋予相应的优先因子Pk(k=1,2,…,K)。2.根据决策者的需要,将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。其中,ωkl-和ωkl+分别为第k个目标中第l个子目标的优先权。第四节目的规划法99目的规划的建模步骤1.根据问题所提出的各目标与条件,确定目标5.根据决策者的要求,按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的、要求实现极小化的目标函数,即达成函数。⑴恰好达到目标值,取dl++dl-。⑵不希望低于目标值,取dl-。⑶不希望超过目标值,取dl+。第四节目的规划法1005.根据决策者的要求,按下列情况之一构造一个由优先因子和权系

图解法同样适用两个变量的目标规划问题,但其操作简单,原理一目了然。同时,也有助于理解一般目标规划的求解原理和过程。步骤:1.确定各约束条件的可行域,即将所有约束条件(包括目标约束和绝对约束,暂不考虑正负偏差变量)在坐标平面上表示出来;2.在目标约束所代表的边界线上,用箭头标出正、负偏差变量值增大的方向;二、目的规划的图解法第四节目的规划法101图解法同样适用两个变量的目标规划问题,但其操作简单3.求满足最高优先等级目标的解;4.转到下一个优先等级的目标,在不破坏所有较高优先等级目标的前提下,求出该优先等级目标的解;5.重复4,直到所有优先等级的目标都已审查完毕为止;6.确定最优解或满意解。例4

用图解法求解目标规划问题第四节目的规划法1023.求满足最高优先等级目标的解;例4用图解法求解012345678123456

⑴⑵⑶Ax2

x1BC

B(0.6250,4.6875)C(0,5.2083),B、C线段上的所有点均是该问题的解(无穷多最优解)。第四节目的规划法10301234练习:用图解法求解下列目标规划问题第四节目的规划法104练习:用图解法求解下列目标规划问题第四节目的规划法42⑴⑵⑶⑷CD结论:有无穷多最优解。C(2,4),D(10/3,10/3)第四节目的规划法105⑴⑵⑶⑷CD结论:有无穷多最优解。C(2,4),D(10/三、目的规划的单纯形法单纯形法的基本思想:确定初始基可行解检验结束Y旋转运算寻找新的基可行解N第四节目的规划法106三、目的规划的单纯形法单纯形法的基本思想:确定初始基可行解检例5

已知一个生产计划的线性规划模型为其中目标函数为总利润,x1,x2为产品A,B产量。现有下列目标:

1.要求总利润必须超过2500元;

2.为避免积压,A,

B的生产量不超过60件和100件;

3.由于甲资源供应比较紧张,不要超过现有量140。试建立目标规划模型,并用单纯形法求解。第四节目的规划法107例5已知一个生产计划的线性规划模型为其中目标函数为总利润P1P3P2第四节目的规划法108P1P3P2第四节目的规划法46cj00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-250030121-10000000d2-14021001-100000d3-601000001-1000d4-100010000001-1σkjP1

-2500-30-1201000000P2

000000002.501P3

00000010000θ=min{2500/30,140/2,60/1,-}=60,故d3-为换出变量。σ

=2.5P2-(0×P1+0×0-1×0+0×0)=2.5P2,将2.5填P2行。第四节目的规划法109cj00P100P302.5P20P2CBXBbx1x2d1cj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-7000121-100-3030000d2-2001001-1-22000x1601000001-1000d4-100010000001-1σkjP1

-7000-12010030-3000P2

000000002.501P3

00000010000θ=min{700/30,20/2,-,-}=10,故d2-为换出变量。σ

=2.5P2-(30P1+2×0-1×0+0×0)=2.5P2-30P1第四节目的规划法110cj00P100P302.5P20P2CBXBbx1x2dcj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-4000-31-1-151500002.5P2d3+1001/2001/2-1/2-11000x17011/2001/2-1/200000d4-100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min{400/15,-,-,-}=10,故d1-为换出变量。σ

=0-(-15P1+2.5P2/2+1/2×0+0×0)=15P1-2.5/2111cj00P100P302.5P20P2CBXBbx1x2dcj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P3d2+80/30-1/51/15-1/15-1100002.5P2d3+70/302/51/30-1/3000-11000x1250/312/51/30-1/300000000d4-100010000001-1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min{-,350/6,1250/6,100/1}=75,故d3+为换出变量。第四节目的规划法112cj00P100P302.5P20P2CBXBbx1x2dcj

00P100P302.5P20P2CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P3d2+115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000d4-125/300-1/121/12005/2-5/21-1σkjP1

00010000000P2

000000005/201P3

-115/300-1/121/12101/2-1/200表中P3行有负检验数,说明P3

级目标没有实现,但已无法改进,得到满意解

x1=60,x2=175/3,d2+

=115/3,d4-

=125/3。第四节目的规划法113cj00P100P302.5P20P2CBXBbx1x2d

结果分析:计算结果表明,工厂应生产A产品60件,B产品175/3件,2500元的利润目标刚好达到。d4-

=125/3,表明产品B比最高限额少125/3件,满足要求。d2+

=115/3表明甲资源超过库存115/3公斤,该目标没有达到。即甲资源多消耗115/3公斤,刚好实现2500元的利润目标。而按现有消耗水平和资源库存量,无法实现利润目标。

可考虑如下措施:降低A、B产品对甲资源的消耗量,以满足现有甲资源库存量的目标;或改变P3级目标值,增加甲资源115/3公斤。

若很难实现上述措施,则需改变现有目标的优先等级,以取得可行的满意解果。第四节目的规划法114结果分析:计算结果表明,工厂应生产A产品60件1.建立初始单纯形表。

一般假定初始解在原点,即以约束条件中的所有负偏差变量或松弛变量为初始基变量,按目标优先等级从左至右分别计算出各列的检验数,填入表的下半部。2.检验是否为满意解。判别准则如下:

按优先级别从高到低依次检查各检验数行。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论