第五章目标规划.ppt

《第五章目标规划.ppt》由会员分享，可在线阅读，更多相关《第五章目标规划.ppt（47页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第五章第五章 目标规划目标规划一、目标规划概述一、目标规划概述LP与与 GP比较：比较：（1）线性规划只能处理）线性规划只能处理一个一个目标，而目标规划能统目标，而目标规划能统 筹兼筹兼 顾处理顾处理多种多种目标的关系，求得更切实际要求的解。目标的关系，求得更切实际要求的解。（2）线性规划立足于满足）线性规划立足于满足所有所有约束条件的约束条件的可行解可行解，而，而在实际问题中可能存在相互矛盾的约束条件；目标规在实际问题中可能存在相互矛盾的约束条件；目标规划可以在相互矛盾的约束条件下找到划可以在相互矛盾的约束条件下找到满意解满意解，即满意，即满意方案。方案。（3）线性规划的约束条件是）线性规划

2、的约束条件是不分主次不分主次地同等对待的，地同等对待的，而目标规划可根据实际需要给予而目标规划可根据实际需要给予轻重缓急轻重缓急的考虑。的考虑。电视机厂装配电视机厂装配25寸和寸和21寸两种彩电，每台电视机需寸两种彩电，每台电视机需装备时间装备时间1小时，每周装配线计划开动小时，每周装配线计划开动40小时，预计小时，预计每周每周25寸彩电销售寸彩电销售24台，每台可获利台，每台可获利80元，每周元，每周21寸彩电销售寸彩电销售30台，每台可获利台，每台可获利40元。元。该厂的目标是：该厂的目标是：1、充分利用装配线，避免开工不足。、充分利用装配线，避免开工不足。2、允许装配线加班，但尽量不超过

3、、允许装配线加班，但尽量不超过10小时。小时。3、装配电视机的数量尽量满足市场需求。、装配电视机的数量尽量满足市场需求。例例 甲甲 乙乙 有效工时有效工时金工金工 4 2 400装配装配 2 4 500收益收益 100 80 车间车间产品产品LP：maxz=100 x1+80 x2 2x1+4x2 5004x1+2x2 400 x1,x2 0 x*=(50,100)z*=13000 例例目标约束目标约束：100 x1+80 x2 d+d-=10000 d+.d-=0 d+,d-0 引入：引入：正偏差变量正偏差变量 d+：决策值超过目标值部分决策值超过目标值部分负偏差变量负偏差变量 d-：决策值

4、不足目标值部分决策值不足目标值部分GP：该厂去年总收益该厂去年总收益9000，上级对该厂下达的指标是：，上级对该厂下达的指标是：今年希望总收益不低于今年希望总收益不低于10000目标函数目标函数：mind-单一目标要求：minz=d-100 x1+80 x2-d+d-=100004x1+2x2 4002x1+4x2 500 x1,x2,d-,d+0 d+.d-=0数学模型 例例2某某工工厂厂生生产产甲甲，乙乙两两种种产产品品，已已知知有有关关数数据据见见下表。试求获利最大的生产方案。下表。试求获利最大的生产方案。甲甲乙乙拥有量拥有量原原 材材 料料/kg设备台时设备台时/h21121110利润

5、（元利润（元/件）件）810最优决策方案为：最优决策方案为：(1)原材料价格上涨，超计划要高价购买，所以要严原材料价格上涨，超计划要高价购买，所以要严格控制。格控制。(2)根据市场信息，产品根据市场信息，产品甲销售量有下降趋势，故产甲销售量有下降趋势，故产品甲的产量尽量不大于产品乙的产量。品甲的产量尽量不大于产品乙的产量。(3)充分利用设备，不希望加班。充分利用设备，不希望加班。(4)尽可能达到并超过利润计划指标尽可能达到并超过利润计划指标56元。元。多目标要求多目标要求：甲甲乙乙拥有量拥有量原原 材材 料料/kg设设 备备 台台 时时/h21121110利润（元利润（元/件）件）8102x1

6、+x2 11x1-x2+d1-d1+=0 x1+2x2+d2-d2+=108x1+10 x2+d3-d3+=56x1,x2,di-,di+0 di-.di+=0,i1、2、3d1-:x1不足不足x2 部分部分d1+:x1超过超过x2 部分部分d2-:设备使用不足设备使用不足10 部分部分d2+:设备使用超过设备使用超过10 部分部分d3-:利润不足利润不足56 部分部分d3+:利润超过利润超过56 部分部分设设x1，x2为产品为产品甲甲，产品乙的产量产品乙的产量。minz=P1d1+P2(d2-+d2+)+P3(d3-)数学模型数学模型电视机厂装配电视机厂装配25寸和寸和21寸两种彩电，每台电

