运筹学第四章目标规划课件.ppt

1、第四章第四章 目标规划目标规划一、目标规划的数学模型二、目标规划的图解法三、解目标规划的单纯形法四、应用举例第四章一、目标规划的数学模型一、目标规划的数学模型例1：产品III限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68解得：最优生产计划为：x1=8件，x2=2件，max z=64元。LP：max z=6x1+8x2 5x1+10 x2 604x1+4x2 40 x1,x2 0 s.t.x1 x2 第四章但如果站在企业高层领导者的角度看：一个计划要满足多方面的要求。财务、物资、销一个计划要满足多方面的要求。财务、物资、销售、计划。售、计划。线性规划问题有最优解的必

2、要条件是其可行解集线性规划问题有最优解的必要条件是其可行解集非空。但实际问题有时不能满足这样的要求。非空。但实际问题有时不能满足这样的要求。线性规划解的可行性和最优性具有十分明确的意线性规划解的可行性和最优性具有十分明确的意义。实际问题中往往还会作某种调整和修改。义。实际问题中往往还会作某种调整和修改。一、目标规划的数学模型一、目标规划的数学模型第四章1961年，查恩斯（A.Charnes）和库柏（W.W.Cooper）提出了目标规划（Goal Programming，简称GP）。v目标规划在处理实际决策问题时，承认各项决策目标规划在处理实际决策问题时，承认各项决策要求的存在有其合理性；要求的

3、存在有其合理性；v在作最终决策时，不强调其绝对意义上的最优性。在作最终决策时，不强调其绝对意义上的最优性。一、目标规划的数学模型一、目标规划的数学模型第四章例2 假设计划人员还被要求考虑如下的意见：由于产品由于产品II销售疲软，故销售疲软，故产品产品II的产量不的产量不超过产品超过产品I的一半；的一半；原材料严重短缺，生产中应避免过量消耗；原材料严重短缺，生产中应避免过量消耗；能节约能节约4小时设备工时；小时设备工时；利润不少于利润不少于48元。元。最后达成了一致意见：（目标）1)原材料使用限额原材料使用限额突破；突破；2)产品产品II产量要求必须产量要求必须考虑；考虑；3)设备工时问题设备工

4、时问题考虑（节约考虑（节约4个）；个）；4)最后最后考虑计划利润的要求。考虑计划利润的要求。一、目标规划的数学模型一、目标规划的数学模型第四章1、偏差变量对每一个决策目标，引入正、负偏差变量d+和d-。d+:决策值超过目标值的部分。d-：决策值未达到目标值的部分。d+0和d-0 d+d-0目标规划数学模型涉及的基本概念目标规划数学模型涉及的基本概念一、目标规划的数学模型一、目标规划的数学模型第四章2绝对约束和目标约束绝对约束：必须严格满足的等式或不等式约束。目标约束：目标规划所特有的约束，约束右端项看作要追求的目标值，在达到目标值时，允许发生正或负的偏差。绝对约束是硬约束。目标约束是一种软约束

5、，目标约束中决策值和目标值之间的差异用偏差变量表示。必为等式。一、目标规划的数学模型一、目标规划的数学模型第四章3优先因子和权系数不同目标的主次轻重有两种差别。一种差别是绝对的，可用优先因子Pt来表示。优先因子间的关系为PtPt+1，即Pt对应的目标比Pt+1对应的目标有绝对的优先性。另一种差别是相对的，这些目标具有相同的优先因子，它们的重要程度可用权系数的不同来表示。一、目标规划的数学模型一、目标规划的数学模型第四章 4目标规划的目标函数目标规划的目标函数(又称为准则函数或达成函数)由各目标约束的偏差变量及相应的优先因子和权系数构成。其目标函数只能是极小化。有三种基本表达式：(1)要求恰好达

6、到目标值。minf(d+d-)(2)要求不超过目标值，但允许不足目标值。minf(d+)(3)要求不低于目标值，但允许超过目标值。minf(d-)一、目标规划的数学模型一、目标规划的数学模型第四章5x1+10 x2 602x2 x1+d1-d1+=04x1+4x2+d2-d2+=366x1+8x2+d3-d3+=48x1,x2,di-,di+0 di-.di+=0 i=1,2,3 minZ=P1d1+P2(d2+)+P3(d3-)一、目标规划的数学模型一、目标规划的数学模型s.t.(1)原材料使用限额不得突破；(2)产品II产量要求必须优先考虑；(3)设备工时问题其次考虑（节约4个）；(4)最

