最优化方法及其应用课后答案(郭科-陈聆-魏友华)

最优化方法部分课后习题解答习题一1.一直优化问题的数学模型为：22121122123142min()(3)(4)5()02()50..()0()0fxxxgxxxgxxxstgxxgxx=−+−⎧=−−≥⎪⎪⎪=−−+≥⎨⎪=≥⎪=≥⎪⎩试用图解法求出：（1）无约束最优点，并求出最优值。（2）约束最优点，并求出其最优值。（3）如果加一个等式约束，其约束最优解是什么？12()0hxxx=−=解：（1）在无约束条件下，的可行域在整个平面上，不难看出，当=（3，4）()fx120xx*x时，取最小值，即，最优点为=（3，4）：且最优值为：=0()fx*x*()fx（2）在约束条件下，的可行域为图中阴影部分所示，此时，求该问题的最优点就是()fx在约束集合即可行域中找一点，使其落在半径最小的同心圆上，显然，从图示中可12(,)xx以看出，当时，所在的圆的半径最小。*155(,)44x=()fx其中：点为和的交点，令求解得到：1()gx2()gx1122125()02()50gxxxgxxx⎧=−−=⎪⎨⎪=−−+=⎩1215454xx⎧=⎪⎪⎨⎪=⎪⎩即最优点为：最优值为：=*155(,)44x=*()fx658（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。2.一个矩形无盖油箱的外部总面积限定为S，怎样设计可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为：该优化问题属于三维的优化问题。123122313123max()220..00fxxxxxxxxxxSxstxx=++≤⎧⎪⎪⎨⎪⎪⎩3231/3,/3,/121823sssxsyszsv⎛⎞=====⎜⎟⎝⎠习题二3.3.3.3.计算一般二次函数的梯度。1()2TTfxXAXbXc=++解：设：则：1212(),(,,...),(,,...)TTijnnnnAabbbbXxxx×===，将它对变量球偏导数得：1111()2nnnijijiiijifxaxxbxc====++∑∑∑(1,2,...)ixin===123()()()()fxxfxfxxfxx⎡⎤∂⎢⎥∂⎢⎥⎢⎥∂∇=⎢⎥∂⎢⎥⎢⎥∂⎢⎥∂⎣⎦111112221111112211221122nnjjiijinnjjiijinnnjjininjiaxaxbaxaxbaxaxb======⎡⎤++⎢⎥⎢⎥⎢⎥++⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥++⎢⎥⎣⎦∑∑∑∑∑∑⋮11111221123111122nnjjiijinnjjiijinnininjjijaxaxbaxaxbbaxax======⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥++⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦∑∑∑∑∑∑⋮⋮=1()2TAXAXb++5.5.5.5.求下列函数的梯度和HesseHesseHesseHesse矩阵（1）解：22212313()234fxxxxxx=++−220-4()040406fx⎛⎞⎜⎟∇=⎜⎟⎜⎟−⎝⎠（2）解：12212()3xxfxxxe=+1212121212122221222212116+()6+6+xxxxxxxxxxxxxexexxefxxexxexxe⎛⎞+∇=⎜⎟⎜⎟+⎝⎠6.6.6.6.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：（1）22121212(,)23fxxxxxx=−++解：不是半正定，即非凸，然后判断-，经验证：不是半2()fx∇()fx()fx2(())fx∇−正定，由此可知：非凸非凹。()fx（2）221211221(,)24356fxxxxxxx=−+−−解：半正定，故为凸函数。2()fx∇()fx（3）22212312312(,,)234fxxxxxxxx=+−−解：不是半正定，即非凸，然后判断-，经验证：不是半2()fx∇()fx()fx2(())fx∇−正定，由此可知：非凸非凹。()fx7.7.7.7.设约束优化问题的数学模型为：2211221122221212min()4410()20..()220fxxxxxgxxxstgxxxxx=++−+=−+≥⎧⎨=−−−+≥⎩试用K-TK-TK-TK-T条件判别点是否为最优点。[]1,1Tx=−解：对于点，=0，，点满足约束条件，故点是可行解。[]1,1Tx=−1()gx2()0gx≥X且是起作用约束，,,，由条件下的1()gx{}1I=2()2fx⎛⎞∇=⎜⎟−⎝⎠11()1gx⎛⎞∇=⎜⎟−⎝⎠()0igx∇≥K-T条件得：，得到，点满足K-T条()()0,0iiiiIfxgxλλ∈∇−∇=≥∑12λ=[]1,1Tx=−件。又因正定，故为严格凸函数，该最优化问题是凸规划问题，由2()fx∇()fx是K-T点，所以也是该问题的全局最优点。[]*1,1Tx=−[]*1,1Tx=−8.8.8.8.设约束优化问题：221211222312min()(2)()0..()0()10fxxxgxxstgxxgxxx=−+⎧=−≤⎪=−≤⎨⎪=−++≤⎩它的当前迭代点为，试用K-T条件判定它是不是约束最优解。[]1,0Tkx=解：对于点，点是可行点，[]1,0Tkx=123()10,()0,()0kkkgxgxgx=−≤==[]1,0Tkx=且起作用的约束条件是，，,，23(),()gxgx{}2,3I=k2()0fx−⎛⎞∇=⎜⎟⎝⎠2k0g()1x⎛⎞∇=⎜⎟−⎝⎠，由约束条件为时的K-T条件得，应有：3k2g()1x⎛⎞∇=⎜⎟⎝⎠()0igx≤解得：，所以为K-T点。()()0,0iiiiIfxgxλλ∈∇+∇=≥∑2311λλ=⎧⎨=⎩[]1,0Tkx=现判断该问题是否为凸规划问题，因正定，故为凸函数，为2()fx∇()fx12(),()gxgx线性函数，亦为凸函数，半正定，所以为凸函数，所以该优化问题为凸23g()x∇3g()x规划问题，即点是该问题的约束最优解。[]1,0Tkx=习题三1.1.1.1.对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。（1111）1231234123516max()321236984210..300,(1,2...6)jfxxxxxxxxxxxxstxxxj=+++++=⎧⎪+−+=⎪⎨−=⎪⎪≥=⎩解：令123456123630081-4020(,,,,,)30000-1APPPPPP⎛⎞⎜⎟==⎜⎟⎜⎟⎝⎠（1）基解不是基可行解，1167(0,,,0,0,0)36x=−（2）基解不是基可行解，2(0,10,0,7,0,0)x=（3）基解是基可行解，且，3(0,3,0,0,3.5,0)x=()3fx=（4）基解不是基可行解，4721(,4,0,0,0,)44x=−（5）基解不是基可行解，55(0,0,,8,0,0)2x=−（6）基解是基可行解，且，63(0,0,,0,16,0)2x=()3fx=（7）基解不是基可行解，71(1,0,,0,0,3)2x=−（8）基解是基可行解，且，8(0,0,0,3,5,0)x=()0fx=（9）基解不是基可行解。9515(,0,0,2,0,)44x=−（10）基解是基可行解，且。1039(,0,0,0,4,)44x=9()4fx=（11）基解不是基可行解。11167(0,,,0,0,0)36x=−（12）基解不是基可行解。12(0,10,0,7,0,0)x=−（13）基解是基可行解，且。137(0,3,0,0,,0)2x=()3fx=（14）基解不是基可行解。145(0,0,,8,0,0)2x=−（15）基解是基可行解，且。153(0,0,,0,8,0)2x=()3fx=（16）基解是基可行解，且。16(0,0,0,3,5,0)x=()3fx=2.2.2.2.用单纯形法求解下列线性规划问题：（1111）12121212max()105349..528,0fxxxxxstxxxx=++≤⎧⎪+≤⎨⎪≥⎩解：将现行规划问题化为标准形式如下：12341231241234min(())10500349..528,,,0fxxxxxxxxstxxxxxxx−=−−++++=⎧⎪++=⎨⎪≥⎩作初始单纯形表，并按单纯形表步骤进行迭代，如下：此时，均为正，目标函数已不能再减小，于是得到最优解为：jσ*3(1,,0,0)2x=目标函数值为：*()17.5fx=3.3.3.3.分别用单纯形法中的大MMMM法和两阶段法求解下列线性规划问题：BCBXb-101x-52x03x04xiθ03x93410304x8[5]2011.60-10-50003x4.20[2.8]1-0.61.5-101x1.610.400.24160-102-52x1.501514314−-101x11017−2717.5005142514（1）1234123412341234min()52362347..223,,,0fxxxxxxxxxstxxxxxxxx=−+−+++=⎧⎪+++=⎨⎪≥⎩解：（1111）大MMMM法：把原问题化为标准形式，并加入人工变量如下：1234561234512346123456min()52362347..223,,,,,0fxxxxxMxMxxxxxxstxxxxxxxxxxx=−+−++++++=⎧⎪++++=⎨⎪≥⎩作初始单纯形表，并按单纯形表步骤进行迭代，如下：因为M是一个很大的正数，此时均为正，jσ所以，得到最优解：，最优值为*(0,0,1,1,)Tx=*()3fx=−（2222）两阶段法BCBXb51x-22x33x-64x-64x-64xiθM5x71234101.75M6x3211[2]011.5-10M5-3M-2-3M3-4M-6-6M00M5x1-30[1]01-21-64x1.510.50.5100.539-M11+3M16-M003M+333x1-30101-2-64x12.50.501-0.51.5329100M-6M+15首先，构造一个仅含人工变量的新的线性规划如下：1234561234512346123456min()00002347..223,,,,,0gxxxxxxxxxxxxstxxxxxxxxxxx=+++++++++=⎧⎪++++=⎨⎪≥⎩按单纯形法迭代如下：最优解为：，最优值：*(0,0,1,1,0,0)x=()0gx=因人工变量，则原问题的基可行解为:,进入第二阶段计算560xx==*(0,0,1,1,)Tx=如下表所示：由上表可知，检验数均大于等于0，所以得到最优解：*(0,0,1,1,)Tx=最优值为。*()3fx=−4.4.4.4.某糖果厂用原料AAAA，BBBB，CCCC加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号糖果中A,B,CA,B,CA,B,CA,B,C含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售BCBXb01x02x03x04x14x14xiθ15x71234101.7516x3211[2]011.5-10-3-3-4-60015x1-30[1]01-2104x1.510.50.5100.53-140-100303x1-30101-204x12.50.501-0.51.5BCBXb51x-22x33x-64x33x1-3010-64x12.50.501329100价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立这个问题的线性规划数学模型。解：设表示甲、乙、丙中分别含A、B、C的含量，构造此问题的,,0,1,2,3iiixyzi≥=数学规划模型如下：12312312311122233312312312312312max()0.91.41.90.450.951.450.50.450.952000250012000.40.60.60..0.850.150.1500.20.20.800.60.60.400.50.5fxxxxyyyzzzxyzxyzxyzxxxstyyyxxxyyyzz=+++++−++++≤++≤+