目标规划演示教案

1、目标规划目标规划1. 目标规划的数学模型目标规划的数学模型一一. 引例引例 某工厂生产两种产品、某工厂生产两种产品、,已知有关数据如下表已知有关数据如下表:产品产品I和和II的产量分别是的产量分别是X1和和X2则模型则模型0,404460105. .86)(21212121xxxxxxtsxxZMaxLP其最优解，即最其最优解，即最优生产计划为优生产计划为X1=8件件,X2=2件件Max Z=64件件试求获利最大的生产方案试求获利最大的生产方案.解解1. 目标规划的数学模型目标规划的数学模型(2)但在实际中工厂作决策时但在实际中工厂作决策时,要考虑市场等一系列其它条件要考虑市场等一系列其它条件

2、如如(1)根据市场信息根据市场信息,产品产品II的销售量有下降的趋势的销售量有下降的趋势, 故考虑故考虑 产品产品I的产量不少于产品的产量不少于产品II的一半的一半.(3)最好能节约最好能节约4小时设备工时；小时设备工时；(2)原材料严重短缺原材料严重短缺,生产中应避免过量消耗生产中应避免过量消耗.(4)计划利润不少于计划利润不少于48元；元；(5)应尽可能达到并超过计划利润指标应尽可能达到并超过计划利润指标56元元.这样在考虑产品决策时这样在考虑产品决策时,便为多目标决策问题便为多目标决策问题. 1961年，查恩斯年，查恩斯(A.charnes)和库柏和库柏(W.W.Cooper)提提出目标

3、规划出目标规划(goal programming)方法方法,它是解决这类决策它是解决这类决策问题的方法之一问题的方法之一.1. 目标规划的数学模型目标规划的数学模型(3)决策变量决策变量是代表一个决策方案的变量是代表一个决策方案的变量, 如上例的如上例的X1和和X2对每一个决策目标对每一个决策目标,引入引入两个变量两个变量d+和和d-, 二、与目标规划数学模型有关的概念二、与目标规划数学模型有关的概念分别表示决策值超过或不足目标值的部分分别表示决策值超过或不足目标值的部分称为称为偏差变量偏差变量故故 正负偏差变量是表示偏离一个目标的偏离量正负偏差变量是表示偏离一个目标的偏离量正偏差变量正偏差变

4、量d+表示决策值超过目标值的部分表示决策值超过目标值的部分.负偏差变量负偏差变量d-表示决策值未达到目标值的部分表示决策值未达到目标值的部分.显然显然,d-,d+ 0 由由 于一个决策值不可能即超过目标值同时又未达于一个决策值不可能即超过目标值同时又未达到目标值，到目标值，故有故有:d-*d+ =01. 目标规划的数学模型目标规划的数学模型(4)2、绝对约束和目标约束、绝对约束和目标约束绝对约束绝对约束是指必须严格满足的等式约束或不等式约束是指必须严格满足的等式约束或不等式约束也称也称硬约束硬约束目标约束目标约束就是把一个目标加上负偏差变量减去正偏差就是把一个目标加上负偏差变量减去正偏差 变量

5、等于目标值的一个约束条件变量等于目标值的一个约束条件. 也称也称软约束软约束3. 优先因子优先因子(优先等级优先等级)与权系数与权系数把目标规划中的目标分为不同的优先级把目标规划中的目标分为不同的优先级,优先级的高低分别用优先因子优先级的高低分别用优先因子P1,P2,表示表示优先因子优先因子P1表示第一优先级目标表示第一优先级目标,P2表示第二优先级表示第二优先级 目标目标,其余类推其余类推. 优先因子间的关系：优先因子间的关系：PkPk+1权系数权系数是表示同一优先级的不同目标的重要程度是表示同一优先级的不同目标的重要程度.1. 目标规划的数学模型目标规划的数学模型(5)当一目标值确定后当一

6、目标值确定后,决策者的要求是尽可能缩小偏离决策者的要求是尽可能缩小偏离目标值目标值，则目标函数一般形式有，则目标函数一般形式有 是按各目标约束的正、负是按各目标约束的正、负偏差变量和赋于相应的优先因子而构造的。偏差变量和赋于相应的优先因子而构造的。min Z=f(d-,d+) 应用时应用时,有三种基本形式有三种基本形式(1)要求恰好达到目标值要求恰好达到目标值.这时决策值超过或不足目标值这时决策值超过或不足目标值 都是不希望的都是不希望的,因此有因此有 min f(d-+d+)(3) 要求不低于目标值要求不低于目标值,但允许超过目标值但允许超过目标值.这时这时,不不 希望决策值低于目标值希望决

7、策值低于目标值,(2) 要求不超过目标值，但允许不足目标值要求不超过目标值，但允许不足目标值.这时，不这时，不 希望决策值不超过目标值希望决策值不超过目标值, 因此有因此有 min f(d+)因此有因此有 min f(d-)4、目标规划的目标函数：、目标规划的目标函数：1. 目标规划的数学模型目标规划的数学模型(6)前面例前面例1的目标规划数学模型的目标规划数学模型:第一第一 考虑到原材料严重短缺考虑到原材料严重短缺,生产中应避免过量消耗生产中应避免过量消耗 故故5X1+10X26060第二第二 根据市场信息根据市场信息,产品产品II的销售量有下降的趋势的销售量有下降的趋势,故故考虑产品考虑产

8、品I的产量不少于产品的产量不少于产品II的一半的一半.021121ddxx第三第三 最好能节约最好能节约4小时设备工时小时设备工时第四第四 计划利润不少于计划利润不少于48元元36442221ddxx48863321ddxx目标函数目标函数min,11dP,22dP33dP1. 目标规划的数学模型目标规划的数学模型(7)故该问题的数学模型为故该问题的数学模型为3 , 2 , 1, 0, 0,488636440260105. .,min2133212221112121332211kddXXddXXddXXddXXXXtsdPdPdPkk绝对约束绝对约束目目标标约约束束1. 目标规划的数学模型目标

9、规划的数学模型(8)目标规划数学模型的一般形式为目标规划数学模型的一般形式为KkddnjxmibxaKkgddxCIidwdwPkkjnjijijkkknjjkjKkkikkiki,.,2 , 1,0,.,2 , 1,0,.,2 , 1),(,.,2 , 1,.,2 , 1),)(min111绝对约束绝对约束目标约束目标约束目标函数目标函数非负约束非负约束正负偏差变量正负偏差变量1. 目标规划的数学模型目标规划的数学模型(9)例例2. 某织布厂生产甲某织布厂生产甲,乙两种布料乙两种布料,平均生产能力都是平均生产能力都是1千千米米/小时。这个工厂的正常生产能力是每周小时。这个工厂的正常生产能力是

10、每周80小时。甲小时。甲种衣料每千米可获利种衣料每千米可获利2500元元,乙种布料每千米可获利乙种布料每千米可获利1500元。已知下一个星期甲种衣料的需求量最多为元。已知下一个星期甲种衣料的需求量最多为70千千米米,乙种衣料下一个星期的需求量最多为乙种衣料下一个星期的需求量最多为45千米千米.该厂确该厂确定的目标依次为定的目标依次为:试建立该问题的目标规划模型试建立该问题的目标规划模型.(1)避免开工不足避免开工不足,使职工的正常工作保持稳定使职工的正常工作保持稳定;(3)努力达到最大需求量努力达到最大需求量;(2)允许加班允许加班;但加班时间不超过但加班时间不超过10小时小时;(4)尽量减少

11、加班时间尽量减少加班时间;解解:设生产甲设生产甲,乙两种布料的时间分别为乙两种布料的时间分别为X1和和X21. 目标规划的数学模型目标规划的数学模型(10)避免开工不足避免开工不足,使职工的正常工作保持稳定使职工的正常工作保持稳定努力达到最大需求量努力达到最大需求量允许加班允许加班;但加班时间不超过但加班时间不超过10小时小时尽量减少加班时间尽量减少加班时间第一目标第一目标801121ddXX第二目标第二目标 901121ddXX第三目标第三目标70331ddX45442ddX第四目标第四目标801121ddXX目标目标函数函数),35(,min144332211dPddPdPdP例例1 用图

12、解法求解下列目标规划问题用图解法求解下列目标规划问题:2. 目标规划的图解法（例目标规划的图解法（例11）3 , 2 , 1, 0, 0,488636440260105,min2133212221112121332211kddXXddXXddXXddXXXXdPdPdPkkA AB BD DE EC CF F2.目标规划的图解法目标规划的图解法(例例12)0 05x5x1 1+10 x+10 x2 2=60=60 x2x2x1x1x x1 1-2x-2x2 2=0=01d1d4x4x1 1+4x+4x2 2=36=362d6x6x1 1+8x+8x2 2=48=483d2.目标规划的图解法目标

13、规划的图解法(例例21)(1)充分利用装配线每周计划开动充分利用装配线每周计划开动40小时小时; 例、例、某电视机厂装配黑白和彩电两种电视机某电视机厂装配黑白和彩电两种电视机,每装配一每装配一 台电视机需占用装配线台电视机需占用装配线1小时小时,装配线每周计划开动装配线每周计划开动 40小时小时,预计市场每周彩色电视机的销量是预计市场每周彩色电视机的销量是24台台,每每 台可获利台可获利80元元;黑白电视机的销量是黑白电视机的销量是30台台,每台可获每台可获 利利40元元.该厂确定的目标依次为该厂确定的目标依次为:(2)允许装配线加班允许装配线加班;但加班时间每周尽量不超过但加班时间每周尽量不

14、超过10小时小时(3)装配电视机的数量尽量满足市场需要装配电视机的数量尽量满足市场需要,因彩色因彩色电视机的利润高电视机的利润高,取其权系数为取其权系数为2.试建立该问题的目标规划模型试建立该问题的目标规划模型.解：解： 设设X1,X2分别表示彩色和黑白电视机的产量分别表示彩色和黑白电视机的产量2.目标规划的图解法目标规划的图解法(例例22)第一目标第一目标第二目标第二目标第三目标第三目标401121ddxx)2(,min4332211ddPdPdPZ24331ddx502221ddxx30442ddx4 , 3 , 2 , 1, 0,21jddxxjj充分利用装配线每周计划开动充分利用装配线

15、每周计划开动40小时小时允许装配线加班允许装配线加班;但加班时间每周尽量不超但加班时间每周尽量不超过过10小时小时装配电视机的数量尽量满足市场需要装配电视机的数量尽量满足市场需要,因彩色因彩色电视机的利润高电视机的利润高,取其权系数为取其权系数为2.目标函数目标函数2.目标规划的图解法目标规划的图解法(例例23)4 , 3 , 2 , 1, 0,30245040. .)2(min21442331222111214332211jddxxddxddxddxxddxxtsddPdPdPZjj2.目标规划的图解法（例目标规划的图解法（例24）X X1 1 X X2 2 0 0 X X1 1+X+X2

16、2=40=401dX X1 1+X+X2 2=50=502dX X1 1=24=243dX X2 2=30=304d)2(,min4332211ddPdPdPZ目标函数目标函数A AB BC CD DG GH HE EF F最优解在最优解在E E点取得点取得3.目标规划的单纯形法目标规划的单纯形法(1) 目标规划的数学模型结构与线性规划的数学模型结目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别构没有本质的区别.故可用单纯形法求解故可用单纯形法求解.二是二是判别最优解的准则要考虑到优先级的因素判别最优解的准则要考虑到优先级的因素不同之处不同之处一是一是初始单纯形表中的检验数行按优先

17、级初始单纯形表中的检验数行按优先级P 列成一个矩阵列成一个矩阵;解目标规划问题的单纯形法的计算步骤：解目标规划问题的单纯形法的计算步骤：第一步：建立初始单纯形表第一步：建立初始单纯形表在表中将检验数行按优先因子个数分别列成在表中将检验数行按优先因子个数分别列成K行。行。令令i=13.目标规划的单纯形法目标规划的单纯形法(2)例：例：初始基为单位矩阵初始基为单位矩阵(1)取初始基变量取初始基变量单纯形表为单纯形表为3 , 2 , 1, 0,561081020112. .)()(min213321222111213213322211jddxxddxxddxxddxxxxxtsdPddPdPZjj3

18、213,dddxABCCbBCABbBBB11113.目标规划的单纯形法目标规划的单纯形法(3)P1的检验数：的检验数：C=（0，0，0，0，1，0，0，0，0），），CB=（0，0，0，0） P2的检验数：的检验数：C=(0,0,0,0,0,1,1,0,0)P3的检验数的检验数:C=(0,0,0,0,0,0,0,1,0)CB=（0，0，1，0）CB=（0,0,0,1）3.目标规划的单纯形法目标规划的单纯形法(4)第二步第二步检验时检验时,要依照优先级的顺序要依照优先级的顺序,由检验数矩阵的上边行开由检验数矩阵的上边行开始始,首先满足前边优先级首先满足前边优先级. 判别最优解的准则有二条判别最

19、优解的准则有二条:检验第检验第i行中是否存在负数行中是否存在负数,且对应的前且对应的前 i-1行的行的系数是零，若有取其中最小者对应的变量为入系数是零，若有取其中最小者对应的变量为入基变量，基变量，转第三步转第三步。若无负数，则转第五步。若无负数，则转第五步。 i)如行优先级如行优先级P1,P2,Pk行的全体检验数均非负行的全体检验数均非负,则则 相应的单纯形表的解为最优解相应的单纯形表的解为最优解;ii )前前P1,P2,Pi行的检验数均非负行的检验数均非负,而第而第Pi+1行的检验行的检验 数中有负数数中有负数,如在这个负检验数所在列上的前几行如在这个负检验数所在列上的前几行 中有正检验数

