目标规划典型例题.docx

《目标规划典型例题.docx》由会员分享，可在线阅读，更多相关《目标规划典型例题.docx（9页珍藏版）》请在三一文库上搜索。

1、主要解题方法和典型例题分析题型I目标规划数学模型的建立当线性规划问题有多个目标需要满足时，就可以通过建立目标规划数学模型来描述。目标规划数学模型的建立步骤为：第一步，确定决策变量；第二步，确定各目标的优先因子；第三步，写出硬约束和软约束；第四步，确定目标函数。例6-1某公司生产甲、乙两种产品，分别经由I、II两个车间生产。已知除外购外，生产一件甲产品需要I车间加工4小时，II车间装配2小时，生产一件乙产品需I车间加工1小时，II车间装配3小时，这两种产品生产出来以后均需经过检验、销售等环节。已知每件甲产品的检验销售费用需40元，每件乙产品的检验销售费用需50元。I车间每月可利用的工时为150小

2、时，每小时的费用为80元；II车间每月可利用的工时为200小时，每小时的费用为20元，估计下一年度平均每月可销售甲产品100台，乙产品80台。公司根据这些实际情况定出月度计划的目标如下：P1:检验和销售费用每月不超过6000元;P2：每月售出甲产品不少于100件；P3：I、II两车间的生产工时应该得到充分利用；P4：I车间加班时间不超过30小时；P5：每月乙产品的销售不少于80件。试确定该公司为完成上述目标应制定的月度生产计划，建立其目标规划模型。解：先建立目标规划的数学模型。设X1为每月计划生产的甲产品件数，X2为每月生产的乙产品的件数。根据题目中给出的优先等级条件，有以下目标及约束：(1)

3、检验及销售费用目标及约束min(d1)40X1 50X2 d1d16000(2)每月甲产品的销售目标及约束min(d2)X1d2 d2100(3)I、II两车间工时利用情况目标及约束I车间min(d3), II 车间4x1 x2 d3 d3 150min(d4) x1 3x2 d4 d4200(4)I车间加班时间目标及约束d3min(d5) d5 d530(5)每月乙产品销售目标及约束min(d6)x2 d6 d680根据优先等级层次，确定优先因子和权系数，得出目标规划的数学模型如下minZpap2d2P3(4d3d4)p4d5p5d640x150x2d1d16000x1d2d21004x1x

4、2d3d3150s.tx13x2d4d4200d3d5d530x2d6d680X,x20;di,di0;i1,L,6例6-2有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应量a、销地Bj(j=1,2,3,4)的需要量bj、各产销地之间的单位物资运费Cj如表5-1所示。表中，ai和bj的单位为吨，Cij的单位为元/吨。编制调运方案时要求按照相应的优先级依次考虑下列六个目标：P1:B4是重点保证单位，其需要量应尽可能全部满足；P2:A3向B1提供的物资不少于100吨；P3:每个销地得到的物资数量不少于其需要量的80%;P4：实际的总运费不超过当不考虑P1至P6各目标时的最小总运费的1

5、10%;P5:因路况原因，尽量避免安排A2的物资运往B4；P6:XBB和B3的供应率要尽可能相同；试建立该问题的目标规划模型。表6-1AiBiB2B3B4aiA15267300A23546200A34523400bj200100450250解：设xij为从Ai运往Bj的运输量，首先求出当不考虑P1至P6各目标时的最小总运费为2950元。在各级目标中没有涉及到供应量，因此供应量构成硬约束:XiiXi2Xi3Xi4300x21x22x23x24200x31x32x33x34400根据各优先级目标，可写出相应的目标及目标约束。P1:B4是重点保证单位，其需要量应尽可能全部满足mind1x14x24x

6、34didi250P2:A3向Bi提供的物资不少于100吨mind2X3id2d2100P3:每个销地得到的物资数量不少于其需要量的80%min( d3X11X21X12X22x13X23d4d5 )X31d3X32 d4X33 d5d3160d480d5360P4：实际的总运费不超过当不考虑P1至P6各目标时的最小总运费的110%。mind634Cjxjd6d62950110%i1j1P5：因路况原因，尽量避免安排A2的物资运往B4mind7X24d7d70P6:对Bi和B3的供应率要尽可能相同min(d8d8)X11 X21 X31200X13 X23 X33450d8d8综上所述，将该问

7、题列成优先目标规划模型:minz1d1,minz2d2,minz3d3d4d5minz4d6,minz5d7,minz6d8d8Xiix12Xl3Xl4300X21X22X23X24200X31X32X33X34400X14X24X34didi250X31d2d2100XiiX21X31d3d3160x12X22X32d4d480Xi3X23X33d5d536034CijXijd6d63245i1j1X24d7d70200(XiiX21X31)(X13X23X33)d8d80300题型II目标规划的图解法目标规划的图解法就是通过图形来确定所给目标规划的满意解，虽然比较直观，但因为是平面图，所以

