运筹学（清华大学第三版）习题集(5)

由f(t4)?f(t4')知：下一步应取a4?0.231，b4?0.846。 （4）a4?0.231，b4?0.846，

1t5?(a4?b4)?0.539，f(t5)?1.751

2t6?t5?0.01?0.549，f(t5')?1.752

由f(t5)?f(t5')可知，应取t5?0.539作为近似极小点，近似极小值为1.751。原问题的极小点所属区间为[0.231, 0.549]。

2?2x1x2?x1?x2例. 试以X(0)?(0, 0)T为初始点，用最速下降法求f(X)?2x12?x2的极小点。

2?2x1x2?x1?x2可得： 解：由f(X)?2x12?x2?1?4x1?2x2??42?， ?f(X)??H(X)?????22???1?2x1?2x2?由H(X)正定，可知f(X)为凸函数，存在唯一极大点。用梯度法列表计算如下： 步骤 0 1 2 3 4 3X(k) (0, 0)T (?1, 1)T P(k) (?1, 1)T (1, 1)T ?k 1 0.2 1 f(X(k)) 0 ?1 ?1.2 ?1.24 (?0.8, 1.2)T (?1, 1.4)T (?0.96, 1.44)T (?0.2, 0.2)T (0.2, 0.2)T 0.2 ?1.248 2.521.510.50-0.5-2.5-2-1.5-1-0.500.5 2?2x1x2?x1?x2的例. 试以X(0)?(0, 0)T为初始点，用变尺度法求f(X)?2x12?x2极小点。

2?2x1x2?x1?x2可得： 解：由f(X)?2x12?x2?1?4x1?2x2??42?， ?f(X)??H(X)?????22???1?2x1?2x2?由H(X)正定，可知f(X)为凸函数，存在唯一极大点。用变尺度法计算如下： 步骤 0 X(k) (0, 0) TH(k) P(k) (?1, 1)T ?k 1 f(X(k)) ?1 0??? 0 1???0.5 ?0.5??? ??0.5 1.5? 0 1 2 3(?1, 1) T(0, 1)T 0.5 ?1 ?1.25 (?1, 1.5)T 2.521.510.50-0.5-2.5-2-1.5-1-0.500.5 例. 用K-T条件解非线性规划

??minf(x)?(x?3)2 ???0?x?5解：原问题写为标准形式为：

?minf(x)?(x?3)2??f(x)?2(x?3)??， 故??g1(x)?1 ? g1(x)?x?0??g(x)??1? g(x)?5?x?0?22?分别向两个约束条件引入广义Lagrange乘子?1和?2，则K-T条件可写为：

?2(x?3)??1??2?0??x?0?1 ???2(5?x)?0???1,?2?0先不考虑?1,?2?0，?1和?2的取值有4种情况： （1）?1?0且?2?0，则K-T条件无解。

（2）?1?0且?2?0，解得x?0、?1??6，不符合?1,?2?0，故不是K-T点。 （3）?1?0且?2?0，解得x?5、?2??4，不符合?1,?2?0，故不是K-T点。 （4）?1?0且?2?0，解得x?3，满足所有K-T条件，故是K-T点。

由于原规划中目标函数为凸函数、可行域也为凸集，故有唯一极小点，

即所求得的K-T点x*?3。

例. 求解二次规划

22?minf(X)?x1?x2?8x1?10x2? ? 6?3x1?2x2?0? x?0, x?012?解：可知，原问题为凸规划，存在唯一的极小点，也是最小点。令

g1(X)?6?3x1?2x2，g2(X)?x1，g3(X)?x2，则

?f(X)?(2x1?8, 2x2?10)T，?g1(X)?(?3, ?2)T， ?g2(X)?(1, 0)T，?g3(X)?(0, 1)T

分别向三个约束引入广义Lagrange乘子y3, y1, y2，则K－T条件可写为：

??2x1?8???3??1??0??y?y?y???3??1??2???0??2??0??1???2x2?10?? ?y3(6?3x1?2x2)?0?yx?0?11??y2x2?0向6?3x1?2x2?0引入松弛变量x3，则上述条件可化为：

?2x1?3y3?y1?8??2x2?2y3?y2?10 ??3x1?2x2?x3?6??y3x3?0, y1x1?0, y2x2?0先不考虑最后一行约束，为求解前三个约束，分别在前两个约束引入人工变量z1和z2，可得：

min?(Z)?z1?z2?2x1?3y3?y1?z1?8 ?s..t?2x2?2y3?y2?z2?10?3x?2x?x?623?1取初始解为z1?8, z2?10, x3?6，其它变量为0，用单纯形法求解（注意求解时应满足y3x3?0, y1x1?0, y2x2?0），可得：

X*?(4/13, 33/13, 0)T，Y*?(0, 0, 32/13)T，Z*?(0, 0)T

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学（清华大学第三版）习题集(5)在线全文阅读。