i第四章 目标规划及其图解法

第四章目标规划

前面的线性规划问题，研究的都是只有一个目标函数，若干个约束条件的最优决策问题．然而现实生活中，衡量一个方案的好坏标准往往不止一个，而且这些标准之间往往不协调，甚至是相互冲突的，标准的度量单位也常常各不相同．例如，在资源的最优利用问题中，除了考虑所得的利润最大，还要考虑使生产的产品质量好，劳动生产率高，对市场的适应性强等等．目标规划对众多的目标分别确定一个希望实现的目标值，然后按目标的重要程度（级别）依次进行考虑与计算，以求得最接近各目标预定数值的方案．如果某些目标由于种种约束不能完全实现，它也能指出目标值不能实现的程度以及原因，以供决策者参考．第四章目标规划第一节目标规划的基本概念与数学模型一、问题的提出二、目标规划的基本概念

1.决策变量与偏差变量

２.目标约束与绝对约束３.目标规划的目标函数(达成函数)４.优先因子与权系数三、目标规划的数学模型第二节目标规划的图解法第一节目标规划的基本概念与数学模型例4-1

某生物药厂需在市场上采购某种原料，现市场上有甲、乙两个等级，单价分别为2千元/kg和1千元/kg，要求采购的总费用不得超过20万元，购得原料的总重量不少于100kg，而甲级原料又不得少于50kg，问如何确定最好的采购方案（即用最少的钱、采购最多数量的原料）．一、问题的提出目标函数为：约束条件有：分析：这是一个含有两个目标的数学规划问题．设分别为采购甲级、乙级原材料的数量（单位：kg）

为花掉的资金，为所购原料总量．则：例4-2

某工厂在计划期内要生产甲、乙两种产品，现有的资源及两种产品的技术消耗定额、单位利润如表4-1所示．试确定计划期内的生产计划，使利润最大，同时厂领导为适应市场需求，尽可能扩大甲产品的生产，减少乙产品的生产．

表4-1产品的资源、技术消耗定额、单位利润表

甲（每件）乙（每件）现有资源钢材（kg）9.243600木材(m3)452000设备负荷（台小时）3103000单位产品利润(元)70120

分析:设分别是计划期内甲、乙产品的产量．则该问题的数学模型为对于多目标问题，线性规划很难为其找到最优方案．极有可能出现：第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案．就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的．实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法——目标规划．第一节目标规划的基本概念与数学模型二、目标规划的基本概念1．决策变量与偏差变量

２.目标约束与绝对约束３.目标规划的目标函数(达成函数)４.优先因子与权系数三、目标规划的数学模型第四章目标规划第二节目标规划的图解法一、问题的提出二、目标规划的基本概念多目标规划问题的一般形式如下(简记为：GP1)

1．决策变量与偏差变量

决策变量也称控制变量，用x1、x2、…、xn

表示．在多目标规划问题中，由于目标之间存在冲突或约束条件中有矛盾方程，我们可以设想降低目标要求、“放松”严格的约束条件，即从实际出发，根据经验、历史资料或市场的需求、上级部门的任务下达等来给每个目标确定一个希望达到的目标值ei

,(i=1，2，…，m)．一般说来，这些值ei

的确定并不要求十分精确或严格，允许决策的实际值大于或小于ei

．我们称实际值与目标值的差距为偏差变量．用表示．当目标值确定时，所做的决策只可能出现以下三种情况：即由所构成的3种不同组合表示的含义：为正偏差变量——第

i个目标实际值超出目标值的部分．表示第i个目标的实际值超出目标值表示第i个目标的实际值未达到目标值表示第i个目标的实际值恰好等于目标值．并且无论发生哪种情况均有:为负偏差变量——第

i个目标实际值不足目标值的差距规定۞

在例4-2中，若提出目标y1的期望值e1=45000元，y2的期望值e2=250件，y3的期望值e3=200件，则可引入偏差变量（i=1，2，3）,表示利润超过45000元的数量，则表示利润距45000元还差的数量,表示甲产品产量超过250件的部分，……．这样可得三个目标函数方程

