目标规划第节教材.ppt

第3节 解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定： (1) 因目标规划问题的目标函数都是求最小化，所以以cj-zj≥0，j=1,2,…，n为最优准则。 (2) 因非基变量的检验数中含有不同等级的优先因子，即 因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的数学模型化为标准型： ① 取xs，d1-，d2-，d3-为初始基变量，列初始单纯形表，见表4-1。 ② 取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) ⑥ 即进行基变换运算，计算结果见表4-2 返回到(2)。依此类推，直至得到最终表为止。见表4-3。 表4-3 表4-3所示的解x1*=2，x2*=4为例1的满意解。此解相当于图4-1的G点。 检查表4-3的检验数行，发现非基变量d3+的检验数为0，这表示存在多重解。在表4-3中以非基变量d3+为换入变量，d1-为换出变量，经迭代得到表4-4。 由表4-4得到解x1*=10/3，x2*=10/3，此解相当于图4-1的D点，G、D两点的凸线性组合都是例1的满意解 第4节 灵敏度分析 目标规划的灵敏度分析方法与线性规划相似，这里除分析各项系数的变化外，还有优先因子的变化问题，下面举例说明。 改变目标优先等级的分析。 例5 已知目标规划问题 在得到最终表后，见表4-5。 目标函数的优先等级变化为： (1) min z=P1(2d1++32+)+P2d4++P3- (2) min z= P1d3-+P2(2d1++3d3+)+P3d4+ 试分析原解有什么变化。 表4-5 解 分析(1)，实际是将原目标函数中d4+，d3-的优先因子对换了一下。这时将表4-5的检验数中的P2、P3行和cj行的P2、P3对换即可。这时可见原解仍满足最优解条件。 分析(2)，将变化了的优先等级直接反映到表4-5上。再计算检验数，得表4-6。然后进行迭代，直到求得新的满意解为止。从表4-7中得到新的满意解x1*=4，x2*=12。 表4-6 第5节 应 用 举 例 ?例6 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： (1) 不超过年工资总额60000元； (2) 每级的人数不超过定编规定的人数； (3) Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升； (4) Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。 有关资料汇总于表4-8中，问该领导应如何拟订一个满意的方案。 表4-8 解 设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