8、最多只能求解包含两个决策变量的目标规划问题。其解题步骤是：第一步，建立直角坐标系，作出硬约束的限制区域；第二步，作出其他约束条件当偏差变量为0时的图形，确定其它各约束条件的限制区域；第三步，结合决策变量的可行范围，按优先因子考察各偏差变量的变化对目标函数的影响，确定尽可能满足目标的满意解。例6-3用图解法找出以下目标规划问题的满意解。minZPi(didi)PzQd?da)X110x2d1d1503X15x2d2d220s.t8x16x2d3d3100Xi,X2,di,di0,i1,2,3解：第一步，因为本题没有硬约束，所以先作出偏差变量为0时，各目标约束所确定的直线，如图5-1所示。第二步，

9、按优先因子考虑各偏差变量的变化对目标函数的影响，确定约束条件所限定的X1,X2范围。要满足min(didi),只能在CD射线上取得满意解；显然，在CD射线上，5(&di)0o其次，在CD射线上使P2(2d2d3)达到极小点的只能是C点。第二步，确定满意解。由图6-1可知，满意解为xi50,x208x1+6x2=100图6-1例6-4用图解法找出以下目标规划问题的满意解。minZp1d2p1d2Psd1x12x2d1d11010x112x2d2d262.4s.t24x28x1,x2,di,d20,i1,2解：第一步，首先作出硬约束等式直线AB:2x1x28第二步，再作出偏差变量为0时，各目标约束

10、所确定的直线DI和CH,如图6-2所示。第三步，按优先因子考虑各偏差变量的变化对目标函数的影响，确定约束条件所限定的x1,x2范围。要满足min(d2d?),并且满足硬约束2x1x28所在范围，只能在GC线段上取得满意解；而要满足mind1,满意解又只能是在CE线段上。第三步，确定满意解。由图6-2可得满意解为C(0,和E(,)连线上任一点图6-2题型III目标规划的单纯形法例6-5用单纯形法求以下目标规划问题的满意解minZp1d2p1d2p2d1x12x2d1d11010x112x2d2s.t2x1x2d262.48x1,x2,di,di0,i1,2解：第一步，将原规划化为标准型minZp

11、1(d2d2)p2d1x12x2d1d11010x112x2d2d262.4s.t2%x2x38x1,x2,x3,di,di0,i1,2第二步，取d1,d2,x3为初始基变量，列初始单纯形表，如表6-2所示表6-2c000P20P1P1旦aikiCbXBbx1x2x3d1d1d2d2P2d1101201-10010/2P1d210120001-1120x3821100008/1Cj-zjPi-io-i200002P2-i-200i00第三步，取k=1,检查检验数的Pi行的负数，取最小者-12对应的变量X2为换入变量，并用最小比值原则确定换出变量为di,见表6-3。表6-3Cj000P20PiP

12、ibiaikCbXbbxix2x3didid2d20x25I/2i0I/2-I/200-Pid2400-66i-i60x333/20i-I/2I/2003/(i/2)cj-ziPi-4006-602P2000i000第四步，还是取k=1,检查检验数的Pi行的负数，取最小值-6对应的变量di为换入变量，并用最小比值规则确定换出变量d2,见表6-4。表6-4C000P20PiPibiaikCbXbbxix2x3didid2d20x25/6i000i/i2-i/i2-0di2/300-iiI/6-I/60x37/60i00-i/i2i/i2Cj-zjPi00000iiP2000i000第五步，检查检

13、验数的Pi行，P2行，都没有负数了，故得到满意解x*(0,5.2)T且因为非基变量xi的检验数为0,所以存在多重解。例6-6用单纯形法求解下列目标规划问题。minZpi(2di3d2)p2d4p3d3xix2didiI0xid2d24s.t5xi3x2d3d356xix2d4d4I2为？240,ii,2,3,4解：第一步：该问题已经化为标准形，以di,d2,d3,d4为基变量，建立初始单纯形表，如表6-5所示。表6-5初始单纯性表XBbXiX2d1d1d2d2d3d3d4d4di10111-1000000d2410001-10000d3565300001-100d412110000001-1C

14、j-ZjPi0002030000P20000000001P3-5-300000100第二步：在表6-5中，检验数矩阵中第一列、第二列均有负数，因此此表对应的解不是满意解，需要进行迭代。以为进基变量，d2为出基变量，进行基变换运算，结果如表6-6所示。表6-6第一次迭代表XbbX1X2d1d1d2d2d3d3d4d4d16011-1-110000X1410001-10000d3360300-551-100d480100-11001-1Cj-zjP10002030000P20000000001P30-3005-50100第三步：在表5-6中，检验数矩阵中第二列仍有负数，以X2为进基变量，di为出基

15、变量，进行基变换运算，结果如表6-7所示。表6-7第二次迭代表XBbX1X2d1d1d2d2d3d3d4d4X26011-1-110000Xi410001-10000d31800-33-221-100d4200-1100001-1cj-zjPi0002030000P20000000001P3003-32-20100第三步：在表6-7中，检验数矩阵中每一列第一个非零元素均为非负数，因此此表所对应的解为满意解。标 min Z1 p1(2dl 3d2)满意解为(Xi,X2)(4,6),目标达到情况是：第一级目0达到最优，第二级目标minZ2p2d40达到最优,第三级目标minZ3p3d318,没有达到最优。