第7章 目标规划

1、山西大学经济与管理学院山西大学经济与管理学院运筹学运筹学主讲：范建平主讲：范建平 博士博士第7章 目标规划第7章 目标规划2022年6月5日星期日山西大学经济与管理学院 范建平2p目标规划（目标规划（Goal programming，GP）是多目标线性规划）是多目标线性规划的一种模型与方法，可以解决线性规划无法解决的一些的一种模型与方法，可以解决线性规划无法解决的一些实际问题。实际问题。p它以线性规划为基础，其模型结构与算法本质上同线性它以线性规划为基础，其模型结构与算法本质上同线性规划一致，但也有自己的特点。规划一致，但也有自己的特点。7.1 基本模型2022年6月5日星期日山西大学经济与管

2、理学院 范建平37.1.1 问题的由来2022年6月5日星期日山西大学经济与管理学院 范建平4p线性规划模型在实际应用中主要有以下线性规划模型在实际应用中主要有以下2点不足：点不足：n（1）线性规划只有一个目标函数，只能使一个目标最优化。线性规划只有一个目标函数，只能使一个目标最优化。n（2）线性规划能付诸实施的一个前提是可行域非空集。线性规划能付诸实施的一个前提是可行域非空集。【例7-1】2022年6月5日星期日山西大学经济与管理学院 范建平5p某化工厂用某种成套设备生产甲、乙两种产品，单耗分别为每吨某化工厂用某种成套设备生产甲、乙两种产品，单耗分别为每吨2、3工时，而设备正常生产每天最大运

3、行能力为工时，而设备正常生产每天最大运行能力为18工时，需要增加能工时，需要增加能力可加班运行。甲、乙产品利润分别为力可加班运行。甲、乙产品利润分别为500元元/吨、吨、400元元/吨，每周吨，每周需求量分别为需求量分别为30、20吨。该厂希望两种产品，每天利润达到吨。该厂希望两种产品，每天利润达到4000元元以上，产量符合需求量比例，还希望充分利用设备正常生产能力，以上，产量符合需求量比例，还希望充分利用设备正常生产能力，但尽量避免加班，则应如何安排生产？但尽量避免加班，则应如何安排生产？ 单耗单耗/ /（工时（工时/ /吨）吨）最大生产能力最大生产能力/(/(工时工时/ /天天) )甲乙设

4、备2318利润/（1100元/件）54需求量（吨/周）3020【例7-1】2022年6月5日星期日山西大学经济与管理学院 范建平63本例有利润、产量、产能 项目标，属于。若只考虑利润一项目标，而将产量、产能目标转化为约束条件，就成为一个多目线性标规划问解题规划问题。 121212121212zmax 54064s.t. 2302+7-1a318,0 xxzxxxxxxxxxx设 每天甲、乙产品的产量为、吨，总利润为1 100 元，数学模型如下：、式：甲、乙产品的周需求量除以每周工作日5.式：甲、乙产品的需求量比例约束【例7-1】山西大学经济与管理学院 范建平7CAO(0,0)z法向2x1+3x

5、2=18x1x269BED*129 2/,3/;347-1O0F5Fxxz吨用图解法求解，见图，可行域为线段，而点 即给出最优解该结果未能使利润达到目标天吨 天元4值：000元。2x1-3x2=0图 7-1 1212121211227-1b5447-27-1amax 54064230s.t.2318,0.0 xxzxxxxxxxxxx若给式增加利润约束：见图F【例7-1】CAO(0,0)z法向2x1+3x2=18x1x269BED1254407-2xx见图可行域为空集。线增加性规一个新约束。：划无能为力。2x1-3x2=0F图 7-2 而目标规划则不把式、作为硬性约束，而是作为三个目标变通处理

6、。108NGM5x1+4x2=4012D6,2EMNDxx若各目标优先满足的顺序为、这样，虽然利润、产量目、，则应在线段上标都未满足，却是在不选择离直线加班的前提最近的一点作为问题的下，利润目解：标最优方案。12120 23,80 23BGOADECGxx这样，利润、产量目标都得若各目标优先满足的顺序为、到满足，但是每天消耗设备能力约为2，则应在线1工时，超段上选择离五边形最近的一点 作过正常生产能力18工时，需加为问题的解：班3工时。 121212121122max 54064230s7-1b.t.2544318,00zxxxxxxxxxxxx7.1.2 基本概念山西大学经济与管理学院 范建

