2019/6/20 本章内容 第4章目标规划 Goal Programming 4.3目标规划的图解法 2019年6月3日 A △出 4.1概述 目标规划与线性规划的比较 2、线性规划求最优解：目标规划是找到一个满意解。 提出G,GP在实政中 投轻产路天经 丹聚后装春封扩学受晶、市场 △出 △型兰 4.2目标规划的数学模型 例41某工厂生产两种产品，具体数据如下表。 一、问题的提出 11 资源拥有量 P:值 原材料（公斤） 2 1 11 设备小时 10 利澜（干元件）8 10 试求获利最大的生产方案 △性 △ 1
2019/6/20 1 第4章 目标规划 Goal Programming 马俊 国际商学院 2019年6月3日 1 本章内容 4.1 概述 4.2 目标规划的数学模型 4.3 目标规划的图解法 2 3 1952年,美国学者Charnes等提出GP。GP在实践中 的应用十分广泛，它的重要特点是对各个目标分级加 权与逐级优化，这符合人们处理问题要分轻重缓急、 保证重点的思考方式。 4.1 概述 多目标规划 目标规划(Goal Programming,简称GP) -------一类特殊的多目标规划. 目标规划与线性规划的比较 1、线性规划只讨论一个线性目标函数在一组线性约束 条件下的极值问题；而目标规划是多个目标决策，可求得 更切合实际的解。 2、线性规划求最优解；目标规划是找到一个满意解。 3、线性规划中的约束条件是同等重要的，是硬约束；而 目标规划中有轻重缓急和主次之分，即有优先权。 4、线性规划的最优解是绝对意义下的最优，但需花去大 量的人力、物力、财力才能得到；实际过程中，只要求得 满意解，就能满足需要（或更能满足需要）。 目前，已经在经济计划、生产管理、经营管理、市场 分析、财务管理等方面得到了广泛的应用。 4 5 4.2 目标规划的数学模型 LP：单一目标函数 追求目标的极端值 GP：多个目标函数 尽可能达到等（有弹性） 一、问题的提出 例4-1 某工厂生产两种产品，具体数据如下表。 Ⅰ Ⅱ 资源拥有量 原材料(公斤) 2 1 11 设备(小时) 1 2 10 利润(千元/件) 8 10 试求获利最大的生产方案 6
2019/6/20 市场实际情况 LP:Max Z=8X;+10X2 2X1+X2≤11 (②原材料价格上涨，超计划要高价购买 X+2X2≤10 (③)充分利用设备1，不希望加班。 、X1,X2≥0 (④尽可能达到并超过利洞计划指标56元 X*=(4,3)7Z*=62 要实现上述多个目标决策者如何建模分析？ 二、建立目标规划数学模型有关概念 3、目标优先级： 同一级中可以有若干个目标：P 1、决策变量与偏差变量： 用 系数W1,Wz,W2表 偏差变量d,d心，满足d×d=0 4、目标函数 2、约束条件： 利目标： 硬约束（绝对约） min Z-f(d-+d) 软约束（目标约束），引入，d min Z=f(d (3)不超过目标 min Z=f(d") 例42GP:设X,X2为产品I,产品Ⅱ产量。 MinZ=P,d,*+P2(dz+dz')+P:da (2X,+X2s11 d:X,产量不足X部分 该厂目标： X-x2+d-d,=0 d,:X,产量超过X2部分 分利用装配线每周计划开动 X,+2X2+d-d,=10 40小时i0小庆 尽重清足市场需求。因网络电视利润高，取其 8X,+10X2+d5-d'=56 d:设备使用不足10部分 权系数为 d,:设备使用超过10部分 XX2,di,d20 d,d=0 d:利不足56部分 试速立该问愿的GP并求解普通和网络电视机的产量 d:利湘超过56颜分型
2019/6/20 2 7 LP： Max Z=8X1 + 10X2 X* =(4,3)T Z* =62 2X1+X2 11 X1+2X2 10 X1 , X2 0 8 (2) 原材料价格上涨，超计划要高价购买。 (1) 依据市场情况，产品Ⅰ销售量要下降，希望产品Ⅰ 的产量不大于产品Ⅱ的产量。 (3) 充分利用设备I，不希望加班。 (4) 尽可能达到并超过利润计划指标56元。 市场实际情况 要实现上述多个目标,决策者如何建模分析? 9 二、建立目标规划数学模型有关概念 2、约束条件： 硬约束(绝对约束) 软约束 (目标约束)，引入d - , d + 1、决策变量与偏差变量： 偏差变量d - , d +，满足d -×d +＝0 10 4、目标函数： (1) 恰好达到目标： min Z= f (d -+d+) (2) 超过目标： min Z= f (d - ) (3) 不超过目标： min Z= f (d +) 3、目标优先级： P1 P2 … PL； 同一级中可以有若干个目标：P21 , P22 ,P23 …。 其重要程度用权重系数W21 ,W22 ,W23 …表 示。 11 2X1+X2 11 X1 -X2 +d1 - -d1 +=0 X1 +2X2 +d2 - -d2 +=10 8X1 +10X2 +d3 - -d3 +=56 X1 , X2 , di - , di + 0 di - . di + =0 d1 - : X1产量不足X2 部分 d1 + : X1产量超过X2 部分 d2 - : 设备使用不足10 部分 d2 + :设备使用超过10 部分 d3 - : 利润不足56 部分 d3 + :利润超过56 部分 例4-2 GP：设X1 ，X2为产品Ⅰ，产品Ⅱ产量。 Min Z =P1d1 ++P2 (d2 -+d2 + )+P3d3 - 12 例4-3 电视机厂装配普通和网络两种电视机，每台 电视机需装备时间1小时，每周装配线计划开动40 小时，预计每周网络电视销售24台，每台可获利80 元，每周普通电视机销售30台，每台可获利40元。 该厂目标： 第1级：充分利用装配线每周计划开动40小时。 第2级：允许装配线加班，但每周尽量不超过10小时。 第3级：尽量满足市场需求。因网络电视利润高，取其 权系数为2。 试建立该问题的GP,并求解普通和网络电视机的产量
2019/6/20 解：设X,X2分别表示普通和网络电视机产量，有 三、GP建模一般步 Min Z=P:df+P:dz"+P:(2dg+d) 1、设定约束条件。（目标约束、绝对约宋） 1X,+X2+dd*=40 2、规定目标约束优先级。 X,+X2+d2-d2=50 X,+d5-d6=24 3、建立模型。 X2+d-d*=30 X1,X2,d,d20作1,2,3,40 △出 △4丝 四、P的特点 一般模型 mz=2女+d+p2a+aG 品经智禁资速组染策变量的清意值，使决策销果与 含5s6.= ①目标函数中仅有偏差变量。 2+G-G=g.= ②目标函数总是求偏差变量最小。 x,20,(i=1…n) d,dG≥0，k=1…k) Θ绣 △出出 △型兰 某公司生产并销售三种产品A、 这 组装线每月 min==Pdi +d+Pj+P(i+dd+d) 32500元、C每台40000 ,每月销售计划分别： 25000x+32500+4000+d-d=49000 为8台、 C为4台，该公司决策者有如下考虑 30x1+40x,+50x+d5-d=600 组装线空闲 d+d-d=30 馬+d-d=8 不得超过30小时 第四，努力按销售计划来完程 为+-d= x+di-d=4 试建立该同愿的GP慎型。 △丝出 ,.2012.3=l2.6△3w
2019/6/20 3 13 解：设X1 , X2 分别表示普通和网络电视机产量，有 Min Z=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) 14 三、GP建模一般步骤 1、设定约束条件。(目标约束、绝对约束) 2、规定目标约束优先级。 3 、建立模型。 15 一般模型 ( ) ( ) ( ) ( ) ( ) ( ) ( ) = = + − = = = = + + + = + + − = − + = = − − + + = − − + + d d k K x j n c x d d g k K a x b i m Z P w d w d P w d w d k k j n j k j j k k k n j ij j i K k L Lk k Lk k K k k k k k , 0 1 0 1 , 1 , , 1 min 1 1 1 1 1 1 1 ， ， 16 目标规划：求一组决策变量的满意值，使决策结果与 给定目标总偏差最小。 ③ Z=0：各级目标均已达到； Z>0：部分目标未达到。 ① 目标函数中仅有偏差变量。 ② 目标函数总是求偏差变量最小。 四、GP的特点 17 例4-4 某公司生产并销售三种产品Ａ、B、C，在组装 时要经过同一条组装线，三种产品装配时间分别为30 小时、40小时和50小时。组装线每月工作600小时。 这三种产品的销售利润分别为：A每台25000元、B每 台32500元、C每台40000元，每月销售计划分别：A 为8台、B为6台、C为4台，该公司决策者有如下考虑： 首先，争取利润达到每月490000元； 第二，要充分发挥生产能力，不使组装线空闲； 第三，如果加班，加班时间不得超过30小时； 第四，努力按销售计划来完成生产数量。 试建立该问题的GP模型。 min ( ) 1 1 2 2 3 3 4 4 4 5 5 6 6 z Pd P d P d P d d d d d d − − + − + − + − + = + + + + + + + + 1 2 3 1 1 25000 32500 40000 490000 x x x d d − + + + + − = 1 2 3 2 2 30 40 50 600 x x x d d − + + + + − = 2 3 3 d d d 30 + − + + − = x d d 1 4 4 8 − + + − = x d d 2 5 5 6 − + + − = 3 6 6 x d d 4 − + + − = , , 0, 1, 2,3; 1, 2, ,6 i j j x d d i j − + = = 18
2019/6/20 4.3LGP的图解法 例42GP:设X,X为产品I,产品Ⅱ产量。 图解法的基本步骤 Min Z=P,d,*+Pz(dz+dz")+P3dg" ()在第一象限内作出绝对约束条件的图形 (2)令各个偏差变量为0，作出所有目标的束 2X+X2s11 d:X,产量不足X2部分 (3)作图表示出各个偏差变量对约束直线影响： X1-X2+d:-d,=0 (4)考虑第一优先级的最优解集合，依次考虑 d,:X,产量超过X部分 X,+2X2+d2-d,*=10 后一级别的解集合： 8X,+10X2+d-d,=56 d:设备使用不足10部分 (5)求所有解集合的公共部分（可能无，尽可能）。 d:设备使用超过10部父 d5:利润不足56部分 d.d=0 :利润过56分 解：①可行域0AB 目标3：GD线2 ®用8X+10X2-56 1X,t2X2=10 求得G=(2,4④) D C 20 10 5A dx+2X,=10 x[刻[[8g}raoa列 2X+x2=1 八8X+10x-56△ ④Znn=0 △ 例4-3 d MinZ=P,dr+Padz'+Pf2dj+di) X,+X2+d-d,*=40 40- X,+x2d2-d2=50 X2=30 X,*d-d*=2 Xz+di-d'=30 B X,+X2=50
2019/6/20 4 4.3 LGP的图解法 19 图解法的基本步骤 （1）在第一象限内作出绝对约束条件的图形； （2）令各个偏差变量为0，作出所有目标约束； （3）作图表示出各个偏差变量对约束直线影响； （4）考虑第一优先级的最优解集合，依次考虑 后一级别的解集合； （5）求所有解集合的公共部分(可能无,尽可能)。 20 2X1+X2 11 X1 -X2 +d1 - -d1 +=0 X1 +2X2 +d2 - -d2 +=10 8X1 +10X2 +d3 - -d3 +=56 X1 , X2 , di - , di + 0 di - . di + =0 d1 - : X1产量不足X2 部分 d1 + : X1产量超过X2 部分 d2 - : 设备使用不足10 部分 d2 + :设备使用超过10 部分 d3 - : 利润不足56 部分 d3 + :利润超过56 部分 例4-2 GP：设X1 ，X2为产品Ⅰ，产品Ⅱ产量。 Min Z =P1d1 ++P2 (d2 -+d2 + )+P3d3 - 21 11 10 10 5 5 7 X2 A X1 B D C E F G d2 + d1 - d3 + X1+2X2 = 10 X1 -X2=0 2X1+X2 =11 8X1+10X2=56 O 22 解：① 可行域⊿OAB ② 目标1： ⊿OBC 目标2：ED线段 目标3：GD线段 ③ 用 8X1+10X2=56 X1+ 2X2=10 求得 G=(2,4) X1 -X2=0 X1+2X2=10 解为X= = α+ (1-α) (0 α 1) X1 2 10/3 X2 4 10/3 ④ Zmin =0 23 例 4-3 Min Z=P1d1 -+P2d2 ++P3 (2d3 -+d4 - ) X1+X2 +d1 - -d1 +=40 ① X1 +X2+d2 - -d2 +=50 ② X1 +d3 - -d3 +=24 ③ X2+d4 - -d4 +=30 ④ 24 X2 30 30 40 50 X1 O B A C D E F d3 + d4 + d1 + d2 - X1+X2 =40 X1+X2 =50 X2 =30 X1 =24 解：
2019/6/20 ()满足目标①、②的满意域为ABCD 此处写大标题 (2)先考虑⑧的满意域为ABEF,再考虑④， 无公共清意域。 目标规划问题的Microsoft Excel求解 4Zn=dr=30-X2+d=30-26=4p0 A出 △堂型 5
2019/6/20 5 25 (1) 满足目标①、②的满意域为ABCD (2) 先考虑③的满意域为ABEF,再考虑④， 无公共满意域。 (4) Zmin =d4 - =30 - X2 + d4 +=30-26=4>0 (3)取E X1+X2=50 X1=24 E(24,26) 获利2960 此处写大标题 目标规划问题的 Microsoft Excel 求解 26