1212最优化方法部分课后习题解答习题一1.一直优化问题的数学模型为:minf(x)=(x−3)2+(x−4)2⎧g(x)=x−x−5≥0⎪1122s.t.⎪⎪g(x)=−x−x+5≥0⎨212⎪g(x)=x≥0⎪31试用图解法求出:⎪⎩g4(x)=x2≥0(1)无约束最优点,并求出最优值。(2)约束最优点,并求出其最优值。(3)如果加一个等式约束h(x)=x1−x2=0,其约束最优解是什么?解:(1)在无约束条件下,f(x)的可行域在整个x0x平面上,不难看出,当x*=(3,4)时,f(x)取最小值,即,最优点为x*=(3,4):且最优值为:f(x*)=0(2)在约束条件下,f(x)的可行域为图中阴影部分所示,此时,求该问题的最优点就是在约束集合即可行域中找一点(x1,x2),使其落在半径最小的同心圆上,显然,从图示中可以看出,当x*=155(,)44时,f(x)所在的圆的半径最小。⎧5⎧x=15⎪g1(x)=x1−x2−=0⎪14其中:点为g1(x)和g2(x)的交点,令⎨2求解得到:⎨5⎪⎩g2(x)=−x1−x2+5=0即最优点为x*=(15,5):最优值为:f(x*)=65⎪x=⎩24448(3).若增加一个等式约束,则由图可知,可行域为空集,即此时最优解不存在。2.一个矩形无盖油箱的外部总面积限定为S,怎样设计可使油箱的容量最大?试列出这个优化问题的数学模型,并回答这属于几维的优化问题.解:列出这个优化问题的数学模型为:maxf(x)=x1x2x3⎧x1x2+2x2x3+2x1x3≤S⎪x0该优化问题属于三维的优化问题。s.t.⎪1⎨x0⎪2⎪⎩x30s3s18⎜⎟23⎝⎠1212121211221x=s/3,y=s/3,z=3v==1⎛s⎞2⎝⎠习题二3.计算一般二次函数f(x)=1XTAX+bTX+c的梯度。2解:设:A=(a),b=(b,b,...b)T,X=(x,x,...x)T则:ijn×n12n12nf(x)=1∑n∑naxx+∑nbx+cx(i=1,2,...n)2i=1j=1ijijiii=1,将它对变量i球偏导数得:⎡1n1n⎤⎡n⎤⎡n⎤⎡∂f(x)⎤⎢2∑a1jxj+2∑ai1xi+b1⎥⎢∑a1jxj⎥⎢∑ai1xi⎥⎢∂x⎥⎢j=1i=1⎥⎢j=1⎥⎢i=1⎥⎢1⎥⎢1n1n⎥⎢n⎥⎢n⎥⎡b1⎤∇f(x)=⎢∂f(x)⎥=⎢2∑a2jxj+2∑ai2xi+b2⎥=1⎢∑a2jxj⎥+1⎢∑ai2xi⎥+⎢b⎥⎢∂x⎥⎢j=1i=1⎥2⎢j=1⎥2⎢i=1⎥⎢2⎥⎢2⎥⎢⋮⎥⎢⋮⎥⎢⋮⎥⎢⎣b⎥⎢∂f(x)⎥⎢⎥⎢⎥⎢⎥3⎦⎢⎥⎢1n1n⎥⎢n⎥⎢n⎥⎣∂x3⎦⎢2∑anjxj+2∑anxii+bn⎥⎢∑anjxj⎥⎢⎣∑ainxi⎥⎣j=11Ti=1⎦⎣j=1⎦i=1⎦=(AX+AX)+b25.求下列函数的梯度和Hesse矩阵(1)f(x)=x2+2x2+3x2−4xx⎛20-4⎞解:∇2f(x)=⎜040⎟12313⎛x2ex1x2⎜⎟⎜−406⎟6x+ex1x2+xxex1x2⎞(2)f(x)=3xx2+ex1x2解:∇2f(x)=⎜2212⎟12⎜6x+ex1x2+xxex1x26x+x2ex1x2⎟⎝21211⎠6.判断下列函数是凸函数,凹函数,还是既不凸也不凹函数:(1)f(x,x)=−x2+2x2+3xx解:∇2f(x)不是半正定,即f(x)非凸,然后判断-f(x),经验证:∇2(−f(x))不是半正定,由此可知:f(x)非凸非凹。(2)f(x,x)=2x2−4xx+3x2−5x−6解:∇2f(x)半正定,故f(x)为凸函数。s/12123123121122⎪12k1=[](3)f(x,x,x)=x2+2x2−3x2−4xx解:∇2f(x)不是半正定,即f(x)非凸,然后判断-f(x),经验证:∇2(−f(x))不是半正定,由此可知:f(x)非凸非凹。7.设约束优化问题的数学模型为:minf(x)=x2+4x+x2−4x+10⎧g1(x)=x1−x2+2≥0s.t.⎨g(x)=−x2−x2−2x+2x≥0⎩21212试用K-T条件判别点x=[−1,1]T是否为最优点。解:对于点x=[−1,1]T,g(x)=0,g(x)≥0,点满足约束条件,故点X是可行解。12⎛2⎞⎛1⎞且g1(x)是起作用约束,I={1},∇f(x)=⎜−2⎟,∇g1(x)=⎜−1⎟,由∇gi(x)≥0条件下的⎝⎠⎝⎠K-T条件得:∇f(x)−∑λ∇g(x)=0,λ≥0,得到λ=2,点x=[−1,1]T满足K-T条iii1i∈I件。又因∇2f(x)正定,故f(x)为严格凸函数,该最优化问题是凸规划问题,由x*=[−1,1]T是K-T点,所以x*=[−1,1]T也是该问题的全局最优点。8.设约束优化问题:minf(x)=(x−2)2+x2⎧g1(x)=−x1≤0st..⎨g2(x)=−x2≤0⎪g(x)=−1+x2+x≤0⎩312它的当前迭代点为x=[1,0]T,试用K-T条件判定它是不是约束最优解。解:对于点x=[1,0]Tg(x)=−1≤0,g(x)=0,g(x)=0,点x=[1,0]T是可行点,k1k2k3kk⎛−2⎞⎛0⎞且起作用的约束条件是,g2(x),g3(x),I={2,3},∇f(xk)=⎜0⎟,∇g2(xk)=⎜−1⎟⎝⎠⎝⎠∇g(x)=⎛2⎞,由约束条件为g(x)≤0时的K-T条件得,应有:3k⎜⎟i⎝⎠∇f(x)+∑λ∇g(x)=0,λ≥0⎧λ2=1T解得:,所以x1,0为K-T点。iii⎨λ=1ki∈I⎩3k1233⎝⎠现判断该问题是否为凸规划问题,因∇2f(x)正定,故f(x)为凸函数,g(x),g(x)为线性函数,亦为凸函数,∇2g(x)半正定,所以g(x)为凸函数,所以该优化问题为凸规划问题,即点x=[1,0]T是该问题的约束最优解。习题三1.对于下列线性规划问题找出所有基解,指出哪些是基可行解,并确定出最优解。maxf(x)=3x1+x2+2x3⎧12x1+3x2+6x3+x4=9(1)⎪8x+x−4x+2x=10s.t.⎪1235⎨3x−x=0⎪16⎪⎩xj≥0,(j=1,2...6)⎛1236300解:令A=⎜81-4020⎞⎟=(P,P,P,P,P,P)⎜⎟⎜30000-1⎟123456(1)基解x=(0,16,−7,0,0,0)不是基可行解,136(2)基解x2=(0,10,0,7,0,0)不是基可行解,(3)基解x3=(0,3,0,0,3.5,0)是基可行解,且f(x)=3,(4)基解x4=(7,−4,0,0,0,2144不是基可行解,(5)基解x=(0,0,−5,8,0,0)不是基可行解,52(6)基解x=3是基可行解,且f(x)=3,(0,0,,0,16,0)62(7)基解x=(1,0,−1,0,0,3)不是基可行解,72(8)基解x8=(0,0,0,3,5,0)是基可行解,且f(x)=0,(9)基解x9=5(,0,0,4−2,0,15)不是基可行解。4(10)基解x10=39(,0,0,0,4,)44是基可行解,且f(x)=9。4(11)基解x=(0,16,−7,0,0,0)不是基可行解。1136(12)基解x12=(0,10,0,−7,0,0)不是基可行解。(13)基解x13=7(0,3,0,0,,0)2是基可行解,且f(x)=3。)⎪⎪j(14)基解x=(0,0,−5,8,0,0)不是基可行解。142(15)基解x=3是基可行解,且f(x)=3。(0,0,,0,8,0)152(16)基解x16=(0,0,0,3,5,0)是基可行解,且f(x)=3。2.用单纯形法求解下列线性规划问题:maxf(x)=10x1+5x2⎧3x1+4x2≤9(1)s.t.⎨5x1+2x2≤8⎪x,x≥0⎩12解:将现行规划问题化为标准形式如下:min(−f(x))=−10x1−5x2+0x3+0x4⎧3x1+4x2+x3=9s.t.⎨5x1+2x2+x4=8⎪x,x,x,x≥0⎩1234作初始单纯形表,并按单纯形表步骤进行迭代,如下:CBXBb-10x1-5x20x30x4θi0x39341030x48[5]2011.60-10-5000x34.20[2.8]1-0.61.5-10x11.610.400.24160-102-5x21.501514−314-10x1110−172717.5005142514此时,σ均为正,目标函数已不能再减小,于是得到最优解为:x*=目标函数值为:f(x*)=17.53(1,,0,0)23.分别用单纯形法中的大M法和两阶段法求解下列线性规划问题:⎪⎪(1)minf(x)=5x1−2x2+3x3−6x4⎧x1+2x2+3x3+4x4=7s.t.⎨2x1+x2+x3+2x4=3⎪x,x,x,x≥0⎩1234解:(1)大M法:把原问题化为标准形式,并加入人工变量如下:minf(x)=5x1−2x2+3x3−6x4+Mx5+Mx6⎧x1+2x2+3x3+4x4+x5=7s.t.⎨2x1+x2+x3+2x4+x6=3⎪x,x,x,x,x,x≥0⎩123456作初始单纯形表,并按单纯形表步骤进行迭代,如下:CBXBb5x1-2x23x3-6x4-6x4-6x4θiMx571234101.75Mx63211[2]011.5-10M5-3M-2-3M3-4M-6-6M00Mx51-30[1]01-21-6x41.510.50.5100.539-M11+3M16-M003M+33x31-30101-2-6x412.50.501-0.51.5329100M-6M+15因为M是一个很大的正数,此时σj均为正,所以,得到最优解:x*=(0,0,1,1,)T,最优值为f(x*)=−3(2)两阶段法⎪首先,构造一个仅含人工变量的新的线性规划如下:ming(x)=0x1+0x2+0x3+0x4+x5+x6⎧x1+2x2+3x3+4x4+x5=7s.t.⎨2x1+x2+x3+2x4+x6=3⎪x,x,x,x,x,x≥0按单纯形法迭代如下:⎩123456CBXBb0x10x20x30x41x41x4θi1x571234101.751x63211[2]011.5-10-3-3-4-6001x51-30[1]01-210x41.510.50.5100.53-140-10030x31-30101-20x412.50.501-0.51.5最优解为:x*=(0,0,1,1,0,0),最优值:g(x)=0因人工变量x5=x6如下表所示:=0,则原问题的基可行解为:x*=(0,0,1,1,)T,进入第二阶段计算CBXBb5x1-2x23x3-6x43x31-3010-6x412.50.501329100由上表可知,检验数均大于等于0,所以得到最优解:x*=(0,0,1,1,)T最优值为f(x*)=−3。4.某糖果厂用原料A,B,C加工成三中不同牌号的糖果,甲,乙,丙,已知各种牌号糖果中A,B,C含量,原料成本,各种原料的每月限用量,三中牌号糖果的单位加工费及售价如下表所示,问该厂每月应生产这三种牌号糖果各多少千克,使该厂获利最大?试建立这个问题的线性规划数学模型。甲乙丙原料成本(元/千克)每月限用量(千克)A≥60%≥15%2.002000B1.502500C≤20%≤60%≤50%1.001200加工费0.500.400.30售价3.402.852.25解:设xi,yi,zi≥0,i=1,2,3表示甲、乙、丙中分别含A、B、C的含量,构造此问题的数学规划模型如下:maxf(x)=0.9x1+1.4x2+1.9x3+0.45y1+0.95y2+1.45y3−0.5z1+0.45z2+0.95z3⎧x1+y1+z1≤2000⎪x+y+z≤2500⎪222⎪x3+y3+z3≤1200⎪0.4x−0.6x−0.6x≤0⎪123⎪s.t.⎨0.85y1−0.15y2−0.15y3≥0⎪0.2x+0.2x−0.8x≥0⎪123⎪0.6y1−0.6y2+0.4y3≥0⎪0.5z+0.5