7、后考虑计划利润的要求。（不少于48）LP：maxZ=6x1+8x2 5x1+10 x2 604x1+4x2 40 x1,x2 0 s.t.例2第四章一、目标规划的数学模型一、目标规划的数学模型kkkLkkLkLkkkkkkdwdwPdwdwPZ11111min KkddnjxKkgddxCkmibxakkjnjkkkjjnjijij10,1011,11s.t.第四章例例3 资源拥有量原材料(公斤)2 1 11设备(小时)1 2 10利润(千元/件)8 10 (1)、原材料价格上涨，超计划要高价购买，所以要严格控制。(2)、市场情况，产品销售量下降，产品的产量不大于产品的产量。(3)、充分利用设

8、备，不希望加班。(4)、尽可能达到并超过利润计划指标56千元。一、目标规划的数学模型一、目标规划的数学模型第四章设X1，X2为产品，产品产量。目标函数 minZ=P1d1+P2(d2-+d2+)+P3(d3-)一、目标规划的数学模型一、目标规划的数学模型2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0 di-.di+=0s.t.第四章例4、电视机厂装配25寸和21寸两种彩电，每台电视机需装备时间1小时，每周装配线计划开动40小时，预计每周25寸彩电销售24台，每台可获利80元，每周21寸彩电销售30台

9、，每台可获利40元。该厂目标：1、充分利用装配线，避免开工不足。2、允许装配线加班，但尽量不超过10小时。3、尽量满足市场需求。一、目标规划的数学模型一、目标规划的数学模型第四章解：设X1,X2 分别表示25寸，21寸彩电产量minZ=P1d1-+P2d2+P3(2d3-+d4-)一、目标规划的数学模型一、目标规划的数学模型X1+X2+d1-d1+=40X1+X2+d2-d2+=50X1+d3-d3+=24X2+d4-d4+=30X1,X2,di-,di+0(i=1,2,3,4)s.t.第四章小结：小结：1、约束条件：硬约束(绝对约束)软约束(目标约束)，引入d-,d+2、目标优先级：P1 P

10、2 PL 同一级中可以有若干个目标：P21,P22,P23 其重要程度用权重系数W21,W22,W23 表示一、目标规划的数学模型一、目标规划的数学模型第四章3、目标函数：(1)、恰好达到目标：minZ=f(d-+d+)(2)、超过目标：minZ=f(d-)(3)、不超过目标：minZ=f(d+)一、目标规划的数学模型一、目标规划的数学模型第四章4、目标规划的目标：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。目标函数中只有偏差变量。目标函数总是求偏差变量最小。Z=0：各级目标均已达到 Z0：部分目标未达到。一、目标规划的数学模型一、目标规划的数学模型第四章二、目标规划的图解法二、目

11、标规划的图解法例例1minZ=d-100X1+80X2-d+d-=100004X1+2X2 4002X1+4X2 500X1,X2,d-,d+0 d+.d-=0s.t.第四章X1O50100X250100125E100X1+80X2=100002X1+4X2=500C4X1+2X2=400Bd+(1)、绝对约束可行域OBEC(2)、目标约束满意域CBE(3)、多个可行满意解：(60,50),10000;(70,50),11000;E(50,100),13000。(4)、Zmin=0二、目标规划的图解法二、目标规划的图解法minZ=d-100X1+80X2-d+d-=100004X1+2X2 4

12、002X1+4X2 500X1,X2,d-,d+0 d+.d-=0s.t.第四章例例2：用图解法求解。：用图解法求解。3,2,10,1232820124164min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPziis.t.二、目标规划的图解法二、目标规划的图解法第四章X243X11d1dABOED2d2d3d3d问题的解为：线段DE二、目标规划的图解法二、目标规划的图解法3,2,10,1232820124164min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii第四章例例3minZ=

