7运筹学之目标规划

《7运筹学之目标规划》由会员分享，可在线阅读，更多相关《7运筹学之目标规划（24页珍藏版）》请在装配图网上搜索。

1、第七章目标规划1目标规划的提出线性规划问题是讨论一个给定的线性目标函数在一组线性约束 条件下的最大值或最小值问题。对于一个实际问题，管理科学者根据 管理层决策目标的要求，首先确定一个目标函数以衡量不同决策的优 劣，且根据实际问题中的资源、资金和环境等因素对决策的限制提出 相应的约束条件以建立线性规划模型；然后用计算机软件求出最优方 案并作灵敏度分析以供管理层决策之用。而在一些问题中，决策目标 往往不只一个，且模型中有可能存在一些互相矛盾的约束条件的情 况，用已有的线性规划的理论和方法无法解决这些问题。因此，1961 年美国学者查恩斯(A.Charnes)和库柏(W.W.Coopor)提出了目标

2、 规划的概念与数学模型，以解决经济管理中的多目标决策问题。我们将通过几个例子来说明在实际应用中线性规划存在一系列 的局限性。例1某厂生产A、B两种产品每件所需的劳动力分别为4个人工和 6个人工，所需设备的单位台时均为1。已知该厂有10个单位机器台 时提供制造这两种产品，并且至少能提供70个人工。又，A、B产品 的利润，每件分别为300元和500元。试问：该厂各应生产多少件A、 B产品，才能使其利润值最大？解 设该厂能生产A、B产品的数量分别为气,七件，则有max z - 300x + 500xA CX1+X2 V I0s.t 70x 0, j -1,2.i j图解法求解如下：电+砺=10图7-

3、1由上图可得，满足约束条件的可行解集为0，即机时约束和人工 约束之间产生矛盾，因而该问题无解。但在实际中，该厂要增加利润， 不可能不生产A、B两种产品，而由线性规划模型无法为其找到一个 合适的方案。例2某厂为进行生产需采购A、B两种原材料，单价分别为70元/ 公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少 于80公斤，而A原材料不少于20公斤。问如何确定最好的采购方 案(即花掉的资金最少，购买的总量最大)？解 这是一个含有两个目标的数学规划问题。设气,x2分别为购买两种 原材料的公斤数，f (x ,x)为花掉的资金，f (x,x)为购买的总量。建 112212立该问题的数学模

4、型形式如下:min f (尤,尤)=70x + 50x1 (12 )12max f (x ,x )= x + x2121270x + 50x 8012x1 20x , x 0对于这样的多目标问题，线性规划很难为其找到最优方案。极可能的结果是，第一个方案使第一目标的结果值优于第二方案，同时第 二方案使第二目标的结果值优于第一方案。也就是说很难找到一个最 优方案，使两个目标的函数值同时达到最优。另外，对于多目标问题， 还存在有多个目标存在有不同重要程度的因素，而这也是线性规划所 无法解决的。在线性规划的基础上，建立了一种新的数学规划方法一一目标规 划法，用于弥补线性规划的上述局限性。总的来说，目标

5、规划和线性 规划的不同之处可以从以下几点反映出来：1、线性规划只能处理一个目标，而现实问题往往存在多个目标。目标规划能统筹兼顾地处理多个目标的关系，求得切合实际需求的 解。2、线性规划是求满足所有约束条件的最优解。而在实际问题中， 可能存在相互矛盾的约束条件而导致无可行解，但此时生产还得继续 进行。即使存在可行解，实际问题中也未必一定需要求出最优解。日 标规划是要找一个满意解，即使在相互矛盾的约束条件下也找到尽量 满足约束的满意解，即满意方案。3、线性规划的约束条件是不分主次地等同对待，这也并不都符合 实际情况。而目标规划可根据实际需要给予轻重缓急的考虑。2目标规划的基本概念与数学模型 2.1

6、基本概念在这一小节里介绍与目标规划有关的基本概念。1 .偏差变量对于例1,造成无解的关键在于约束条件太死板。设想把约束条 件“放松”比如占用的人力可以少于70人的话，机时约束和人工约 束就可以不再发生矛盾。在此基础上，引入了正负偏差的概念，来表 示决策值与目标值之间的差异。d+ 正偏差变量，表示决策值超出目标值的部分，目标规划里 规定d + 0 ;id:负偏差变量，表示决策值未达到目标值的部分，目标规划 里规定d- 0。i实际操作中，当日标值（也就是计划的利润值）确定时，所作的 决策可能出现以下三种情况之一：（1）决策值超过了目标值（即完成或超额完成计划利润值），表 示为 d+ 0，d-= 0

