《多目标规划课件.ppt》由会员分享，可在线阅读，更多相关《多目标规划课件.ppt（141页珍藏版）》请在金锄头文库上搜索。
1、第五章 多目标规划,在实际问题中，衡量一个设计方案的好坏往往不止一个。例如：设计一个导弹，既要射程远，命中率高，还要耗燃料少；又如：选择新厂址，除了要考虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的污染等社会因素。这类问题即为多目标数学规划问题。,第五章 多目标规划,早在1772年，Franklin就提出了多目标问题矛盾如何协调的问题，1896年，Pareto首次从数学角度提出了多目标最优决策问题，直到二十世纪50-70年代Charnes, Karlin, Zadeh等人先后做了许多较有影响的工作，多目标规划受到人们的关注。至今多目标规划已广泛应用于经济、管理、系统工程等科技的各个领域
2、。,1多目标规划问题举例,例1生产计划问题 某工厂计划生产两种产品甲和乙，生产每件甲的利润为4元，生产每件乙的利润为3元，每件甲的加工时间为每件乙的两倍，若全部时间用来加工乙，则每日可生产乙500件，但工厂每日供给的原料只够生产甲和乙的总数共400件，产品甲是紧俏商品，预测市场日需求量为300件。决策者希望制定一个日生产方案，不仅能得到最大的利润，且能最大地满足市场需求。,生产计划问题,问题分析 设每日生产甲、乙的数量分别为x1, x2, 令X=(x1, x2), 则其目标函数为利润 f1(X)=4x1 + 3x2 甲的产量 f2(X)=x1 都取最大值 满足约束条件 x1 + x2400（原
3、料供应约束） 2x1 + x2500（加工时间约束） x10，x20,多目标规划问题举例,例2投资问题 假设在一段时间内有a（亿元）的资金可用于建厂投资，若可供选择的项目记为1,2,m, 而且一旦对第i个项目投资，则必须用掉ai（亿元）; 而在这段时间内这第个项目可得到的收益为ci（亿元）, 其中i=1,2,m, 问如何确定最佳的投资方案？,投资问题,问题分析 上述要求的最佳方案应为：投资少，收益大。,多目标规划的标准形式,V-min F(X)=(f1(X), f2(X),fp(X)T s.t. gi(X)0, i=1,2,m 其中X=(x1,x2,xn)T, p2 这里V-min 是指对向量
4、形式的p个目标(f1(X), f2(X),fp(X)T求最小。 一般假设多目标规划中的目标函数已经是规范化了的。,2 多目标规划解的概念与性质,1. 多目标规划解的概念 例3 解分别对单个目标求出其最优解，对于第一个目标的最优解x(1)=1; 第二个目标的最优解x(2)=1, 为同一点，取x*=1作为多目标问题的最优解，其目标函数值F*(x) =(-2,-1). 可以用变量空间和目标函数空间来分别描述各种解的情况。,多目标规划解的概念,下面考察例1中生产计划问题。问：是否能找到一个可行解X*=(x1*, x2*)T使之同时为f1(X)与f2(X)的最大解？ 在可行域内容易求解 max f1(X
5、)的唯一最优解为 (100, 300), 见图中B点。 max f2(X)的唯一最优解为 (250, 0), 见图中C点。 由此可得共同的最优解X*并不存在。当一目标达到最优时，另一目标达不到最优，两目标相互矛盾。因此需要根据别的原则，权衡两者之间的得失，从R中找出满意的方案来。,多目标规划解的概念,如何比较方案的好坏呢？ 就上述问题，设XR，YR，称X比Y好（或Y比X劣），若 f1(X)f1(Y) f2(X) f2(Y) 或 f1(X)f1(Y) f2(X) f2(Y) 不难得到除线段BC之外的其余R上的点均为劣解，而BC上无劣解，且两两无法比较，因此决策者只有根据某些别的考虑从BC上挑选出
6、满意的方案来。这时称BC上的点为非劣解，或有效解。,多目标规划解的概念,对于一般的多目标规划问题： (VP) V-min F(X)=(f1(X), f2(X),fp(X)T s.t. gi(X)0, i=1,2,m 其中X=(x1,x2,xn)T, p2 设R=X| gi(X)0, i=1,2,m 定义1 设X*R，若对任意j=1,2,p, 以及任意XR均有 fj(X)fj(X*), j=1,2,p 则称X*为问题(VP)的绝对最优解。最优解的全体记为Rab*,多目标规划解的概念,对于无绝对最优解的情况，引进下面的偏好关系： 设F1=(f11, f21, ,fp1)T, F2=(f12, f2
7、2, ,fp2)T (1)F1F2意味着F1每个分量都严格小于F2的相应分量，即fj1fj2, j=1,2,p (2)F1F2等价于fj1fj2, j=1,2,p，且至少存在某个j0 (1j0p), 使fj01fj02 (3)F1F2等价于fj1fj2, j=1,2,p,多目标规划解的概念,定义2 设X*R，若不存在XR满足F(X)F(X*), 则称X*为问题(VP)的有效解（或Pareto解）。有效解的全体记为Rpa* 定义3 设X*R，若不存在XR满足F(X)F(X*), 则称X*为问题(VP)的弱有效解（或弱Pareto解）。弱有效解的全体记为Rwp*,多目标规划解的性质,记Rj*为单目
8、标问题 (Pj) min fj(X) s.t. gi(X)0, i=1,2,m 的最优解集合，j=1,2,p，可见 而R，Rab*，Rpa*，Rwp*，R1*, Rp*之间的关系有下列图示。并有下列定理。,多目标规划解的性质,多目标规划解的性质,定义4 如果f1(X), f2(X),fp(X)和g1(X), g2(X),gm(X)均为凸函数，则称多目标数学规划（VP）为凸多目标数学规划。 一般来说，即使（VP）为凸多目标数学规划，Rwp*和Rpa*也不一定为凸集。,多目标规划解的性质,2. 多目标规划问题的像集 在（VP）中，取定一可行解X0R，可得到其相应的目标函数值 F(X0)=( f1(
9、X0), , fp(X0)T 此为EP空间中的一个点，从而确定了从X到F(X)的一个映射，即 F XF(X) 集合F(R)=F(X) |XR称为约束集合R在映射F之下的像集。,多目标规划解的性质,一般来说，即使（VP）是凸多目标规划，像集F(R)也不一定为凸集（见例3）。 但是，当目标函数f1(X), f2(X),fp(X)为线性函数，约束集合R为凸多面体时，可以证明：像集F(R)为EP中的凸多面体。,多目标规划解的性质,对于像集F(R)，还可以定义有效点及弱有效点。 定义5 设F*F(R)，若不存在FF(R)，满足 FF* 则称F*为像集F(R)的有效点，有效点的全体记为Epa*. 定义6
10、设F*F(R)，若不存在FF(R)，满足 FF* 则称F*为像集F(R)的弱有效点，弱有效点的全体记为Ewp*.,多目标规划解的性质,类似地可证明：像集F(R)的有效点一定是弱有效点，即 通过在像集F(R)上寻找有效点（或弱有效点），就可以确定约束集合R上的有效解（或弱有效解）。对此，有如下的定理。,多目标规划解的性质,定理4 在像集F(R)上，若Epa*已知，则在约束集合R上，有 定理5 在像集F(R)上，若Ewp*已知，则在约束集合R上，有 另外通过对像集的研究，可以更直观地认识问题，并且可以提供一些处理多目标规划的方法。,3处理多目标规划的一些方法,在2中，注意到，要使多目标规划（VP）
11、中所有子目标同时实现最优经常是不可解的，那么如何制定比较标准在（弱）有效解集中找到满意解呢？,处理多目标规划的一些方法,3.1 约束法（主要目标法） 在目标函数f1(X), f2(X),fp(X)中，选出其中的一个作为主要目标，如f1(X), 而其它的目标f2(X),fp(X)只要满足一定的条件即可。,处理多目标规划的一些方法,如fj(X)fj0, j=2,p，,处理多目标规划的一些方法,3.2 分层序列法 把（VP）中的p个目标f1(X), f2(X),fp(X)按其重要性排一个次序；分为最重要目标、次要目标等等。不妨设p个目标责任制的重要性序列为 f1(X), f2(X),fp(X) 首先
12、求第一个目标f1(X)的最优解 (P1) min f1(X) XR 设其最优值为f1*，再求第二个目标的最优解,处理多目标规划的一些方法,(P2) min f2(X) XR1 其中R1=RX |f1(X)f1* 其最优值为f2*，然后求第三个目标的最优解 (P3) min f3(X) XR2 其中R2=R1X |f2(X)f2* 求得最优值为f3*,，最后求第p个目标的最优解 (Pp) min fp(X) XR p-1 其中Rp-1=Rp-2X |fp-1(X)fp-1*,处理多目标规划的一些方法,此时求得最优解X*，最优值为fp*，则X*就是多目标问题(VP)在分层序列意义下的最优解。进一步
13、有下列定理。 定理6 设X*是由分层序列法所得到的最优解，则X*Rpa*.,处理多目标规划的一些方法,证明用反证法证明。 假设X*不Rpa*，则必存在YR，使 F(Y)F(X*) 下面分两种情形讨论： (1)若f1(Y)f1(X*), 而f1(X*)=f1*, 故得(P1)的可行解Y满足 f1(Y)f1(X*)=f1* 此与f1*=min f1(X)相矛盾。 XR,处理多目标规划的一些方法,(2)若fj(Y)= fj(X*), j=1,2,j0-1 但fj0(Y)fj0(X*) 2j0p 此时必有fj(Y)= fj(X*)fj*, j=1,2,j0-1 因此，Y是问题 (Pj0) min fp
14、(X) XRj0-2X |fj0-1(X)fj0-1* 的可行解，又由 fj0(Y)fj0(X*)fj0* 此与fj0*是问题(Pj0)的最优值相矛盾。 综合(1)(2), 定理得证。,处理多目标规划的一些方法,3.3 评价函数法 直接求解多目标规划问题是比较困难的，有一类方法是通过构造一个评价函数（或效用函数）U(F(X)将多目标规划问题(VP)转化为单目标规划问题 min U(F(X) XR 然后求解该问题，并将其最优解X*作为(VP)的最优解。 由于构造评价函数的多种多样，也就出现了多种不同的评价函数方法。,处理多目标规划的一些方法,1. 线性加权和法 对(VP)中的p个目标f1(X),
15、 f2(X),fp(X)按其重要程度给以适当的权系数j0(j=1,2,p),且j=1，然后构造评价函数 目标函数是一种和的形式，这里要求所有应具有相同量纲，若量纲不同，必须进行统一量纲或无量纲化处理。,处理多目标规划的一些方法,问题的难点是如何确定合理的权系数。 (1)“老手法” (2)-方法,处理多目标规划的一些方法,2. 平方和加权法 对单目标规划问题 (Pj) min fj(X) j=1,2,p XR 求出一个尽可能好的下界f10,fp0（可看成是规定值）， min fj(X) fj0 j=1,2,p XR,处理多目标规划的一些方法,构造评价函数 然后求min U(F(X) XR 求得最优解X*作为多目标规划的解。,处理多目标规划的一些方法,3. 理想点法（虚拟点法） 先求p 个单目标规划问题的最优解，记 fj*=fj(X(j)=min fj(X) j=1,2,p XR 若所有X(j)( j=1,2,p)都相同，设为X*，则X*为多目标函数的绝对最优解，但一般不易达到，因此向量 F*=(f1*,f2*,fp*) 只是一个理想点。,处理多目标规划的一些方法,C（1975）提出的理想点，其中心思想是定义一个模，在这个模的意义下，找一个点尽量接近理想点F*，即求 min U(F(X)= min |F(X)-F*| XR