13、P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0第四章CDEd2+X1+2X2=10d1-X1-X2=07FGd3+8X1+10X2=56A11B2X1+X2=11105X2510X1OminZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0解：解：可行域OAB 目标1：OBC 目标2：ED线段 目标3：GD线段

14、第四章例例4minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2+d1-d1+=40 X1+X2+d2-d2+=50 X1+d3-d3+=24 X2+d4-d4+=30 第四章30304050X2X1OADd1+X1+X2=40d2-BCX1+X2=50d4+X2=30EFd3+X1=24解：解：minZ=P1d1-+P2d2+P3(2d3-+d4-)X1+X2+d1-d1+=40 X1+X2+d2-d2+=50 X1+d3-d3+=24 X2+d4-d4+=30 第四章(1)、满足目标、满足目标、的满意域为的满意域为ABCD(2)、先考虑、先考虑的满意域为的满意域为ABEF再考

15、虑再考虑，无公共满意域。，无公共满意域。(4)、Zmin=d4-=30-X2+d4+=30-26=40(3)、取、取EX1+X2=50X1=24E(24,26)获利获利2960第四章应用案例应用案例红星制药厂生产A、B两种药品，有关数据如下：A B 电力 2 3 100(百度)煤 4 2 120(百吨)利润 6 4 (万元)（1）求最优生产计划（2）电力可多供应20（百度），利润能否达240（万元）？（3）若（2）达不到，改为以下目标规划 目标1：保证利润不低于240万元 目标2：耗电量、耗煤量应尽量少地超过120二、目标规划的图解法二、目标规划的图解法第四章解：解：用单纯形法求解，得解为：x