20、中有正检验数,则相应的单纯形表的解为满意解则相应的单纯形表的解为满意解.3.目标规划的单纯形法目标规划的单纯形法(5)第四步第四步：按单纯形法进行换基迭代，建立新的单纯形：按单纯形法进行换基迭代，建立新的单纯形 表，转第二步。表，转第二步。第五步第五步：当：当i=K 时，计算结束，表中的解即为满意解。时，计算结束，表中的解即为满意解。否则令否则令i=i+1, 转第二步。转第二步。第三步第三步按最小比值规则确定出基变量，当存在两个和两按最小比值规则确定出基变量，当存在两个和两 个以上相同的最小比值时，具有较高优先级别的个以上相同的最小比值时，具有较高优先级别的 变量为出基变量。变量为出基变量。3

21、.目标规划的单纯形法目标规划的单纯形法(例例1)3.目标规划的单纯形法目标规划的单纯形法(例例1-2)上所有的检验数都为非负，上所有的检验数都为非负，则则X1=2，X2=4即为满即为满意解意解。但非基变量。但非基变量d3+的检验数为的检验数为0，这表示存在，这表示存在多组解。多组解。3.目标规划的单纯形法目标规划的单纯形法(例例2)例例2. 2. 3 , 2 , 1, 0, 0,488636440260105,min21332122211121321332211kddXXddXXddXXddXXXXXdPdPdPkk5.目标规划应用举例目标规划应用举例(例例1)例例1 1：某单位领导在考虑本单

