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

1、第第3节节 解目标规划的单纯形法解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定： (1) 因目标规划问题的目标函数都是求最小化，所以以cj-zj0，j=1,2,，n为最优准则。 (2) 因非基变量的检验数中含有不同等级的优先因子，即KknjPazckkjjj, 2 , 1;, 2 , 1 因P1P2PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数1j的正、负。若1j=0，这时此检验数的正、负就决定于P2的系数2j的正、负，下面可依此类推。 解目标规划问题的单纯形法的计

2、算步骤： (1) 建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。 (2) 检查该行中是否存在负数，且对应的前k-1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。 (3) 按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。 (4) 按单纯形法进行基变换运算，建立新的计算表，返回(2)。 (5) 当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到(2)。例例4 4 试用单纯形法来求解例2。将例2的数学模型化为标准型： 3 , 2 , 1, 0,561081020

3、112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss满足约束条件：目标函数： 取xs，d1-，d2-，d3-为初始基变量，列初始单纯形表，见表4-1。 cj P1 P2 P3 P4 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ P2 P3 xs d1- d2- d3- 11 0 10 56 2 1 1 8 1 -1 2 10 1 1 -1 1 -1 1 -1 11/1 / 10/2 56/10 cj-zj P1 P2 P3 -1 -8 -2 -10 1 2 1 取k=1，检查P1行的

4、检验数，因该行无负检验数， 故转(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-2 表4-3返回到(2)。依此类推，直至得到最终表为止。见表4-3。 cj P1 P2 P3 P4 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ xs d1- x2- x1- 3 2 4 2 1

5、1 1 1 -1 2 3 4/3 -5/3 -2 -3 -4/3 5/3 -1/2 -1/2 -1/6 1/3 1/2 1/2 1/6 -1/3 6 4 24 cj-zj P1 P2 P3 -1 -8 -2 -10 1 1 1 1 表4-3所示的解x1*=2，x2*=4为例1的满意解。此解相当于图4-1的G点。检查表4-3的检验数行，发现非基变量d3+的检验数为0，这表示存在多重解。在表4-3中以非基变量d3+为换入变量，d1-为换出变量，经迭代得到表4-4。 cj P1 P2 P3 P4 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3- d3+ xs d3+ x2 x

6、1 1 4 10/3 10/3 1 1 1 -1 2 -1/3 2/3 1 -2 1/3 -2/3 -1 6 1/3 1/3 1 -6 -1/3 -1/3 -1 1 cj-zj P1 P2 P3 1 1 1 1 由表4-4得到解x1*=10/3，x2*=10/3，此解相当于图4-1的D点，G、D两点的凸线性组合都是例1的满意解第第4 4节节 灵敏度分析灵敏度分析 目标规划的灵敏度分析方法与线性规划相似，这里除分析各项系数的变化外，还有优先因子的变化问题，下面举例说明。 改变目标优先等级的分析。例例5 5 已知目标规划问题4 , 3 , 2 , 1, 0,125635410)32(min2144

7、21332122111214332211iddxxddxxddxxddxddxxdPdPddPzii满足约束条件：目标函数： 在得到最终表后，见表4-5。 目标函数的优先等级变化为： (1) min z=P1(2d1+32+)+P2d4+P3- (2) min z= P1d3-+P2(2d1+3d3+)+P3d4+ 试分析原解有什么变化。表4-5 cj 2P1 3P1 P2 P3 CB XB b x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ x2 x1 d3- d4- 6 4 18 2 1 1 1 1 1 -3 -1 -1 -2 3 1 -1 1 -2 1 -1

8、2 1 -1 1 -1 cj-zj P1 P2 P3 3 2 -3 2 3 -2 1 1 解解 分析(1)，实际是将原目标函数中d4+，d3-的优先因子对换了一下。这时将表4-5的检验数中的P2、P3行和cj行的P2、P3对换即可。这时可见原解仍满足最优解条件。 分析(2)，将变化了的优先等级直接反映到表4-5上。再计算检验数，得表4-6。然后进行迭代，直到求得新的满意解为止。从表4-7中得到新的满意解x1*=4，x2*=12。表4-6 cj 2P1 3P1 P2 P3 CB XB b x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ x2 x1 d3- d4- 6

9、4 18 2 1 1 1 1 1 -3 -1 -1 -2 3 1 -1 1 -2 1 -1 2 1 -1 1 -1 cj-zj P1 P2 P3 3 2 -3 2 3 -2 1 1 第第5 5节节 应应 用用 举举 例例 例6 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： (1) 不超过年工资总额60000元； (2) 每级的人数不超过定编规定的人数； (3) ，级的升级面尽可能达到现有人数的20%，且无越级提升； (4) 级不足编制的人数可录用新职工，又级的职工中有10%要退休。 有关资料汇总于表4-8中，问该领导应如何拟订一个满意的方案。表4-8等级 工资额(元/年) 现

10、有人数 编制人数 2000 1500 1000 10 12 15 12 15 15 合计 37 42 解解 设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为： P1不超过年工资总额60000元； P2每级的人数不超过定编规定的人数； P3、级的升级面尽可能达到现有人数的20%。先分别建立各目标约束。年工资总额不超过60000元 2000(10-100.1+x1)+ 1500(12-x1+x2)+1000(15-x2+x3)+ d1-d1+ =60000 每级的人数不超过定编规定的人数： 对级有 10(1-0.1)+x1+d2-d2+=12 对级有 12-x1

11、+x2+d3-d3+=15 对级有 15-x2+x3+d4-d4+=15 ，级的升级面不大于现有人数的20%，但尽可能多提； 对级有 x1+d5-d5+=120.2 对级有 x2+d6-d6+=150.2 目标函数：min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-) 以上目标规划模型可用单纯形法求解，得到多重解。现将这些解汇总于表4-9，这单位的领导再按具体情况，从表4-9中选一个执行方案 变 量 含义 解 1 解 2 解 3 解 4 x1 x2 x3 d1- d2- d3- d4- d5+ d6+ 晋升到级的人数 晋升到级的人数 新招收级的人数 工资总额的结余额 级缺编

