最优化习题1-7.pdf

最优化方法部分课后习题解答习 题一1.一 直优化问题的数学模 型 为： 2 21 21 12 2 123 14 2 m in()(3)(4)5() 0() 50. () 0() 0fxx xgxxxgxxxstgxxgxx=+=+ = 试 用图解法求出： （ 1） 无 约束最优点，并求出最优 值 。（ 2） 约 束最优点，并求出其最优 值 。 （ 3） 如 果加一个等式约束 ， 其约束最优解是什 么 ？12() 0hxxx=解 ： （ 1） 在 无 约束 条件 下， 的可 行域 在整 个 平面 上， 不 难 看出 ， 当 =（ 3 ， 4 ）()fx 120 xx *x时， 取最 小值 ，即 ，最 优点 为 =（ 3 ， 4 ） ：且 最优 值为 ： =0()fx *x *()fx（ 2）在 约束 条件 下， 的可 行域 为图 中阴 影部 分所 示， 此时 ，求 该问 题的 最优 点就 是()fx 在约 束集 合即 可行 域中 找一 点 ，使 其落 在半 径最 小的 同心 圆上 ，显 然， 从图 示中 可12(,)x以看 出， 当 时， 所在 的圆 的半 径最 小。*155(,)4x= ()fx 其中 ：点 为 和 的交 点， 令 求解 得到 ：1()gx2()gx 1 122 125() 0() 50gxxxgxxx=+= 1215454xx=即最 优点 为 ：最 优值 为： =*155(,)4x= *()fx658 （ 3） .若增 加一 个等 式约 束， 则由 图可 知， 可行 域为 空集 ，即 此时 最优 解不 存在 。2.一 个矩形无盖油箱的外 部 总面积限定为 S，怎样设计可 使 油箱的容量 最 大？试列 出 这个 优化 问题的数学模型，并回答 这 属于几维的 优 化问题 .解： 列出 这个 优化 问题 的数 学模 型为 ： 该优化问题属于三维的优化问题。12312 2313123m ax()0. 00fxxxxxxSxstxx=+ 3231/3, /3, /121823sssxsyszsv = =习题二 3 .3 3 3 计算一般二次函数 的梯度。1()2T TfxXAXbXc= +解：设： 则：12 12(), (,.), (,.)T Tijn n nAabbbXxx= = =，将它对变量 球偏导数得： 11 11()2nn nijij iii j ifx ax bxc= = + (1,2,.)ix n= = 12 3 ()()() ()fxxfxfxxfxx= 1 1 11 12 2 21 1 1 1 1 12 21 12 2 1 12 2 n njj iij in njj ii j in nnjj ini n j i ax axbax axb ax axb= = = = + + + + + + 1 11 1 12 21 1 23111 12 2 n njj iij in njj iij inn ininjj ij ax axbax axbbax ax= = = + + =1( )2 TAXAXb+5 .5 5 5 求下列函数的梯度 和 H esH H eH 矩阵 （ 1 ） 解：2 2 21 3 13() 4fxxxxx=+ 2 2 0 -4()0 4 04 0 6fx = （ 2） 解： 1221()3xfxxe=+ 12 12 1212 12 122 2 122 22 12 11 6+()6+ 6+ x x xx x xxe xexefxxexexxe += + 6 .6 6 6 判断下列函数是凸函数，凹函数，还是既不凸也不凹函数： （ 1 ） 2 212 1 12(,) 3fx xxx=+解： 不是半正定， 即 非凸， 然 后判断 - ， 经验证： 不是 半2()fx ()fx ()fx 2()fx正定，由此可知： 非凸非凹。()fx（ 2 ） 2 212 1 12 1(,) 4356fx xxxx=+解： 半正定，故 为凸函数。2()fx ()fx （ 3 ） 2 2 21231 3 12(,) 4fxxxxxx=+解： 不是半正定， 即 非凸， 然 后判断 - ， 经验证： 不是 半2()fx ()fx ()fx 2()fx正定，由此可知： 非凸非凹。()fx7 .7 7 7 设约束优化问题的数学模型为： 2 21 1 21 12222 1 12m in() 4 410() 0. () 0fxxxxxgxxxstgxxxxx=+=+=+试 用 K -TK K K 条件判别点 是否为最优点。1, Tx=解：对于点 ， =0 ， ，点满足约束条件，故点 是可行解。1,Tx=1()gx 2()0gx X且 是起作用约束， , , ， 由 条件下 的 1()gx 1I= 2()2fx=1 1()1gx= ()0igxK-T条件得： ，得到 ，点 满足 K-T条() ()0, 0i i i iIfx gx = 12= 1,Tx=件。又因 正定，故 为严格凸函数，该最优化问题是凸规划问题，由2()fx ()fx是 K-T点，所以 也是该问题的全局最优点。 * 1,Tx= * 1,Tx=8 .8 8 8 设约束优化问题： 2211 12 2 23 12 m in()(2)() 0. () 0()1 0fxx xgxxstgxxgx xx=+=+ 它的当前迭代点为 ，试 用 K-T条件判定它是不是约束最优解。1,0Tkx=解：对于点 ，点 是 可 行 点 ，1,0Tkx=1 2 3()10,()0,()0k k kgx gxgx= = = 1,0Tkx=且起作用的约束条件是， ， , ， 2 3(),()gxgx 2,3I= k 2()0fx=2k 0g()1x=，由约束条件为 时的 K-T条件得，应有：3k 2g()1x= ()0igx 解得： ，所以 为 K-T点。() ()0, 0i i iiIfx gx += 2311= 1,0Tkx= 现判断该问题是否为凸规划问题，因 正定，故 为凸函数， 为2()fx ()fx 1 2(),()gxgx线性函数，亦为凸函数， 半正定，所以 为凸函数，所以该优化问题为凸23g()x 3g()x规划问题，即点 是该问题的约束最优解。1,0Tkx= 习题三 1 .1 1 1 对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。 （ 1 1 1 1 ） 12 312 34 12 3516m ax()31236 98 4210.3 00,(1,2.6)jfxxxxxxxxxxxxstxxxj=+=+= 解：令 12345612 3 6 3 0 0 8 1 -4 0 2 0 (,)3 0 0 0 0 -1A PPP = = （ 1 ） 基解 不是基可行解，1 167(0, ,0,0)36x=（ 2 ） 基解 不是基可行解， 2(0,10,0,7,0,0)x=（ 3 ） 基解 是基可行解，且 ，3(0,3,0,3.5,0)x= ()3fx=（ 4 ） 基解 不是基可行解，47 21(,4,0,0,)4 4x=（ 5 ） 基解 不是基可行解， 5 5(0, ,8,0,0)2x=（ 6 ） 基解 是基可行解，且 ，6 3(0,0,16,0)2x= ()3fx=（ 7 ） 基解 不是基可行解， 7 1(1,0, ,0,3)2x=（ 8 ） 基解 是基可行解，且 ，8(0,0,3,5,0)x= ()0fx=（ 9 ） 基解 不是基可行解。 95 15(,0,2,0,)4 4x=（ 1 0 ） 基解 是基可行解，且 。103 9(,0,0,4,)4x= 9()4fx=（ 1 1 ） 基解 不是基可行解。 11167(0, ,0,0)36x=（ 1 2 ） 基解 不是基可行解。12(0,10,0,7,0,0)x=（ 1 3 ） 基解 是基可行解，且 。 13 7(0,3,0,0)2x= ()3fx= （ 1 4 ） 基解 不是基可行解。145(0, ,8,0,0)2x=（ 1 5 ） 基解 是基可行解，且 。153(0,0,8,0)2x= ()3fx=（ 1 6 ） 基解 是基可行解，且 。 16(0,0,3,5,0)x= ()3fx=2 .2 2 2 用单纯形法求解下列线性规划问题： （ 1 1 1 1 ） 12 121212m ax()105349.5 8, 0fxxxxxstxxx=+解：将现行规划问题化为标准形式如下： 12 3 4123124 1234 m in()1050034 9.5 8, 0fx xxxxxxxstxxxxx=+=+= 作初始单纯形表，并按单纯形表步骤进行迭代，如下： 此时， 均为正，目标函数已不能再减小，于是得到最优解为：j * 3(1,0,0)2x=目标函数值为： *()17.5fx=3 .3 3 3 分别用单纯形法中的 大 M法和两阶段法求解下列线性规划问题： BCBX b-101x-52x 03x 04x i03x 9341030 4x 85 2011.60-10-50003x 4.202.8 1-0.61.5-10 1x 1.610.400.24160-102-52x 1.501514314-10 1x 11017 2717.5005142514 （ 1 ） 1234123 4123 41234m in()52367.2 23, 0fxxxxxxxxxstxxxxxx=+=+= 解： （ 1） 大 M法 ：把原问题化为标准形式，并加入人工变量如下： 1234 5 6123 45123 46 123456 m in()52367.2 2 3, 0fxxxxxMxMxxxxxxstxxxxxxxx=+=+= 作初始单纯形表，并按单纯形表步骤进行迭代，如下： 因为 M是一 个很 大的 正数 ，此 时 均为正，j所以，得到最优解： ，最优值为*(0,1,)Tx= *()3fx=（ 2） 两 阶段法 BCBXb 51x -22x 33x -64x -64x -64x iM5x71234101.75M 6x32112011.5-10M5-3M-23M3-4M-6M00M 5x1-301 01-21-64x1.510.50.5100.539-M1+3M16-M003M+33 3x1-30101-2-64x12.50.501-0.51.5329100M-6+15 首先 ，构 造一 个仅 含人 工变 量的 新的 线性 规划 如下 ： 123456 123 45123 46123456m in()00007.2 2 3, 0gxxxxxxxxxxxxstxxxxxxxx=+=+= 按单纯形法迭代如下： 最优 解为 ： ，最优值：*(0,1,0,0)x= ()0gx=因人工变量 ，则原问题的基可行解为 : ,进入第二阶段计算560 xx= *(0,1,)Tx=如下表所示： 由上 表可 知， 检验 数均 大于 等于 0，所 以 得到最优解： *(0,1,)Tx=最优值为 。*()3fx=4 .4 4 4 某糖果厂用原 料 A， B， C加工成三中不同牌号的糖果， 甲， 乙， 丙， 已知各种牌号 糖 果 中 A,B,C含量， 原料成本， 各种原料的每月限用量， 三中牌号糖果的单位加工费及 售 BCBXb01x 02x 03x 04x 14x 14x i15x 7 101.75 6x 32112 01.-10-3-3-4-6 015x - 0101-210 4x1.51.50.5100.53- 40-10 303x 1-3 1-2 4x 2.50.501-0.51.5 BCBX b 51x -22x 33x -64x33x 1-3 0 1 0-6 4x 2.5 .50 13 91 0 价如下表所示， 问 该厂每月应生产这三种牌号糖果各多少千克， 使该厂获利最大？试 建立这个问题的线性规划数学模型。 解：设 表示甲、乙、丙中分别含 A、 B、 C的含量，构造此问题的, 0,1,2,3iiixyzi=数学规划模型如下： 1 2 3 1 2 3 1 2 3 111222333 1 2 31 2 31 2 3 1 2 31 2 m ax()0.91.41.90.450.951.450.50.450.952000250012000.40.60.60 .0.850.150.1500.20.20.800.60.60.400.50.5 fxxxx yyyz z zxyzxyzxyzxxx st yy yxxxyyyzz =+ + 30.50, 0,1,2,iii zxyzi =5 .5 5 5 求解下列线性规划问题的对偶问题 （ 1） 12 312312 3123123m in()2242353 7. 465, 0fxxxxxxxxxxstxxxxx=+ （ 2） 12312 31231231 2 3m ax()56355.47 8, 0, 0fxxxxxxxxxxstxxxx xx=+=+ 无 约 束 甲 乙 丙 原料成本（元 /千克） 每月限用量 （千克）A60%15% 2.002000B 1.502500 C20%60%50%1.001200加工费 0.500.400.30售价 3.402.852.25 解： （ 1） 由表 3 .7 可得该问题的对偶问题为： 12 3123 12 31 2 31 23m ax()235233 42.57640, 0gyyyyyyyyyystyyyyyy=+（ 2） 该问题的对偶问题为： 12 312 31 2 3 12 31 2 3 m in()5383452576.2, 0, 0gyyyyyyyyyystyyyy yy=+=+ 无 约 束 6 用对偶单纯形法求解下列线性规划问题： （ 1 ） 1 2 313 2 3123m in()41218. 5, 0fxxxxxxstxxxx=+ 解： （ 1） 首先，将 “ ” 约束条件两边反号，再加入松弛变量，得： 1 2 3 451342 35 12345 m in()4121803. 5, 0fxxxxxxxxxst xxxxxx=+=+= 建立初始单纯形表如下图所示，所有 。0 j则对应对偶问题解是可行的，则继续迭代： 计算 ， 所以 为换出变量， ， 确定 为 换入变量 。m in3,55= 5x m in6,96= = 2x继续迭代，得到如下单纯形表： BC BXb 41x 122x 183x 04x 05x0 4x -3- 0- 10 5x -50-2 -20141 18 0 。 4 3m in33, m in422x x= =换 出 ， ， ， 换 入 此时，所有 ，故原问题的最优解为 ,最优值为：0j * 30,12Tx= *()36fx=其对偶问题得到最优解为： ，最优值为： 。*2,6Tx= *()36fx= 7 .7 7 7 已知线性规划问题 123123 12123m in()26. 4, 0fxxxxxxxstxxxx=+ 先用单纯形法求出最优解，再分别就下列情况进行分析： （ 1 1 1 1 ） 目标函数中变量 的系数分别在什么范围内变化，问题的最优解不变； 123,xx（ 2 2 2 2 ） 两个约束条件的右端分别在什么范围内变化，问题的最优解不变。解：将该规划问题化为标准型，引入松弛变量 45,xx123 4 51234 12512345m in()2 00,6. , 0fxxxxxxxxxxstxxxxxx=+=+= BC BXb 41x 122x 183x 04x 05x0 4x -3- 0- 10 2x -2.501 10-.540 6 0 BC BXb 41x 122x 183x 04x 05x0 3x 13 0 113 0 2x .513 1 013-.520 26 用单纯形法求解，如下表： 由上表可知， 所 有的检验数均大于等于零， 得 最优解 : ,所以原问题 的*(0,2,0,4,0)Tx=最优解为： ，最优值*(0,2,0,)Tx= *()2fx=（ 1） 。 123 13 2xxxxx x变 量 ， ， 中 ， ， 为 非 基 变 量 ， 为 基 变 量3 3 1 1,),2 2 2 21 1 0 0,),c ccc cc ccc c =+ +=+ +1 1 111 13 3 33 3 3由 ， 当 时 ， ， 所 以 ， 当 此 时 最 优 解 不 变 。由 ， 当 时 ， ， 所 以 ， 当 此 时 最 优 解 不 变 。，最优解不变。() 2 3,1c综上， 1,) 4,00,),2c c c+1 2 3当 ， ， 此 时 最 优 解 不 变 。（ 2） 的变化范围 1b1 11 1 1410.541 0200.52000 0b bBbB b + =+ =+ 得到： ，最优解保持不变。 1 1 1 140 4 2b b b b+ ， 则 的 变 化 范 围 是1 1 22 20 0410.540.50200.520.50BbB bb b + =+ =+ 得到： ，最优解保持不变。 2 248b b， 则 的 变 化 范 围 是 0,12习题四 BCBXb21x -12x 13x 04x 05x i04x 1 11106 5x .5-12 00122-11 004x 41.50 1-.5-1 2x 2-0. 1000.1.501 .5 3 .3 3 3 用 Newton法求解 3() 21ttt=+用 第 1题求得的区间，按精度 计算。0.1=解： 0 100 1 1 1 0 10()(0), 1,()0, 0, ()() 2t ttht t t hh =+= =因 为 ， 则211 2 2 1 2()22, 22,()() K=20,=0b=3tth t t t =+= ， ， 反 向 ， 因 为 所 以 ，则搜索区间为 取：t0,3 2()3,()6,(0)20,(3)250tt t =，0 0 0 151,()1,()6, t 10.0166t t t =所 以 ， ， 继 续 迭 代 0 5=t6t ，00 0 00()491149, 0.01, 0.8165()606060ttt tt t tt= = 则 令 ， 则 。*00.00050.01, 0.817,()0.088tt =继 续 迭 代 ， 因 为 1 1 2 21.832608,()0.306764, 1.111392,()0.987592t t t t = = = =，因为 ，所以新的搜索区间为 -1.832608， 0.056：12,tt继 续 迭 代 1 2()()t t ， 1 1 2 21.111292,()0.987592, 0.665448,()0.888075t t t t = = = =， ，所以新的搜索区间为 -1.832608， -0.665448：12,tt继 续 1 2()()t t ，1 1 2 21.386753,()0.854402, 1.111392,()0.987592t t t t = = = =， 因为 ，所以新的搜索区间为 -1.386753， -0.66544812,tt继 续 1 2()()t t ， 2 2 1 10.940987,()0.996518, 1.111392,()0.987592t t t t = = = =， ，所以新的搜索区间为 -1.111392， -0.665448：12,tt继 续 1 2()()t t因 为 ， 1 1 2 20.940987,()0.996518, 0.835799,()0.973038t t t t = = = =， ，所以新的搜索区间为 -1.111392， -0.835799：12,tt继 续 1 2()()t t因 为 ， 2 2 1 10.940987,()0.996518, 1.006115,()0.999962t t t t = = = =， ，所以新的搜索区间为 -1.111392， -0.940987：12,tt继 续 1 2()()t t因 为 ， 1 1 2 21.046295,()0.997857,1.006115,()0.999962t t t t = = = =， ，所以新的搜索区间为 -1.046295， -0.940987：12,tt继 续 1 2()()t t因 为 ， 2 2 1 10.981215,()0.999647,1.006115,()0.999962t t t t = = = =， ，所以新的搜索区间为 -1.046295， -0.981215：12,tt继 续 1 2()()t t因 为 ， 1 1 2 21.021434,()0.999540, 1.006115,()0.999962t t t t = = = =， ，所以新的搜索区间为 -1.021434， -0.981215：12,tt继 续 1 2()()t t因 为 ， 2 2 1 10.996579,()0.999987,1.006115,()0.999962t t t t = = = =， ，所以新的搜索区间为 -1.006115， -0.981215：12,tt继 续 1 2()()t t因 为 ， 1 1 2 20.996579,()0.999987,0.990727,()0.999914t t t t = = = =， ，所以新的搜索区间为 -1.006115， -0.990727：12,tt继 续 1 2()()t t继 续 1 2()()t t继 续 1 2()()t t因 为 2 2 1 10.998830,()0.999998505, 1.000237,()1.00000016t t t t = = = = ， ，新的搜索区间为 -1.002472， -0.99883012,tt继 续 1 2()()t t因 为 1 1 2 21.001081,()0.999999075, 1.000237,()1.00000016t t t t = = = = ，因为 ， 停止迭代。 所以：12tt，所以，新的搜索区间为 0.5227， 1， 0()0.1588()0.063t t =， ，新的搜索区间为： 0.6232， 1， 0()0.2032()0.2029t t = = = = 同 理 继 续 迭 代 ， 最 后 至 ， 此 时 最 优 解 ，2 .2 2 2 用 Newton法求解 22121 12 0m in()60104 0.01.Tfx xxxxx x =+ = =-， 初 始 点 ， 0，解： 12 211 110 01 1 * * () ()102,4 121 33() ()12 123321 0 1033()() 8,6012433()0,0, ()00.018,6, ()8 T TT T gxfx xx xxGx Gx xxGxgxfx fxx fx =+ = = = = = = = =最 优 解 为 3 .3 3 3 用修 正 Newton法求解 2 21 2 12 0m in()4 1 0.01.Tfxx x xx x =+ = =（ ） （ ） +10， 初 始 点 ， 0， 解： 1 2() ()89,43Tgxfxxx=+ 01000 09834txxtpt=+= ，11080 8() ()04 104Gx Gx= = ， 0()93Tgx=， 则 ，令10 0 109938()() ,31 8404 TpGxgx = = = 01000 09834txxtpt=+= 219999() 161()168fxt t t fx=+=时 ， 最 小 1 1 1* *93, ()0,0, ()00.018493 157,()84 16T TTx fx fxx fx= = =，4 .4 4 4 用共轭梯度法求解 2 21 0m in4 1 0.01.Txx x + = =（ ） ， 取 初 始 点 ， 1，解： 令 ， 2 21 1 12() 4,()2,8Tfxxxfxxx=+= 0 0()2,8Tpfx= 1000 0 0 01212,1818 Txxtpt t t=+=+=令 ，2 20 0m in(12)4(18)m in()t t t+= 则 0 0()5206800.130969dt t tdt=1 10.738062,0.047752()1.476124,0.382016T Tx fx= = ， 则 210 20()2.3248780.03418968()fxfx= = 1 100()pfxp =+新 搜 索 方 向 为 1.47612421.5445020.0341890.38201680.108504 = + = 2111 1 10.7380621.544502,0.0477520.108504Txxtp t t=+= +因 此 有 111 1( )00.477127dfxtp tdt+=由 21110.738062 1.545020.47127 0.,0.70.4752 0.18504 Txxtp =+= + = 因 而 得 下 一 迭 代 点 ，2()00.01fx=停 止 迭 代 * *0,0,()0Tx fx= =5 .5 5 5 用共轭梯度法求解 221 12m in()2 0.01.fxxxx =+ =-， 自 定 初 始 点 ，解： ，取初始点 ， 1221()4, Tfxxxxx= 00,1Tx= 0 0()1,2Tpfx= 1000 0 0 001,1212 Txxtp t t t=+=+=令 2 20 0 0 0m in2(12)(12)m in()t t t t t+= 则 0 0()16500.125dt t tdt=1 10.3125,0.375 ()0.875,0.4375T Tx fx= =， 210 20()0.957031250.1914065()fxfx= = 1 100()pfxp =+新 搜 索 方 向 为 0.87510.6835940.1914060.437520.82012 = + = =2111xxtp=+因 而 得 下 一 迭 代 点 1 10.31250.683594,0.3750.820312Tt t ，111 1( )00.456927dfxtp tdt+=由 则 停止迭代 2 2 20.000,0.000()0,0, ()00.01T Tx fx fx= = =，则 = ，综上所述，原问题的最优解 ，最优值为*x20,0Tx= *0,0Tx= *()0fx= 6 .6 6 6 用 DFP法求解 2 21 2 0m in()45 6 8 0.01.Tfxx x x =+ = =（ ） （ ） ， 初 始 点 ， 9，6 、解：取 0 1 280, , ()840, 1202 THIA gxx x= = 0 08,19, 24,6T Tx g= =第一步迭代得： 1 14.86154,8.21538, 1.10768,4.43076T Tx g= =用 DFP法第二次迭代： 0103.13846,0.78462Tsxx=01025.10768,1.56924Tygg= 则 ，0 00001000 000T TT Ts HyHHHsyyy=+因： 0080.03071,Tsy= 00000632.85811T TyHyyy=，0 9.849932.462502.462500.61563Ts = 0 9.849932.462502.462500.61563Ts = 1100.123080.3070.9610.6260.126970.3149010.3070.700.6260.3900.31491.038H =+ = 则搜索方向 1 110.28017,4.48248TpHg= 从 出发沿 进行直线搜索，即：1x 1p 1114.861540.28017,8.215384.48248Txxtp t t=+= + 由 ，得11( )0dfxtpdt+= 0.48674t=所以 ，由于 ，所以 是极小2115.000,6.000Txxtp=+ 2()0,0Tgx= 25,6Tx=点。 习题六1 .1 1 1 用外点罚函数法求解： 1221 122 1m in()() 0. () 0fxxxgxxxstgxx=+=+ 解：利用外点罚函数法构造增广目标函数，如下： 2 2212 12 112( ) ( )(,) ( )xx xxxxDFxxx x+= 对于 的情况：xD 由 得：1 20, 0FFxx= 2111() ,22 24(1)x = + 当 时，+ ()()0,x 即： ，且()0,x= ()0fx=2 .2 2 2 用外点罚函数法求解： 221m in()fxxx=+.st 1()10gxx= 解：构造增广目标函数： 22 21 122 1 (1)( )(,) ( )xx xxDFxxx x+= 对于 的情况：xD由 得： 1 20, 0FFxx= 1 1222(1)00 x xx=推出： () ,01x = + 当 时， 。+ ()()1,0 x即： 且 。()1,0 x= ()1fx= 4 .4 4 4 用内点罚函数法求解： 31 2 1 12 21m in()()3() 0. () 0fxx xgxxstgxx=+=解：利用内点罚函数法构造如下增广目标函数： 31 2 1 21 11(,)() ( )3k kFxr x xrxx=+由 得： 1200FxFx= *()(1, )k kkxx rr=+当 时，0 kr+*()(1,0)kxx=，*x(1,0) *8()3fx= 5 .5 5 5 用内点罚函数法求解： 31 2 121m in() 30. 0 x xxstx+解法同上。 习题七 1 .1 1 1 用动态规划求解： 2123123m ax 4. 0(1,2,3)iExxxxxstx i=+=解：将原问题表示为： 2123m axEuu=1234. 0(1,2,3) iuuustu i+=由此，确定状态变量为： ， 决策变量为：123,xx 123,uu状态转移方程： 。 11;xu=221;xux=+3324xux=+用动态规划的思想顺推，如下： 第一步， 1:k= 。11 *11 11 11() ,m axuxfx uxux= =且第二步， 2:k= 2222 22 22 2110 21220 2220 () ()( )( ).m axm axm axuxux ux fx ufxufxuuxu = = = 2222 2 2 22 2 *22 2 21( )1 1 1()m ax0,04 4uuxu u uxfx x xux = = =令 ： ()=， 由 ()=0， 得 ：， ， 且第三步， 3:k= 3333 33 233 3220 232330 2 23 330 () ()( )1( ).4m axm axm axuxux ux fx ufxufxuuxu = = = 2 233 33 3 3 34 4 *33 3 3 3 3 43 33 1 1( )4 21 1 1()m ax0,06464214 () 464uuxu u uxfx x xuxx fx = = = 同 理 ， 令 ： ()=， 由 ()=0， 得 ：， ， 且 将 代入上述表达式，逆序递推求出：33()4fx=*3 3 *2 2*1 1 * * * * 42211. (1,2)()4(1,2)()4.xuxuxu u fux fx= = = =,，,，,新 问 题 的 最 优 解 为 ： ， 且原 问 题 的 最 优 解 为 ： ， 且 2 .2 2 2 设 有 5 5 5 5 个城市，编号 从 1 1 1 1 到 5 5 5 5 ，记第 个城市与第 个城市的距离为 ，记：i j ijd ，5 0652600.557() 50.50152510327530ijDd = 试分别用函数迭代法和策略迭代法求出各城市到 第 5 5 5 5 个城市的最短距离。 解：法一，函数迭代法： 1 51 1 1 1 1 2 1052 12 1 2 1() (1,2,3,4,5)()2,(2)7,(3)5,(4)3,(5)0.2() ()(1)m in02,67,55,23,20(),(2)m in62,07,0.55,3,70 (2), (3)m in52,0.57,m in i ijjk fidif f f f fk fi dfjf ff f f = = = +=+ =+ 时 ，时 ， ， =2=5.5 12 12 1 2 13 2053 2 3 05,13,50(3),(4)m in22,57,15,03,0(4),(5)0(5). ()()3() () (1)m in02,65.5,54,23,20(1),(2)m in62,05.5,0.54m inijj ff ff fi fifik fi dfj f ff += = = + =+=+ =4=3对 于 所 有 ,并 不 满 足 ， 故 须 继 续 迭 代 。时 ， ， =2=23 2 3 23 2 3 2 4 3054 ,53,70 (2),()m in52,0.55.5,04,13,50(3),(4)m in22,55.5,14,03,0(4),(5)0(5).()() 4,() ()(1)m in02,64.5,54m inijj ff ff ff fi fifi k fi dfjf +=+=+= = = = +=+ =4.5=4=3对 于 ,并 不 满 足 ， 故 须 继 续 迭 代 。 时 ， 34 3 4 34 34 3 4 33 ,23,20(1),(2)m in62,04.5,0.54,53,70 (2),(3)m in52,0.54.5,04,13,50(),(4)m in22,54.5,14,03,0(4),(5)0(5). ()()()()5 ff ff ff ff f i fifififi +=+=+=+= = =2=4.5=4=3 对 于 ,满 足 ，故 ，故 各 城 市 到 第 个(1)2,(2)4.5,(3)4,(4)3,(5)0.f f f f f= =城 市 的 最 短 距 离 分 别 为 ： 法二，策略迭代法： 设初始策略为： 11()2,3,4,5,uui=则在策略 下，由点 到点 5 的路程 分别为： 1u i 1()fi1 451 1 3411 2311 121(4)(5)303, (5)0.(3) (4)134,(2)(3)0.544.5,() (2)64.510.5.kf cf kff cff cff cf=+=+= =+=+=+=+=+=+=其 中 ， 对 ， 有计算 ，并确定新策略 ： 2()fi 2u2 11 2 12 21 2 1 2 31 2 (1)m in()m in010.5,64.5,54,23,202,(1)5().(2)m in()m in610.5,04.5,0.54,53,704.5,(2)3(2).(3)m in() m in510.5,0.54.5,04,13,504,(3)4 jj j f cfj u uf cfj u uf cfj u =+=+=+= =+ =+=12 41 2 1(3).(4)m in()m in210.5,54.5,14,03,03,(4)5(4).j uf cfj u u=+=+=计算 ，并确定新策略 ： 3()fi 3u3 12 3 23 22 3 2 3 32 3 23 (1)m in()m in02,64.5,54,23,202,(1)5(1).(2)m in()m in62,04.5,0.54,53,704.5,(2)3(2).()m in() m in52,0.54.5,04,13,504,()4(3). jj j f cfj u uf cfj u uf cfj u uf =+=+=+=+= =+ =+=42 3 2(4)m in()m in22,54.5,14,03,03,(4)5(4).jcfj u u=+=+=此时，对于 ，有 ，故 为最优策略。i 3 2()()uiui= 2()ui即：最优策略为 。2(5,3,4,5,)u= 从各城市到城市 5 的最短距离分别为 ： 2， 4.5， 4， 3， 0，且最短路线分别为： 15， 2345， 345， 45， 55。