《线性规划教学PPT目标规划》由会员分享，可在线阅读，更多相关《线性规划教学PPT目标规划（28页珍藏版）》请在金锄头文库上搜索。
1、第五讲 目标规划 n目标规划问题及其数学模型n目标规划的图解法 n目标规划应用举例 第一节 目标规划问题及其数学模型(1)线性规划是单目标最优化问题; (2)线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容;(3)线性规划数学模型是相对于实际问题的近似。线性规划问题的局限性一、目标规划问题的提出 二、目标规划的数学模型例1 某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见表6-l。表6-l产 品限 量原材料 （kg/件）51060设备工时 （h/件）4440利润 （元/件）681. 举例解：设产品I
2、和的产量分别为x1和x2，当用线性规划来描 述和解决这个问题时，其数学模型为:用图解法或单纯形法求解，解得：最优生产计划为x18件，x22件，max z64元。从线性规划的角度来看，问题已经得到了圆满的解决。 但如果站的角度不同，决策的目标也可能不同。例2 假设在例 l 的基础上，要求考虑如下意见：(1)由于产品销售疲软，故希望产品的产量不超过产品I的一半；(2)原材料严重短缺，生产中应避免过量消耗；(3)最好能节约4小时设备工时；(4)计划利润不少于48元。面对这些意见，决策人员需要会同各有关方面做进一步的协调，最后达成了一致意见：原材料使用限额不得突破；产品 产量要求必须优先考虑；设备工时
3、问题其次考虑；最后考虑 计划利润的要求。类似这样的多目标决策问题是典型的目标规划问题。 2.目标规划数学模型涉及到的基本概念（1）偏差变量对每一个决策目标，引入正、负偏差变量d+和d，分别表示决策值超过或不足目标值的部分。按定义应有d+0，d0，d+d0。（2）绝对约束和目标约束绝对约束是指必须严格满足的约束条件，如线性规划中的约束条件都是绝对约束。绝对约束是硬约束，对它的满足与否，决定了解的可行性。目标约束是目标规划特有的概念，是一种软约束，目标约束中决策值和目标值之间的差异用偏差变量表示。（3）优先因子和权系数不同目标的主次轻重有两种差别。一种差别是绝对的，可用优先因子 来表示。只有在高级
4、优先因子对应的目标已满足的基础上，才能考虑较低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝不允许违背已满足的高级优先因子对应的目标。优先因子间的关系为 ，即 对应的目标比 对应的目标有绝对的优先性。另一种差别是相对的，这些目标具有相同的优先因子,它们的重要程度可用权系数的不同来表示。 （4）目标规划的目标函数目标规划的目标函数由各目标约束的偏差变量、相应的优先因子和权系数构成。由于目标规划追求的是尽可能接近各既定目标值,也就是使各有关偏差变量尽可能小，所以其目标函数只能是极小化。有三种基本表达式： 要求恰好达到目标值。这时，决策值超过或不足目标值都是不希望的，因此有： 要求不超过目
5、标值，但允许不足目标值。这时，不希望决策值超过目标值，因此有： 要求不低于目标值，但允许超过目标值。这时，不希望决策值低于目标值，因此有： 例2 假设在例 l 的基础上，要求考虑如下的意见：(1)由于产品销售疲软，故希望产品的产量不超过产品I的一半；(2)原材料严重短缺，生产中应避免过量消耗；(3)最好能节约4小时设备工时；(4)计划利润不少于48元。面对这些意见，决策人员需要会同有关各方作进一步的协调，最后达成了一致意见：1.原材料使用限额不得突破；2.产品产量要求必须优先考虑；3.设备工时问题其次考虑；4.最后考虑计划利润的要求。1.原材料使用限额不得突破(绝对约束)2.产品产量要求必须优
6、先考虑（P1）3.设备工时问题其次考虑(P2)4.最后考虑计划利润的要求(p3)根据上述概念，例2的目标规划数学模型如下： 其中，(6.1a)为绝对约束，(6.1b)、(6.1c)、(6.ld)为目标约束。根据题意，P1为两种产品产量要求的优先因子；P2为节约工时要求的优先因子；P3为计划利润要求的优先因子，它们应满足P1P2P3。 目标规划数学模型的一般形式为 ：模型中gk为第k个目标约束的预期目标值， 和 为 优先因子对应各目标的权系数。在建立目标规划数学模型时，需要确定预期目标值、优先级和权系数等，应当综合运用各种决策技术,尽可能地减少主观片面性。 第二节 目标规划的图解法 对于只有两个
7、决策变量的目标规划问题，可以用图解方法来求解。在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子Pj对应的解空间为Rj，则优先因子Pj+1对应的解空间只能在Rj中考虑。即 :若Rj，而Rj+1=，则Rj中的解为目标规划的满意解，它只能保证满足P1，P2，Pj级目标。而不保证满足其后的各级目标。例3 用图解法解例2的目标规划模型。解：解题过程见图6-l。 AB图6-1中，OAB区域是满足绝对 约束(6.1a)和非负条件的解空间 。对于所有目标约束，去掉偏差 变量，画出相应直线，然后标出 偏差变量变化时直线平移方向
8、。例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，R
9、3为四边形EDCF区域)，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。 另一种情况是像例4那样，得到的解不能满足所有目标。这时，我们要做的是寻找满意解，使它尽可能满足高级别的目标，同时又使它对那些不能满足的较低级别目标的偏离程度尽可能地小。如在例4中，解空间R3。于是我们在R2(四边形ABCD区域)中选择了E点，它满足P1和P2的目标。对P3的目标，它只满足 ，而 未能满足 。至于更低级的P4目标 ，它也不能满足( )。 目标规划的灵敏度分析 在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，对它们的灵敏度分析是目标规划灵敏度分析的主要内容。目标规划灵
10、敏度分析的方法、原理同线性规划的灵敏度分析本质上相同，下面通过例子讲述。 例7 对例4的目标规划问题，已求得满意解为x113/2，x2=5/4(见表6-6)。现决策者想知道，目标函数中各目标的优先因子和权系数对最终解的影响。为此，提出了下面二个灵敏度分析问题，即目标函数分别变为： 原目标函数：原目标函数：例4 用图解法解下面的目标规划。 从图6-2可见，在考虑P1和P2的目标后， 解空间R2为四边形ABCD区域。在考虑P3的 目标时，因为 的权系数比 的大， 所以先考虑 。此时，x1和x2的取 值范围缩小为四边形ABEF区域；然后考 虑 。但在四边形ABEF区域内无 法满足 0，所以，只能退一
11、步，要 求在四边形区域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 +
12、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+
