资源预览内容
第1页 / 共28页
第2页 / 共28页
第3页 / 共28页
第4页 / 共28页
第5页 / 共28页
第6页 / 共28页
第7页 / 共28页
第8页 / 共28页
第9页 / 共28页
第10页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第五讲 目标规划 n目标规划问题及其数学模型n目标规划的图解法 n目标规划应用举例 第一节 目标规划问题及其数学模型(1)线性规划是单目标最优化问题; (2)线性规划有最优解的必要条件是其可行解集非空,即各约束条件彼此相容;(3)线性规划数学模型是相对于实际问题的近似。线性规划问题的局限性一、目标规划问题的提出 二、目标规划的数学模型例1 某工厂生产两种产品,受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下,要求制订一个获利最大的生产计划。具体数据见表6-l。表6-l产 品限 量原材料 (kg/件)51060设备工时 (h/件)4440利润 (元/件)681. 举例解:设产品I和的产量分别为x1和x2,当用线性规划来描 述和解决这个问题时,其数学模型为:用图解法或单纯形法求解,解得:最优生产计划为x18件,x22件,max z64元。从线性规划的角度来看,问题已经得到了圆满的解决。 但如果站的角度不同,决策的目标也可能不同。例2 假设在例 l 的基础上,要求考虑如下意见:(1)由于产品销售疲软,故希望产品的产量不超过产品I的一半;(2)原材料严重短缺,生产中应避免过量消耗;(3)最好能节约4小时设备工时;(4)计划利润不少于48元。面对这些意见,决策人员需要会同各有关方面做进一步的协调,最后达成了一致意见:原材料使用限额不得突破;产品 产量要求必须优先考虑;设备工时问题其次考虑;最后考虑 计划利润的要求。类似这样的多目标决策问题是典型的目标规划问题。 2.目标规划数学模型涉及到的基本概念(1)偏差变量对每一个决策目标,引入正、负偏差变量d+和d,分别表示决策值超过或不足目标值的部分。按定义应有d+0,d0,d+d0。(2)绝对约束和目标约束绝对约束是指必须严格满足的约束条件,如线性规划中的约束条件都是绝对约束。绝对约束是硬约束,对它的满足与否,决定了解的可行性。目标约束是目标规划特有的概念,是一种软约束,目标约束中决策值和目标值之间的差异用偏差变量表示。(3)优先因子和权系数不同目标的主次轻重有两种差别。一种差别是绝对的,可用优先因子 来表示。只有在高级优先因子对应的目标已满足的基础上,才能考虑较低级优先因子对应的目标;在考虑低级优先因子对应的目标时,绝不允许违背已满足的高级优先因子对应的目标。优先因子间的关系为 ,即 对应的目标比 对应的目标有绝对的优先性。另一种差别是相对的,这些目标具有相同的优先因子,它们的重要程度可用权系数的不同来表示。 (4)目标规划的目标函数目标规划的目标函数由各目标约束的偏差变量、相应的优先因子和权系数构成。由于目标规划追求的是尽可能接近各既定目标值,也就是使各有关偏差变量尽可能小,所以其目标函数只能是极小化。有三种基本表达式: 要求恰好达到目标值。这时,决策值超过或不足目标值都是不希望的,因此有: 要求不超过目标值,但允许不足目标值。这时,不希望决策值超过目标值,因此有: 要求不低于目标值,但允许超过目标值。这时,不希望决策值低于目标值,因此有: 例2 假设在例 l 的基础上,要求考虑如下的意见:(1)由于产品销售疲软,故希望产品的产量不超过产品I的一半;(2)原材料严重短缺,生产中应避免过量消耗;(3)最好能节约4小时设备工时;(4)计划利润不少于48元。面对这些意见,决策人员需要会同有关各方作进一步的协调,最后达成了一致意见:1.原材料使用限额不得突破;2.产品产量要求必须优先考虑;3.设备工时问题其次考虑;4.最后考虑计划利润的要求。1.原材料使用限额不得突破(绝对约束)2.产品产量要求必须优先考虑(P1)3.设备工时问题其次考虑(P2)4.最后考虑计划利润的要求(p3)根据上述概念,例2的目标规划数学模型如下: 其中,(6.1a)为绝对约束,(6.1b)、(6.1c)、(6.ld)为目标约束。根据题意,P1为两种产品产量要求的优先因子;P2为节约工时要求的优先因子;P3为计划利润要求的优先因子,它们应满足P1P2P3。 目标规划数学模型的一般形式为 :模型中gk为第k个目标约束的预期目标值, 和 为 优先因子对应各目标的权系数。在建立目标规划数学模型时,需要确定预期目标值、优先级和权系数等,应当综合运用各种决策技术,尽可能地减少主观片面性。 第二节 目标规划的图解法 对于只有两个决策变量的目标规划问题,可以用图解方法来求解。在用图解法解目标规划时,首先必须满足所有绝对约束。在此基础上,再按照优先级从高到低的顺序,逐个地考虑各个目标约束。一般地,若优先因子Pj对应的解空间为Rj,则优先因子Pj+1对应的解空间只能在Rj中考虑。即 :若Rj,而Rj+1=,则Rj中的解为目标规划的满意解,它只能保证满足P1,P2,Pj级目标。而不保证满足其后的各级目标。例3 用图解法解例2的目标规划模型。解:解题过程见图6-l。 AB图6-1中,OAB区域是满足绝对 约束(6.1a)和非负条件的解空间 。对于所有目标约束,去掉偏差 变量,画出相应直线,然后标出 偏差变量变化时直线平移方向 。例4 用图解法解下面的目标规划。 解:解题过程见图6-2。 从图6-2可见,在考虑P1和P2的目标后,解空间R2为四边形ABCD区域。在考虑P3的目标时,因为 的权系数比 的大,所以先考虑 。此时,x1和x2的取值范围缩小为四边形ABEF区域;然后考虑 。但在四边形ABEF区域内无法满足 0,所以,只能退一步,要求在四边形区域ABEF中找一点,使 尽可能小,这一点就是点E(6.5,1.25)。所以,问题的满意解为x16.5,x21.25。 在用图解法解目标规划时,可能会遇到下面两种情况。一种情况是像例3那样,最后一级目标的解空间非空。这时得到的解能满足所有目标的要求。当解不唯一时(如例3,R3为四边形EDCF区域),决策者在作实际决策时究竟选择哪一个解,完全取决于决策者自身的考虑。 另一种情况是像例4那样,得到的解不能满足所有目标。这时,我们要做的是寻找满意解,使它尽可能满足高级别的目标,同时又使它对那些不能满足的较低级别目标的偏离程度尽可能地小。如在例4中,解空间R3。于是我们在R2(四边形ABCD区域)中选择了E点,它满足P1和P2的目标。对P3的目标,它只满足 ,而 未能满足 。至于更低级的P4目标 ,它也不能满足( )。 目标规划的灵敏度分析 在目标规划建模时,目标优先级和权系数的确定往往带有一定的主观性,因此,对它们的灵敏度分析是目标规划灵敏度分析的主要内容。目标规划灵敏度分析的方法、原理同线性规划的灵敏度分析本质上相同,下面通过例子讲述。 例7 对例4的目标规划问题,已求得满意解为x113/2,x2=5/4(见表6-6)。现决策者想知道,目标函数中各目标的优先因子和权系数对最终解的影响。为此,提出了下面二个灵敏度分析问题,即目标函数分别变为: 原目标函数:原目标函数:例4 用图解法解下面的目标规划。 从图6-2可见,在考虑P1和P2的目标后, 解空间R2为四边形ABCD区域。在考虑P3的 目标时,因为 的权系数比 的大, 所以先考虑 。此时,x1和x2的取 值范围缩小为四边形ABEF区域;然后考 虑 。但在四边形ABEF区域内无 法满足 0,所以,只能退一步,要 求在四边形区域ABEF中找一点,使 尽可能小,这一点就是点E(6.5,1.25)。 所以,问题的满意解为x16.5,x2 1.25。 例4 用图解法解下面的原目标规划。 第四节 目标规划应用举例n例:多目标运输问题如下表。目标要求:P1:产地不存货,且销量至少满足一半P2:满足B1需求,且A4B2尽量少运P3:总运费最小销地 产地 B1 B2 B3产量A1A2 A3A45 8 37 4 52 6 94 6 6100 40 40 120销量 120 140 140400/300n解:设Ai到Bj的运输量为xij X11+ X12 + X13 +d1-d1+=100 X21+ X22 + X23 +d2-d2+=40 X31+ X32 + X33 +d3-d3+=40 X41+ X42 + X43 +d4-d4+=120 X11+ X21 + X31 + X41+d5-d5+=120/2 X12+ X22 + X32+ X42+d6-d6+=140/2 X13+ X23+ X33 + X43 +d7-d7+=140/2 X11+ X21 + X31 + X41 +d8-d8+=120 X42 +d9-d9+=0 Cij Xij +d10-d10+=0 Xij, dL-dL+ 0 i=1,2,3,4 j=1,2,3 L=1,2,10minZ=P1(d1-+d1+ + d7+)+P2(d8-+d8+ +d9+)+P3 d10+
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号