《多目标规划(2)》由会员分享，可在线阅读，更多相关《多目标规划(2)（61页珍藏版）》请在金锄头文库上搜索。
1、多目标规划（2）,单纯形解法,1、多目标规划的单纯形算法,多目标规划问题与线性规划问题相似，也可以用单纯形算法求解。 但是要注意： 在比较检验数大小时，要先比较较高级别的系数，再比较较低级别的系数。,例1,一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：设生产甲产品X1件，乙产品X2件，则应用线性规划，建立模型如下：MAX Z=6X1+4X22X1+3X2 0用单纯形法求得最优解=（20，20）；最优值=200（百元）,问题提出,该厂提出如下
2、目标（1）利润达到280百元； （2）钢材不超过100吨，工时不超过120小时；如何安排生产？,解：引进级别系数 P1：（1）利润达到280百元； P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）,建立多目标规划数学模型： 目标函数：Min S=P1d1-+P2(5d2+d3+) 约束方程：6X1+4X2+ d1- d1+=2802X1+3X2+ d2- d2+=1004X1+2X2+ d3- d3+=120X1,X2,di-, di+ 0(i=1,2,3),解：先化成标准型 目标函数：Max S=-P1d1-P2(5d2+d3+) 约束方程：6X1+4X2+ d1-
3、d1+=2802X1+3X2+ d2- d2+=1004X1+2X2+ d3- d3+=120X1,X2,di-, di+ 0(i=1,2,3),初始单纯形表,首先满足第一目标P1进基变量X1，出基变量d3- 主元（4）,主元运算：第三行除以4,主元运算：第一行加上第三行（-6）倍,主元运算：第二行加上第三行（-2）倍,重新计算检验数,第二行除以2,第一行加上第二行（-1）,第三行加上第二行（-1/2）,计算检验数,计算检验数,第一行乘上4/5,第三行加上第一行（3/8）,计算检验数,最后变量 d1-的检验数为-P1+(4/5)P2由于假定P1P2，所以此检验数也小于零。,该问题的最优方案为生
4、产A产品44个单位，B产品4个单位，利润为280百元。此时，原料正好用了100吨，工时比原计划超了64小时。,例2,设某工厂生产甲、乙两种产品，都要经过两道工序，有关资料如下表。假如工序1，2都允许加班，使得利润不少于1000元作为目标。又以：第1，2工序的加班工时之和尽可能在160之内为第一目标；产品乙的生产量必须严格控制在70公斤之内为第二目标；该厂的利润越高越好为第三目标；尽量减少工序1，2加班工时为第四目标.试问：在上述条件下，该厂应如何生产？,解：设X1，X2为甲，乙两种产品的生产公斤数， d1-， d1+分别为低于或超过利润1000元的偏差 d2-， d2+分别为第1道工序剩余和加
5、班的工时数 d3-， d3+分别为第2道工序剩余和加班的工时数 d4-， d4+为加班工时之和低于或超过160工时数 由于产品X2必须严格控制在70公斤之内为第一目标，则可取d5-为实际公斤数不到70的偏差，且 d5+=0。,建立多目标规划模型 目标函数：Min Z=P1d4+ P2d5- + P3d1-+ P4( d2+d3+) 约束方程： 6X1+4X2+ d1- d1+=10002X1+ X2+ d2- d2+=100X1+ X2+ d3- d3+=80d2+ + d3+ + d4 -d4+=160X2 + d5 =70X1,X2,di-, di+ , d5 0(i=1,2,3,4),化
6、为标准型 目标函数：Max s= -P1d4+-P2d5- - P3d1- P4( d2+d3+) 约束方程：6X1+4X2+ d1- d1+=10002X1+ X2+ d2- d2+=100X1+ X2+ d3- d3+=80d2+ + d3+ + d4 d4+=160X2 + d5 =70X1,X2,di-, di+ , d5 0(i=1,2,3,4),到目前为止，已经不能再进行下去， （2）（1）否则会破坏已经满足的条件。 该题的解答：X1=200/3 ，X2=70，d1- =320， d2+=103， d3+=57 d4+= d4- = d5- =0 即该厂生产方案：生产产品甲200/
7、3公斤，产品乙70公斤，第1道工序加班103工时，第2道工序加班57工时，才能获利 1000- d1- =1000-320=680元。,应用举例,例1 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： (1) 不超过年工资总额60000元； (2) 每级的人数不超过定编规定的人数； (3) ，级的升级面尽可能达到现有人数的20%，且无越级提升； 级不足编制的人数可录用新职工，又级职工中有10%要退休。有关资料汇总于表4-8中，问该领导应如何拟订一个满意的方案。,应用举例,解：设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为： P1不超过年工资总
8、额60000元； P2每级的人数不超过定编规定的人数； P3、级的升级面尽可能达到现有人数的20%。 先分别建立各目标约束。 年工资总额不超过60000元2000(10100.1+x1)+1500(12x1+x2)+1000(15x2+x3)+d1d1+ =60000,应用举例,每级的人数不超过定编规定的人数： 对级有 10(1 0.1)+x1+d2d2+=12 对级有 12 x1+x2+d3d3+=15 对级有 15 x2+x3+d4 d4+=15 ，级的升级面不大于现有人数的20%，但尽可能多提： 对级有 x1+d5 d5+=120.2 对级有 x2+d6 d6+=150.2 目标函数：m
9、in z=P1d1+P2(d2+d3+d4+)+P3(d5+d6) 以上目标规划可用单纯形法求解，得到多重解。将这些解汇总于表4-9，单位领导再按具体情况，从表4-9中选出执行方案。,应用举例,表4-9,应用举例,例7 已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表4-10。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优先等级： P1B4是重点保证单位，必须全部满足其需要； P2A3向B1提供的产量不少于100； P3每个销地的供应量不小于其需要量的80%； P4所定调运方案的总运费不超过最小运费调运方案的10%； P5因路段的问题，尽量避免安排将A2的
10、产品往B4； P6给B1和B3的供应率要相同； P7力求总运费最省。试求满意的调运方案。,应用举例,解 ：表上作业法求得最小运费的调运方案见表4-11。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。,表4-11,应用举例,供应约束 x11+x12+x13+x14300 x21+x22+x23+x24200 x31+x32+x33+x34400 需求约束： x11+x21+x31+d1 d1+=200 x12+x22+x32+d2 d2+=100 x13+x23+x33+d3 d3+=450 x14+x24+x34+d4 d4+=250 A3向B1提供的产品量不少于1
11、00 x31+d5 d5+=100,应用举例,每个销地的供应量不小于其需要量的80% x11+x21+x31+d6d6+=2000.8 x12+x22+x32+d7 d7+=1000.8 x13+x23+x33+d8 d8+=4500.8 x14+x24+x34+d9 d9+=2500.8 调运方案的总运费不超过最小运费调运方案的10%,应用举例,因路段的问题，尽量避免安排将A2的产品运往B4 x24+d11d11+=0 给B1和B3的供应率要相同 (x11+x21+x31)(200/450)(x13+x23+x33)+d12 d12+=0 力求总运费最省目标函数为：,应用举例,计算结果，得到满意调运方案见表4-12。,总运费为 3360元,
