7运筹学之目标规划(胡运权版)

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产品的数量分别为 x1,x2件，则有max z 300x1 500x2 x1 x2 10st 4x1 6x2 70X 0, j 1.2.图解法求解如下：玉+西=10由上图可得，满足

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

4、1 x1, x270x1 50x2max f2 x1 ,x2x1x21570x1 50x2 5000s.t.x1 x2 80x1 20x1, x2 0对于这样的多目标问题，线性规划很难为其找到最优方案。极可能的结果是，第一个方案使第一目标的结果值优于第二方案，同时第二方案使第二目标的结果值优于第一方案。也就是说很难找到一个最优方案，使两个目标的函数值同时达到最优。另外， 对于多目标问题，还存在有多个目标存在有不同重要程度的因素，而这也是线性规划所无法解决的。在线性规划的基础上，建立了一种新的数学规划方法目标规划法，用于弥补线性规划的上述局限性。总的来说，目标规划和线性规划的不同之处可以从以下几

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

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

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

8、 之间可能存在正或负的偏差（请读者分别按照上面所讲的三种情况来理解）。绝对约束也可根据问题的需要变换为目标约束。此时将约束右端项看作所追求的目标值。如，例1 中绝对约束x1 x2 10，可变换为目标约束x1 x2 didi10 。3目标规划的目标函数对于满足绝对约束与目标约束的所有解，从决策者的角度来看，判断其优劣的依据是决策值与目标值的偏差越小越好。因此目标规划的目标函数是与正、负偏差变量密切相关的函数，我们表示为min z f di ,di 。它有如下三种基本形式：（ 1）要求恰好达到目标值，即正、负偏差变量都尽可能地小。此时，构造目标函数为： min z didi（ 2）要求不超过目标值

9、，即允许达不到目标值，正偏差变量尽可能地小。此时构造目标函数为：min z di（ 3）求超过目标值，即超过量不限，负偏差变量尽可能地小。此时构造目标函数为： min z di4优先次序系数与权系数一个规划问题往往有多个目标。决策者在实现这些目标时，存在有主次与轻重缓急的M 系数：M1 , M2 ,不同。又于有 K级目标的问题，按照优先次序分别赋予不同大小的大，Mk。Mi , M2 ,，M k为无穷大的正数，并且， MiM2Mk ： 符号表示“远大于”），这样，只有当某一级目标实现以后 （即目标值为0），才能忽略大 M 的影响，否则目标偏离量会因为大 M的原因而无穷放大。 并且由于M kM k

10、 1 ,所以只有 先考虑忽略Mk影响（实现第k级目标）后，才能考虑第 k 1级目标。实际上这里的大 M 是对偏离目标值的惩罚系数，优先级别越高，惩罚系数越大。权系数i用来区别具有相同优先级别的若干目标。在同一优先级别中，可能包含有两个或多个目标，它们的正负偏差变量的重要程度有差别，此时可以给正负偏差变量赋予不同 的权系数i和i。各级目标的优先次序及权系数的确定由决策者按具体情况给出。§ 2.2目标规划的数学模型综上所述，目标规划模型由目标函数、目标约束、绝对约束以及变量非负约束等几部 分构成。目标规划的一般数学模型为：目标函数min ZKLM kkdkdk 1l 1目标约束nGjXj

11、 j idi di gil 1,2,| L绝对约束naijxj j 1,b i 1,2,| m非负约束xj0j 1,2，|ndk 40 k 1,2,|,K例3在例1中，假定目标利润不少于15000元，为第一目标；占用的人力可以少于70人,为第二目标。求决策方案。解 按决策者的要求分别赋予两个目标大M系数M1,M 2o列出模型如下：min z M1d1M2d2300x 500x2 d1 d1150004x1 6x2 d2 d270s.tx1 x2 10x1,x2,di ,di0 i 1,2,3.例4某纺织厂生产 A、B两种布料，平均生产能力均为1千米/小时，工厂正常生产能力是80小时/周。又A布