22、位职工的升级调资方案时某单位领导在考虑本单位职工的升级调资方案时, , 依次遵守以下规定依次遵守以下规定: :(2)(2)每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数; ;(1)(1)不超过年工资总额不超过年工资总额6000060000元元; ;(3)(3) 二，三级的升级面尽可能达到现有人数的二，三级的升级面尽可能达到现有人数的20%;20%;注注: :三级不足编制的人数可录用新职工三级不足编制的人数可录用新职工, ,又一级的职又一级的职 工中有工中有10%10%要退休要退休; ;有关资料汇总如有关资料汇总如右表右表等等级级 工工资资额额( (元元/ /年年) ) 现现有有人

23、人数数 编编制制人人数数 一一 二二 三三 2 20 00 00 0 1 15 50 00 0 1 10 00 00 0 1 10 0 1 12 2 1 15 5 1 12 2 1 15 5 1 15 5合合计计 3 37 7 4 42 2 试建立该问题的目标规划模型试建立该问题的目标规划模型5.目标规划应用举例目标规划应用举例(例例1-2)解：解：设设X X1 1，X X2 2，X X3 3分别表示提升到一、二级和录用到三分别表示提升到一、二级和录用到三 级的新职工人数级的新职工人数 对各目标确定的优先因子为：对各目标确定的优先因子为：P P1 1-不超过年工资总额不超过年工资总额60000

