第五章运筹学目标规划

1、.,第五章 目标规划( Goal Programming),本章基本要求：,理解目标规划概念 掌握目标规划建模技巧 能够运用图解法求解模型,.,一、问题提出与目标规划的数学模型,线性规划：在一组线性约束下一个线性函数的极值问题。,线性规划的局限性 只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。,实际决策中，衡量方案优劣常常需要考虑多个目标,比如 1）.生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等； 2）.生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。 这些目标

2、中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。,.,目标规划（Goal Programming） 在线性规划的基础上发展起来的解决多目标规划问题的最有效的方法之一。 美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版的管理模型及线性规划的工业应用一书中，首先提出的。 1976年伊格尼齐奥发表了目标规划及其扩展一书，系统归纳总结了目标规划的理论和方法。,.,例1.某企业计划生产甲、乙两种产品，这些产品分别要在A、B、C、D四种不同的设备上加工。各产品占用资源数量，资源拥有量及产品利润见下表。

3、问如何安排生产，才能获得最大的总利润？,3,2,利润（百元/件）,12,4,0,D,16,0,4,C,8,2,1,B,12,2,2,A,设备工作台时,乙,甲,消耗 产品 设备,解：设 x1， x2 分别表示甲乙产品的产量，则相应的线性规划模型为：,它的最优解为: x1 =4, x2 =2, z =14,.,假设企业的经营目标不仅仅是利润，而是要考虑多个方面的目标:,（1）企业利润不低于12（百元）。 （2）力争使甲乙两种产品的比例大致为1：1。 （3）设备B必要时可以加班，但不希望加班；设备A既要充分利用，又尽可能不加班。,是否可以用线性规划解决上述多目标的问题？,为了解决上述多目标的规划问题

4、，就需要使用目标规划的方法。,线性规划模型存在以下几方面的局限性:,1.LP只能处理单目标优化问题。因此，线性规划模型中人为地将一些次要目标转化为约束。（在实际中，目标和约束可以相互转化） 2.LP要求问题的解必须满足全部约束条件，但实际中并非所有约束都必须严格满足。 3.LP中各个约束（实际上也可以看作目标）都处于同等重要地位，但实际问题中各个目标既有层次上的差别，又有权重上的区分。 4.LP寻求最优解，但很多问题只要找到满意解即可。,.,目标规划解决上述LP建模中的局限性的方法： 对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到；

5、 对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况； 对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件； 引入目标的优先等级和加权系数；建立使组合偏差最小的目标函数。,.,1.确定目标函数的期望值 每一个目标函数希望达到的期望值(或目标值、理想值)。 根据历史资料、市场需求或上级部门的布置等来确定。,2.设置偏差变量，用来表明实际值同目标值之间的差异。,超出目标的差值，称正偏差变量； -未达到目标的差值，称负偏差变量。 与两者必有一个为零 （1）-0，0 表示实际值超出规定目标值； （2）-0，0 表示实际值未达到目标值； （3）-=0，0 表示实际

6、值同规定目标值恰好一致。,.,3.统一处理目标和约束,系统约束(硬约束)：对资源使用上有严格限制的约束，用严格的等式或不等式表示（同线性规划中的约束）。 如：4x1 16 (设备C的使用时间) 4x2 12 (设备D的使用时间),目标约束（软约束）：引入正、负偏差变量后，对各个目标建立的目标约束方程。,原来的目标函数变成了约束条件的一部分，即目标约束(软约束),.,设备A既要充分利用，又尽可能不加班,可以写成 mind3- +d3+ 2x1+2x2+ d3- d3=12 (设备A) 设备B允许加班，只是不希望加班或少加班，可以写成 mind4 x1+2x2+ d4- - d4=8 (设备B),

7、原来的目标函数，在目标规划中只是成了问题要达到的目标之一 ,“目标利润不低于12（百元 ）”, 可以表示成 mind1- 2x1 +3x2 + d1- - d1=12,要求甲、乙两种产品的比例尽可能接近11，可以表示成 mind2- + d2 x1-x2 +d2- - d2 = 0,.,4.目标函数、目标的优先级和权系数,（1）在目标规划中，如果两个不同目标的重要程度相差悬殊，为达到某一目标可牺牲其他目标，称这些目标是属于不同层次的优先级。优先级层次的高低可通过优先因子P1，P2表示。 并规定P k P k+1 ，即不同优先级之间的差别无法用数字大小衡量。 （2）对属于同一层次优先级的不同目标