7、平9 7-121-11.7目标约束刚性约束弹性约束：也称系统约束，必需满足的约束。如的约束、式；：也称目标约束，是尽量【例】【例】目标规划往往没满足有最的约束；如的式、优解，只有满意解。 121212121122max 54064230s7-1b.t.2544318,00zxxxxxxxxxxxxCAO(0,0)z法向2x1+3x2=18x1x269BED2x1-3x2=0F图 7-2108NGM5x1+4x2=407.1.2 基本概念+2.dd为了刻画满意解对应的每一目标的实际值与目标值的差距，需要引入偏差变量的概念与符号：，表示实际值未达目标值的差距，表示实际值超过目标值的差距正、负偏差变

8、偏差变量负偏差变量正量二者，至少一个取偏差变量值为0.1211-7-1b54+40 xxdd【例7 1】的模型，可为其式同时引入正、负偏差变量，成为：譬如， 111212111211121114025454400;54400;54=40=30;ddxxxxddxxddxxdd当实际值未达到目标值时，即时,则当时,则偏差变量二者当时,，至少一个取值为0，更具体地、0、0、说：则0、7.1.2 基本概念1221,2,3.rkrrPPPP kr由于目标规划有不止一个目标，为了区分其重要性与重要程度，需要引入优先级的概念与符号：若有个目标的重要性相差悬殊，则可划分为 个，并用优先因子表示重要性，其中“

9、”表示“远远重要于”。优先因子是定性因优先级与权数素，非优先级数量指标。-+dd若有几个目标的重要性相差不是很悬殊，则可归于同一优先级。又，则为区别其重要程度的差异，还可以赋予不同的权数；另外，对偏差变量 ，也可赋予不同的权数，而权数是无实际量纲的若其数量纲相同量指标。【例7-1】续123-PPP假设：该厂提出3个目标并规定优先级如下：甲、乙两种产品每天利润达到4000元以上；：甲、乙两种产品的产量符合需求量比下面例；：充分利以【例7 1】来说明如何建立目标规划用设备正常生产能力，并尽量模型避免加班。12111222123354+402 -3+023+1,2,318,kxxddxxddxxdd

10、zk 这样，式、全都需要改成下述目标约束：利润：产量：产下面，分别建立每个优先级能：的目标函数，记为称为分目标函数【例7-1】续2022年6月5日星期日山西大学经济与管理学院 范建平13 1112115440=1in4000mxxddzd 分目标函数：为使两种产品每天利润达到元以上，即，应使；即便达不到这点，也应使最小化，即0 122222222222 -30=0+=0+min2+xxdddddzddd为使两种产品产量符合需求量比例，即，应使或；即便达不到这点，也应使最小化，即 3233333=min3+20ddddzdd为充分利用设备正常生产能力，并尽量避免加班，应使；即便达不到这点，宁肯加

11、班也不闲置设备能力；若认定前者重要程度是后者2倍，则赋予不同权数1、2，即有：，【例7-1】续2022年6月5日星期日山西大学经济与管理学院 范建平14121211112221233121222333-GP6454+40s.t.2 -3+023+18,7-2,0 ,1mi,2,3n 2kkxxxxddxxddxxzPdP ddP dxdddxddk为简化表示，可将上述3个目标合并为如下形式的1个目标，得【例7 1】的模型：7.1.3 一般模型11173=,1,2,73s.t.,1,2,73,min ,0 ,1,2,73nsjjsjnirkkjjiiijjkkkrmaa xbslba xddez

