目标规划图解法标规划单纯形法

第二节目标规划问题的图解法

minZ=d-100X1+80X2-d++d-=100004X1+2X2

4002X1+4X2

500X1,

X2,

d-,

d+0

d+.d-=0例11X2X1O50100501001252X1+4X2=5004X1+2X2=400CEB绝对约束可行域OBEC2X2X1O50100501001252X1+4X2=500100X1+80X2=100004X1+2X2=400CEBd+目标约束满意域BEC3(1)绝对约束可行域OBEC(2)目标约束满意域BEC(3)多个可行满意解：

(60,50),10000;(70,50),11000;E(50,100),13000。(4)Zmin=04例2minZ=P1d1++P2(d2-+d2+)+P3(d3-)2X1+X211X1

-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,

X2,

di-,

di+05111057X2X1AB2X1+X2=11O可行域⊿OAB6111010557X2X1ABCDEFd2+d1-d3+X1+2X2=10X1-X2=08X1+10X2=562X1+X2=11O可行域⊿OAB目标1：⊿OBC目标2：ED线段目标3：GD线段G7解：①可行域⊿OAB②目标1：⊿OBC目标2：ED线段目标3：GD线段③用8X1+10X2=56X1+2X2=10求G=(2,4)利润=568

X1-X2=0

X1+2X2=10D=(10/3,10/3)利润=60解为X==

α+(1-α)(0α1)X1210/3

X2410/3④Zmin=09例3minZ=P1d1-+P2d2++P3(2d3-+d4-)X1+X2+d1--d1+=40①

X1

+X2+d2--d2+=50②X1+d3--d3+=24③X2+d4--d4+=30④10X230304050X1OBACDEFd3+d4+d1+d2-X1+X2=40X1+X2=50X2=30X1=24解：G11(1)、、满足目目标①、②的满意意域为ABCD(2)、、先考虑虑③的满满意域为为ABEF再考虑④④，无公公共满意意域。(3)、EX1+X2=50X1=24E(24,26)GX1+X2=50X2=30G(20,30)12(4)、、d4-=30-X2+d4+=30-26=4>0因为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点13§6.3目标标规划问问题的单单纯形法法目标规划划的数学学模型，，特别是是约束的的结构与与线性规规划模型型没有本本质的区区别，只只是它的的目标不不止是一一个，虽虽然其利利用优先先因子和和权系数数把目标标写成一一个函数数的形式式，但在在计算中中无法按按单目标标处理，，所以可可用单纯纯形法进进行适当当改进后后求解。。在组织织、构造造算法时时，我们们要考虑虑目标规规划的数数学模型型一些特特点，作作以下规规定：(1)因因为目目标规划划问题的的目标函函数都是是求最小小化，所所以检验验数的最最优准则则与线性性规划是是相反的的；一、目标标规划问问题单纯纯形法的的特点14(2)因因为非非基变量量的检验验数中含含有不同同等级的的优先因因子，Pi>>Pi+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（j>i）级第k个检验数数的正、、负情况况；15（3）根根据（LGP））模型特特征，当当不含绝绝对约束束时，di-（i=1,2,…,K）构成了了一组基基本可行行解。在在寻找单单纯形法法初始可可行点时时，这个个特点是是很有用用。16二、目标标规划问问题单纯纯形法的的计算步步骤(1)建建立初始始单纯形形表．在在表中将将检验数数行按优优先因子子个数分分别列成成K行。。初始的的检验数数需根据据初始可可行解计计算出来来，方法法同基本本单纯形形法。当当不含绝绝对约束束时，di-（i=1,2,……,K）构成了了一组基基本可行行解，即即可得到到初始单单纯形表表。17(2)确确定换入入变量：：按优先先级顺序序，检查查检验数数是否存存在负值值，选取取优先级级最高的的最小负负值对应应的变量量入基；；(3)按按单纯形形法中的的最小比比值规则则确定换换出变量量，当存存在两个个和两个个以上相相同的最最小比值值时，选选取具有有较高优优先级别别的变量量为换出出变量；；18(4)按按单纯形形法进行行基变换换运算，，建立新新的单纯纯形表；；(5)迭迭代计算算停止判判别准则则：如果各优优先级的的检验数数均为非非负；某一优先先级有负负检验数数，但是是该负检检验数对对应的上上一级优优先级的的检验数数为正检检验数。。19三、应用用实例Min{P1(d1-+d2+),P2d3-}x1+d1--d1+=102x1+x2+d2--d2+=403x1+2x2+d3--d3+=100x1,x2,di-,di+≥020例Min{P1d1-,P2d2+,P3d3-}5x1+10x2≤60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48x1,x2,di-,di+≥0+x3=6021000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000122000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000123000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000124000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000125000p100p2p30CBXBbx1x2x3d1-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σp1000100000p2000000100p300000001026因有两个个非基变变量的检检验数为为0，所所以，有有无穷多多解。27例试用用单纯形形法来求求解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.28解:由于P1,P2优先级对对应的目目标函数