8、，其重要程度的差别可以通过设置权系数来表达。权系数越大，表示目标越重要。,目标规划中的目标函数是各个实际值与目标值之间的最小差距。,本例中，假设： P1 ：企业利润目标； P2 ：甲、乙产品的产量尽可能达到11的要求； P3 ：设备A、B尽量不超负荷工作，在第三优先级中，设备A的重要性是设备B的三倍。,.,本例中，假设： P1 ：企业利润目标； P2 ：甲、乙产品的产量尽可能达到11的要求； P3 ：设备A、B尽量不超负荷工作，在第三优先级中，设备A的重要性是设备B的三倍。,.,目标约束：f(x) + d- d = f0 ; 1.要求性能指标f(x) 尽量达到目标值f0 （即不足f0不好，超出

9、f0也不好） min(d-+ d) = f0 2.要求性能指标f(x)的值不少于目标值f0 (即允许超过f0，但尽可能不要少于f0） min（d-） f0 3.要求性能指标 f(x) 的值不超过目标值 f0 (即允许少于f0，但尽可能不要超过f0） min（d） f0,小结,.,二、建立目标规划模型的步骤,第一步：定义决策变量和有关的常量 定义决策变量和决策目标约束等式右边的常数。等式右边的常数是可利用的资源或是决策者特定的目标值。 第二步：建立决策目标约束 通过分析决策变量之间的关系以及决策变量与目标值之间的关系，建立一组目标约束。并从所有的决策目标中，找出绝对决策目标（即，如果不满足将导致

10、最终结果无法实现的目标），将这些目标作为第一优先级。而后再确定其余目标的优先级。 第三步：建立指标偏差函数,.,目标规划的一般模型为：,.,例2 某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见下表,.,设产品I和II的产量分别为X1和X2，当用线性规划来描述和解决这个问题时，其数学模型为：,其最优解，即最优生产计划为X1=8，X2=2，maxz=64,.,假设计划人员还被要求考虑如下意见： （1）由于产品II销售疲软，故希望产品II的产量不超过产品I的一半。 （2）原材料严重短缺，生产中应避免过量消耗。 （3）最

11、好能节约4小时设备工时； （4）计划利润不少于48元。 面对这些意见，计划人员作出如下意见，首先原材料使用额不得突破；产品II产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。,.,例2的目标规划模型如下：,minZ= P1 d1- + P2d2+ + P3d3- 5x1+10 x2=60 x1-2x2 +d1- d1+ = 0 4x1+4x2 +d2- - d2+ = 36 6x1 +8x2 +d3- - d3+ = 48,.,课堂练习1： 某工厂计划生产A、B两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。 厂长首先考虑要充分利用供电部门分配的

12、电量限额66， 然后考虑利润不低于100元； 其次据市场调查结果，希望B产品的产量不低于A产品的产量， 问应如何安排产品A、B的产量。,20,10,单位产品利润,8,1,2,原材料,66,12,10,电力,资源限量,B,A,消耗 产品 资源,.,解：设x1 、x2分别表示A、B两种产品的产量，则目标规划模型如下：,.,课堂练习2： 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需要占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量为24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为： 第一优先级：充分利用装配线每周计划开动的40

13、小时； 第二优先级：允许装配线加班，但加班的时间尽量不超过10小时； 第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机利润高，取其权为2。 试确定该厂为达到以上目标的最优生产计划。（建立数学模型）,.,解：设 x1, x2 分别表示彩色和黑白电视机的产量。该问题的目标规划模型为：,.,二、目标规划的解法,（一）目标规划的图解法 （二）目标规划的单纯形解法,.,第二节 目标规划的图解法,由于目标规划是在线性规划的基础上建立，并弥补了部分不足所以两种规划模型结构没有本质区别，解法也非常类似形式上的区别主要在于：线性规划只能处理一个目标，而目标规划能统筹兼顾地处理多个目标关系，以求得切合实

14、际需求的解；线性规划是求满足所有约束条件的最优解，而目标规划是要在多个目标或约束条件下找到尽量好的满意解；线性规划的约束条件是不分主次地同等对待，而目标规划可根据实际需要给予轻重缓急的考虑,.,(一)、目标规划的图解法,只含有两个决策变量(不考虑偏差变量)的目标规划模型 线性规划是在可行域中寻找一点，使单个目标极大或极小； 目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的 折衷方案。 目标规划的图解法的思路,首先是在可行域内寻找一个使P1级各目标均满足的区域R1； 然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2 R1)； 接着再在R2中寻找一个满足P3级各目标的区域R3(

15、R3 R2 R1)； 如此继续，直到寻找到一个区域RK(RK RK-1 R3 R2 R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。,.,目标规划的图解法的步骤 第一步：按照系统约束画出可行域， 第二步：不考虑正负偏差变量，画出目标约束的边界线， 第三步：按优先级别和权重依次分析各级目标。,.,选择F点作为满意解 即x1=3,x2=3,企业的利润是15百元。,F,G,H,x1,x2,(1),(2),(3),(4),(5),(6),例2 用图解法求解目标规划,.,课堂练习： 用图解法求解目标规划,x1,x2,(1),(2),(3),(4),由

16、于E点使得d4-取值最小，故E点为满意解 (24,26),E,.,O,5,10,练习：min Z=p1 ( d1+ + d1) + p2 d2,（1）可行域：OBC,（2）优先级p1目标，满足（d1+ + d1）最小，则在目标线上即可满足。同时满足可行域，则CD直线可行。,（3）次优先级p2目标，满足d2最小，则沿其目标线往上即可满足。同时满足可行域，则FGC可行。但要优先考虑p1，则只能是ED直线。,F,G,.,练习 用图解法求解,.,min Z=p1 d1 + p2 d2,o,M,C,D,A,B,F,（1）可行区域：OMCD; （2）满足p1，d1-最好为0，可行域ABCD； （3）满足p

17、2，d2+最好为0，但是要首先满足p1，即只能在ABCD中取值，必然有d2+ 0，则应在ABCD中选择一个，使d2+最小。,.,解：, 可行域OACD, 目标1： 区域 ABCD 目标2：点A,.,图解法的缺点：只能解决二维决策变量的情况，对于三维及以上，很难顺利解决； 一般的方式：单纯形法； 优先因子的处理：在计算中，应注意p1p2.pn，优先因子之间差距非常大，可采用差距很大的数来代替； 目标约束看做等式约束，偏差量也看做决策变量。,二、目标规划的一般解法,.,5.2 目标规划的一般解法,例4 用单纯形法求解,.,解法一：传统型单纯形法,1、标准化,.,2、建立初始单纯形表 选择负偏差量为

18、基准变量。,检验检验数是否均为非负？如否，则要进行变量替换。,maxcC Bi a ij,.,2、基变量的替换,x1换入；d1-换出。,x1,0,mini =bi/aik|aik0=l,.,3、最终单纯形表,x1 =10， x2 =20， d3- =30g1=10，g2=40，g3=70,.,解法二：目标规划的“特殊”单纯形法,列出初始单纯形表。目标规划中目标函数一定是求最小，不必将极小的情况转换为求极大，仍然采用原有目标函数。同时，选择负偏差量作为基变量，构成初始基向量；（求min，非基变量的检验数全0合格） 按照传统单纯形法的方式求解检验数，此时由于检验数中必然会含有优先因子，按照优先因子

19、的优先程度，将检验数分成多行，每行输入检验数中对应的优先因子的系数，则每个变量对应的总检验数即为（行系数*优先因子）； 从最优先因子开始，检查其系数，观察其系数是否为非负，如非负，则完成。如含有负系数，则需要进行变量的替代； 确定换入变量：从最优先因子开始，选择其负检验数中最小值所对应的变量为换入变量；（选择绝对值最大的负检验数） 确定换出变量：按照单纯形法的方法，确定b/alj（alj0）中最小值对应的行作为主元行，其对应的原基变量为换出向量；,.,用换入向量替代基变量中的换出向量，对矩阵进行迭代运算； 再次检查检验数，观察检验数是否为非负。如果第一优先级所有检验数均为非负时，则转入下一优先

20、级； 迭代运算停止的准则：（1）检验数p1，p2.，pk行的所有值均为非负；（2）p1，p2.，pi行所有检验数均为非负，第pi+1行存在负检验数，但在负检验数所在的列的上面行中都有正检验数（原因是p1p2.pi+1）,.,.,初始表,.,.,最优表,.,目标规划的“特殊”单纯形法总结,1、列出初始单纯形表。仍然采用原有目标函数，且选择负偏差量作为基变量，构成初始基向量； 2、按照传统单纯形法的方式求解检验数，并按照优先因子的优先程度，将检验数分成多行，每行中填入检验数中相应的优先因子的系数，则每个变量对应的总检验数即为（行系数*优先因子）； 3、从最优先因子开始，检查其系数，观察其系数是否为

21、非负，如非负，则完成。如含有负系数，则需要进行变量的替代； 4、确定换入变量：从最优先因子开始，选择其检验数中最小值所对应的变量为换入变量； 5、确定换出变量：按照单纯形法的方法，确定b/alj中最小的值对应的行作为主元行，其对应的原基变量为换出向量；,.,6、用换入向量替代基变量中的换出向量，对矩阵进行迭代运算； 7、再次检查检验数，观察检验数是否为非负。如果第一优先级所有检验数均为非负时，则转入下一优先级； 8、迭代运算停止的准则：（1）检验数p1，p2.，pk行的所有值均为非负；（2）p1，p2.，pi行所有检验数均为非负，第pi+1行存在负检验数，但在负检验数所在的列的上面行中都有正检

22、验数（原因是p1p2.pi+1）,.,5.3 应用举例,例、某单位制定职工升级计划，基本情况如下：,1、升级调薪模型,.,要求： 1、不能超过月工资总额600000元； 2、提级时，每级的定编人数不能超过； 3、升级面不超过现有人数的20； 4、C级不足的人数可用新职工补足； A级将有10的人要退休，退休 后工资由福利基金中开支。,.,解：设x1表示由B级提升到A级的人员数； x2表示由C级提升到B级的人员数； x3表示新录用C级的人员数。,根据规定优先因子： p1 不超过工资总额； p2 各级人员不超编； p3 升级面20%，但尽可能多提。,.,工资总额 2000（1001000.1+x1）

23、+1500(120 x1+ x2) +1000(150 x2+ x3)（）600000 化为,编制限额的目标约束：,提升的目标约束,.,构造目标函数,（1）目标1：工资总额不得超过，成本型目标，不能对d1-求min，则目标函数中取消d1- ；,（2）目标2：编制限额，成本型目标，不能对d2-、 d3- 、d4-和求min，则目标函数中取消；,（3）目标3：人员升级，利润型目标，不能对d5+和 d6+ 求min，目标函数中应取消。,.,得到的结果：,变量 含义 x1 提升到A级的人数 24 30 30 24 x2 提升到B级的人数 30 30 50 52 x3 录用为C级的人数 30 30 50

24、 52 d1- 工资总额节余 33000 30000 d2- A级编制不足人数 6 6 d3- B级编制不足人数 24 30 1 2 d4- C级编制不足人数 d5+ B级编制超过人数 6 6 d6+ C级编制超过人数 20 22,.,2、投资计划模型,某经济特区的计委有一笔资金，在下一个计划期内可向钢铁、化工、石油等行业投资建新厂。这些工厂能否预期建成是一定风险的，在建成投产后，其收入与投资额有关，经过分析研究，各工厂的建设方案的风险因子及投产后可增收入的百分比例如表所示。,.,计委根据该地区情况提出以下要求：用于钢铁的投资额不超过总资金的35%；用于化工的投资额至少占总资金的15%；用于石

25、油的投资不超过总资金的50%。 并且，首先要考虑总风险不超过0.2；其次考虑总收入至少要增长0.55%；然后再考虑各项投资的总和不能超过总资金额，现在要确定对不同行业的各投资历方案所占的比例。,.,解：（1）确定决策变量：假设xi为第i方案投资金的百分比，且总的投资比例为100%； （2）确定绝对约束： 1）用于钢铁工业的投资额不超过总资金的35% ：,2）用于化工工业的投资额至少占总资金的15% ：,3）用于石油工业的投资额不超过总资金的50% ：,.,（3）确定目标约束： 1）总风险不超过0.2，为第一优先级，赋予有限因子p1：,2）总收入至少要增长0.55% ，为第二优先级，赋予有限因子

26、p2：,3）各项投资不能超过总投资金额 ，为第三优先级，赋予有限因子p3：,.,（4）建立目标函数，完成模型：,.,应用举例2,某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外购件外，生产一台录音机需甲车间加工2 h，乙车间装配1 h；生产一台电视机需甲车间加工1 h，乙车间装配3 h。这两种产品生产出来后均需经检验、销售等环节。已知每台录音机检验销售费用需50元，每台电视机检验销售费用需30元。又甲车间每月可用的生产工时为120 h，车间管理费用为80元/h；乙车间每月可用的生产工时为150 h，车间管理费用为20元/h。估计每台录音机利润为100元，每台电视机利润为

27、75元，又估计下一年度内平均每月可销售录音机50台，电视机80台。 工厂确定制订月度计划的目标如下： 第一优先级：检验和销售费用每月不超过4600元； 第二优先级：每月售出录音机不少于50台； 第三优先级：甲、乙量车间的生产工时得到充分利用（重要性权系数按两个车间每小时费用的比例确定）； 第四优先级：甲车间加班不超过20 h； 第五优先级：每月销售电视机不少于80台； 第六优先级：两个车间加班总时间要有控制（权系数分配与第三优先级相同）。 试确定该厂为达到以上目标的最优月度计划生产数字。,.,建模方法：,(1) 设定约束条件 (构建目标约束、绝对约束和非负约束)；,(2) 规定目标约束优先级；

28、,(3) 根据目标所属的类型，建立关于偏差量的目标函数，完成模型的建立。,.,（1）甲、乙两车间的可用工时约束： 2 x1 +x2 +d1- -d1+=120（甲车间）； x1 +3x2 +d2- -d2+=120（乙车间）,解：设x1为每月生产的录音机台数，x2为每月生产的电视机台数。列出约束条件：,（2）检验和销售费用的限制： 50 x1 +30 x2 +d3- -d3+=4600,（3）每月销售量的要求： x1 +d4- -d4+=50（录音机）； x2 +d5- -d5+=120（电视机）,（4）对甲加班的限制： d1+ d6- -d6+=20,目标1：检验和销售费用每月不超过4600

29、元； 目标2：每月售出录音机不少于50台； 目标3：甲、乙量车间的生产工时得到充分利用（重要性权系数按两个车间每小时费用的比例确定）； 目标4：甲车间加班不超过20 h； 目标5：每月销售电视机不少于80台,.,确定目标函数： 首先要确定优先级；然后确定各目标的类型，对目标函数进行取舍。,第一优先级：检验和销售费用每月不超过4600元； 第二优先级：每月售出录音机不少于50台； 第三优先级：甲、乙量车间的生产工时得到充分利用（重要性权系数按两个车间每小时费用的比例确定）；,（1）对于第一优先级： 属于成本型目标，在目标函数中相应的部分为：p1d3+。,（2）第二优先级： 属于利润型目标，在目标

30、函数中相应的部分为：p2d4-。,（3）第三优先级： 属于利润型目标，同时，在同一优先级内，存在权重。权重比为甲：乙=80元/h：20元/h=4：1。则在目标函数中相应的部分为：p3（4d1-+d2-）。,.,第四优先级：甲车间加班不超过20 h； 第五优先级：每月销售电视机不少于80台； 第六优先级：加班时间进行控制（权重与三 一致）。,（4）第四优先级： 属于成本型目标，则在目标函数中相应的部分为：p4d6+。,（5）第五优先级： 属于利润型目标，则在目标函数中相应的部分为：p5d5+。,（6）第六优先级： 属于成本型目标，则在目标函数中相应的部分为： p6（4d1+d2+）。,.,目标规划的模型为：,.,已知三个工厂生产的产品供应四个用户需要，各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费用如表所示：,3、生产计划模型,.,用表上作业法求得最优调配方案如下表，总运费为2950元。 但上述方案只考虑了运费为最少，没有考虑到很多具体情况和条