12、料每千米获利 2500元，B布料每千米获利 1500元。已知A、B两种布 料每周的市场需求量分别是 70千米和45千米。现该厂确定一周内的目标为：第一优先级：避免生产开工不足；第二优先级：加班时间不超过10小时；第三优先级：根据市场需求达到最大销售量；第四优先级：尽可能减少加班时间。试求该问题的最优方案。解 设x1,x2分别为生产甲、乙布料的小时数。对于第三优先级目标，根据 A、B布料利润的比值2500:1500 5:3 ,取二者达到最大销量的权系数分别为5和3。该问题的目标规划模型为：min z M 1d1M 2d2 M3 5d3 3d4M 4d1x1 x2 d1 d180x1 x2 d2

13、d290s.tx1 d3 d3 70x2 d4 d445x1,x2,di ,di 0综上所述，目标规划建立模型的步骤为：1、根据问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；2、根据决策者的需要将某些或全部绝对约束转换为目标约束，方法是绝对约束的左式 加上负偏差变量和减去正偏差变量；3、给各级目标赋予相应的惩罚系数Mk (k 1,2,|K ), Mk为无穷大的正数，且M1M2M k ;4、对同一优先级的各目标，再按其重要程度不同，赋予相应的权系数h；5、根据决策者的要求，各目标按三种情况取值：恰好达到目标值，取di di允许超过目标值，取di不允许超过目标值，取 di ;然后构

14、造一个由惩罚系数、权系数和偏差变量组成的、要求实现极小化的目标函数。§ 3目标规划的求解3. 1图解法只有两个决策变量的目标规划数学模型，可以使用简单直观的图解法求解。其方法与线性规划图解法类似， 先在平面直角坐标系第一象限内作出各约束等式或不等式的图象，然后由绝对约束确定了可行域，由目标约束和目标函数确定最优解或满意解。对于绝对约束，与线性规划中的约束条件画法完全相同。对于目标约束方程，除作出直线外，还要在直线上要标出正负偏差变量的方向，其可行域方向取决于目标函数中对应目标。另外，目标规划是在前一级目标满足的情况下再来考虑下一级目标，很有可能尽可能满足目标的解不是可行解（即非可行解

15、）,而是权衡以后得出的最优解一一满意解。因而在目标规划里称求得的解为满意解。注意在求解的时候，把绝对约束作最高级别考虑。例5用图解法求解目标规划问题min z M 1d1d1M 2d2 M 3d3x1 x2 d1d103x15x2d2d215s.t4x13x2d3d324x1 x2 7x1,x2,di ,di0 i 1,2,3.解 在平面直角坐标系第一象限内作出各约束条件的图像，目标约束要在直线旁标上di和 di+。首先，绝对约束x1 x2 7确定了可行解范围在三角形 OEF内;根据第一级目标，要求实现min d1d1(恰好)，因而可行解范围缩小到线段OC上；根据第二级目标，要求实现mind?

16、(不少于)，在线段 OC上，取d2 0的点A,此时可行解范围缩小到线段 AC上；根据第三级目标，要求实现min d3 ,在线段AC上，取d30的点B,此时解的范围缩小到线段AB上。所以，线段AB上的所有点为满意解。可求得 A(15/8,15/8) , B(24/7,24/7)。例6用图解法求解 例4的目标规划模型。解在平面直角坐标系第一象限内作出各约束条件对应的图象，并在目标约束直线旁标上di 和 di目标函数要求实现min di ,解的范围是线段 AC的右上方区域;根据第一级目标,根据第二级目标,目标函数要求实现 min d2 ,解的范围缩小到四边形 ABDC内的区域;根据第三级目标，目标函

