目标规划典型例题

1§6.4主要解题方法和典型例题分析题型I目标规划数学模型的建立当线性规划问题有多个目标需要满足时，就可以通过建立目标规划数学模型来描述。目标规划数学模型的建立步骤为：第一步，确定决策变量；第二步，确定各目标的优先因子；第三步，写出硬约束和软约束；第四步，确定目标函数。例6-1某公司生产甲、乙两种产品，分别经由I、II两个车间生产。已知除外购外，生产一件甲产品需要I车间加工4小时，II车间装配2小时，生产一件乙产品需I车间加工1小时，II车间装配3小时，这两种产品生产出来以后均需经过检验、销售等环节。已知每件甲产品的检验销售费用需40元，每件乙产品的检验销售费用需50元。I车间每月可利用的工时为150小时，每小时的费用为80元；II车间每月可利用的工时为200小时，每小时的费用为20元，估计下一年度平均每月可销售甲产品100台，乙产品80台。公司根据这些实际情况定出月度计划的目标如下：P1：检验和销售费用每月不超过6000元；P2：每月售出甲产品不少于100件；P3：I、II两车间的生产工时应该得到充分利用；P4：I车间加班时间不超过30小时；P5：每月乙产品的销售不少于80件。试确定该公司为完成上述目标应制定的月度生产计划，建立其目标规划模型。解：先建立目标规划的数学模型。设x1为每月计划生产的甲产品件数，x2为每月生产的乙产品的件数。根据题目中给出的优先等级条件，有以下目标及约束：（1）检验及销售费用目标及约束11211min()40506000dxxdd；（2）每月甲产品的销售目标及约束2122min()100dxdd；（3）I、II两车间工时利用情况目标及约束I车间31233min()4150dxxdd，II车间41244min()3200dxxdd（4）I车间加班时间目标及约束5355min()30dddd2（5）每月乙产品销售目标及约束6266min()80dxdd根据优先等级层次，确定优先因子和权系数，得出目标规划的数学模型如下：1122334455612111221233124435526612min(4)405060001004150..32003080,0;,0;1,,6iiZpdpdpddpdpdxxddxddxxddstxxdddddxddxxddi例6-2有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应量ai、销地Bj(j=1,2,3,4)的需要量bj、各产销地之间的单位物资运费Cij如表5-1所示。表中，ai和bj的单位为吨，Cij的单位为元/吨。编制调运方案时要求按照相应的优先级依次考虑下列六个目标：P1：B4是重点保证单位，其需要量应尽可能全部满足；P2：A3向B1提供的物资不少于100吨；P3：每个销地得到的物资数量不少于其需要量的80%；P4：实际的总运费不超过当不考虑P1至P6各目标时的最小总运费的110%；P5：因路况原因，尽量避免安排A2的物资运往B4；P6：对B1和B3的供应率要尽可能相同；试建立该问题的目标规划模型。表6-1BjcijAiB1B2B3B4aiA15267300A23546200A34523400bj200100450250解：设xij为从Ai运往Bj的运输量，首先求出当不考虑P1至P6各目标时的最小总运费为2950元。在各级目标中没有涉及到供应量，因此供应量构成硬约束：400200300343332312423222114131211xxxxxxxxxxxx3根据各优先级目标，可写出相应的目标及目标约束。P1：B4是重点保证单位，其需要量应尽可能全部满足250min113424141ddxxxdP2：A3向B1提供的物资不少于100吨100min22312ddxdP3：每个销地得到的物资数量不少于其需要量的80%36080160)min(553323134432221233312111543ddxxxddxxxddxxxdddP4：实际的总运费不超过当不考虑P1至P6各目标时的最小总运费的110%。3166416%1102950minijijijddxcdP5：因路况原因，尽量避免安排A2的物资运往B40min77247ddxdP6：对B1和B3的供应率要尽可能相同0450200)min(8833231331211188ddxxxxxxdd综上所述，将该问题列成优先目标规划模型：40)(300200)(0324536080160100250400200300min,min,minmin,min,min883323133121117724316641553323134432221233312111223111342414343332312423222114131211886756454332211ddxxxxxxddxddxcddxxxddxxxddxxxddxddxxxxxxxxxxxxxxxddzdzdzdddzdzdzijijij题型II目标规划的图解法目标规划的图解法就是通过图形来确定所给目标规划的满意解，虽然比较直观，但因为是平面图，所以最多只能求解包含两个决策变量的目标规划问题。其解题步骤是：第一步，建立直角坐标系，作出硬约束的限制区域；第二步，作出其他约束条件当偏差变量为0时的图形，确定其它各约束条件的限制区域；第三步，结合决策变量的可行范围，按优先因子考察各偏差变量的变化对目标函数的影响，确定尽可能满足目标的满意解。例6-3用图解法找出以下目标规划问题的满意解。11122312111222123312min()(2)10503520..86100,,,0,1,2,3iiZpddpddxxddxxddstxxddxxddi解：第一步，因为本题没有硬约束，所以先作出偏差变量为0时，各目标约束所确定的直线，如图5-1所示。第二步，按优先因子考虑各偏差变量的变化对目标函数的影响，确定约束条件所限定的x1,x2范围。要满足11min()dd，只能在CD射线上取得满意解；显5然，在CD射线上，111()0pdd。其次，在CD射线上使223(2)pdd达到极小点的只能是C点。第三步，确定满意解。由图6-1可知，满意解为**1250,0xx例6-4用图解法找出以下目标规划问题的满意解。1212311211122212122min210101262.4..28,,,0,1,2iZpdpdpdxxddxxddstxxxxddi解：第一步，首先作出硬约束等式直线AB：8221xx第二步，再作出偏差变量为0时，各目标约束所确定的直线DI和CH，如图6-2所示。第三步，按优先因子考虑各偏差变量的变化对目标函数的影响，确定约束条件所限定的x1,x2范围。要满足22min()dd，并且满足硬约束1228xx所在范围，只能在GC线段上取得满意解；而要满足1mind，满意解又只能是在CE线段上。第三步，确定满意解。由图6-2可得满意解为C(0，5.2)和E（0.6，4.7）连线上任一点。x1D1d1dC502d2d100/8BA20/33d3d04F100/6Ex2-53x1+5x2=208x1+6x2=100x1-10x2=50图6-16题型III目标规划的单纯形法例6-5用单纯形法求以下目标规划问题的满意解。121221121112221212min210101262.4..28,,,0,1,2iiZpdpdpdxxddxxddstxxxxddi解：第一步，将原规划化为标准型1222112111222123123min()210101262.4..28,,,,0,1,2iiZpddpdxxddxxddstxxxxxxddi第二步，取123,,ddx为初始基变量，列初始单纯形表，如表6-2所示。表6-2cj000P20P1P1iiikbaCBXBbx1x2x31d1d2d2dP21d101[2]01-10010/2P12d62.410120001-162.4/120x3821100008/10DCB2dEFGA2dHI1d1dx2x1x1+2x2=1010x1+12x2=62.42x1+x2=8图6-27cj-zjP1-10-1200002P2-1-200100第三步，取k=1，检查检验数的P1行的负数，取最小者-12对应的变量x2为换入变量，并用最小比值原则确定换出变量为1d，见表6-3。表6-3cj000P20P1P1iiikbaCBXBbx1x2x31d1d2d2d0x251/2101/2-1/200-P12d2.4400-6[6]1-12.4/60x333/201-1/21/2003/(1/2)cj-zjP1-4006-602P20001000第四步，还是取k=1，检查检验数的P1行的负数，取最小值-6对应的变量1d为换入变量，并用最小比值规则确定换出变量2d，见表6-4。表6-4cj000P20P1P1iiikbaCBXBbx1x2x31d1d2d2d0x25.25/610001/12-1/12-01d0.42/300-111/6-1/60x32.87/60100-1/121/12cj-zjP10000011P20001000第五步，检查检验数的P1行，P2行，都没有负数了，故得到满意解*(0,5.2)Tx。且因为非基变量x1的检验数为0，所以存在多重解。例6-6用单纯形法求解下列目标规划问题。112243312111221233124412min(23)104..535612,,,0,1,2,3,4iiZpddpdpdxxddxddstxxddxxddxxddi解：第一步：该问题已经化为标准形，以1d，2d，3d，4d为基变量，建立8初始单纯形表，如表6-5所示。表6-5初始单纯性表Bxb1x2x1d1d2d2d3d3d4d4d1d10111-10000002d4[1]0001-100003d565300001-1004d12110000001-1cj-zjP10002030000P20000000001P3-5-300000100第二步：在表6-5中，检验数矩阵中第一列、第二列均有负数，因此此表对应的解不是满意解，需要进行迭代。以1x为进基变量，2d为出基变量，进行基变换运算，结果如表6-6所示。表6-6第一次迭代表Bxb1x2x1d1d2d2d3d3d4d4d1d60[1]1-1-1100001x410001-100003d360300-551-1004d80100-11001-1cj-zjP10002030000P20000000001P30-3005-50100第三步：在表5-6中，检验数矩阵中第二列仍有负数，以2x为进基变量，1d