7、视机需寸两种彩电，每台电视机需装备时间装备时间1小时，每周装配线计划开动小时，每周装配线计划开动40小时，预计小时，预计每周每周25寸彩电销售寸彩电销售24台，每台可获利台，每台可获利80元，每周元，每周21寸彩电销售寸彩电销售30台，每台可获利台，每台可获利40元。元。该厂的目标是：该厂的目标是：1、充分利用装配线，避免开工不足。、充分利用装配线，避免开工不足。2、允许装配线加班，但尽量不超过、允许装配线加班，但尽量不超过10小时。小时。3、装配电视机的数量尽量满足市场需求。、装配电视机的数量尽量满足市场需求。例例3解：设解：设x1,x2 分别表示分别表示25寸，寸，21寸彩电产量寸彩电产量

8、,di+,di-分别为分别为正、负偏差变量，则：正、负偏差变量，则：minz=P1d1-+P2d2+P3(2d3-+d4-)x1+x2+d1-d1+=40 x1+x2+d2-d2+=50 x1 +d3-d3+=24 x2+d4-d4+=30 x1,x2,di-,di+0(i=1,2,3,4)数学模型数学模型负偏差变量负偏差变量d-:表示决策值不足目标值部分。表示决策值不足目标值部分。d-0 变量约束：变量约束：xj 0 j=1,2,n d+0,d-0 小结：小结：目标规划数学模型中的基本要素：目标规划数学模型中的基本要素：1、变量：、变量：决策变量决策变量x1,x2,xn:表示决策问题的计划产

9、品产量或计划生产表示决策问题的计划产品产量或计划生产 时间。时间。正偏差变量正偏差变量d+:表示决策值超过目标值部分。表示决策值超过目标值部分。d+0 2、约束条件：、约束条件：绝对约束绝对约束(硬约束硬约束)：必须严格满足的等式约束或不等式约束。必须严格满足的等式约束或不等式约束。目标约束目标约束(软约束软约束)：含有含有d-,d+的约束。通常用等式来描述。的约束。通常用等式来描述。(3)要求不超过目标：要求不超过目标：目标优先级（优先因子）目标优先级（优先因子）：P1 P2 PL 同一级中可以有若干个目标：同一级中可以有若干个目标：P21,P22,P23 其重要程度用权重系数其重要程度用权

10、重系数w21,w22,w23 表示表示3、目标函数：、目标函数：(1)要求恰好达到目标：要求恰好达到目标：minz=d-+d+(2)要求超过目标：要求超过目标：minz=d-minz=d+二、目标规划的数学模型二、目标规划的数学模型一般形式：一般形式：结论：结论：目标规划：求一组决策变量的满意值，使决策结果与目标规划：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。给定目标总偏差最小。Z=0：各级目标均已达到各级目标均已达到 Z0：部分目标未达到。部分目标未达到。目标函数中只有偏差变量、优先因子、权系数。目标函数中只有偏差变量、优先因子、权系数。目标函数总是求偏差变量最小。目标函数总是

11、求偏差变量最小。练习练习1某工厂生产某工厂生产A、B两种型号的机床，每种型号的机床均需经过两种型号的机床，每种型号的机床均需经过I、两道工序，每台机床所需的加工时间、销售利润及工厂每两道工序，每台机床所需的加工时间、销售利润及工厂每周最大加工能力如下表所示。周最大加工能力如下表所示。工序工序 型号型号 每周最大每周最大加工能力加工能力 A B I（小时（小时/台）台）4 4 6 6 200（小时（小时/台）台）3 2 100利润（元利润（元/台）台）200 500如果工厂经营目标的期望值和优先等级如下：如果工厂经营目标的期望值和优先等级如下：P1：经理希望每周总利润恰好为：经理希望每周总利润恰

12、好为5000元；元；P2：因合同要求，：因合同要求，A型机每周至少生产型机每周至少生产20台，台，B型机每周至少型机每周至少生产生产30台（以利润作为权系数）；台（以利润作为权系数）；P3：工序：工序的生产时间最好用足，甚至可适当加班。的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型。试建立这个问题的目标规划模型。答案1解：设解：设x1，x2分别为生产分别为生产A、B两种机床的台数，两种机床的台数，di+,di-分别为正、负偏差变量，对于第二优先级目分别为正、负偏差变量，对于第二优先级目标，根据标，根据A,B机床的利润机床的利润200：500=2：5的比值，的比值，取二者权系数