24、60000元元; ;P P2 2-每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数P P3 3-二，三级的升级面尽可能达到现有人数的二，三级的升级面尽可能达到现有人数的20%;20%;分别建立目标约束：分别建立目标约束：第一目标：年工资总额不超过第一目标：年工资总额不超过6000060000元：元：20002000（10-1010-10* *0.1+X0.1+X1 1) )+1500(12-X+1500(12-X1 1+X+X2 2) )+1000(15-X+1000(15-X2 2+X+X3 3) )=6000011dd5.目标规划应用举例目标规划应用举例(例例1-3)第二目标：

25、第二目标：每级的人数不超过定编规定的人数每级的人数不超过定编规定的人数对对I I级有级有10(1-0.1)+X10(1-0.1)+X1 1+ + =12对对IIII级有级有 12-X12-X1 1+X+X2 2+ + =15对对IIIIII级有级有15-X15-X2 2+X+X3 3+ + =1522dd33dd44dd第二目标第二目标：二、三级的升级面尽可能达到现有人数的二、三级的升级面尽可能达到现有人数的20%20%对对IIII级有级有 X X1 1+ + =12*0.255dd对对IIIIII级有级有X X2 2+ + =15*0.266dd目标函数目标函数: )(),(,min653432211ddPdddPdPZ5.目标规划应用举例目标规划应用举例(例例1-4)该问题的数学模型该问题的数学模型: )(),(,min653432211ddPdddPdPZS.T. 20002000（10-1010-10* *0.1+X0.1+X1 1) )+1500(12-X+1500(12-X1 1+X+X2 2) )+1000(15-X+1000