4.3用单纯形法求解目标规划ppt课件.ppt

1;.目标规划单纯形法的求解步骤例 * 题2目标规划求解问题过程目标规划求解问题过程明确问题，列出明确问题，列出( (或修改或修改) )目标的优先级和权系数目标的优先级和权系数构造目标构造目标规划的模型规划的模型求出求出满意解满意解满意否？满意否？分析各项目分析各项目表完成情况表完成情况据此制定出据此制定出决策方案决策方案是是否否3 由目标规划数学模型的标准型可看出，它实质上是由目标规划数学模型的标准型可看出，它实质上是 最小化的线性规划，所以可用单纯形法求解．最小化的线性规划，所以可用单纯形法求解． 这这时时，，我我们们应应该该把把目目标标优优先先等等级级系系数数P Pi i（（i i = = 1, 1, 2, 2, …, , k k））理理解解为为一一种种特特殊的正常数，且注意到各等级系数之间的关系：殊的正常数，且注意到各等级系数之间的关系：P P1 1»P P2 2 »…»P Pk k．． 而检验数就是各优先因子而检验数就是各优先因子P P1 1, , P P2 2 , ,…, , P Pk k的线性组合。

的线性组合当所有检验数都满足最优性条件（当所有检验数都满足最优性条件（ ）时，从最终）时，从最终表上即可得出目标规划的解．表上即可得出目标规划的解．ci - zj = ∑αkj Pk ,j=1,2,…,n ; k=1,2,…,KP Pk k是指不同数量的很大的数是指不同数量的很大的数 d d- -是松弛变量是松弛变量 d d+ +是剩余变量是剩余变量P Pk k>>MP>>MPk+1 k+1 (M(M是任意大的正数）是任意大的正数）4例例例例: : 用单纯形法求解下面目标规划问题用单纯形法求解下面目标规划问题: : 解：解：解：解：引入松驰变量引入松驰变量 x x3 3 , , 将它们化为标准型：将它们化为标准型：5 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 [1] -2 0 1 -1 0 0 0 0 0 36 4 4 0 0 0 1 -1 0 0 P3 48 6 8 0 0 0 0 0 1 -1 P1 -1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 -6 -8 0 0 0 0 0 0 1 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0 1 -2 0 1 -1 0 0 0 0 0 36 0 12 0 -4 4 1 -1 0 0 P3 48 0[20] 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 1　　　　　　　　单单单单纯纯纯纯形形形形表表表表1 16 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0 1 -2 0 1 -1 0 0 0 0 0 36 0 12 0 -4 4 1 -1 0 0 P3 48 0[20] 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5 -2/5 0 01/10-1/10 036/5 0 0 0 -2/5 2/5 1 -1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 0　　　　　　　　单单单单纯纯纯纯形形形形表表表表1 1全部检验数非负，全部检验数非负，计算结束。

计算结束72 2 2 2．最优性检验．最优性检验．最优性检验．最优性检验 目标规划的最优性检验是分优先级进行的，目标规划的最优性检验是分优先级进行的，目标规划的最优性检验是分优先级进行的，目标规划的最优性检验是分优先级进行的，从从从从P P P P1 1 1 1级开始依次到级开始依次到级开始依次到级开始依次到P P P Pk k k k 级为止，级为止，级为止，级为止，具体检验具体检验具体检验具体检验P P P Pi i i i 级目标级目标级目标级目标 时，可能有下述三种情况．时，可能有下述三种情况．时，可能有下述三种情况．时，可能有下述三种情况． （（（（1 1 1 1）若检验数矩阵的）若检验数矩阵的）若检验数矩阵的）若检验数矩阵的P P P Pi i i i 行系数均行系数均行系数均行系数均≥≥≥≥0 0 0 0，则，则，则，则P P P Pi i i i 级目标已达最优，级目标已达最优，级目标已达最优，级目标已达最优， 应转入对应转入对应转入对应转入对P P P Pi+1i+1i+1i+1 级目标的寻优，直到级目标的寻优，直到级目标的寻优，直到级目标的寻优，直到 i = ki = ki = ki = k，计算结束。

计算结束计算结束计算结束 1 1、建立初始单纯形表建立初始单纯形表 一般假定初始解在原点，一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，即以约束条件中的所有负偏差变量或松弛变量为初始基变量， 按目标优先等级从左至右分别计算出各列的检验数，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部填入表的下半部 ，得检验数矩阵得检验数矩阵单纯形法的计算步骤：单纯形法的计算步骤：单纯形法的计算步骤：单纯形法的计算步骤：8（（2 2）若检验数矩阵的）若检验数矩阵的P Pi i 中有负系数，且负系数所在列的中有负系数，且负系数所在列的前前i i-1-1行优先因子的系数全为行优先因子的系数全为0 ( 0 ( 例如例如 -P-P-P-P2 2 2 2 +223 P+223 P+223 P+223 P3 3 3 3 <0<0<0<0 ) ) ，，可判定该检验数为负，可判定该检验数为负，则选该系数（若此类负系数有多个，则可选绝对值最大者）所在列对应的非基则选该系数（若此类负系数有多个，则可选绝对值最大者）所在列对应的非基变量为入基变量，继续进行基变换．变量为入基变量，继续进行基变换． （（3 3））若若检检验验数数矩矩阵阵的的P Pi i行行中中有有负负系系数数，，但但负负系系数数所所在在列列的的前前i i-1-1行行优优先先因子的系数有因子的系数有0 0，也有正数，，也有正数，（（例例如如 P P P P2 2 2 2 - - - - 3 3 3 3 P P P P3 3 3 3 >0>0>0>0）），，即即整整个个检检验验数数的的值值可可判判为为正正（（因因P Pi i-1-1»P Pi i ）），，故故也也应转入对应转入对P Pi i+1+1级目标的寻优，否则会使高优先级别的目标函数值劣化．级目标的寻优，否则会使高优先级别的目标函数值劣化． 9 3 3 3 3．基变换．基变换．基变换．基变换 ① ① 入基变量的确定：在入基变量的确定：在P Pk k行，从那些上面没有行，从那些上面没有 正检验数正检验数 的负检验数中，选的负检验数中，选绝对值最大者，对应的变量绝对值最大者，对应的变量x xs s就是进基变量。

就是进基变量若若P Pk k行行中中有有几几个个相相同同的的绝绝对对值值最最大大者者，，则则依依次次比比较较它它们们各各列列下下部部的的检检验验数数，，取取其其绝对值最大的负检验数的所在列的绝对值最大的负检验数的所在列的x xs s为进基变量为进基变量假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量10② ② 出基变量的确定：出基变量的确定：按最小非负比值规则确定出基变量，当存在两个或两个按最小非负比值规则确定出基变量，当存在两个或两个 以上相同的最小比以上相同的最小比值时，选取具有较高优先级别的变量为换出变量值时，选取具有较高优先级别的变量为换出变量③ ③ 主元素的确定：主元素的确定：出基变量与入基变量在系数矩阵中对应的交叉点上的元素即为主元素．出基变量与入基变量在系数矩阵中对应的交叉点上的元素即为主元素．④ ④ 迭代变换：迭代变换：同线性规划的单纯形法．得到新的单纯形表，获得一组新解同线性规划的单纯形法．得到新的单纯形表，获得一组新解⑤⑤对求得的解进行分析：对求得的解进行分析： 若计算结果满意，停止运算；若计算结果满意，停止运算； 若不满意，需修改模型，即调整目标优先等级和权系数，若不满意，需修改模型，即调整目标优先等级和权系数， 或者改变目标值，重新进行第或者改变目标值，重新进行第1 1步。

步11 4 4．．从从从从表表表表中中中中找找找找到到到到基基基基本本本本可可可可行行行行解解解解和和和和相相相相应应应应于于于于各各各各优优优优先先先先级级级级的的的的目目目目标标标标函函函函数数数数值值值值 每每个个单单纯纯形形表中常数列表中常数列b b，即为各基变量的相应取值．，即为各基变量的相应取值．本本题题最最后后一一个个单单纯纯形形表表已已为为最最优优，，它它对对应应的的基基本本可可行行解解：：x x1 1=24/5, =24/5, x x2 2=12/5, =12/5, x x3 3=12, d=12, d2 2- -=36/5=36/5，即为最优解．这与图解法得到结果一致．，即为最优解．这与图解法得到结果一致． 注注注注意意意意：：：：在在最最优优单单纯纯形形表表中中非非基基变变量量d d1 1+ +和和d d3 3+ +的的检检验验数数都都是是零零，，故故知知本本题题有有多多个个最最优解．优解． 如以如以 d d1 1+ +为入基变量继续迭代，可得单纯形表为入基变量继续迭代，可得单纯形表2 2，，如以如以d d3 3+ +为入基变量继续迭代，可得单纯形表为入基变量继续迭代，可得单纯形表3 3．．12 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1 -5 5 0 0 0 0 0 x1 0 1 -2 0 1 -1 0 0 0 0 0 36 0 12 0 -4 4 1 -1 0 0 P3 48 0[20] 0 -6 6 0 0 1 -1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6 -6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5 -2/5 0 01/10-1/10 036/5 0 0 0 -2/5 2/5 1 -1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 0　　　　　单纯形表　单纯形表　单纯形表　单纯形表1 113 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 20 010/3 1 0 0 0 0 -5/6 5/6 0 x1 8 1 4/3 0 0 0 0 0 1/6-1/6 0 4 0 -4/3 0 0 0 1 -1 -2/3 2/3 0 8 010/3 0 -1 1 0 0 1/6-1/6 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 0表表表表2 2 2 2　　续单纯形表　　续单纯形表　　续单纯形表　　续单纯形表1 1 1 114 cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 12 0 0 1 1 -1 0 0 -1 1 0 x1 6 1 0 1/10 1/2 -1/2 0 0 0 0 0 0 0 0 -3/5 -1 1 1 -1 0 0 0 x2 3 0 1 1/20 -1/4 1/4 0 0 0 0 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 0表表表表3 3 3 3　　续单纯形表　　续单纯形表　　续单纯形表　　续单纯形表1 1 1 115例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题16Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 001－－11－－100000P21012001－－1000 P3 5681000001－－100 x3 11210000001σkjP1 0000100000P2 -10－－1－－20002000P3 -56－－8－－10000001017Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 053/201－－11/2-1/20000x251/21001/2-1/2000 P3 63000-551－－100 x3 63/2000-1/21/2001σkjP1 0000100000P2 0000011000P3 -6－－30005-5010θ= min｛10/3,10,6/3,12/3｝= 2,故故 为换出变量。

为换出变量18Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 02001－－13-3-1/21/200x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21σkjP1 0000100000P2 0000011000P3 0000000100 最优解为最优解为x1＝＝2 2，， x2 ＝＝4 4 但非基变量但非基变量 的检验数为零，故此题有无穷多最优的检验数为零，故此题有无穷多最优解θ= min｛4 , 24 ,－, 6｝= 4,故故 为换出变量为换出变量19Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-1－－1-11001σkjP1 0000100000P2 0000011000P3 000000100 最优解为最优解为x1＝10/3,，x2 =10/3则这两个解得凸组合都是本例的满意解。

则这两个解得凸组合都是本例的满意解20例例 : : 用单纯形法求解下述目标规划问题：用单纯形法求解下述目标规划问题：解解 : : 第一步：列出初始单纯形表第一步：列出初始单纯形表第二步：确定换入变量第二步：确定换入变量 第三步：确定换出变量第三步：确定换出变量21第四步：用换入变量替换基变量中的换出变量第四步：用换入变量替换基变量中的换出变量2223 例、例、例、例、已知一个生产计划的线性规划模型为已知一个生产计划的线性规划模型为 其中目标函数为总利润，其中目标函数为总利润，x x1 1,x,x2 2 为产品为产品A A、、B B产量现有下列目标：产量现有下列目标： 1 1、要求总利润必须超过、要求总利润必须超过 2500 2500 元；元； 2 2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A A、、B B的生产量不超过的生产量不超过 60 60 件和件和 100 100 件；件； 3 3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不要超过现有量140140。

试建立目标规划模型，并用单纯形法求解试建立目标规划模型，并用单纯形法求解24 1 1、要求总利润必须超过、要求总利润必须超过 2500 2500 元；元； 2 2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A A、、B B的生产量不超过的生产量不超过 60 60 件和件和 100 100 件；件； 3 3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不要超过现有量14014025Cj00P100P302.5P20P2CBXBbx1x2P1250030121－－1000000014021001－－100000601000001－－1000100010000001－－1σkjP1 -2500－－30－－1201000000P2 000000002.501P3 00000010000θ= min｛2500/30,140/2,60/1｝=60 ,故故 为换出变量为换出变量26Cj 00P100P302.5P20P2CBXBbx1x2P17000121－－100－－30300002001001－－1－－22000x1601000001－－1000100010000001－－1σkjP1 －－7000－－12010030－－3000P2 000000002.501P3 00000010000θ= min｛700/30,20/2,－, －｝=10 ,故故 为换出变量。

为换出变量27Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1 -400030115-150000P2 -250-5/400-5/45/45/2001P3 00000010000θ= min｛400/15,－,－, －｝=10 ,故故 为换出变量为换出变量28Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－－1σkjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/301/5-1/151/15100000θ= min｛－,350/6,1250/6,100/1｝=75 ,故故 为换出变量为换出变量29Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/21－－1σkjP1 00010000000P2 000000005/201P3 -115/300-1/121/12101/2-1/200表中表中P P3 3检验数为负，说明检验数为负，说明P3 优先等级目标没有实现，但已无法改进，得到满意解优先等级目标没有实现，但已无法改进，得到满意解 x1 ＝60， x2 ＝175/3， ＝115/3， ＝125/3。

30 结果分析：计算结果表明，工厂应生产结果分析：计算结果表明，工厂应生产A A产品产品6060件，件，B B产品产品175/3175/3件，件，25002500元的利润目标刚好达到元的利润目标刚好达到 d d4 4- - ＝＝125/3125/3，表明产品，表明产品B B比最高限额少比最高限额少125/3125/3件，满足要求件，满足要求 d d2 2+ +＝＝115/3 115/3 表明甲资源超过库存表明甲资源超过库存115/3115/3公斤，该目标没有达到公斤，该目标没有达到 从表中还可以看到，从表中还可以看到，P3 的检验数还有负数，的检验数还有负数，但其高等级的检验数却是正数，但其高等级的检验数却是正数，要保证要保证 P1目标实现，目标实现，P3等级目标则无法实现等级目标则无法实现所以，按现有消耗水平和资源库存量，无法实现所以，按现有消耗水平和资源库存量，无法实现25002500元的利润目标元的利润目标 可考虑如下措施：可考虑如下措施：降低降低A A、、B B产品对甲资源的消耗量，产品对甲资源的消耗量，以满足现有甲资源库存量的目标；以满足现有甲资源库存量的目标；或改变或改变P3等级目标的指标值，增加甲资源等级目标的指标值，增加甲资源115/3115/3公斤。

公斤 若很难实现上述措施，则需改变现有目标的优先等级，若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意结果以取得可行的满意结果满意解满意解 x x1 1 ＝＝6060，， x x2 2 ＝＝175/3175/3，， d d2 2+ +＝＝115/3115/3，， d d4 4- - ＝＝125/3125/3 1 1、要求总利润必须超过、要求总利润必须超过 2500 2500 元；元； 2 2、考虑产品受市场影响，为避免、考虑产品受市场影响，为避免积压，积压，A A、、B B的生产量不超过的生产量不超过 60 60 件和件和 100 100 件；件； 3 3、由于甲资源供应比较紧张，不、由于甲资源供应比较紧张，不要超过现有量要超过现有量140140。