《4.3用单纯形法求解目标规划.ppt》由会员分享，可在线阅读，更多相关《4.3用单纯形法求解目标规划.ppt（31页珍藏版）》请在三一文库上搜索。
1、,第三节 用单纯形法求解目标规划,本节内容的安排,目标规划求解问题过程,由目标规划数学模型的标准型可看出，它实质上是 最小化的线性规划，所以可用单纯形法求解 这时，我们应该把目标优先等级系数Pi（i = 1, 2, , k）理解为一种特殊的正常数，且注意到各等级系数之间的关系：P1P2 Pk 而检验数就是各优先因子P1, P2 , Pk的线性组合。,当所有检验数都满足最优性条件（ ）时，从最终表上即可得出目标规划的解,ci - zj = kj Pk ,j=1,2,n ; k=1,2,K,Pk是指不同数量的很大的数 d-是松弛变量 d+是剩余变量,PkMPk+1 (M是任意大的正数）,例: 用单
2、纯形法求解下面目标规划问题:,解：引入松驰变量 x3 , 将它们化为标准型：,单纯形表1,单纯形表1,全部检验数非负，计算结束。,2最优性检验 目标规划的最优性检验是分优先级进行的， 从P1级开始依次到Pk 级为止， 具体检验Pi 级目标 时，可能有下述三种情况,（1）若检验数矩阵的Pi 行系数均0，则Pi 级目标已达最优， 应转入对Pi+1 级目标的寻优，直到 i = k，计算结束。,1、建立初始单纯形表。 一般假定初始解在原点， 即以约束条件中的所有负偏差变量或松弛变量为初始基变量， 按目标优先等级从左至右分别计算出各列的检验数， 填入表的下半部 ，得检验数矩阵。,单纯形法的计算步骤：,（
3、2）若检验数矩阵的Pi 中有负系数，且负系数所在列的 前i-1行优先因子的系数全为0 ( 例如 -P2 +223 P3 0 ) ， 可判定该检验数为负， 则选该系数（若此类负系数有多个，则可选绝对值最大者）所在列对应的非基变量为入基变量，继续进行基变换,（3）若检验数矩阵的Pi行中有负系数，但负系数所在列的前i-1行优先因子的系数有0，也有正数， （例如 P2 - 3 P3 0），即整个检验数的值可判为正（因Pi-1Pi ），故也应转入对Pi+1级目标的寻优，否则会使高优先级别的目标函数值劣化,3基变换 入基变量的确定：在Pk行，从那些上面没有 正检验数 的负检验数中，选绝对值最大者，对应的变
4、量xs就是进基变量。 若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。 假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。, 出基变量的确定： 按最小非负比值规则确定出基变量，当存在两个或两个 以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。 主元素的确定： 出基变量与入基变量在系数矩阵中对应的交叉点上的元素即为主元素 迭代变换： 同线性规划的单纯形法得到新的单纯形表，获得一组新解,对求得的解进行分析： 若计算结果满意，停止运算； 若不满意，需修改模型，即调整目标优先等级和权系数， 或者改变目标值，重新
5、进行第1步。,4从表中找到基本可行解和相应于各优先级的目标函数值 每个单纯形表中常数列b，即为各基变量的相应取值 本题最后一个单纯形表已为最优，它对应的基本可行解：x1=24/5, x2=12/5, x3=12, d2-=36/5，即为最优解这与图解法得到结果一致,注意：在最优单纯形表中非基变量d1+和d3+的检验数都是零，故知本题有多个最优解 如以 d1+为入基变量继续迭代，可得单纯形表2， 如以d3+为入基变量继续迭代，可得单纯形表3,单纯形表1,表2续单纯形表1,表3续单纯形表1,例：用单纯形法求解下列目标规划问题,= min10/3,10,6/3,12/3= 2,故 为换出变量。,最优
6、解为x12， x2 4。 但非基变量 的检验数为零，故此题有无穷多最优解。 = min4 , 24 , 6= 4,故 为换出变量。,最优解为x110/3,，x2 =10/3。 则这两个解得凸组合都是本例的满意解。,例 : 用单纯形法求解下述目标规划问题：,解 : 第一步：列出初始单纯形表,第二步：确定换入变量 第三步：确定换出变量,第四步：用换入变量替换基变量中的换出变量,例、已知一个生产计划的线性规划模型为,其中目标函数为总利润，x1,x2 为产品A、B产量。现有下列目标： 1、要求总利润必须超过 2500 元； 2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100
7、件； 3、由于甲资源供应比较紧张，不要超过现有量140。 试建立目标规划模型，并用单纯形法求解。,1、要求总利润必须超过 2500 元； 2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3、由于甲资源供应比较紧张，不要超过现有量140。,= min2500/30,140/2,60/1=60 ,故 为换出变量。,= min700/30,20/2, =10 ,故 为换出变量。,= min400/15, =10 ,故 为换出变量。,= min,350/6,1250/6,100/1=75 ,故 为换出变量。,表中P3检验数为负，说明P3 优先等级目标没有实现，但已无
8、法改进，得到满意解 x1 60， x2 175/3， 115/3， 125/3。,结果分析：计算结果表明，工厂应生产A产品60件， B产品175/3件，2500元的利润目标刚好达到。 d4- 125/3，表明产品B比最高限额少125/3件，满足要求。 d2+115/3 表明甲资源超过库存115/3公斤，该目标没有达到。 从表中还可以看到，P3 的检验数还有负数， 但其高等级的检验数却是正数， 要保证 P1目标实现，P3等级目标则无法实现。 所以，按现有消耗水平和资源库存量，无法实现2500元的利润目标。 可考虑如下措施： 降低A、B产品对甲资源的消耗量， 以满足现有甲资源库存量的目标； 或改变P3等级目标的指标值，增加甲资源115/3公斤。 若很难实现上述措施，则需改变现有目标的优先等级， 以取得可行的满意结果。,满意解 x1 60， x2 175/3， d2+115/3， d4- 125/3。,1、要求总利润必须超过 2500 元； 2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3、由于甲资源供应比较紧张，不要超过现有量140。,