第4章 多目标规划.ppt

x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1- d1+ d2+ d2- X1+X2=50 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d2- d1+ x1 x2 0 20 30 40 50 10 10 30 40 20 50 d2- X1=30 d1+ d3- x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1+ d2- d3- X1=30 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1+ d2- d3- X1=30 d4- x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1+ d2- d3- d4- Min d2+ =0 可行域如图 x1 x2 0 20 30 40 50 10 10 30 40 20 50 d1+ d2- d4- Min d3- = 0 线段AB是可行域 A B x1 x2 0 20 30 40 50 10 10 30 40 20 50 d2- d4- Min d4- P=(30,20)唯一最优解。 d2- =10 d4- = 10 P 例4-10 Min S=P1d1-+P2d2++ P3d3-+ P3d4- 5X1+10X2+ d1-- d1+=100 2X1 + X2 + d2-- d2+=14 X1 + d3-- d3+=6 X2+ d4-- d4+=10 X1,X2,di-, di+ ? 0(i=1,2,3,4) x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d1- 5X1+10X2=100 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d1- d2+ d2- 2X1 +X2 =14 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d1- d2+ d2- d3+ d3- X1 =6 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d1- d2+ d2- d3+ d3- d4+ d4- X2=10 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d2+ d2- d3+ d3- d4+ d4- Min d1- = 0 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d2- d3+ d3- d4+ d4- Min d2+ = 0 可行域如图 x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d2- d3+ d4+ d4- Min d3- =0 可行域为空如图 d3- x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d2- d3+ d4+ d4- Min d3- ≠0,如何使P3 （d3-+ d4-）最小呢？ Q d3-Q E d3-E x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d2- d3+ d4+ d4- x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d2- d3+ d4+ d4- x1 x2 0 10 15 20 25 5 5 15 20 10 25 d1+ d2- d3+ d4+ d4- P1(2,10) P2(26/3,8/3) 2X1 +X2 =14 d3-+ d4-= 16-(X1 +X2) = 16-(2X1 +X2 )+X1 =2+X1 于是P1为最优点。 多目标规划的单纯形算法 多目标规划问题与线性规划问题相似，可用单纯形算法求解。 注意：在比较检验数大小时，要先比较较高级别的系数，再比较较低级别的系数。 例4-11（例4-6） 目标函数：Min S=P1d1-+P2(5d2++d3+) 约束方程： 6X1+4X2+ d1-- d1+=280 2X1+3X2+ d2-- d2+=100 4X1+2X2+ d3-- d3+=120 X1,X2,di-, di+ ? 0(i=1,2,3) 方案2与（2）的差距： 工时损失 =0*5+（160