62目标规划图解法-63标规划单纯形法.ppt

第二节目标规划问题的图解法,minZ=d-,100X1+80X2-d+d-=100004X1+2X24002X1+4X2500X1,X2,d-,d+0d+.d-=0,例1,绝对约束可行域OBEC,X2,X1,O,50,100,50,100,125,2X1+4X2=500,100X1+80X2=10000,4X1+2X2=400,C,E,B,d+,目标约束满意域BEC,(1)绝对约束可行域OBEC(2)目标约束满意域BEC(3)多个可行满意解：(60,50),10000;(70,50),11000;E(50,100),13000。(4)Zmin=0,例2,11,10,5,7,X2,X1,A,B,2X1+X2=11,O,可行域OAB,11,10,10,5,5,7,X2,X1,A,B,C,D,E,F,d2+,d1-,d3+,X1+2X2=10,X1-X2=0,8X1+10X2=56,2X1+X2=11,O,可行域OAB,目标1：OBC目标2：ED线段目标3：GD线段,G,解：,可行域OAB,目标1：OBC目标2：ED线段目标3：GD线段,Zmin=0,例3,X2,30,30,40,50,X1,O,B,A,C,D,E,F,d3+,d4+,d1+,d2-,X1+X2=40,X1+X2=50,X2=30,X1=24,解：,G,(1)、满足目标、的满意域为ABCD,(2)、先考虑的满意域为ABEF再考虑，无公共满意域。,(4)、d4-=30-X2+d4+=30-26=40,因为X2+d4-d4+=30,所以d4-=30X2+d4+ZE=P3d4-=P3(30-x2+d4+)=P3(30-26)=4P3,而因为x1+d3-d3+=24ZG=P3*2d3-=P3*2(24-20)=8P3,所以，取E点,6.3目标规划问题的单纯形法,目标规划的数学模型，特别是约束的结构与线性规划模型没有本质的区别，只是它的目标不止是一个，虽然其利用优先因子和权系数把目标写成一个函数的形式，但在计算中无法按单目标处理，所以可用单纯形法进行适当改进后求解。在组织、构造算法时，我们要考虑目标规划的数学模型一些特点，作以下规定：(1)因为目标规划问题的目标函数都是求最小化，所以检验数的最优准则与线性规划是相反的；,一、目标规划问题单纯形法的特点,(2)因为非基变量的检验数中含有不同等级的优先因子，PiPi+1，i=1,2,L-1.于是从每个检验数的整体来看：Pi+1（i=1,2,L-1）优先级第k个检验数的正、负首先决定于P1，P2，Pi优先级第k个检验数的正、负。若P1级第k个检验数为0，则此检验数的正、负取决于P2级第k个检验数；若P2级第k个检验数仍为0，则此检验数的正、负取决于P3级第k个检验数，依次类推。换一句话说，当某Pi级第k个检验数为负数时，计算中不必再考察Pj（ji）级第k个检验数的正、负情况；,（3）根据（LGP）模型特征，当不含绝对约束时，di-（i=1,2,K）构成了一组基本可行解。在寻找单纯形法初始可行点时，这个特点是很有用。,二、目标规划问题单纯形法的计算步骤(1)建立初始单纯形表在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时，di-（i=1,2,K）构成了一组基本可行解，即可得到初始单纯形表。,(2)确定换入变量：按优先级顺序，检查检验数是否存在负值，选取优先级最高的最小负值对应的变量入基；(3)按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量；,(4)按单纯形法进行基变换运算，建立新的单纯形表；(5)迭代计算停止判别准则：如果各优先级的检验数均为非负；某一优先级有负检验数，但是该负检验数对应的上一级优先级的检验数为正检验数。,三、应用实例,MinP1(d1-+d2+),P2d3-x1+d1-d1+=102x1+x2+d2-d2+=403x1+2x2+d3-d3+=100 x1,x2,di-,di+0,例,MinP1d1-,P2d2+,P3d3-5x1+10 x260 x1-2x2+d1-d1+=04x1+4x2+d2-d2+=366x1+8x2+d3-d3+=48x1,x2,di-,di+0,+x3=60,因有两个非基变量的检验数为0，所以，有无穷多解。,例试用单纯形法来求解Minz=P1（d1+d2+)+P2d3+P3d4-+P4（d1-+2d2-)x1+d1-d1+=9x2+d2-d2+=84x1+6x2+d3-d3+=6012x1+18x2+d4-d4+=252x1,x2,di-,di+0,i=1,2,3,4.,解:由于P1,P2优先级对应的