您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 62目标规划图解法-63标规划单纯形法
1第二节目标规划问题的图解法minZ=d-100X1+80X2-d++d-=100004X1+2X24002X1+4X2500X1,X2,d-,d+0d+.d-=0例12X2X1O50100501001252X1+4X2=5004X1+2X2=400CEB绝对约束可行域OBEC3X2X1O50100501001252X1+4X2=500100X1+80X2=100004X1+2X2=400CEBd+目标约束满意域BEC4(1)绝对约束可行域OBEC(2)目标约束满意域BEC(3)多个可行满意解:(60,50),10000;(70,50),11000;E(50,100),13000。(4)Zmin=05例2minZ=P1d1++P2(d2-+d2+)+P3(d3-)2X1+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,X2,di-,di+06111057X2X1AB2X1+X2=11O可行域⊿OAB7111010557X2X1ABCDEFd2+d1-d3+X1+2X2=10X1-X2=08X1+10X2=562X1+X2=11O可行域⊿OAB目标1:⊿OBC目标2:ED线段目标3:GD线段G8解:①可行域⊿OAB②目标1:⊿OBC目标2:ED线段目标3:GD线段③用8X1+10X2=56X1+2X2=10求G=(2,4)利润=569X1-X2=0X1+2X2=10D=(10/3,10/3)利润=60解为X==α+(1-α)(0α1)X1210/3X2410/3④Zmin=010例3minZ=P1d1-+P2d2++P3(2d3-+d4-)X1+X2+d1--d1+=40①X1+X2+d2--d2+=50②X1+d3--d3+=24③X2+d4--d4+=30④11X230304050X1OBACDEFd3+d4+d1+d2-X1+X2=40X1+X2=50X2=30X1=24解:G12(1)、满足目标①、②的满意域为ABCD(2)、先考虑③的满意域为ABEF再考虑④,无公共满意域。(3)、EX1+X2=50X1=24E(24,26)GX1+X2=50X2=30G(20,30)13(4)、d4-=30-X2+d4+=30-26=40因为X2+d4--d4+=30所以d4-=30–X2+d4+ZE=P3d4-=P3(30-x2+d4+)=P3(30-26)=4P3而因为x1+d3--d3+=24ZG=P3*2d3-=P3*2(24-20)=8P3所以,取E点14§6.3目标规划问题的单纯形法目标规划的数学模型,特别是约束的结构与线性规划模型没有本质的区别,只是它的目标不止是一个,虽然其利用优先因子和权系数把目标写成一个函数的形式,但在计算中无法按单目标处理,所以可用单纯形法进行适当改进后求解。在组织、构造算法时,我们要考虑目标规划的数学模型一些特点,作以下规定:(1)因为目标规划问题的目标函数都是求最小化,所以检验数的最优准则与线性规划是相反的;一、目标规划问题单纯形法的特点15(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个检验数的正、负情况;16(3)根据(LGP)模型特征,当不含绝对约束时,di-(i=1,2,…,K)构成了一组基本可行解。在寻找单纯形法初始可行点时,这个特点是很有用。17二、目标规划问题单纯形法的计算步骤(1)建立初始单纯形表.在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来,方法同基本单纯形法。当不含绝对约束时,di-(i=1,2,…,K)构成了一组基本可行解,即可得到初始单纯形表。18(2)确定换入变量:按优先级顺序,检查检验数是否存在负值,选取优先级最高的最小负值对应的变量入基;(3)按单纯形法中的最小比值规则确定换出变量,当存在两个和两个以上相同的最小比值时,选取具有较高优先级别的变量为换出变量;19(4)按单纯形法进行基变换运算,建立新的单纯形表;(5)迭代计算停止判别准则:如果各优先级的检验数均为非负;某一优先级有负检验数,但是该负检验数对应的上一级优先级的检验数为正检验数。20三、应用实例Min{P1(d1-+d2+),P2d3-}x1+d1--d1+=102x1+x2+d2--d2+=403x1+2x2+d3--d3+=100x1,x2,di-,di+≥021例Min{P1d1-,P2d2+,P3d3-}5x1+10x2≤60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48x1,x2,di-,di+≥0+x3=6022000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000123000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000124000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000125000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000126000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3120011-100-110x124/51002/5-0.4000.1-0.10d2-36/5000-2/50.41-1-0.60.60x212/5010-0.30.3000.05-0.05σp1000100000p2000000100p300000001027因有两个非基变量的检验数为0,所以,有无穷多解。28例试用单纯形法来求解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.29解:由于P1,P2优先级对应的目标函数中不含di-,所以其检验数只需取系数。分别为(0,0,0,1,0,1,0,0,0,0)和(0,0,0,0,0,0,0,1,0,0)x1x2d1-d1+d2-d2+d3-d3+d4-d4+bP10001010000P20000000100P3-12-1800000001P4-1-201020000d1-101-10000009d2-01001-100008d3-4600001-10060d4-12180000001-1252312X1+X211X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,X2,di-,di+0min{P1d1+,P2(d2-+d2+),P3(d3-)}练习:
本文标题:62目标规划图解法-63标规划单纯形法
链接地址:https://www.777doc.com/doc-630504 .html