运筹学概论第4章目标规划

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第4章,目标规划,目标规划问题的提出,目标规划数学模型,目标规划的图解法,(1)线性规划是单目标最优化问题,(2)线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容,(3)线性规划数学模型是相对于实际问题的近似,1.线性规划问题的局限性,一、目标规划问题的提出,例1 某工厂生产两种产品，受到原材料供给和设备工时的限制。在单件利润等有关数据的条件下，要求制订一个获利最大的生产方案。具体数据见表。,产品,限量,原材料（kg/件）,5,10,60,设备工时（h/件）,4,4,40,利润（元/件）,6,8,最优生产方案为x18件，x22件，max z64元。,2.目标规划问题的提出,在处理实际问题时，线性规划存在着由其“刚性本质所注定的某些固有的局限性(目标唯一、可能域为空、近似性)。现代决策强调定量分析和定性分析相结合。线性规划无法胜任这样的要求。,1961年，查恩斯(A.Charnes)和库柏()提出目标规划(goal programming)。在处理实际决策问题时，成认各项决策要求(即使是冲突的)的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具。,例2 假设在例 l 的根底上，要求考虑如下意见：,(1)由于产品销售疲软，故希望产品的产量不超过产品I的一半；,(2)原材料严重短缺，生产中应防止过量消耗；,(3)最好能节约4小时设备工时；,(4)方案利润不少于48元。,面对这些意见，方案人员需要会同有关各方作进一步的协调，最后达成了一致意见：原材料使用限额不得突破；产品产量要求必须优先考虑；设备工时问题其次考虑；最后考虑方案利润的要求。,类似这样的多目标决策问题是典型的目标规划问题。,线性规划,目标规划,3.目标规划与线性规划相比的优点,1线性规划只能处理一个目标，而现实问题往往要处理多个目标。目标规划就能统筹兼顾地处理多个目标的关系，求得更切合实际要求的解。,2线性规划立足于求满足所有约束条件的最优解，而在实际问题中，可能存在相互矛盾的约束条件。目标规划可以在相互矛盾的约束条件下找到满意解。,3目标规划的最优解指的是尽可能地到达或接近一个或假设干个已给定的指标值。,4线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际的需要给予轻重缓急的考虑。,二、目标规划的数学模型,1偏差变量,对每一个决策目标，引入正、负偏差变量d+和d，分别表示决策值超过或缺乏目标值的局部。按定义应有d+0，d0，d+d0。,2绝对约束和目标约束,绝对约束是指必须严格满足的约束条件，如线性规划中的约束条件都是绝对约束。绝对约束是硬约束，对它的满足与否，决定了解的可行性。,目标约束是目标规划特有的概念，是一种软约束，目标约束中决策值和目标值之间的差异用偏差变量表示。,3优先因子和权系数,不同目标的主次轻重有两种差异。一种差异是绝对的，可用优先因子 来表示。只有在高级优先因子对应的目标已满足的根底上，才能考虑较低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝不允许违背已满足的高级优先因子对应的目标。优先因子间的关系为 ，即,对应的目标比 对应的目标有绝对的优先性。,另一种差异是相对的，这些目标具有相同的优先因子,它们的重要程度可用权系数的不同来表示。,4目标规划的目标函数,目标规划的目标函数由各目标约束的偏差变量及相应的优先因子和权系数构成。由于目标规划追求的是尽可能接近各既定目标值,也就是使各有关偏差变量尽可能小，所以其目标函数只能是极小化。,有三种根本表达式：,要求恰好到达目标值。这时，决策值超过或缺乏目标值都是不希望的，因此有：,要求不超过目标值，但允许缺乏目标值。这时，不希望决策值超过目标值，因此有：,要求不低于目标值，但允许超过目标值。,这时，不希望决策值低于目标值，因此有：,例2(1)产品的产量不超过产品I的一半；,(2)原材料严重短缺，生产中应防止过量消耗；,(3)最好能节约4小时设备工时；,(4)方案利润不少于48元。,一致意见：,1.原材料使用限额不得突破；,2.产品产量要求必须优先考虑；,3.设备工时问题其次考虑；,4.最后考虑方案利润的要求。,产品,限量,原材料（kg/件）,5,10,60,设备工时（h/件）,4,4,40,利润（元/件）,6,8,目标规划数学模型的一般形式为：,模型中g,k,为第k个目标约束的预期目标值，和 为,优先因子对应各目标的权系数。,在建立目标规划数学模型时，需要确定预期,目标值、优先级,和,权系数,等，应当综合运用各种决策技术,尽可能地减少主观片面性,。,习题:,1、公司决定使用1000万元新产品开发基金开发A，B，C三种新产品，对应的投资利润率分别为5%、7%和10%。公司制定如下的优先顺序目标：,第一，A产品至少投资300万元；,第二，为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的35%；,第三，应至少留有10%的开发基金，以备急用；,第四，使总的投资利润最大。,建立投资分配方案的目标规划模型。,2、某彩色电视机组装工厂，生产A、B、C三种规格电视机。装配工作在同一生产线上完成，三种产品每件装配时的工时消耗分别为6小时、8小时和10小时，生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元、650元和800元。每月销量预计分别为12台、10台和6台。该厂经营目标如下：,P1：利润指标定为至少每月1.6104元；,P2：充分利用生产能力；,P3：加班时间不超过24小时；,P4：产量恰好能够满足预计销量；,为确定生产方案，试建立该问题的目标规划模型,三、目标规划的图解法,只有两个决策变量的目标规划问题可以用图解方法来求解。,在用图解法解目标规划时，首先必须满足所有绝对约束。在此根底上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，假设优先因子Pj对应的解空间为Rj，那么优先因子Pj+1对应的解空间只能在Rj中考虑。即:,假设Rj，而Rj+1=，那么Rj中的解为目标规划的满意解，它只能保证满足P1，P2，Pj级目标。而不保证满足其后的各级目标。,例3 用图解法解例2的目标规划模型,。,解：,解题过程见图6-l。,A,B,图6-1中，OAB区域是满足绝对约束(6.1a)和非负条件的解空间。对于所有目标约束，去掉偏差变量，画出相应直线，,然后标出偏差变量变化时直线平移方向,。,按优先级上下，首先考虑p1，此时要求 ，因而解空间R1为OAC区域；再考虑P2，此时要求 ，因而解空间R2为ODC区域；最后考虑P3，此时要求 ，因而解空间R3为四边形EDCF区域。容易求得E，D，C，F四点的坐标分别为(8,0)、(9,0)、(6,3)、(4.8,2.4)，故问题的解可表示为：,其中：,此题解能满足式6.1的所有目标的要求，即能使min z=0，这种情况并不总是出现，即很多目标规划问题只能满足前面Pj级目标的要求。见下一个例子。,例4 用图解法解下面的目标规划。,从图6-2可见，在考虑P,1,和P,2,的目标后，解空间R,2,为四边形,ABCD,区域。在考虑P,3,的目标时，因为 的权系数比 的大，所以先考虑 。此时，x,1,和x,2,的取值范围缩小为四边形,ABEF,区域；然后考虑 。但在四边形ABEF区域内无法满足 0，所以，只能退一步，要求在四边形区域,ABEF,中找一点，使 尽可能小，这一点就是点E(6.5,1.25)。所以，问题的,满意解为,x,1,6.5，x,2,1.25。,在用图解法解目标规划时，可能会遇到下面,两种情况,。,一种情况,是像例3那样，最后一级目标的解空间非空。这时得到的解能满足所有目标的要求。当解不唯一时(如例3，R,3,为四边形EDCF区域)，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。,另一种情况,是像例4那样，得到的解不能满足所有目标。这时，我们要做的是寻找满意解，使它尽可能满足高级别的目标，同时又使它对那些不能满足的较低级别目标的偏离程度尽可能地小。如在例4中，解空间R,3,。于是我们在R,2,(四边形ABCD区域)中选择了E点，它满足P,1,和P,2,的目标。对P,3,的目标，它只满足 ，而 未能满足 。至于更低级的P,4,目标 ，它也不能满足()。,