12、人数 级缺编人数 级缺编人数 级超编人数 级超编人数 2.4 3 0 6300 0.6 2.4 3 0 0 2.4 3 3 3300 0.6 2.4 0 0 0 3 3 3 3000 0 3 0.6 0 0 3 5 5 0 0 1 0 0.6 2 例7 已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表4-10。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优先等级： P1B4是重点保证单位，必须全部满足其需要； P2A3向B1提供的产量不少于100； P3每个销地的供应量不小于其需要量的80%； P4所定调运方案的总运费不超过最小运费调运方案的10%； P5

13、因路段的问题，尽量避免安排将A2的产品往B4； P6给B1和B3的供应率要相同； P7力求总运费最省。 试求满意的调运方案。表4-10销 地产地 B1 B2 B3 B4 产量 A1 A2 A3 5 3 4 2 5 5 6 4 2 7 6 3 300 200 400 销 量 200 100 450 250 900/1000 解解 上作业法求得最小运费的调运方案见表4-11。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。销 地产地 B1 B2 B3 B4 产量 A1 A2 A3 虚设点 200 100 200 250 150 100 300 200 400 100 销

14、量 200 100 450 250 1000/1000 表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提供的产品量不少于100 x31+d5-d5+=100 每个销地的供应量不小于其需要量的80% x11+x21+x31+d6-d6+=2000.8 x12+x22+x32+d7-d7+=1000.8 x13+x23+x33+d8-d8+=4500.8 x14+x24+x34+d9-d9+=2500.8调运方案的总运费不超过最小运费调运方案的10%31411010%)101 (2950ijijijddxc 因路段的问题，尽量避免安排将A2的产品运往B4 x24+d11-d11+=0 给B1和B3的供应率要相同 (x11+x21+x31)-(200/450)(x13+x23+x33)+d12-d12+=0力求总运费最省314113132950ijijij