16、1=20，x2=20，Zmax=200(万元)(2)、用灵敏度分析，可得：x1=15，x2=30，Zmax=210(3)、建立目标规划模型(1)、max Z=6x1+4x22x1+3x2 1004x1+2x2 120 x1,x2 0s.t.minZ=P1(d1-)+P2(d2+d3+)6x1+4x2+d1-d1+=2402x1+3x2+d2-d2+=120 4x1+2x2+d3-d3+=120 xi,di-,di+0s.t.二、目标规划的图解法二、目标规划的图解法第四章1010 x2x1DCBAd3-d1+d2-4x1+2x2=1206x1+4x2=2402x1+3x2=120OEA(40，0

17、)，B(60，0)C(24，24)，D(0，60)二、目标规划的图解法二、目标规划的图解法第四章分析：满足P1，部分满足P2的点有A,B,C,D(如果不考虑A，B产品均需生产)由解方程可得：A(40，0)，B(60，0)C(24，24)，D(0，60)比较与目标的偏差A点：ZA =P1d1-+P2d2+P2d3+=0+0+P2d3+=(4x1+2x2+d3-120)P2 =(440-120）P2=40P2B点：ZB =120P2 C点：ZC =24P2 D点：ZD =60P2结论：取C点二、目标规划的图解法二、目标规划的图解法第四章三、解目标规划的单纯形法三、解目标规划的单纯形法计算步骤：1.

18、建立初始单纯形表。在表尾将检验数行按优先因子个数分别列成k行，置k=1。2.检验该行中是否存在负数且对应的前k-1行的系数为0。若有取其中最小者对应的变量为换入变量，转3）。若无负数，转5）。3.按最小比值规则确定换出变量，当存在两个及两个以上相同的最小比值时，选取具有较高级别的变量为换出变量。4.按单纯形法进行基变换运算，建立新计算表，返2）。5.当k=K时，计算结束。其中的解即为满意解。否则置k=K+1,返2）。第四章例6 用单纯形法解下列问题minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2 11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10

19、X2+d3-d3+=56X1,X2,di-,di+0s.t.三、解目标规划的单纯形法三、解目标规划的单纯形法第四章CjCBXBbx1x2x3d1-d1+d2-d2+d3-d3+j=cj-zjP1P2P3minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2+X3=11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0第四章Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0X3112110000000d1-01-101-10000P2d2-10120001-100P3

20、d3-56810000001-1 j=cj-zjP1000010000P2-1-20000200P3-8-100000001minZ=P1d1+P2(d2-+d2+)+P3(d3-)2X1+X2+X3=11X1-X2+d1-d1+=0X1+2X2+d2-d2+=108X1+10X2+d3-d3+=56X1,X2,di-,di+0第四章Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0X3112110000000d1-01-101-10000P2d2-10120001-100P3d3-56810000001-1 j=cj-zjP1000010000P2-1

21、-20000200P3-8-100000001解：化标准形。列初始单纯形表三、解目标规划的单纯形法三、解目标规划的单纯形法第四章Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0X363/20100-1/21/2000d1-53/2001-11/2-1/2000 x251/21000-1/200P3d3-630000-551-1 j=cj-zjP1000010000P2000001100P3-300005-501三、解目标规划的单纯形法三、解目标规划的单纯形法第四章Cj0000P1P2P2P30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0

22、X33001002-2-1/2 1/20d1-20001-13-3-1/2 1/20 x24010004/3-4/3-1/6 1/60 x1210000-5/35/31/3-1/3 j=cj-zjP1000010000P2000001100P3000000010相当G x=(2,4)利润为56三、解目标规划的单纯形法三、解目标规划的单纯形法第四章说明：1，还可以再做一步，d3+d1-,可得 X=(10/3，10/3)，对应于D点；2，初始表中检验数行：要注意化为非基变 量表示式再填入。三、解目标规划的单纯形法三、解目标规划的单纯形法第四章例7：用单纯形法求解minZ=P1d1-+P2d2+P3

23、(2d3-+d4-)X1+X2+d1-d1+=40 X1+X2+d2-d2+=50 X1+d3-d3+=24 X2+d4-d4+=30 s.t.三、解目标规划的单纯形法三、解目标规划的单纯形法第四章Cj00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-40111-10d2-50111-12P3d3-24101-1P3d4-30011-1 j=cj-zjP1P2P3解：列初始单纯形表三、解目标规划的单纯形法三、解目标规划的单纯形法第四章Cj00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d

24、1-40111-10d2-50111-12P3d3-24101-1P3d4-30011-1 j=cj-zjP1-1-101000000P20000010000P3-2-100000201三、解目标规划的单纯形法三、解目标规划的单纯形法第四章Cj00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+P1d1-16011-1-11000d2-26011-1-11000 x124101-1P3d4-30011-1 j=cj-zjP10-101001000P20000010000P30-100002001三、解目标规划的单纯形法三、解目标规划的单纯形法第四章C

25、j00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0 x216011-1-11000d2-1000-111-100000 x124101-1P3d4-1400-111-11-1 j=cj-zjP10010000000P20000010000P3001-1001101三、解目标规划的单纯形法三、解目标规划的单纯形法第四章Cj00P100P22P30P30CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0 x22601001-1-11000d1+1000-111-100000 x124101-1P3d4-40000-111-11-1

26、 j=cj-zjP10010000000P20000010000P300001-11101所以，原问题的解为：X124，X226。d4-4，所以市场需求没有满足，每周21寸彩电只生产26台。三、解目标规划的单纯形法三、解目标规划的单纯形法第四章1、友谊农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。各种作物每亩需施化肥分别为012吨、020吨、015吨。预计秋后玉米每亩可收获500千克，售价为024元千克，大豆每亩可收获200千克，售价为120元千克，小麦每亩可收获350千克，售价为0.70元千克。农场年初规划时考虑如下几个方面：p1：年终收益不低于350万元；p2：总产量不低于125万吨

27、；p3：小麦产量以05万吨为宜；p4：大豆产量不少于02万吨；p5：玉米产量不超过06万吨；p6：农场现能提供5000吨化肥；若不够，可在市场高价购买，但希望高价采购量愈少愈好。试就该农场生产计划建立数学模型。四、四、应用举例应用举例第四章解：设种植玉米x1亩，大豆x2亩，小麦x3亩，则该问题的数学模型为:minZ=P1d1-+P2d2-+P3(d3-+d3+)+P4d4+P5d5+P6(d6+)X1+X2+X3 3104120X1+240X2+245X3+d1-d1+=350 104500X1+200X2+350X3+d2-d2+=1250 104350X3+d3-d3+=500 10420

28、0X2+d4-d4+=200 1041000X3+d5-d5+=600 1040.12X1+0.2X2+0.15X3+d6-d6+=5000X1,X2,di-,di+0s.t.四、四、应用举例应用举例第四章2：某电子公司生产录音机和收音机两种产品，它们均需经过两个工厂加工，每一台录音机在第一个工厂加工2小时，然后送到第二个工厂装配试验25小时才变为成品；每一台收音机需在第一个工厂加工4小时，在第二个工厂装配试验15小时才变为成品。录音机与收音机每台厂内的每月储存成本分别为8元和15元。第一个工厂有12部制造机器，每部每天工作8小时，每月正常工作天数为25天，第二个工厂有7部装配试验设备，每部每

29、天工作16小时，每月正常工作天数仍为25天。每部机器每小时的运转成本是：第一个工厂为18元，第二个工厂为15元。每台录音机的销售利润为20元，收音机为23元。依市场预测，次月的录音机与收音机的销售量估计分别为1500台和1000台。四、四、应用举例应用举例第四章该公司依下列次序为目标优先次序，以实现下月的生产与销售目标。P1：厂内的储存成本最少。P2：录音机销售量必须完成1500台。P3：第一、二工厂的生产设备应全力运转，避免有空闲时间。两厂的运转成本当作它们间的权系数。P4：第一个工厂的超时作业时间全月份不宜超出30小时。P5：收音机销售量必须完成l000台。P6；两个工厂的超时工作时间总和

30、应予限制，其限制的比率依各厂每小时运转成本为准。试建立这个问题的目标规划模型。四、四、应用举例应用举例第四章该公司依下列次序为目标优先次序，以实现下月的生产与销售目标。P1：厂内的储存成本最少。P2：录音机销售量必须完成1500台。P3：第一、二工厂的生产设备应全力运转，避免有空闲时间。两厂的运转成本当作它们间的权系数。P4：第一个工厂的超时作业时间全月份不宜超出30小时。P5：收音机销售量必须完成l000台。P6；两个工厂的超时工作时间总和应予限制，其限制的比率依各厂每小时运转成本为准。试建立这个问题的目标规划模型。2：某电子公司生产录音机和收音机两种产品，它们均需经过两个工厂加工，每一台录

31、音机在第一个工厂加工2小时，然后送到第二个工厂装配试验25小时才变为成品；每一台收音机需在第一个工厂加工4小时，在第二个工厂装配试验15小时才变为成品。录音机与收音机每台厂内的每月储存成本分别为8元和15元。第一个工厂有12部制造机器，每部每天工作8小时，每月正常工作天数为25天，第二个工厂有7部装配试验设备，每部每天工作16小时，每月正常工作天数仍为25天。每部机器每小时的运转成本是：第一个工厂为18元，第二个工厂为15元。每台录音机的销售利润为20元，收音机为23元。依市场预测，次月的录音机与收音机的销售量估计分别为1500台和1000台。第四章minZ=P1d1+P2d2-+P3(6d3

32、-+5d4-)+P4d11+P5d5-+P6(6d3+5d4+)8X1+15X2+d1-d1+=0X1+d2-d2+=1500 2X1+4X2+d3-d3+=24002.5X1+1.5X2+d4-d4+=2800d1+d11-d11+=30X2+d5-d5+=1000X1,X2,di-,di+0 i=1,25,11s.t.四、四、应用举例应用举例第四章3：某唱片商店聘用5位全日工售货员和4位半日工售货员，他们的工作、工资情况如表：工作时数 /月/人销售量（张/时）工资（元/月）加班费（元/时）全日工16053004.5半日工8022002已知每售出一张唱片可获利1.5元。要求确定满足以下目标的服务计划：P1：月销售量达到5500张。P2：全日售货员总加班时间不超过100小时。P3：维持全体售货员充分就业，但对全日工要加倍照顾。P4：尽量减少加班时间，但全日工、半日工有所区别。四、四、应用举例应用举例第四章解；设x1,x2 分别为全日工.半日工售货员每月工作时数。)3()2(min324323212110ddPddPdPdPz0,100320800550025212121212123322211121ddddxxdddddxddxddxxiis.t.四、四、应用举例应用举例第四章作作 业业4.64.7