13、分别为取二者权系数分别为2和和5。该问题的目标规划模。该问题的目标规划模型为：型为：minfP1（d1+d1+）+P2（2d2+5d3）+P3d4 200X1+500X2+d1-d1+=5000 X1+d2-d2+=20 X2+d3-d3+=30 3X1+2X2+d4-d4+=100 X1，X2，di,di+0 i=1,2,3,4练习2已知单位牛奶、牛肉、鸡蛋中的维生素及胆固醇含量等有已知单位牛奶、牛肉、鸡蛋中的维生素及胆固醇含量等有关数据如表所示，如果只考虑这三种食物，并且设定以下三关数据如表所示，如果只考虑这三种食物，并且设定以下三个目标：个目标：P1：满足三种维生素的每日最小需要量；：满

14、足三种维生素的每日最小需要量；P2：使得每日摄入的胆固醇最少；：使得每日摄入的胆固醇最少；P3：使得每日购买食品的费用最少；：使得每日购买食品的费用最少；项项目目牛奶牛奶(500g)(500g)牛肉牛肉(500g)(500g)鸡鸡蛋蛋(500g)(500g)每日最小需要量每日最小需要量(mg)(mg)维维生素生素A(mgA(mg)5050757590901 1维维生素生素C(mgC(mg)6868808080802020维维生素生素D(mgD(mg)808095951001005 5胆固醇胆固醇(单单位位)707050504040 费费用用(元元)2 216163 3试建立该问题的目标规划数学

15、模型。试建立该问题的目标规划数学模型。答案2设设x1,x2,x3分别表示牛奶，牛肉，鸡蛋的购买量，分别表示牛奶，牛肉，鸡蛋的购买量，di+,di-分别为分别为正、负偏差变量则正、负偏差变量则 ，i=1,2,3,4,5练习练习3某作坊有某作坊有6名熟练工，名熟练工，3名见习工，单件产品的利润为名见习工，单件产品的利润为2.5元元/件，具体工况如下表所示：件，具体工况如下表所示：工作时间工作时间（小时（小时/月月.人）人）产量产量（件（件/小时）小时）熟熟练练工工160 5见习见习工工802经理的目标是：经理的目标是：下月产量达下月产量达4000件；件；限制熟练工的加班时间不超过限制熟练工的加班时

16、间不超过50小时；小时；在优先考虑熟练工的前提下，保持全体职工能充分就业；在优先考虑熟练工的前提下，保持全体职工能充分就业；（以产量作为权系数）（以产量作为权系数）尽量减少见习工的加班时间。尽量减少见习工的加班时间。要求：建立该问题的目标规划模型要求：建立该问题的目标规划模型。答案3解：设全体熟练工下个月工作时间为解：设全体熟练工下个月工作时间为 小时，全体见习工下个小时，全体见习工下个月工作时间为月工作时间为 小时，小时，di+,di-分别为正、负偏差变量，则目分别为正、负偏差变量，则目标规划模型为：标规划模型为：Step2.根据目标函数中的优先因子来分析求解：根据目标函数中的优先因子来分析

17、求解：1.先考虑先考虑P1优先因子的目标的实现优先因子的目标的实现;2.再考虑再考虑P2优先因子的目标的实现优先因子的目标的实现;3.最后考虑最后考虑P3优先因子的目标的实现优先因子的目标的实现;三、目标规划的图解法三、目标规划的图解法具有两个具有两个决策变量决策变量的目标规划，可以用图解法来分析求解。的目标规划，可以用图解法来分析求解。图解法的主要步骤：图解法的主要步骤：Step1在平面直角坐标系内，作各约束条件：在平面直角坐标系内，作各约束条件：1.先画出绝对约束条件（画法同线性规划图解法）；先画出绝对约束条件（画法同线性规划图解法）；2.再画出目标约束条件：再画出目标约束条件：先令先令

18、di-=di+=0，作相应直线；，作相应直线；在直线旁标上在直线旁标上di-、di+，表明目标约束可沿表明目标约束可沿di-、di+所所示方向平移（平移方向是使示方向平移（平移方向是使di-或或 di+增加的方向）。增加的方向）。x2x1O50100501001252x1+4x2=500100 x1+80 x2=100004x1+2x2=400CBAd+d-绝对约束可行域为绝对约束可行域为OABC目标约束满意域为目标约束满意域为ABC该问题有无穷多个有效解：该问题有无穷多个有效解：其中：其中：A点点(100,0),10000;(70,50),11000;B点点(50,100),13000 mi

19、nz=0例例1minz=P1d1+P2(d2-+d2+)+P3(d3-)2x1+x2 11x1-x2+d1-d1+=0 x1+2x2+d2-d2+=108x1+10 x2+d3-d3+=56x1,x2,di-,di+0例例2d3+5x211101057x1ABCd2+d1-x1+2x2=10 x1-x2=08x1+10 x2=562x1+x2=11Od1+d2-d3-解：解：5x211101057x1d3+ABCd2+d1-x1+2x2=10 x1-x2=08x1+10 x2=562x1+x2=11Od1+d2-d3-可行域可行域OAB5x211101057x1d3+ABCd2+d1-x1+2

20、x2=10 x1-x2=08x1+10 x2=562x1+x2=11Od1+d2-d3-可行域可行域OAB 目标目标1：OBC 5x211101057x1d3+ABCd2+d1-x1+2x2=10 x1-x2=08x1+10 x2=562x1+x2=11Od1+d2-d3-可行域可行域OAB 目标目标1：OBC DE目标目标2：ED线段线段G目标目标3：GD线段线段 有效解为有效解为GD线段：线段：G=(2,4)利润利润=56D=(10/3,10/3)利润利润=60 minz=0例例3minz=P1d1-+P2d2+P3(2d3-+d4-)x1+x2+d1-d1+=40 x1+x2+d2-d2

21、+=50 x1 +d3-d3+=24 x2+d4-d4+=30 x1,x2,di-,di+0(i=1,2,3,4)解：解：x230304050 x1OBACDEFd3+d4+d1+d2-x1+x2=40 x1+x2=50 x2=30 x1=24d3-d4-d2+d1-1.满足目标满足目标、的满意域为的满意域为ABCD2.先考虑先考虑的满意域为的满意域为ABEF 解：解：x230304050 x1OBACDEFd3+d4+d1+d2-x1+x2=40 x1+x2=50 x2=30 x1=24d3-d4-d2+d1-1.满足目标满足目标、的满意域为的满意域为ABCD2.先考虑先考虑的满意域为的满意

22、域为ABEF 再考虑再考虑，无公共满意域。，无公共满意域。3.在满足目标在满足目标、的基础的基础上，使得上，使得d4-最小的是最小的是E点点(24,26)获利获利2960。4.minZ=d4-=4课堂练习课堂练习用图解法求解下列目标规划问题用图解法求解下列目标规划问题:minZ=P1(d1-)+P2(d2+d3+)6x1+4x2+d1-d1+=2402x1+3x2+d2-d2+=120 4x1+2x2+d3-d3+=120 xi,di-,di+01.2.1010 x2x1DCBAd3-d1+d2-4x1+2x2=1206x1+4x2=2402x1+3x2=120OE课堂练习答案课堂练习答案1解

23、解.d2+d3+d1-C点点(24，24)d3+=24有效解为：有效解为：minZ=d3+=24x1x2050 x1-10 x2=50d1-d1+3x1+5x2=20d2+d2-d3+d3-8x1+6x2=100A有效解为：有效解为：A点点(50，0)d2+=130d3+=300minz=2d2+d3+=560作业：用图解法找出目标规划的满意解作业：用图解法找出目标规划的满意解minz=P1(d3+d4+)+P2d1+P3d2-+P4（d3-+1.5d4-)x1+x2+d1-d1+=4 2x1+x2+d2-d2+=10 x1 +d3-d3+=3 x2+d4-d4+=2 x1,x2,di-,di

24、+0(i=1,2,3,4)四、目标规划的单纯形法四、目标规划的单纯形法2.因非基变量的检验数中含有不同等级的优先因子，即因非基变量的检验数中含有不同等级的优先因子，即 因因 ；从从每每个个检检验验数数的的整整体体来来看看：检检验验数数的的正正、负负首首先先决决定定于于 的的系系数数 的的正正、负负。若若 ，这这时时，检检验验数数的的正正、负负就就决决定定于于 的的系系数数 的的正正、负负。下下面面可依此类推。可依此类推。考虑目标规划数学模型的一些特点，作以下规定：考虑目标规划数学模型的一些特点，作以下规定：1.因目标规划问题的目标函数都是求极小值，所以以因目标规划问题的目标函数都是求极小值，所

25、以以 为最优准则。为最优准则。单纯形法举例单纯形法举例minz=P1d1-+P2d2+P3(2d3-+d4-)x1+x2+d1-d1+=40 x1+x2+d2-d2+=50 x1 +d3-d3+=24 x2+d4-d4+=30 x1,x2,di-,di+0(i=1,2,3,4)回忆：表上作业法B1B2B3B4产产量量A141241116A2263910A38511622814121448销地销地产地产地10882614销量销量行位势行位势列位势列位势0411-13-51012-3-11012求解：求解：cj00P100P22 P30P30 x1x2d1-d1+d2-d2+d3-d3+d4-d4

26、+bP1 d1-0 d2-2P3 d3-P3 d4-111011011000-100001000-100001000-100001000-140502430P1P2P3-10-2-10-1000100000010000002000001xjXBcj00P100P22 P30P30 x1x2d1-d1+d2-d2+d3-d3+d4-d4+bP1 d1-0 d2-0 x1P3 d4-001011011000-100001000-100-1-11011-100001000-116262430P1P2P3000-10-1000100000010102-100000001xjXBcj00P100P22

27、P30P30 x1x2d1-d1+d2-d2+d3-d3+d4-d4+b0 x20 d2-0 x1P3 d4-001010001-10-1-110101000-100-101110-1-10001000-116102414P1P2P300000010100-1000010001001000001xjXBcj00P100P22 P30P30 x1x2d1-d1+d2-d2+d3-d3+d4-d4+b0 x20 d1+0 x1P3 d4-001010000-1000100110-1-1-101-101110-1-10001000-12610244P1P2P300000010000000101-10

28、01001000001xjXB五、应用举例五、应用举例例例1 某某单单位位领领导导在在考考虑虑本本单单位位职职工工的的升升级级调调资资方方案案时时，依依次次遵遵循循以以下下规规定：定：1）不超过月工资总额）不超过月工资总额60000元。元。2）每级的人数不超过定编规定的人数。）每级的人数不超过定编规定的人数。3），级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%。4）级级不不足足编编制制的的人人数数可可录录用用新新职职工工，又又级级的的职职工工中中有有10%要退休。要退休。有关资料汇总于下表中，问单位领导应如何拟定一个满意方案。有关资料汇总于下表中，问单位领导应如何拟定一个满

29、意方案。等等 级级工资额工资额（元（元/月）月）现有人数现有人数编制人数编制人数200015001000101215121515合合 计计3742解解：设设x1，x2，x3分分别别表表示示提提升升到到、级级和和录录用用到到级级的的新新职职工人数。工人数。某某公公司司拟拟用用一一笔笔资资金金投投资资于于四四种种资资产产（如如股股票票、债债券券、）。公公司司财财务务人人员员对对这这四四种种资资产产进进行行了了评评估估，估估算算出出在在这这一一时时期期内内购购买买Sj的的收收益益率率为为rj，并并预预测测出出购购买买Sj的的风风险险损损失失率率为为qj。考考虑虑到到投投资资越越分分散散，总总的的风风

30、险险越越小小，公公司司决决定定，当当用用这这笔笔资资金金购购买买若若干干资资产产时时，总总体体风风险险可可用用所所投投资资的的Sj中中最最大大的的一一个个风风险险来来度度量量。购购买买Sj要要付付交交易易费费，费费率率为为pj（相相关关数数据据见见下下表表）。另另外外，假假定定同同期期银银行行存存款款利率为利率为5%，且既无交易费，又无风险。公司对投资提出以下要求：，且既无交易费，又无风险。公司对投资提出以下要求：1）总投资额尽量不超过）总投资额尽量不超过1000000元（元（P1）。）。2）总收益不少于总投资的）总收益不少于总投资的15%（P2）。）。3）投资的总体风险尽可能小（）投资的总体风险尽可能小（P3）。）。4）对资产的投资不少于总投资的）对资产的投资不少于总投资的10%（P4）。）。例例2SjrjqjpjS1282.51S2211.52S3235.54.5S4252.66.5解：解：设设xj为投资于资产为投资于资产Sj的投资额的投资额(j=1,2,3,4)，x5为存入银行的金额。为存入银行的金额。