17、数要求实现min 5d3 3d4 ,先考虑min 5d3 ,解的范围缩 小为四边形 ABFE内的区域，再考虑 min 3d4 ,四边形 ABFE内的所有点，均无法满足d4 0,此时在可行域 ABFE内考虑使d4达到最小的满意点 F, F点不满足d4 0,但它是使第三级目标最满意的满意解；根据第四级目标，目标函数要求实现mind1 ,由于解的范围已经缩小到点F,所以唯一的点F也是使第四级目标最满意的满意解。综上所述，该问题的满意解为点F,可求得F(70,20)。给出图解法求解步骤如下：1、在直角坐标系的第一象限作出绝对约束和目标约束的图象，绝对约束确定出可行解的区域，在目标约束直线上用箭头标出正

18、负偏差变量值增大的方向(正、 负偏差变量增大的方向相反)；2. 在可行解的区域内，求满足最高优先等级目标的解；3、转到下一个优先等级的目标，在满足上一优先等级目标的前提下，求出满足该等级目标的解；4、重复3，直到所有优先等级目标都审查完毕；5、确定最优解或满意解。3. 2 单纯形法目标规划是线性规划的推广与发展，其数学模型结构与线性规划的数学模型结构没有本质的区别，求解线性规划的单纯形法，同样也是目标规划的求解方法。在目标规划里加入了大 M 惩罚系数，可用大M 法来进行求解。这里不再举例。用单纯形法求解目标规划，迭代结束有两种情况。一种所有检验数均已非负时，所获得的解使所有目标偏离量为0，此解

19、为最优解。另一种情况是所有检验数均已非负时，并没有使所有目标达到最优值，但达到最优的目标值一定是优先等级排在前面的，此时获得的解为满意解。如 例4用单纯形法求的满意解为70,20 T,目标值为z 75M3 10M4 ,可以看到求得的解并没有使第三级和第四级目标达到最优，但已使第一、二级目标达到最优，这和前面用图解法求得的结果一致。4. 3 EXCEL 电子表格法目标规划同样能由EXCEL 求得其满意解。关键在于如何建立电子表格模型。例 7 用 EXCEL 求解 例 4的目标规划模型。解 我们来看一下如何为例4 中的目标规划问题建立电子表格模型，见图7-4。口IS二 SUMP 阅 DUCT 胱:

20、快 B9：C9)二D5寸品展6= SWJWDUCT(B6:CGaB9;C9)=D6Y&iH6T=SUMPRODUCT(B7:CT, 59:C幻司 7fT+H78=stmpR)ODUCT能: c乱斑：cq)=D8-G8+HB10 =5*H5+4*GE+3, 5*HT*2, L小Hg+G5蜕知军就选通田*用情号注型 P脖京丰余国ABCDEFc1某坊织厂最优产品型合何题2各产品对各因考t3的单位商耐的需右4因素产品1产品2目标图正面差负偏差总和端常数5开工时间11>=80100 .80=8D 16加班时间隈制119 口<=go0090二9。17A布料销售量107070007070

21、 I0口布米辟善量0120>=02S4B=噩g决策变量702。总偏移旱52, 5胡划茕静基群iSS目3福；Ijgiic 2d 等于广量文倒篁后曼卜债用 可芟曲元崎'U I用舐 其行.为并,刑专 由可明pus：皿 & g：m图7-4单元格（B5:C8）,实际上是决策变量在目标规划数学模型中的系数，又可理解为对各 对应因素的单位贡献。如单元格B5是产品1对开工时间这一因素的单位贡献，即生产 1千米的A布料使开工时间增加 1。D列计算了决策变量对每一因素的总贡献值。如单元格 D5为总的开工时间，由公式 SUMPRODUCT（B5:C5,B9:C9）计算而得。（B9:C9）为可变

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

