优化原理与方法-作业答案

《优化原理与方法》作业解答要点5.1建造一容积为V(m3)的长方形蓄水池（无盖），要求选择其长、宽、高，使表面积最小，从而建筑用料最省。试写出此问题的数学模型。[解]选择设计变量x1、x2、x3分别代表蓄水池的长、宽、高，优化数学模型为：5.2某公司有资金a万元，可供选择购置的设备有n种，已知相应于第i种设备所需资金为bi万元，可得收益为ci万元，要求收益最大的投资安排。试写出其数学模型。[解]选择设计变量x1、x2、…、xn分别代表n种可选购设备的购买数量，优化数学模型为：5.3某城市要建造一供应服务中心，向该市m个用户提供服务，设第i个用户的位置为（ai，bi），需要货物量为wi吨，试寻求这个中心最经济的位置，使运输量（吨公里数）最小。[解]选择设计变量x1、x2代表中心的位置坐标，优化数学模型为：5.4对于二次型函数（1）写出它的矩阵-向量形式；（2）写出海赛矩阵；（3）证明H(x)的正定性；（4）f(x)是凸函数吗？为什么？[解]（1）t..s22.min],,[3min32min21min1321313221321xxxxxxVxxxxxxxxxxxxT使得寻求xnixnixaxbxcxxxiiniiiniiiTn,1,2,,,1,2,,0t..s.max],,,[1121为整数使得寻求xmiiiiTbxaxwxx1222121)()(.min],[使得寻求xTxxxxf],[8222],[21)(2121x22212142)(xxxxfx（2）（3）（4）因H为正定阵，f(x)为凸函数5.5试判定以下函数的凹、凸性：（1）（2）（3）（4）[解]（1）因f〞(x)=6(4-x)≧0，所以f(x)（x≦4时）为凸函数。（2）（3）因f〞(x)=1/x20，所以f(x)（x0时）为凸函数。（4）5.6试判别下列非线性规划是否为凸规划：（1）（2）2282)(xH为正定阵，135，22-2HH0121082)(Ix为凸函数)(为正定阵，，224，88622-2xfHH02)(Ix。函数凹为为负定阵，，，)(0526161210222-)(2xfHHIx；，4)4()(3xxxf；32)(222121xxxxfx；，0,ln)(1xExxfx。105102)(22212121xxxxxxfx0001054.t.s2)(.min321312221232221xxxxxxxxxxf，，x09.t.s2)(.min2222121xxxxxfx[解]（1）先化为标准式然后判别目标函数f(x)的凸性再判别不等式约束函数g(x)=22214xx的凸性等式约束函数h(x)为线性函数；目标函数为凸函数，可行域为凸集，故该问题为凸规划（2）为凸规划（证略）5.7用牛顿法求下列函数的极小点，终止准则（1）（2）[解]（1）；为凸函数)(为正定阵，，，200020004-xfHH02,2,40)2)(2)(4()(321Ix00010504.t.s2)(.min321312221232221xxxxxxxxxxf，，x；函数凹为)(为半负定阵，，02，02000020002-xgHH0,2,0))(2)(()(321Ix182)(321xxxfH1882)(，1800080002xx10182901*101*000)(10110100018021800080002000)()(11-101001fffH，为极小点。，xxxxxxx。0.22)(kfx；，]0,0,0[81294031232221Txxxxxx；，]1,0[2)1(02241Txxx（2）5.8用共轭梯度法求解[解]122124242)(xxxxfx，0d=)(0xf039.0)94(*0//0/9/203/127/324003/1603/1)(27/3203/113/110444001210)(42121ffffHfffH，95*作为近似极小点。达到迭代精度要求，，0.2)(，0729256)(9500)(继续迭代。，0.2)(，0)()(2121-111211-10001xxxxxxxxxxxxxx81616816，24*，为极小点，0)(，24，1，令3/23/22421)(-1/45/20)(/)(，1)(，22，41，804令444，4241)(2222112011202111001*00558128)2/32/1(6)22(4)()2/32/1)(22(2)22(4)2/32/1(2)22()(2/32/12222/122412/1/02043216)21(8)1(8)()21)(1(2)1(4)21(2)1()(21112222ffttttttttttttttttfffftttttttttttttttftxxxxxdxxdxdxxxxxxx231214)1(4)(400)1(12)(xxfxHxx，。取Txxxxxf]1,1[242)(.min02112221xx5.9试用图解法讨论，当β取何值时：（1）有唯一的最优解，并指出其x*及f*；（2）有无穷多个最优解；（3）不存在有界的最有界。[解]负梯度方向(1)有唯一解的情况当①负梯度方向介于d1与d2之间时，即-β0亦即β0时有唯一解x*=(0,0),f*=0；②负梯度方向介于d2与d3之间时，即1-β0或-1β0时有唯一解x*=(0,1),f*=β；③负梯度方向介于d3与d4之间时，即2-β1或-2β-1时有唯一解x*=(2，3),f*=2+3β。(2)有无穷多解的情况β=0时，解点在OA上；β=-1时，解点在AB上；β=-2时，解点在BC上。(3)有无界解的情况β-2时，不存在有界的最优解。5.10试用单纯形法求解x1x2(2,3)214d113d012dOABC1)(xf101d00421.t.s)(.min212121221xxxxxxExxf，，xx[解]（1）（求解过程略）答案：x*=[1,0,1,3,0,0]T，f*=-4（2）（求解过程略）先化成标准式再求解。答案：x*=[4,5,0,0,0,11]T，f*=-115.11已知线性规划（1）试写出其对偶形式；（2）已知原问题最优点x*=[1,1,2]T，试根据对偶理论，求出对偶问题的最优点W*。[解]（1）根据对称形式的对偶关系，其对偶问题为：（2）由x*=[1,1,2]T知，x1、x2、x3均为基变量，基矩阵及其价格系数矩阵为根据对偶理论，y*=[cBTB-1]T=W*=3*2+6*2+2*1=2000026332.t.s368)(.min321332121321xxxxxxxxxxxxf，，x00036283.t.s263.max321322121321yyyyyyyyyyyyW，，368100113021BcB，1225-10-10--1/55-001-13-22-13681/5--1001130213681TTTT5.12考虑非线性规划：试用KT条件判别：是否为问题的KT点。[解]KT条件为：即将x1代入得第3、5、6式自然满足，由第2式得ν=0，代入第1式得μ=1/80，满足第4式，故x1满足KT条件，是KT点。将x2代入得013)2()3()(0)4(61)(.t.s)(.min222122211xxhxxgxfxxx2]13[33.2][6.40][0321TTT，，，，，xxx013)2()3(0)4(6100)(0)()()(22212221xxxxghgfxxxx013)2()3(0)4(6100))4(6(104262282012221222122212121xxxxxxxxxx00000000460801000000004.26.84.68.401第3、5、6式自然满足，由第1、2式解得ν=0.2，μ=3/400，满足第4式，故x2满足KT条件，是KT点。将x3代入得第5、6式自然满足，由第3式μ=0，且满足第2、4式，代入第1式得ν=，故x3满足KT条件，是KT点。5.13用KT条件解下列问题，并写出它的对偶问题，验证二者最优值是否相等：[解]（1）利用KT条件求解。KT条件为：即0005.21005.2100132)(01xg261300312132311.t.s)1()(.minxxxxfx00000)(0)(0)()(2112121221121)(xxggggfxxxxx000000)(0100132122121221122111)1(xxxxxx由第1式得μ10，则由第3式得x1=1，代回第1式得μ1=4；由第2式得μ2=22x3，则由第4式得x2=μ2=0；其余式子均能满足，故x=(1,0)T满足KT条件，是KT点。此外，在可行域内目标函数的Hesse阵半正定，目标函数为凸函数，约束函数为线性函数，可行域为凸集，故x*=(1,0)T是全局最优点，f*=8/3。（2）通过对偶问题求解。对偶问题为令▽xL(x,μ)=0得（3）补充：利用罚函数法求解。