12、imcx ddjndP z 一般目标规划的模型如下：或LLL系统约束目标约束分目标函数7.1.3 一般模型 m1inikiezd若容许不达目标而避免超过目标值 ，如费用、产能、人力等消耗指标，则只引入正偏差变量，即令 -2minikiezd若容许超过目标而避免不达目标值 ，如利润、收益、品质等产出指标，则只引入负偏差变量，即令 -m3inkkiiiiikzw dew d若既避免超过，又避免不达目标，而希望恰好达到目标值 ，则需同时引入正、负偏差变量，并且分别赋权，即令 -1mi4n0.kimkkiikiiiikwwzw dw d若有几个目标属于同一优先级，且其量纲相同，则需适当引入正、负偏差变

13、量，并且分别赋权，或可为即令目标规划的应用案例-加班时间问题17例：某音像店有5名全职售货员和4名兼职售货员，全职售货员每月工作160小时，兼职售货员每月工作80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。每出售一张CD盈利1.5元。 商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超过100小时，建立

14、相应的目标规划模型。目标规划的应用案例-加班时间问题18首先，确定目标约束的优先级。如下：P1：下月的CD销售量达到27500张；P2：全职售货员加班时间不超过100小时；P3：保持全体售货员充分就业，对全职的要比兼职的加倍加倍优先考虑；P4：尽量减少加班时间，对两种售货员区别对待，权重权重由他们对利润的贡献而定。其次，建立目标约束函数（1）销售目标约束，设全体全职售货员下月的工作时间x1，全体兼职售货员下月的工作时间 x2；达不到销售目标的偏差d1-，超过销售目标的偏差 d1+。 1111211min251027500GPdxxdd 目标规划的应用案例-加班时间问题19 （2）正常工作时间约

15、束。设全体全职售货员下月的停工时间d2-，加班时间d2+ ；全体兼职售货员下月的停工时间d3-，加班时间d3+。（3）加班时间的限制。设全体全职售货员下月的加班不足100小时的偏差d4-，加班超过100小时的偏差 d4+ 。两类售货员区别对待，权重比d2+:d3+ =1:3，另一加班目标约束为3323122233min(2)800320GPddxddxdd224144min900GP dxdd4423122233min(3)800320GP ddxddxdd目标规划的应用案例-加班时间问题20 第三，按目标的优先级，写出相应的目标规划模型：1124323423121112223314412mi

16、n(2)(3)251027500800320s.t.900,0,01,2,3,4llGPdP dPddP ddxxddxddxddxddx xddl运用LINGO软件求解得 x1=900,x2=500，下月共销售CD盘27500张，获利275001.5-80015-10022.5-50010=22000。7.2 基本方法2022年6月5日星期日山西大学经济与管理学院 范建平212022年6月5日星期日山西大学经济与管理学院 范建平22pGP的基本方法与的基本方法与LP类同，也是单纯形法，称为目标规类同，也是单纯形法，称为目标规划单纯形法。由于划单纯形法。由于GP有有r(r2)个分目标，所以其单

17、纯形个分目标，所以其单纯形表中的检验数也分表中的检验数也分r行，各行检验数需按不同优先级的数行，各行检验数需按不同优先级的数据分别计算，且据分别计算，且由高到低，逐级优化由高到低，逐级优化（化为非负）。下（化为非负）。下面以面以【例例7-1】说明该法的基本步骤与运算过程。说明该法的基本步骤与运算过程。【例7-1】2022年6月5日星期日山西大学经济与管理学院 范建平231122121211122212332231336454+40s.t.2 -3+023+18,0 ,1,2,3min7-22 kkxxxxddxxzPdP ddP dddxxddx xdddk7.2 基本方法【例7-1】续132

18、41211122212331122233123346454+40s.t.2 -3+023+18,0 ,1,max ,327-42kkxxxxxxddxxzPdPddPdddxxddx x x x ddkd34-GP7 2-1-jxxx由于【例7 1】等一切问题，其目标函数中一切结构变量的系数恒为0，且目标要求恒为，所以只需将一切偏差变量的权系数全部反号，就可将目标函数标准化。在模型的标准化min、两式引入松弛变量，便得【例7 1。、】的标准型o34,1,2,37-4kx x dk以为基变量，式已是典式。27-47-1.为式建立初始单纯形表，见表建立初始单纯形表o1231234112233341

