单纯形法及应用举例

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

2、，则此检验数的正、负就决定于，则此检验数的正、负就决定于P2的系数的系数2j的的正、负；下面依此类推。正、负；下面依此类推。KknjPazckkjjj, 2 , 1;, 2 , 12第3节 解目标规划的单纯形法v解目标规划问题的单纯形法的计算步骤：(1) 建立初始单纯形表，在表中将检验数行按优先因子个数分别列成建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置行，置k=1。(2) 检查该行中是否存在负数，且对应的前检查该行中是否存在负数，且对应的前k1行的系数是零。若有行的系数是零。若有负数取其中最小者对应的变量为换入变量，转到负数取其中最小者对应的变量为换入变量，转到(3)；若

3、无负数，则；若无负数，则转到转到(5)。(3) 按最小比值规则确定换出变量。当存在两个和两个以上相同的最按最小比值规则确定换出变量。当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。小比值时，选取具有较高优先级别的变量为换出变量。(4) 按单纯形法进行基变换运算，建立新的计算表，返回按单纯形法进行基变换运算，建立新的计算表，返回(2)。(5) 当当k=K时，计算结束，表中的解即为满意解。否则，置时，计算结束，表中的解即为满意解。否则，置k=k+1，返回到返回到(2)。3第3节 解目标规划的单纯形法v例例4 4 试用单纯形法来求解例2。解：解：将例2的数学模型化为标准型

4、：3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss满足约束条件：目标函数：4第3节 解目标规划的单纯形法v 取xs，d1，d2 ，d3为初始基变量，列初始单纯形表，见表4-1。5第3节 解目标规划的单纯形法 取k=1，检查检验数的P1行，因该行无负检验数，故转(5)。 因k(=2)K(=3)，置k=k+1=3，返回到(2)。 查出检验数P2行中有1、 2；取min( 1, 2)= 2。它对应的变量x2为换入变量，转入(3)。 在表4-1上计算最小比值=min(11/1，0

5、，10/2，56/10)=10/2 它对应的变量d2-为换出变量，转入(4)。 进行基变换运算，计算结果见表4-2。返回到(2)。依此类推，直至得到最终表为止。见表4-3。6第3节 解目标规划的单纯形法表4-27第3节 解目标规划的单纯形法表4-38第3节 解目标规划的单纯形法v表4-3所示的解x1*=2，x2*=4为例1的满意解，此解相当于图4-1的G点。9第3节 解目标规划的单纯形法v检查表4-3的检验数行，发现非基变量d3+的检验数为0，表示存在多重解。在表4-3中，以非基变量d3+为换入变量，d1为换出变量，经迭代得到表4-4。10第3节 解目标规划的单纯形法v由表4-4得到解x1*=

6、10/3，x2*=10/3，此解相当于图4-1的D点，G、D两点的凸线性组合都是例1的满意解。11第4节 应用举例例例5 5 某研究所领导在考虑本单位职工的升级调资方案时，依次遵守以下优先级顺序规定：(1) 不超过年工资总额3000万元；(2) 提级时，每级的人数不超过定编规定的人数；(3) ，级的升级面尽可能达到现有人数的20%，且无越级提升；此外，级不足编制的人数可录用新职工，又级的职工中有10%要退休。 有关资料汇总于表5-6中，问该领导应如何拟订一个满意的方案。12第4节 应用举例例例6 已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表5-8。有关部门在研究调运方

7、案时依次考虑以下七项目标，并规定其相应的优先等级：P1B4是重点保证单位，必须全部满足其需要；P2A3向B1提供的产量不少于100；P3每个销地的供应量不小于其需要量的80%；P4所定调运方案的总运费不超过最小运费调运方案的10%；P5因路段的问题，尽量避免安排将A2的产品往B4；P6给B1和B3的供应率要相同；P7力求总运费最省。试求满意的调运方案。13第4节 应用举例14第4节 应用举例v解解 表上作业法求得最小运费的调运方案见表5-9。这时得最小运费为2950元，再根据提出的各项目标的要求建立目标规划的模型。表5-915第4节 应用举例v供应约束x11+x12+x13+x14300 x2

8、1+x22+x23+x24200 x31+x32+x33+x34400v需求约束：x11+x21+x31+d1 d1+=200 x12+x22+x32+d2 d2+=100 x13+x23+x33+d3 d3+=450 x14+x24+x34+d4 d4+=250vA3向B1提供的产品量不少于100 x31+d5 d5+=10016第4节 应用举例v每个销地的供应量不小于其需要量的80%x11+x21+x31+d6d6+=2000.8x12+x22+x32+d7 d7+=1000.8x13+x23+x33+d8 d8+=4500.8x14+x24+x34+d9 d9+=2500.8v调运方案的

9、总运费不超过最小运费调运方案的10%31411010%)101 (2950ijijijddxc17第4节 应用举例v因路段的问题，尽量避免安排将A2的产品运往B4 x24+d11d11+=0v给B1和B3的供应率要相同(x11+x21+x31)(200/450)(x13+x23+x33)+d12 d12+=0v力求总运费最省v目标函数为：314113132950ijijijddxc13712126115104987635241)()(mindPddPdPdPddddPdPdPz18第4节 应用举例v计算结果，得到满意调运方案见表5-10。总运费为3360元元336050320072502110

10、410021004903C19第4节 应用举例练习:某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1) 不超过年工资总额60000元；(2) 每级的人数不超过定编规定的人数；(3) ，级的升级面尽可能达到现有人数的20%，且无越级提升；(4) 级不足编制的人数可录用新职工，又级的职工中有10%要退休。 有关资料汇总于下表中，问该领导应如何拟订一个满意的方案。20第4节 应用举例v解：解：设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为：P1不超过年工资总额不超过年工资总额60000元；元；P2每级的人数不超过定编规定的人数；每级的人数不超过定编规定的人数；P3、级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%。v先分别建立各目标约束。年工资总额不超过年工资总额不超过60000元元2000(10100.1+x1)+1500(12x1+x2)+1000(15x2+x3)+ d1d1+ =6000021第4节 应用举例每级的人数不超过定编规定的人数：每级的人数不超过定编规定的人数：对对级有级有 10(1 0.1)+x1+d2d2+=12对对级有级有 12 x1+x2+d3d3+=15对对级有级有 15 x2+x3+d4 d4+=15，级的升级面不大于现有人数的级的升级面不大于现有人