第4章目标规划

第4章目标规划•第1节目标规划的数学模型•第2节解目标规划的图解法•第3节解目标规划的单纯形法•第4节灵敏度分析•第5节应用举例前言前几章，所讨论的都是单目标的决策问题，但在现实世界中，一个企业可能同时有多个目标：保持比较稳定的价格和利润，提高产品的市场占有率，维持比较稳定的职工队伍等。这些目标很难集中到一个目标上，而且各个目标甚至相互矛盾，相互冲突。对于这类问题，我们提出一种新的方案，目标规划。由于目标之间的不协调性和矛盾性，不大可能实现所有的目标，只能寻求一种折中的方案。目标规划的基本思想是：1对于管理部门提出的每一个目标，由决策者确定一个具体的数量目标，并对每一个目标建立一个目标函数；2寻求一个使目标函数和对应目标间偏差和最小的解。第1节目标规划的数学模型•为了具体说明目标规划与线性规划在处理问题方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。例1某工厂生产Ⅰ，Ⅱ两种产品，已知有关数据见下表。试求获利最大的生产方案。ⅠⅡ拥有量原材料(kg)设备(hr)21121110利润(元/件)810解：这是求获利最大的单目标的规划问题，用x1，x2分别表示Ⅰ，Ⅱ产品的产量，其线性规划模型表述为：0,102112108max21212121xxxxxxxxz满足约束条件：目标函数：用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62(元)。(4,3)0,102112108max21212121xxxxxxxxz满足约束条件：目标函数：实际上工厂在作决策时，要考虑市场等一系列其他条件•（1)根据市场信息，产品Ⅰ的销售量有下降的趋势，故考虑产品Ⅰ的产量不大于产品Ⅱ。•(2)超过计划供应的原材料时，需用高价采购，会使成本大幅度增加。•(3)应尽可能充分利用设备台时，但不希望加班。•(4)应尽可能达到并超过计划利润指标56元。这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。•1.设x1，x2为决策变量，此外，引进正、负偏差变量d+，d-。正偏差变量d＋表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分。因决策值不可能既超过目标值同时又未达到目标值，即恒有d+×d-=0。2.绝对约束和目标约束•绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如：例1的目标函数z=8x1+10x2可变换为目标约束8x1+10x2+d1--d1+=56。约束条件2x1+x2≤11可变换为目标约束2x1+x2+d2-—d2+=11。3.优先因子(优先等级)与权系数•一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同。要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，…，并规定PkPk+1,k=1,2,…，K。表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数ωj,这些都由决策者按具体情况而定。4.目标规划的目标函数•目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是•minz=f(d+,d-)。其基本形式有三种：•(1)要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时•minz=f(d++d-)•(2)要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小。这时minz=f(d+)•(3)要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时minz=f(d-)•对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数，以下用例子说明。•例2例1的决策者在原材料供应受严格限制的基础上考虑：首先是产品Ⅱ的产量不低于产品Ⅰ的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于56元。求决策方案。解按决策者所要求的，分别赋予这三个目标P1，P2，P3优先因子。这问题的数学模型是：3,2,1,0,,,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii满足约束条件：目标函数：目标规划的一般数学模型为)54(3,2,1,0,)44(,,1,0)34(,,1,),()24(,,1,)14()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLll满足约束条件：目标函数：为权系数。lklk,目标规划的建模技巧•1列出全部约束条件•2把要达到指标的约束不等式加上正负偏差量后化为目标约束等式•3对目标赋予相应的优先因子•4对同级目标赋予不同的权系数•5构造一个按优先因子及权系数和对应的目标偏差量所要实现最小化的目标函数•例某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：•(1)不超过年工资总额60000元；•(2)每级的人数不超过定编规定的人数；•(3)Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升；•(4)Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。•有关资料汇总于表4-8中，问该领导应如何拟订一个满意的方案。•解设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为：建模举例表4-8等级工资额(元/年)现有人数编制人数ⅠⅡⅢ200015001000101215121515合计3742•解设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为：•P1——不超过年工资总额60000元；•P2——每级的人数不超过定编规定的人数；•P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。先分别建立各目标约束。年工资总额不超过60000元•2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1—-d1+=60000•每级的人数不超过定编规定的人数：•对Ⅰ级有10(1-0.1)+x1+d2-—d2+=12•对Ⅱ级有12-x1+x2+d3-—d3+=15•对Ⅲ级有15-x2+x3+d4-—d4+=15•Ⅱ，Ⅲ级的升级面不大于现有人数的20%，但尽可能多提；•对Ⅱ级有x1+d5-—d5+=12×0.2•对Ⅲ级有x2+d6-—d6+=15×0.2•目标函数：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)•以上目标规划模型可用单纯形法求解，得到多重解。现将这些解汇总于表4-9，这单位的领导再按具体情况，从表4-9中选一个执行方案变量含义解1解2解3解4x1x2x3d1-d2-d3-d4-d5+d6+晋升到Ⅰ级的人数晋升到Ⅱ级的人数新招收Ⅲ级的人数工资总额的结余额Ⅰ级缺编人数Ⅱ级缺编人数Ⅲ级缺编人数Ⅱ级超编人数Ⅲ级超编人数2.43063000.62.43002.43333000.62.40003333000030.60035500100.62例7已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表4-10。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优先等级：•P1——B4是重点保证单位，必须全部满足其需要；•P2——A3向B1提供的产量不少于100；•P3——每个销地的供应量不小于其需要量的80%；•P4——所定调运方案的总运费不超过最小运费调运方案的10%；•P5——因路段的问题，尽量避免安排将A2的产品往B4；•P6——给B1和B3的供应率要相同；•P7——力求总运费最省。•试求满意的调运方案。表4-10销地产地B1B2B3B4产量A1A2A3534255642763300200400销量200100450250900/1000解上作业法求得最小运费的调运方案见表4-11。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。销地产地B1B2B3B4产量A1A2A3虚设点200100200250150100300200400100销量2001004502501000/1000表4-11•供应约束x11+x12+x13+x14≤300•x21+x22+x23+x24≤200•x31+x32+x33+x34≤400•需求约束：x11+x21+x31+d1--d1+=200•x12+x22+x32+d2--d2+=100•x13+x23+x33+d3--d3+=450•x14+x24+x34+d4--d4+=250•A3向B1提供的产品量不少于100•x31+d5--d5+=100•每个销地的供应量不小于其需要量的80%•x11+x21+x31+d6--d6+=200×0.8•x12+x22+x32+d7--d7+=100×0.8•x13+x23+x33+d8--d8+=450×0.8•x14+x24+x34+d9--d9+=250×0.8调运方案的总运费不超过最小运费调运方案的10%31411010%)101(2950ijijijddxc•因路段的问题，尽量避免安排将A2的产品运往B4•x24+d11--d11+=0•给B1和B3的供应率要相同•(x11+x21+x31)-(200/450)(x13+x23+x33)+d12--d12+=0力求总运费最省314113132950ijijijddxc目标函数为：13712126115104987635241)()(mindPddPdPdPddddPdPdPz计算结果，得到满意调运方案见表4-12。销地产地B1B2B3B4产量A1A2A3虚设点90100101001102509020050300200400100销量2001004502501000总运费为3360元。元336050320072502110410021004903C第2节解目标规划的图解法•对只具有两个决策变量的目标规划的数学模型，可以用图解法来分析求解。用例2来说明（图4-1）。3,2,1,0,,,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii•注意目标规划问题求解时，把绝对约束作最高优先级考虑。在本例中能依先后次序都满足d1+=1，d2++d2-=0，d-3=0，因而z*=0。但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为满意解。例3某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：•第一优先级：充分利用装配线每周计划开动40小时；•第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；•第三优先级：装