第4章目标规划-第3-5节

第3节解目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定：•(1)因目标规划问题的目标函数都是求最小化，所以以cj-zj≥0，j=1,2,…，n为最优准则。•(2)因非基变量的检验数中含有不同等级的优先因子，即KknjPazckkjjj,,2,1;,,2,1•因P1P2…PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数α1j的正、负。若α1j=0，这时此检验数的正、负就决定于P2的系数α2j的正、负，下面可依此类推。解目标规划问题的单纯形法的计算步骤：•(1)建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。•(2)检查该行中是否存在负数，且对应的前k-1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。•(3)按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。•(4)按单纯形法进行基变换运算，建立新的计算表，返回(2)。•(5)当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到(2)。例4试用单纯形法来求解例2。将例2的数学模型化为标准型：3,2,1,0,,,,561081020112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss满足约束条件：目标函数：①取xs，d1-，d2-，d3-为初始基变量，列初始单纯形表，见表4-1。cjP1P2P3P4CBXBbx1x2xsd1-d1+d2-d2+d3-d3+θP2P3xsd1-d2-d3-110105621181-1[2]1011-11-11-111/1/10/256/10cj-zjP1P2P3-1-8-2-10121②取k=1，检查P1行的检验数，因该行无负检验数，故转(5)。③因k(=1)＜K(=3)，置k=k+1=2，返回到(2)。④当k=2时,查出P2行检验数中有-1、-2；取min(-1,-2)=-2。它对应的变量x2为换入变量，转入(3)。⑤在表4-1上计算最小比值它对应的变量d2-为换出变量，转入(4)210)1056,210.0,111min(⑥即进行基变换运算，计算结果见表4-2cjP1P2P3P4CBXBbx1x2xsd1-d1+d2-d2+d3-d3+θP3xsd1-x2-d3-65563/23/21/2[3]111-1-1/21/21/2-51/2-1/2-1/251-1410/3106/3cj-zjP1P2P3-31151-51表4-3返回到(2)。依此类推，直至得到最终表为止。见表4-3。cjP1P2P3P4CBXBbx1x2xsd1-d1+d2-d2+d3-d3+θxsd1-x2-x1-32421111-1234/3-5/3-2-3-4/35/3-1/2-1/2-1/61/31/21/21/6-1/36424cj-zjP1P2P3-1-8-2-101111表4-3所示的解x1*=2，x2*=4为例1的满意解。此解相当于图4-1的G点。检查表4-3的检验数行，发现非基变量d3+的检验数为0，这表示存在多重解。在表4-3中以非基变量d3+为换入变量，d1-为换出变量，经迭代得到表4-4。cjP1P2P3P4CBXBbx1x2xsd1-d1+d2-d2+d3-d3+θxsd3+x2x11410/310/3111-12-1/32/31-21/3-2/3-161/31/31-6-1/3-1/3-11cj-zjP1P2P31111由表4-4得到解x1*=10/3，x2*=10/3，此解相当于图4-1的D点，G、D两点的凸线性组合都是例1的满意解第4节灵敏度分析目标规划的灵敏度分析方法与线性规划相似，这里除分析各项系数的变化外，还有优先因子的变化问题，下面举例说明。•改变目标优先等级的分析。例5已知目标规划问题4,3,2,1,0,,,125635410)32(min214421332122111214332211iddxxddxxddxxddxddxxdPdPddPzii满足约束条件：目标函数：•在得到最终表后，见表4-5。•目标函数的优先等级变化为：•(1)minz=P1(2d1++32+)+P2d4++P3-•(2)minz=P1d3-+P2(2d1++3d3+)+P3d4+•试分析原解有什么变化。表4-5cj2P13P1P2P3θCBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2x1d3-d4-6418211111-3-1-1-231-11-21-121-11-1cj-zjP1P2P332-323-211•解分析(1)，实际是将原目标函数中d4+，d3-的优先因子对换了一下。这时将表4-5的检验数中的P2、P3行和cj行的P2、P3对换即可。这时可见原解仍满足最优解条件。•分析(2)，将变化了的优先等级直接反映到表4-5上。再计算检验数，得表4-6。然后进行迭代，直到求得新的满意解为止。从表4-7中得到新的满意解x1*=4，x2*=12。表4-6cj2P13P1P2P3θCBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+x2x1d3-d4-6418211111-3-1-1-231-11-21-121-11-1cj-zjP1P2P332-323-211第5节应用举例•例6某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：•(1)不超过年工资总额60000元；•(2)每级的人数不超过定编规定的人数；•(3)Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升；•(4)Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。•有关资料汇总于表4-8中，问该领导应如何拟订一个满意的方案。表4-8等级工资额(元/年)现有人数编制人数ⅠⅡⅢ200015001000101215121515合计3742•解设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为：•P1——不超过年工资总额60000元；•P2——每级的人数不超过定编规定的人数；•P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。先分别建立各目标约束。年工资总额不超过60000元•2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1—-d1+=60000•每级的人数不超过定编规定的人数：•对Ⅰ级有10(1-0.1)+x1+d2-—d2+=12•对Ⅱ级有12-x1+x2+d3-—d3+=15•对Ⅲ级有15-x2+x3+d4-—d4+=15•Ⅱ，Ⅲ级的升级面不大于现有人数的20%，但尽可能多提；•对Ⅱ级有x1+d5-—d5+=12×0.2•对Ⅲ级有x2+d6-—d6+=15×0.2•目标函数：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)•以上目标规划模型可用单纯形法求解，得到多重解。现将这些解汇总于表4-9，这单位的领导再按具体情况，从表4-9中选一个执行方案变量含义解1解2解3解4x1x2x3d1-d2-d3-d4-d5+d6+晋升到Ⅰ级的人数晋升到Ⅱ级的人数新招收Ⅲ级的人数工资总额的结余额Ⅰ级缺编人数Ⅱ级缺编人数Ⅲ级缺编人数Ⅱ级超编人数Ⅲ级超编人数2.43063000.62.43002.43333000.62.40003333000030.60035500100.62例7已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表4-10。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优先等级：•P1——B4是重点保证单位，必须全部满足其需要；•P2——A3向B1提供的产量不少于100；•P3——每个销地的供应量不小于其需要量的80%；•P4——所定调运方案的总运费不超过最小运费调运方案的10%；•P5——因路段的问题，尽量避免安排将A2的产品往B4；•P6——给B1和B3的供应率要相同；•P7——力求总运费最省。•试求满意的调运方案。表4-10销地产地B1B2B3B4产量A1A2A3534255642763300200400销量200100450250900/1000解上作业法求得最小运费的调运方案见表4-11。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。销地产地B1B2B3B4产量A1A2A3虚设点200100200250150100300200400100销量2001004502501000/1000表4-11•供应约束x11+x12+x13+x14≤300•x21+x22+x23+x24≤200•x31+x32+x33+x34≤400•需求约束：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提供的产品量不少于100•x31+d5--d5+=100•每个销地的供应量不小于其需要量的80%•x11+x21+x31+d6--d6+=200×0.8•x12+x22+x32+d7--d7+=100×0.8•x13+x23+x33+d8--d8+=450×0.8•x14+x24+x34+d9--d9+=250×0.8调运方案的总运费不超过最小运费调运方案的10%31411010%)101(2950ijijijddxc•因路段的问题，尽量避免安排将A2的产品运往B4•x24+d11--d11+=0•给B1和B3的供应率要相同•(x11+x21+x31)-(200/450)(x13+x23+x33)+d12--d12+=0力求总运费最省314113132950ijijijddxc目标函数为：13712126115104987635241)()(mindPddPdPdPddddPdPdPz计算结果，得到满意调运方案见表4-12。销地产地B1B2B3B4产量A1A2A3虚设点90100101001102509020050300200400100销量2001004502501000总运费为3360元。元336050320072502110410021004903C第4章结束