《目标规划典型例题》由会员分享，可在线阅读，更多相关《目标规划典型例题（9页珍藏版）》请在金锄头文库上搜索。
1、 主要解题方法和典型例题分析题型I目标规划数学模型的建立当线性规划问题有多个目标需要满足时， 就可以通过建立目标规划数学模型 来描述。目标规划数学模型的建立步骤为：第一步，确定决策变量；第二步，确 定各目标的优先因子；第三步，写出硬约束和软约束；第四步，确定目标函数。例6-1某公司生产甲、乙两种产品，分别经由I、II两个车间生产。已知除 外购外，生产一件甲产品需要I车间加工4小时，II车间装配2小时，生产一 件乙产品需I车间加工1小时，II车间装配3小时，这两种产品生产出来以后 均需经过检验、销售等环节。已知每件甲产品的检验销售费用需40元，每件乙产品的检验销售费用需50元。I车间每月可利用的
2、工时为150小时，每小时的 费用为80元；II车间每月可利用的工时为200小时，每小时的费用为20元， 估计下一年度平均每月可销售甲产品 100台，乙产品80台。公司根据这些实际 情况定出月度计划的目标如下：P1:检验和销售费用每月不超过 6000元；P2：每月售出甲产品不少于100件；P3： I、II两车间的生产工时应该得到充分利用；P4： I车间加班时间不超过30小时；P5：每月乙产品白销售不少于80件。试确定该公司为完成上述目标应制定的月度生产计划，建立其目标规划模型。解：先建立目标规划的数学模型。设 X1为每月计划生产的甲产品件数，X2为 每月生产的乙产品的件数。根据题目中给出的优先等
3、级条件，有以下目标及约束：(1)检验及销售费用目标及约束min(d1)40x1 50x2 d1 d16000(3)每月甲产品的销售目标及约束min(d2)X1 d2 d2100I、II两车间工时利用情况目标及约束I车间4x1min(d3)II 车间min(d4)X2 d3 d3 150X1 3x2 d4 d200(4) I车间加班时间目标及约束min(d5)d3 d5 d530(5)每月乙产品销售目标及约束min(d6)x2 d6 d680根据优先等级层次，确定优先因子和权系数，得出目标规划的数学模型如下：min Z pidip2d2 Ps(4d3 CI4) p4d5 p5d640x1 50x
4、2 d1 d16000x1 d2 d21004x1 x2 d3 d3150s.tx1 3x2 d4 d4 200d3 d5 d530x2 d6 d680xi,x2 0；di ,di 0;i 1,L ,6例6-2有三个产地向四个销地供应物资。产地 A(i =1,2,3)的供应量a、销 地B(j =1,2,3,4)的需要量b、各产销地之间的单位物资运费 G如表5-1所示。 表中，a和bj的单位为吨，G的单位为元/吨。编制调运方案时要求按照相应的 优先级依次考虑下列六个目标：P1: B4是重点保证单位，其需要量应尽可能全部满足；P2: A向B提供的物资不少于100吨；P3:每个销地得到的物资数量不少
5、于其需要量的80%P4：实际的总运费不超过当不考虑 P1至P6各目标时的最小总运费的110%P5:因路况原因，尽量避免安排 4的物资运往P6: Xt B和R的供应率要尽可能相同；试建立该问题的目标规划模型。表6-1:jBBB3B4aA15267300A23546200A34523400bj200100450250解：设xij为从A运往Bj的运输量，首先求出当不考虑 P1至P6各目标时的最小 总运费为2950元。在各级目标中没有涉及到供应量，因此供应量构成硬约束：x 11x12x13Xi4300x21x22x 23x24200x31x32x 33x34400根据各优先级目标，可写出相应的目标及目
6、标约束。P1: B4是重点保证单位，其需要量应尽可能全部满足min diXi4 X24 X34 didi250P2: A向B提供的物资不少于100吨min d2x31 d2d2100P3:每个销地得到的物资数量不少于其需要量的80%min( d3X11X21X12X22X13X23d4d5 )X31d3X32 d4X33 d5d3 160 d4 80d5360110%P4：实际的总运费不超过当不考虑 P1至P6各目标时的最小总运费的min d634Cj x j d6 d62950 110%i 1 j 1P5:因路况原因，尽量避免安排 A2的物资运往Bmin d7X 24 d? d70P6:又t
7、 B和R的供应率要尽可能相同min( d8d8 )d8X11X21X31 X13 X23 X33200450综上所述，将该问题列成优先目标规划模型:min z1d1 ,minz2d2,min z3d3d4d5min z4d6 ,minz5d7,min z6d8d8X11x12X13X14300X21X22X23X24200X31X32X33X34400X14x24x34d1d1250X31d2d2100X11X21X31d3d3160x12x22x32d4d480X13x23x33d5d53603 4Cij xj d6d63245i 1 j 1X24 dy dy 0200(X11 X21 X3
8、1) (X13 X23 X33 ) d8 d80300题型II目标规划的图解法目标规划的图解法就是通过图形来确定所给目标规划的满意解，虽然比较直观，但因为是平面图，所以最多只能求解包含两个决策变量的目标规划问题。其解题步骤是：第一步，建立直角坐标系，作出硬约束的限制区域；第二步，作出 其他约束条件当偏差变量为0时的图形，确定其它各约束条件的限制区域；第三 步，结合决策变量的可行范围，按优先因子考察各偏差变量的变化对目标函数的 影响，确定尽可能满足目标的满意解。例6-3用图解法找出以下目标规划问题的满意解。min Z P1(d1 d1) P2(2d2 d3)X1 10x2 d1 d1503X1
9、5x2 d2 d220s.t8X1 6x2 d3 d3100X1,X2,di,di0,i 1,2,3解：第一步，因为本题没有硬约束，所以先作出偏差变量为0时，各目标约束所确定的直线，如图5-1所示。第二步，按优先因子考虑各偏差变量的变化对目标函数的影响，确定约束条件所限定的X1,X2范围。要满足min(d1 d1 ),只能在CD射线上取得满意解；显 然，在CD射线上，p1(d14)0o其次，在CDM线上使P2(2d2 d3)达到极小 点的只能是C点。第二步，确定潴意解。由图6-1可知，潴意解为xi 50, X2 08x1+6x2=100图6-1例6-4用图解法找出以下目标规划问题的满意解。mi
10、n Z p1d2 p1d2 p3dl x1 2x2 d1 d1 10 10x1 12x2 d2 d2 62.4 s.t 2x, x2 8 x1,x2,di ,d20,i 1,2解：第一步，首先作出硬约束等式直线 AB: 2xi x2 8第二步，再作出偏差变量为0时，各目标约束所确定的直线 DI和CH,如图 6-2所示。第三步，按优先因子考虑各偏差变量的变化对目标函数的影响， 确定约束条 件所限定的Xi,X2范围。要满足min(d2 d2),并且满足硬约束2x x2 8所在范 围，只能在G饿段上取得满意解；而要满足min d1 ,满意解又只能是在CE线段 上。第三步，确定满意解。由图6-2可得满
11、意解为C(0,和E(,)连线上任一点X2*图6-2题型III目标规划的单纯形法例6-5用单纯形法求以下目标规划问题的满意解min Z p1d2 p1d2p2dlx1 2x2 d1 d11010x1 12x2 d2 d2 62.4s.t24 x2 8x1,x2,di ,di0,i 1,2解：第一步，将原规划化为标准型min Z p1(d2 d2) p2dl x1 2x2 d1 d11010x1 12x2 d2 d262.4s.t 2x1 x2 x3 8“心心吊0,i 1,2第二步，取d1 ,d2,R为初始基变量，列初始单纯形表，如表 6-2所示表6-2Cj000P20PiPi旦aikiCbXbb
12、xix2x3d1d1d2d2P2d1101201-10010/2Pid210120001-1120x3821100008/1Cj-ZjPi-iO-i2OOOO2F2-i-2OOiOO第三步，取k=1,检查检验数的Pi行的负数，取最小者-12对应的变量X2为 换入变量，并用最小比值原则确定换出变量为 di ,见表6-3。表6-3CjOOOP2OPiPibiaikCbXbbxix2x3didid2d2Ox25i/2iOi/2-i/2OO-Pid24OO-66i-i6Ox333/2Oi-i/2i/2OO3/(i/2)Cj-ZjPi-4OO6-6O2P2OOOiOOO第四步，还是取k=1,检查检验数的
13、Pi行的负数，取最小值-6对应的变量di为换入变量，并用最小比值规则确定换出变量d2 ,见表6-4。表6-4CjOOOP2OPiPibiaikCbXbbxix2x3didid2d2Ox25/6iOOOi/i2-i/i2-Odi2/3OO-iii/6-i/6Ox37/6OiOO-i/i2i/i2Cj-ZjPiOOOOOiiP2OOOiOOO第五步，检查检验数的Pi行，R行，都没有负数了，故得到满意解x* (0,5.2)t且因为非基变量Xi的检验数为0,所以存在多重解。例6-6用单纯形法求解下列目标规划问题。min Z pi (2di 3d2) p2d4 p3d3xi x2 didii0xi d2 d24s.t5xi 3x2 d3 d356xi x2 d4 d4i2为？240,i i,2,3,4解：第一步：该问题
