运筹学多目标规划(2)

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,4-4,多目标规划的单纯形算法,多目标规划问题与线性规划问题相似，可用单纯形算法求解。,注意：在比较检验数大小时，要先比较较高级别的系数，再比较较低级别的系数。,例,4-9,（例,4-5,）,目标函数：,Min Z=P,1,d,1,-,+P,2,(5d,2,+,+d,3,+,),约束方程：,6X,1,+4X,2,+d,1,-,-d,1,+,=280,2X,1,+3X,2,+d,2,-,-d,2,+,=100,4X,1,+2X,2,+d,3,-,-d,3,+,=120,X,1,X,2,d,i,-,d,i,+,0(i=1,2,3),标准型,目标函数：,Max S=-P,1,d,1,-,-P,2,(5d,2,+,+d,3,+,),约束方程：,6X,1,+4X,2,+d,1,-,-d,1,+,=280,2X,1,+3X,2,+d,2,-,-d,2,+,=100,4X,1,+2X,2,+d,3,-,-d,3,+,=120,X,1,X,2,d,i,-,d,i,+,0(i=1,2,3),初始单纯形表,首先满足第一目标,P,1,进基变量,X,1,，出基变量,y,3,-,主元（,4,）,主元运算：第三行除以,4,主元运算：第一行加上第三行（,-6,）倍,主元运算：第二行加上第三行（,-2,）倍,重新计算检验数,第二行除以,2,第一行加上第二行（,-1,）,第三行加上第二行（,-1/2,）,计算检验数,第一行乘上,4/5,第二行加上第一行（,-1/4,）,第三行加上第一行（,3/8,）,计算检验数,最后变量,d,1,-,的检验数为,-P,1,+(4/5)P,2,由于假定,P,1,P,2,，,所以此检验数也小于零。,该问题的最优方案为生产,A,产品,44,个单位，,B,产品,4,个单位，利润为,280,百元。此时，原料正好用了,100,吨，工时比原计划超了,64,小时。,例,4-10,设某工厂生产两种产品，都要经过两道工序，有关资料如下表。假如工序,1,，,2,都允许加班，使得利润不少于,1000,元作为目标。又以：第,1,，,2,工序的加班工时之和尽可能在,160,之内为第一目标；产品乙必须严格控制在,70,公斤之内为第二目标；该厂的利润越高越好为第三目标；尽量减少工序,1,，,2,加班工时为第四目标,.,试问：在上述条件下，该厂应如何生产？,小时,/,公斤,甲,乙,能提供的工时,工序,1,2,1,100,工序,2,1,1,80,产量上界,(kg),不限,70,利润（元,/kg),6,4,解：设,X,1,，,X,2,为甲，乙两种产品的生产公斤数，,d,1,-,，,d,1,+,分别为低于或超过利润,1000,元的偏差,d,2,-,，,d,2,+,分别为第,1,道工序剩余和加班的工时数,d,3,-,，,d,3,+,分别为第,2,道工序剩余和加班的工时数,d,4,-,，,d,4,+,为加班工时之和低于或超过,160,工时数,由于产品,X2,必须严格控制在,70,公斤之内为目标，则可取,d,5,-,为实际公斤数不到,70,的偏差，且,d,5,+,=0,。,目标函数：,Min Z=P,1,d,4,+,+P,2,d,5,+,+P,3,d,1,-,+P,4,(d,2,+,+d,3,+,),约束方程：,6X,1,+4X,2,+d,1,-,-d,1,+,=1000,2X,1,+X,2,+d,2,-,-d,2,+,=100,X,1,+X,2,+d,3,-,-d,3,+,=80,d,2,+,+d,3,+,+,d,4,-d,4,+,=160,X,2,+,d,5,=70,X,1,X,2,d,i,-,d,i,+,d,5,0(i=1,2,3,4),目标函数：,MaxS=-P,1,d,4,+,-P,2,d,5,-,-P,3,d,1,-,-P,4,(d,2,+,+d,3,+,),约束方程：,6X,1,+4X,2,+d,1,-,-d,1,+,=1000,2X,1,+X,2,+d,2,-,-d,2,+,=100,X,1,+X,2,+d,3,-,-d,3,+,=80,d,2,+,+d,3,+,+,d,4,d,4,+,=160,X,2,+,d,5,=70,X,1,X,2,d,i,-,d,i,+,d,5,0(i=1,2,3,4),表,1,C,0,0,-p,3,0,0,-p,4,0,-p,4,0,-p,1,-p,2,C,B,X,B,X,1,X,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,d,5,-,b,-p,3,d,1,-,6,4,1,-1,0,0,0,0,0,0,0,1000,0,d,2,-,2,1,0,0,1,-1,0,0,0,0,0,100,0,d,3,-,1,1,0,0,0,0,1,-1,0,0,0,80,0,d,4,-,0,0,0,0,0,1,0,1,1,-1,0,160,-p,2,d,5,-,0,1,0,0,0,0,0,0,0,0,1,70,p,4,0,0,0,0,0,-1,0,-1,0,0,0,0,p,3,6,4,0,-1,0,0,0,0,0,0,0,1000,p,2,0,1,0,0,0,0,0,0,0,0,0,70,p,1,0,0,0,0,0,0,0,0,0,-1,0,0,表,1,C,0,0,-p,3,0,0,-p,4,0,-p,4,0,-p,1,-p,2,C,B,X,B,X,1,X,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,d,5,-,b,-p,3,d,1,-,6,4,1,-1,0,0,0,0,0,0,0,1000,0,d,2,-,2,1,0,0,1,-1,0,0,0,0,0,100,0,d,3,-,1,1,0,0,0,0,1,-1,0,0,0,80,0,d,4,-,0,0,0,0,0,1,0,1,1,-1,0,160,-p,2,d,5,-,0,1,0,0,0,0,0,0,0,0,1,70,p,4,0,0,0,0,0,-1,0,-1,0,0,0,0,p,3,6,4,0,-1,0,0,0,0,0,0,0,1000,p,2,0,1,0,0,0,0,0,0,0,0,0,70,p,1,0,0,0,0,0,0,0,0,0,-1,0,0,表,1,C,0,0,-p,3,0,0,-p,4,0,-p,4,0,-p,1,-p,2,C,B,X,B,X,1,X,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,d,5,-,b,-p,3,d,1,-,6,0,1,-1,0,0,0,0,0,0,-4,720,0,d,2,-,2,0,0,0,1,-1,0,0,0,0,-1,30,0,d,3,-,1,0,0,0,0,0,1,-1,0,0,-1,10,0,d,4,-,0,0,0,0,0,1,0,1,1,-1,0,160,0,X,2,0,1,0,0,0,0,0,0,0,0,1,70,p,4,0,0,0,0,0,-1,0,-1,0,0,0,0,p,3,6,4,0,-1,0,0,0,0,0,0,0,720,p,2,0,0,0,0,0,0,0,0,0,0,-1,0,p,1,0,0,0,0,0,0,0,0,0,-1,0,0,表,1,C,0,0,-p,3,0,0,-p,4,0,-p,4,0,-p,1,-p,2,C,B,X,B,X,1,X,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,d,5,-,b,-p,3,d,1,-,6,0,1,-1,0,0,0,0,0,0,-4,720,0,d,2,-,2,0,0,0,1,-1,0,0,0,0,-1,30,0,d,3,-,1,0,0,0,0,0,1,-1,0,0,-1,10,0,d,4,-,0,0,0,0,0,1,0,1,1,-1,0,160,0,X,2,0,1,0,0,0,0,0,0,0,0,1,70,p,4,0,0,0,0,0,-1,0,-1,0,0,0,0,p,3,6,0,0,-1,0,0,0,0,0,0,-4,720,p,2,0,0,0,0,0,0,0,0,0,0,-1,0,p,1,0,0,0,0,0,0,0,0,0,-1,0,0,表,1,C,0,0,-p,3,0,0,-p,4,0,-p,4,0,-p,1,-p,2,C,B,X,B,X,1,X,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,d,5,-,b,-p,3,d,1,-,0,0,1,-1,0,0,-6,6,0,0,2,660,0,d,2,-,0,0,0,0,1,-1,-2,2,0,0,1,10,0,X,1,1,0,0,0,0,0,1,-1,0,0,-1,10,0,d,4,-,0,0,0,0,0,1,0,1,1,-1,0,160,0,X,2,0,1,0,0,0,0,0,0,0,0,1,70,p,4,0,0,0,0,0,-1,0,-1,0,0,0,0,p,3,0,0,0,-1,0,0,-6,6,0,0,2,660,p,2,0,0,0,0,0,0,0,0,0,0,-1,0,p,1,0,0,0,0,0,0,0,0,0,-1,0,0,表,1,C,0,0,-p,3,0,0,-p,4,0,-p,4,0,-p,1,-p,2,C,B,X,B,X,1,X,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,d,5,-,b,-p,3,d,1,-,0,0,1,-1,-3,3,0,0,0,0,-1,630,-p,4,d,3,+,0,0,0,0,1/2,-1/2,-1,1,0,0,1/2,5,0,X,1,1,0,0,0,1/2,-1/2,0,0,0,0,-1/2,15,0,d,4,-,0,0,0,0,-1/2,3/2,1,0,1,-1,-1/2,155,0,X,2,0,1,0,0,0,0,0,0,0,0,1,70,p,4,0,0,0,0,1/2,-3/2,1,0,0,0,1/2,5,p,3,0,0,0,-1,-3,3,0,0,0,0,-1,630,p,2,0,0,0,0,0,0,0,0,0,0,-1,0,p,1,0,0,0,0,0,0,0,0,0,-1,0,0,表,1,C,0,0,-p,3,0,0,-p,4,0,-p,4,0,-p,1,-p,2,C,B,X,B,X,1,X,2,d,1,-,d,1,+,d,2,-,d,2,+,d,3,-,d,3,+,d,4,-,d,4,+,d,5,-,b,-p,3,d,1,-,0,0,1,-1,-2,0,-2,0,-2,2,0,320,-p,4,d,3,+,0,0,0,0,1/3,0,-2/3,1,1/3,-1/3,1/3,170/3,0,X,1,1,0,0,0,1/3,0,-2/3,0,1/3,-1/3,-2/3,200/3,-p,4,d,2,+,0,0,0,0,-1/3,1,2/3,0,2/3,-2/3,-1/3,310/3,0,X,2,0,1,0,0,0,0,0,0,0,0,1,70,p,4,0,0,0,0,0,0,0,0,1,-1,0,160,p,3,0,0,0,-1,-2,0,-2,0,-2,2,0,320,p,2,0,0,0,0,0,0,0,0,0,0,-1,0,p,1,0,0,0,0,0,0,0,0,0,-1,0,0,到目前为止，已经不能再进行下去，否则会破坏已经满足的条件。,该题的解答：,X,1,=200/3,，,X,2,=70,，,d,1,-,=320,，,d,2,+,=310/3,，,d,3,+,=170/3,d,4,+,=d,4,-,=d,5,-,=0,即该厂生产方案：生产产品甲,200/3,公斤，产品乙,70,公斤，第,1,道工序加班,310/3,工时，第,2,道工序加班,170/3,工时，才能获利,1000-d,1,-,=1000-320=680,元。,投资规划实例,某经