7、;（2）决策值未达到目标值（即未完成计划利润值），表示为d+= 0，d - 0 ；（3）决策值恰好等于目标值（即恰好完成计划利润指标），表示 为 d + = 0， d - = 0。以上三种情况，无论哪种情况发生，均有d + d- =0o2. 绝对约束与目标约束绝对约束也称系统约束，是指必须严格满足的等式约束和不等式 约束，它对应于线性规划模型中的约束条件。目标约束是目标规划所特有的。当确定了目标值，进行决策时， 允许与目标值存在正或负的偏差。因而目标约束中加入了正、负偏差 变量。如，例1中假定该企业计划利润值为5000元，那么对于目标函数max z = 300七+ 500%，可变换为300气

8、+ 500% + d- - d + = 5000。该式表示决策值与目标值5000之间可能存在正或负的偏差（请读 者分别按照上面所讲的三种情况来理解）。绝对约束也可根据问题的需要变换为目标约束。此时将约束右端 项看作所追求的目标值。如，例1中绝对约束气+ % 0 (j=, n,d -, d + 0(k = 1,2, ., K )k k例3在例1中，假定目标利润不少于15000元，为第一日标；占用 的人力可以少于70人，为第二目标。求决策方案。解 按决策者的要求分别赋予两个目标大m系数M,M2。列出模型如下：min z - M d - + M d+1 12 2300x + 500x + d -d

9、+ -1500012114 x + 6 x + d -d + - 70S.t 0i -1,2,3.V 12 i i例4某纺织厂生产A、B两种布料，平均生产能力均为1千米/小时， 工厂正常生产能力是80小时/周。又A布料每千米获利2500元，B 布料每千米获利1500元。已知A、B两种布料每周的市场需求量分 别是70千米和45千米。现该厂确定一周内的目标为:第一优先级：避免生产开工不足；第二优先级：加班时间不超过10小时；第三优先级：根据市场需求达到最大销售量；第四优先级：尽可能减少加班时间。试求该问题的最优方案。解 设气,x2分别为生产甲、乙布料的小时数。对于第三优先级目标， 根据A、B布料利

10、润的比值2500:1500 -5:3,取二者达到最大销量的权系数分别为5和3。该问题的目标规划模型为：min z - M d - + M d + + M (5d - + 3d -)+ M d+1 12 23344 1x + x + d d + 80 1211x + x + d - 一 d + - 90 1222气+ d- d+ - 70i -1, ,4.x2 + d-d4- -45x , x , d -, d + 012 i i综上所述，目标规划建立模型的步骤为：1、根据问题所提出的各目标与条件，确定目标值，列出日标约束与绝对约束；2、根据决策者的需要将某些或全部绝对约束转换为目标约束， 方法

11、是绝对约束的左式加上负偏差变量和减去正偏差变量；3、给各级目标赋予相应的惩罚系数M( k = 1,2,K)，M为无穷 大的正数，且M1 M. m4、对同一优先级的各目标，再按其重要程度不同，赋予相应的 权系数o ；kl5、根据决策者的要求，各目标按三种情况取值：恰好达到目标 值，取d+ d-允许超过目标值，取d-不允许超过目标值，取d+; 然后构造一个由惩罚系数、权系数和偏差变量组成的、要求实现极小 化的目标函数。3目标规划的求解3.1图解法只有两个决策变量的目标规划数学模型，可以使用简单直观的图 解法求解。其方法与线性规划图解法类似，先在平面百角坐标系第一 象限内作出各约束等式或不等式的图象

12、，然后由绝对约束确定了可行 域，由目标约束和目标函数确定最优解或满意解。对于绝对约束，与线性规划中的约束条件画法完全相同。对于日 标约束方程，除作出直线外，还要在直线上要标出正负偏差变量的方 向，其可行域方向取决于目标函数中对应目标。另外，目标规划是在 前一级目标满足的情况下再来考虑下一级目标，很有可能尽可能满足 目标的解不是可行解（即非可行解），而是权衡以后得出的最优解一 一满意解。因而在目标规划里称求得的解为满意解。注意在求解的时候，把绝对约束作最高级别考虑。例5用图解法求解目标规划问题min z = Mi（d一+ d +）+ M d一+ M d+11223x - x + d - - d

13、+ = 03气 + 5 x 2+ d - 2- d + =154 气 + 3x 2+ d - 3- d +=24x + x 0 i = 1,2,3.12 i i解在平面百角坐标系第一象限内作出各约束条件的图像，目标约束要在直线旁标上七和首先，绝对约束气+% =80100so806加班时间限制1190=d5025g9诀策交量702010总偏移量62.5规划或解契!设宜目株单元格口： SfitlU iJ若于:C第大值曲#最小值也） 可竟单元格（B）|jBS9:$CS9.fcS5H0 约束皿DI5=SWIPmilCT（B5：Cba B9：C9）=D5-（b+H56=SQIPRmUCT （B6 m B

14、勺:西=D6-G6+H67-SUKPRODUCT（BT：C7, B9：C9）=D7-G7+H73二迎PRODUCTS 土国 B9：C9）=D8-GS+HS规却家麟迷溟|JIS5:TIS0 JKS5:JSGG10=5*H5+4*G6+3. 5州T+亢说关+G5旧京用畿性摸墅如 F假定宰鱼图7-4单元格（B5:C8），实际上是决策变量在日标规划数学模型中的系 数，又可理解为对各对应因素的单位贡献。如单元格B5是产品1对 开工时间这一因素的单位贡献，即生产1千米的A布料使开工时间 增加1。D列计算了决策变量对每一因素的总贡献值。如单元格D5为总 的开工时间，由公式SUMPRODUCT（B5:C5,B

15、9:C9）计算而得。（B9:C9）为可变单元格，（G5:H8）为附加的可变单元格。G、H、I、K列是该模型微妙所在。G列和H列分别表示了实际 的正负偏差的值。I列按照数学模型中日标约束方程计算出的左端值。 如单元格I5为第一个日标约束方程的左端值，由D5-G5+H5计算而 得。单元格G10为目标单元格，它是各因素未达日标的总偏差（总罚 数）。但是要注意的是，比如第一级目标，只有负偏差大于0时，才 会产生罚数。同样的第二级目标只有正偏差大于0时才会产生罚数。 依此类推。在这里，决策者还要根据实际情况给出各级目标的罚系数， 本题给出的假定罚系数见单元格G10的计算公式。注意，目标等级 越高，罚系数

16、越大。目标是使总罚数最小。在规划求解参数对话框里，给出目标单元格、可变单元格和约束。 约束是使目标约束等式两端相等。由于依然属于线性规划问题，仍需在选项对话框里选择“采用线 性模型”和“假定非负”复选框。可以看到图7-4的计算结果与前面两种方法相同。对于包含有绝对约束的目标规划模型，绝对约束的优先等级高于 任何目标约束，因而要把它放入规划求解的约束条件里。例8将例3中的目标利润改为4000，试用EXCEL求解最优方案。解 该问题包含有一个绝对约束：机时约束气+ % 素润丁时策 即利A机氏006 1 005=目标值正偏差负偏差总和右端常数如D04000400002270YDL0豹哀总偏离量0nI

17、5= SUIPR02UCT(B5:C5, B3：CB；=D5-G5+H56=SUIPfiODUlCT (B6 烙 08：C8i=D&-G6+H67=SUIPR0DUCT(B7:C7,B3：:CS)规划求蘑理顼H10=1供匪+GWP衰用慢性枝盟） F假定率鱼设置目衍隼无招电：Iwiu v| 等于：L毋夫恒吵 花是小值也 可蜜角元格： IsEjacfs.jflSEKse 约康敏 |SDf? 0(i = 1,2,3).12 i i(2)(3)min z = M (d - + d+) + M (d - + d+)111222x + x 4;x + 2x 6;s.t 0(i = 1,2).12 i im

18、in z = M d + + M d - + M1 32 23(d- + d+)6 x1 + 2 x2 + d-d+ = 24;x + x + d d + = 5;St 12225 x + d -d += 15;x , x ,d-,d + 0(i = 1,2,3).12 i imin z = M d - + M d + + M d - 1 12 23 3K 3,2 x + x + dd + = 210;12 211(4)x + d- -d+ = 60;x + d - - d + = 45;x 0.12 i i7.3某厂组装两种产品，有关数据如表7-1。要求确定两种产品的日生产计划，并满足：（1

19、）不得使装配线超负荷生产；（2）不得有剩余产品；（3）日产值尽可能达到5000元。试找出满意解，并用图示说明之。表7-1产单件组装工产值（元/日装配日销量（件）品时件）能力A1.17040150B1.360607.4上题中，若将目标要求改为：（1）尽可能发挥工厂的装配能力；（2）尽可能满足市场的需求，并使产量与销量保持一致；（3）装配生产线可加班，但时数不得超过30小时；（4）尽可能使日产值最大。试定出两种产品满意的日产计划。7.5已知目标规划问题的约束条件如下：C11C2 x + x + d d + = 2；121112x - 3x + d- d+= 6;x.6; 2 2 2x , x ,

20、d -, d + 0（/ = 1,2） 、12 i i求在下述各目标函数下的满意解：（1）min z = M （d - + d + + d - + d+）I 1122（2）minz = 2M （d-+ d+） + M （d- + d+）111222（3）minz = M（d- + d+） + 2M2（d- + d+）（4）minz = M （d-+ d+） + M （d-+ d+）II 12227.6某公司要将一批货从三个产地运到四个销地，有关数据如表7-2。现要求订出调运计划，且依次满足：（1）b4要保证供应；（2）其余销地的供应量不低于80%；（3）A2给B2的供应量不低于150；（4）A

21、2尽可能少给B1；（5）销地B1、B2的供应量尽可能保持平衡。要求：（1）建立使总运费最小的日标规划模型？（2）建立该问题的电子表格模型，并用EXCEL规划求解进行求 解。表7-2地销地B1B 2B3B4供应量A17379560A226511400A36425750需求量3202404803807.7某公司的管理层已经为其公司的两种新产品制定了各自的 市场日标，具体地说，产品1必须占据15%的市场份额，而产品2 必须有10%的市场份额。为了获得市场，准备开展三次广告活动，其 中两个广告是分别针对产品1和产品2的，而广告3是为了提高整个 公司及其产品的声誉。以x,x ,x分别表示分配在三个广告上

22、的资金123（以百万元为单位），相应的两种产品取得的市场份额估计值（以百 分比表示）为产品1的市场份额=0.5 x 0.2 x13产品2的市场份额=0.3x 0.2x13广告总预算为5500万元，其中必须有至少1000万投资在第 三个广告上。如果两个产品的市场份额目标不能同时实现，管理层认 为两种产品上目标偏离的严重性是同等的。在上述条件下，管理曾希 望得到最有效的资金分配方法。试：（1）建立该问题的数学模型；（2）建立电子表格模型，并用EXCEL规划求解进行求解。7.8某发展中国家有1500万亩共用耕地，该过政府目前正计划 将这些土地分配给三种基本的农作物。生产的农产品一部分出口以换 取紧缺

23、的外币，剩下的是居民的食粮。种植这些农作物也为国家相当 一部分人提供了就业。因此，在分配土地时要考虑的主要因素为：（1） 能获得的外币，（2）可供养的居民数，（3）种植农作物需要的劳动力。 表7-3给出了各种农作物每千亩产量对三个因素的贡献，表的最后一 列为政府给三个因素建立的目标。在估计各个目标的重要性时，政府 认为下面的三个因素是同等重要的，或者说如果目标不能达到的话， 问题的严重性是同等的：（1）外币数量少于目标值100元，（2）供养 目标中有一个人不能得到足够的食物，（3）需要的劳动力比劳动力目 标少或多一人。试：（1）建立该问题的数学模型；（2）建立电子表格模型，并用EXCEL规划求解进行求解；（3）对该问题进行如下的what-if分析：（a）若改变各因素的重 要程度，三因素的罚系数分别设为7, 5, 3,会产生怎样的结果；（b） 若将外币数量的最少目标值100改为200,保持原来的罚数权重不变 的情况，会有什么影响？表7-3因素每千亩底的贡献目标123外币30005000400070000000可供养的居民150751001750000可雇佣的居民101512=20000022