23、给出目标单元格、可变单元格和约束。约束是使目标约束等 式两端相等。由于依然属于线性规划问题，仍需在选项对话框里选择“采用线性模型”和“假定非负” 复选框。可以看到图7-4的计算结果与前面两种方法相同。对于包含有绝对约束的目标规划模型，绝对约束的优先等级高于任何目标约束，因而要把它放入规划求解的约束条件里。例8将例3中的目标利润改为 4000,试用EXCEL求解最优方案。解 该问题包含有一个绝对约束：机时约束x1 x2 10 ,把它定义到规划求解对话框的约JI束里。模型与求解结果见图7-5。保证绝对约束问麴各产品对各国素因索利润人工机时 决策变量的单位灵植产品1产品230Qq500息克秋唱4Q0

24、Q488>=>-c=口标值正隔差负偏差40007010022总和41m70右湍常数钝gTODI5三 SUffPRDDUCTtSS :C5t BE:C8)-D5-G5+H56:£UNPR0DUCT(M=C6m B8：C8)=D6H6+H67=EUHPRODUCT(B7：C7,BE:C8)总偏离量0F褒用续性模里V g腾定率货10=10*强467.1判断以下目标规划的目标函数是否正确。(1) maxz dd(3) maxz dd(4)7.2用图解法求解下列目标规划问题:min z M1d1M 2d3M 3d2；x1 2x2 d1 d14;(1)x1 2x2 d2 d24;s.

25、tx 2x2 d3 d38;X,x2,di,di0(i 1,2,3).min z ddmin z ddmin z M1d3M2d2M3 d1d13336x1 2x2 d1d124;),X x2 d2 d25;s.t5x2 d3 d315;为公"© 0(i 1,2,3).10理置目标单元施皂u iMiJil等于；r最大n中仃金小值0D 可支单元喳£班旧醛的SHJSG妁荣如:皿 0 (K7pm srfia = *小 £中图7-5模型中对两目标的罚系数分别设为10和1。求解结果，利润目标实现了，人工也少于70,目标偏离量为 0。习题min z M1d1M 2d

26、2 M3d3min z M1(d1d1 ) M2(d2 d2)X X2 4;x1 2x2 6;(3)s.t 2x1 3x2 d1d118;3x1 2x2 d2 d2 18;为©40(i 1,2).2x1x2 d1d1210;2x1 d2 d260;(4) 122s.tx2 d3 d345;x2 80;x1,x2,di ,di0.并满足:7.3某厂组装两种产品，有关数据如表7-1。要求确定两种产品的日生产计划,(1)不得使装配线超负荷生产；(2)不得有剩余产品；(3)日产值尽可能达到 5000元。试找出满意解，并用图示说明之。表7-1产品单件组装工时日销量(件)产值(元/件)日装配能力

27、A1.17040150B1.360607.4上题中，若将目标要求改为：(1)尽可能发挥工厂的装配能力；(2)尽可能满足市场的需求，并使产量与销量保持一致;(3)装配生产线可加班，但时数不得超过30小时;(4)尽可能使日产值最大。试定出两种产品满意的日产计划。7.5已知目标规划问题的约束条件如下：2x1 x2 d1 d12;2x1 3x2 d2 d26;s.tx 6;x1,x2,di ,di0(i 1,2)求在下述各目标函数下的满意解：(1) min z M1(d1 d1 d2 d2)(2) min z 2M1(d1 d1 ) M2(d2 d2)(3) min z M1(d1d1 ) 2M2(d2 d2)(4) min z M1(d1d1 ) M2(d2 d2)7.6 某公司要将一批货从三个产地运到四个销地，有关数据如表7-2。现要求订出调运计划，且依次满足：(1) B4要保证供应；(2) 其余销地的供应量不低于80%;(3) A2给B2的供应量不低于150;(4) A2尽可能少给Bi;(5) 销地Bi、B2的供应量尽可能保持平衡。要求：(6) 建立使总运费最小的目标规划模型？(7) 建立该问题的电子表格模型，并用 EXCEL规划求解进行求解。表7-2B1B2B3B4供应量A17379560A226511400A36425750需求重3202404803807.7 某公司的