19、122331237-17-1-10-1-26000040000-14054001-1000000000-118230000001-1-5-400100000-1-101010000010100-12-3001-1-2300000000000-22kjjPPPPcxxxxddddddxxPdPdPdPPP表【例】的初始单纯形表基解 -3000000037.2 基本方法【例7-1】续B7-13LP2,1,2,7,-4b-5TjBjjjjC acjnCc表中，检验数按优先级分为 行，每行检验数的计算公式同单纯形法的：其中即列。L213B27-17-57-1jjjjjkjjkkPPPPPPcacaCP

20、ac但是，各列数据和，以及各行数据和，。如表中行检验数的计算结果，及其按公式计算时所用数据， ， ，即为表中红色的数字；而行其他检验数全为0，不必计算只限于同名行检验数计算时专用。 、 行的检验数也是这样计算出的。113PP按优先级由高到低，依次检查表中各行检验数；现因行有负检验最优性数，则级。检验分目标非优o1231234112233341122331237-17-10000-10-1-1-1-2061010000000040101000000-14054001-10000-102-300001-100-118230000001-1-5-400100000-2300000200-2kjjPP

21、PPcxxxxddddddxxPdPdPdPPP表【例】的初始单纯形表基解 -300000003211L-45PxPd这一步骤同单纯形法一致，在当前存在负检验数的行找出最小者 5，确定进基；再按最小比值规则确定离基变量与主元2；确定主元转。oo7.2 基本方法【例7-1】续 53-5-abcj这一步也同单纯形方法一致，但需将主列的栏3行检验数全都化为0.对表7 1实施该步骤后，得到表7 2，其中空白处数据都为0,。反复运用，得到表换基7 2， 。运算ooo: 123337-2 c,jP PPPP表中栏行检验数已全非负，这两级分目标已获最优； 行还有负检验数，但负检验数所在列的上面行中都存在正检

22、验数，这意味着 级分目标无法获得最优，算法结束。否则，要将 行检验数化为非负，其结果必将破坏更高级分目标的优化。7.2 基本方法【例7-1】续 31jkP的如下：若栏各行检验数全为非负，则当前解为步骤最优性最优解，运检。验准则算结束o在目标规划应用中，如果各分目标的优先级发生变更，其前后求解结果也大相径庭。而优先权的划分、权数的确定，完全取决于决策者的主观判断，对此没有明确的程序。因此，目标规划的应用，与线性规划不同，往往不能一次解决问题，需要多次变更优先权和权数并多次求解，然后比较权衡，从中选择一个比较满意的解作为最终决策。 +12kkPP若行及其上面各行检验数全为非负，但行存在负检验数，而

23、且该行负检验数上面行中都存在正检验数，则当前解为满意解，运算结束。 3kP若行存在一个负检验数，而且它所在列的上面行中检验数均为0，但该列系数全都非正，则问题无解，停止运算。 44若非上述情形，则转，继续运算。o7.3 实用模型2022年6月5日星期日山西大学经济与管理学院 范建平307.3.1 营运管理模型-某公司经营的某种商品由其所辖的2个工厂供应3个客户，每天的供需量 吨以及工厂销给客户1吨该商品所获利润如表7 3所示，最优方案如表7【例7 2】 4所示。客户客户工厂工厂利润利润/ /（元（元/ /吨）吨）日供量日供量/(/(吨吨) )B1B2B3A1700900700120A26008

24、0050080日需量/(吨)9060100客户客户工厂工厂供应量供应量/ /吨吨日供量日供量/(/(吨吨) )B1B2B3A1106050120A28080A3（虚）5050日需量/(吨)9060100250表7-3 利润表表7-4 最优方案【例7-2】 31440 101B270%3900%*最大总利润：由于所得方案仅考虑总利润最大，不符合很多实际情况。为此公司决定重新研拟运销方案，以满足下述目标。客户所需量必须全部满足供应；其他客户的满足率不低于；z元运销总利润不低于原方案的。试建立其数学模型。客户客户工厂工厂供应量供应量/ /吨吨日供量日供量/(/(吨吨) )B1B2B3A1106050