前面通过确定各目标的目标值、引入偏差变量，把目标函数转化成约束方程，从而并入原约束条件中，我们称这类具有机动余地的约束为目标约束．如例4-2的目标函数转化为目标约束（4-10）．因它具有一定的弹性，一般目标约束不会不满足，只是可能偏差要大一些，故也称为软约束．２．

目标约束与绝对约束

绝对约束是指必须严格满足的等式或不等式约束，也称为系统约束．它对应于线性规划中的约束条件（如资源、客观条件约束等），不能满足绝对约束的解即为不可行解，因此也称为硬约束．２．

目标约束与绝对约束目标约束软约束绝对约束硬约束

我们设想将约束条件“放松”，对约束方程也引入偏差变量，使矛盾的方程不再矛盾！然后通过适当的方法，找出问题的关键，即需要增加的资源品种与数量或需降低的产品产量等，就会获得较好的决策效果．这说明两种约束在一定条件下可以转换．

当不易发现约束条件中是否有矛盾方程时，更一般的方法是对所有绝对约束都引入偏差变量，从而把约束条件全部变为等式．如:

目标约束软约束３．目标规划的目标函数(达成函数)

引入偏差变量使原规划问题中的目标函数变成了目标约束，那么现在问题的目标是什么呢？

对于满足绝对约束和目标约束的所有解（可行解），从决策者角度看，判断其优劣的依据是决策值与目标值的偏差越小越好．从而目标规划的目标函数就由原目标函数变成的目标约束中偏差变量来构成．它有三种基本表现形式：①要求恰好达到目标值的，即正、负偏差变量都要尽可能小．构造目标函数为：．②要求不能超过目标值的，即允许达不到目标值，但即使超过，一定要越小越好．构造目标函数为：．③要求超过目标值的，即允许超过目标值，但即使不足，一定要使缺少量越少越好．构造目标函数为：．这样根据各个目标的不同要求，确定出总的目标函数例4-2中的目标函数可表示为

利润希望达到45000,不足部分越小越好!如例4-2其完整的目标规划模型为４．优先因子与权系数

目标规划中，当决策者要求实现多个目标时，这些目标的偏差可能相互替代或抵消，因为我们求的是所有偏差和最小，而实际问题中的目标之间也有主次、轻重、缓急之区别．决策者往往有一些最重要的，第一位要求达到的目标，我们赋予它优先因子P1，在它实现的前提下再去解决次要目标．依次把第二位达到的目标赋予优先因子P2

……，并规定Pk

»Pk+1，即不管Pk+1乘以一个多大的正数M，总成立Pk>MPk+1,表示Pk比Pk+1具有绝对的优先权．因此，不同的优先因子代表着不同的优先等级．

在实现多个目标时，首先保证P1级目标的实现，这时可不考虑其它级别目标，而P2级目标是在保证P1级目标满足的前提下考虑的．决不能因为要使P2级目标更好地实现，而去降低P1级目标的实现值．一般地在目标规划模型中，绝对约束相应的目标函数，其优先等级一定是P1级．

４．优先因子与权系数

若要进一步区别具有相同优先级的多个目标，则可分别赋予它们不同的权系数ωj(ωj

可取一确定的非负实数)，根据目标的重要程度而给它们赋值，重要的目标，赋值较大，反之ωj

值就小．如例4-2中，我们可把利润视作第一位重要，甲、乙产品的产量分配视作第二位，并且甲的产量越大越好，权重分别为10和2，则目标函数为：４．优先因子与权系数

由上面分析看到，目标规划比起线性规划来适应面要灵活得多．它可同时考虑多个目标，而且目标的计量单位也可以多种多样．目标规划的目标约束，给决策方案的选择带来很大的灵活性．并且由于目标规划中划分优先级和权系数的大小，使决策者可根据外界条件变化，通过调整目标优先级和权系数，求出不同方案以供选择．但是，用目标规划来处理问题也存在困难，主要表现在构造模型时需事先拟定目标值、优先级和权系数，而这些信息来自人的主观判断，往往带有模糊性，很难定出一个绝对的数值．４．优先因子与权系数三、目标规划的数学模型通过上面分析，例4-2中问题的模型为

若把约束条件中的不等式全部化为等式约束，我们称之为“标准型”．例4-2中问题的标准型为