25、120A28080A3（虚）5050日需量/(吨)9060100250【例7-2】11121321222311211222132313231111+2122122233111213212221112234334+120+80+90+60+100s.t.+-=100+-=63+-=4min 27+9+7+6+85+-xxxxxxxxxxxxxxddxxddxxddxxxxzP ddPxxdddP d解 数学模型如下：4=129601,2,3;1,2,3,4,0 ,1,2,3,4ijkkdxijddk系统约束，是供不应求运输模型的典型约束P1P2P31233B70%PP90%P 客户所需量必须全部

26、满足供应； 其他客户的满足率不低于； 运销总利润不低于原方案的。7.3.2 晋酬管理模型-3某医院现有医生28名，定编人数32名，其职称级别等情况见表【7 】7例5。级别级别职称职称津贴（元津贴（元/ /月月/ /人）人）现有人数现有人数定编人数定编人数 主任医师280023副主任医师210035主治医师1500812医师10001512表7-5 %14.523、级的人数不低于各级定编人数的30、40、50。 并且规定，级人员的缺额由招聘增补，其他各级人员的增补从原有次低级现拟进别人员行职称调整中晋升。另且其目标要求如下：每月津贴总额不超过万元；知级人员行将退休一人。则应如何确定各级人各级人员

27、都不超过定编人员调整人数？试建立数数；升入学模型。【例7-3】 34231211234123411110.10 15- +0.15 8-+0.21 3- +0.28 2-1+4.57+6+5+10897+6+5+11,2,3,4+-0=891minjxxxxxxxxxxxxxxxjjddzxd表示第级人员增 每补数：故月津贴解 设总额的目标约束与目标函数化简：有得【例7-3】 343423242212111512381243522 1322xxxxxxxxxxxxxx 定编人数的目标约束与目标函数34241212232344552345=3=4=2=2+-+-+-+-min+dddddxxxd

28、ddzdxdxxxdd故有：【例7-3】 1233 0.315 0.42132 0.56xxx 各级晋级人数的目标约束与目标函数6677883637812+-+-+-min=1=2=6+xxxddddddzddd故有：【例7-3】12341134222333124415516627+1122345738836787 +6+5+10+-= 89-+-=3-+-=4- +-=2+-=2s.t.+-=1+-=2+-=6min +0ijzPdxxxxddxxddxxddxxddxP ddddPddxddxddxdddxidd综上，本例数学模型如下，整数，：1,2,3,4,0 ,1,2,8kkddkL7

29、.3.3 库存管理模型4-某公司以批发方式经营某种商品，预计该商品今后4个月的购销价格如表7 6所示。该公司经营这种商品肯定能批发销售出去，但最大销量受仓库容量限制，正常库容量为每月初批发销售，每月中旬采购进货，购货资金完全依赖销售收8吨，非常需要时也可占用机动库容量2吨。该公司。已知第一月初有库存该货6吨，其采购价格为5.4万【例】入7元/吨。月份月份1 12 23 34 4购价5.55.45.65.7销价5.85.66.06.2表7-6 1234该公司预定今后4个月经营目标如下：每月都使用正常库容，尽量不要超贮；每月下旬都预留1万元机动资金，以备急用；力求今后 个月的总盈利达到。应如何拟定

30、购销计划？试建立最大数学模型。【例7-4】12113112241122331,2,3,41,2,3,466- +6- + -+6- + -+-+1.jjxjjyjjyyyxyyx yxyyx yx yx表示第月的采购量 吨 ；表示第月的销售量 吨 ；每月的销量不能解 销量约束超过月初库存量设 111212123123123412346666ysyyxsyyyxxsyyyyxxxs标准化：【例7-4】112112311223411223345.55.85.45.8-5.5 +5.65.65.8-5.5 +5.6-5.4+65.75.8-5.5 +5.6-5.4+6-5.6+ .22.6xyxyxyxyxyxyxyxyxyxy 采购费用约束每月中旬的采购费用不能超过月初的销售收入1151212612312371234123485.