一般地，对于n个决策变量，m个目标约束，目标函数中有k个优先级的目标规划问题，其数学模型的标准型如下：其中：Pi为优先等级；,为权系数．建立目标规划模型的步骤1）根据问题列出各目标与条件，确定各目标的目标值、引入偏差变量，把目标函数转化成约束方程，列出目标约束与绝对约束(例4-2）；2）根据决策者的需要将某些或全部绝对约束，通过引入偏差变量转换为软约束(例4-2）

；3）根据决策者的要求，各目标按三种情况取值：①恰好达到目标值，取；②允许超过目标值，取；③不允许超过目标值，取．然后构造一个由优先因子、权系数与偏差变量组成的、要求最小化的目标函数

(例4-2）

．建立目标规划模型的步骤最重要的目标、必须严格实现的目标及无法再增加的资源约束均应列入P1级，其余按重要程度分别列入后面各级，并在同一级中确定权系数．一般地，如果问题的P1级目标不能完全实现，则我们就认为该问题不可行．#4）给各级目标赋予相应的优先因子

，对同一优先级的各目标，按重要程度不同赋予相应的权系数

(例4-2）

；注意:优先因子与权系数

目标规划中，当决策者要求实现多个目标时，对不同的目标赋予它不同的优先因子Pk

,

不同的优先因子代表着不同的优先等级．Pk比Pk+1具有绝对的优先权．

若要进一步区别具有相同优先级的多个目标，则可分别赋予它们不同的权系数ωj(ωj

可取一确定的非负实数)，根据目标的重要程度而给它们赋值，重要的目标，赋值较大，反之ωj

值就小．第二节目标规划的图解法由于目标规划是在线性规划的基础上建立，所以两种规划模型结构没有本质区别，解法也类似．形式上的区别主要在于：①线性规划只能处理一个目标，而目标规划能统筹兼顾地处理多个目标关系，以求得切合实际需求的解；②线性规划是求满足所有约束条件的最优解，而目标规划是要在目标或约束条件下找到尽量好的满意解；③线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际需要给予轻重缓急的考虑．例4-4

求解下面目标规划:解

将约束方程以直线形式画在图上，只使用决策变量（即），偏差变量在画直线时去掉，直线画好后，在该直线上标出目标函数中与该直线相关的偏差变量增大时直线的平移方向（用垂直于直线的箭头来反映）．如图4-2．l1l2l3l4oABCDEFx1x2R3图4-2图解法示意图再考虑P2级目标，要求目标越小越好，因而解空间R2为△OCD区域按优先级高低，首先考虑P1级目标，要求目标越小越好，就在绝约束的可行解域△OAB中进一步缩小为△OAC，记作R1R1R2最后考虑P3级，此时要求目标越小越好，由图3-2可知R3为四边形CDEF区域，这个区域内的任一点均是该问题的满意解，可使目标函数由于C、D、E、F坐标分别为(6,3)、(9,0)、(8，0)、(4.8,2.4)，故满意解可表示为：其中：这种满足所有目标要求的情况，即：，在实际中并不多见，很多目标规划问题只能满足前面几级目标要求．目标规划图解法的具体演算过程第1步：由决策变量绘画所有约束条件的直线图形，偏差变量以平移直线的方法加以考虑．

第5步：重复第3、4步过程，直到解区域Ri

减少到一点或满足了所有k个级别的目标为止，此时Rk

即为最优解区域，其中的任何一点均为目标规划满意解．第2步：对P1级的各目标，确定解区域R1．第3步：对下一个优先级别Pi级各目标，确定它的最优解空间

Ri

，但必须是Ri

Ri-1(i=2,3,…)．

第4步：在这个过程中，如果某解区域Ri

减小到一点，则结束，因为此时没有进一步改进的可能．例4-5

用图解法求解下面目标规划问题：解

作图4-3：l1x1x2ol2l3R1(10,0)

图4-3图解法示意图AB考虑P2级目标，由于直线l2与R1不相交，所以在R1内无法使因此在不退化P1级目标时，不可能使P2级目标完全满足．这样R2就缩为一点，因为在R1中，使达到最小的为A点，所以：x*=(10,0),由于R2仅含有一个点，所以对P